Computer Science – Discrete Mathematics
Scientific paper
2008-05-15
Computer Science
Discrete Mathematics
Submitted to IEEE Transactions on Information Theory
Scientific paper
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 $\k$-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 $\k$-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 $\k$-complexity of the best conventional trellis realization of a length-n code C to the $\k$-complexity of the best cycle-free realization of C grows at most logarithmically with codelength n. Such a logarithmic growth rate is, in fact, achievable.
No associations
LandOfFree
Constraint Complexity of Realizations of Linear Codes on Arbitrary Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Constraint Complexity of Realizations of Linear Codes on Arbitrary Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Constraint Complexity of Realizations of Linear Codes on Arbitrary Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-509116