ENTROPY LENGTH PROFILES, BOUNDS ON THE MINIMAL COVERING OF BIPARTITE GRAPHS, AND TRELLIS COMPLEXITY OF NONLINEAR CODES/

In this paper, the trellis representation of nonlinear codes is studie d from a new perspective, We introduce the new concept of entropy/leng th profile (ELP), This profile can be considered as an extension of th e dimension/length profile (DLP) to nonlinear codes, This elaboration of the DLP, the entropy/length profiles, appears to be suitable to the analysis of nonlinear codes, Additionally and independently, we use w ell-known information-theoretic measures to derive novel bounds on the minimal covering of a bipartite graph by complete subgraphs. We use t hese bounds in conjunction with the ELP notion to derive both lower an d upper bounds on the stale complexity and branch complexity profiles of (nonlinear) block codes represented by any trellis diagram. We lay down no restrictions on the trellis structure, and we do not confine t he scope of our results to proper of one-to-one trellises only, The ba sic lower bound on the state complexity profile implies that the state complexity at any given level cannot be smaller than the mutual infor mation between the past and the future portions of the code at this le vel under a uniform distribution of the codewords, We also devise a di fferent probabilistic model to prove that the minimum achievable state complexity over all possible trellises is not larger than the maximum value of the above mutual information over all possible probability d istributions of the codewords, This approach is pursued further to der ive similar bounds on the branch complexity profile, To the best of ou r knowledge, the proposed upper bounds are the only upper bounds that address nonlinear codes, The novel fewer bounds are tighter than the e xisting bounds, The new quantities and hounds reduce to well-known res ults when applied to linear codes.