Constraint Complexity of Realizations of Linear Codes on Arbitrary Graphs
A graphical realization of a linear code C consists of an assignment of the coordinates of C to the vertices of a graph, along with a specification of linear state spaces and linear "local constraint" codes to be associated with the edges and vertices, respectively, of the graph. The K-complexity of a graphical realization is defined to be the largest dimension of any of its local constraint codes. K-complexity is a reasonable measure of the computational complexity of a sum-product decoding algorithm specified by a graphical realization. The main focus of this paper is on the following problem: given a linear code C and a graph G, how small can the complexity of a realization of C on G be? As useful tools for attacking this problem, we introduce the Vertex-Cut Bound, and the notion of "vc-treewidth" for a graph, which is closely related to the well-known graph-theoretic notion of treewidth. Using these tools, we derive tight lower bounds on the complexity of any realization of C on G. Our bounds enable us to conclude that good error-correcting codes can have low-complexity realizations only on graphs with large vc-treewidth. Along the way, we also prove the interesting result that the ratio of the complexity of the best conventional trellis realization of a length-n C code to the K-complexity of the best cycle-free realization of C grows at most logarithmically with code length n. Such a logarithmic growth rate is, in fact, achievable.
constraint complexity linear codes graphical realizations sum-product decoding treewidth graphical models vertex-cut trees