Computer Science – Discrete Mathematics
Scientific paper
2006-11-06
Computer Science
Discrete Mathematics
37 pages, 4 figures; submitted to IEEE Transactions on Information Theory, Nov 2006; revised June 2007
Scientific paper
The decomposition theory of matroids initiated by Paul Seymour in the 1980's has had an enormous impact on research in matroid theory. This theory, when applied to matrices over the binary field, yields a powerful decomposition theory for binary linear codes. In this paper, we give an overview of this code decomposition theory, and discuss some of its implications in the context of the recently discovered formulation of maximum-likelihood (ML) decoding of a binary linear code over a discrete memoryless channel as a linear programming problem. We translate matroid-theoretic results of Gr\"otschel and Truemper from the combinatorial optimization literature to give examples of non-trivial families of codes for which the ML decoding problem can be solved in time polynomial in the length of the code. One such family is that consisting of codes $C$ for which the codeword polytope is identical to the Koetter-Vontobel fundamental polytope derived from the entire dual code $C^\perp$. However, we also show that such families of codes are not good in a coding-theoretic sense -- either their dimension or their minimum distance must grow sub-linearly with codelength. As a consequence, we have that decoding by linear programming, when applied to good codes, cannot avoid failing occasionally due to the presence of pseudocodewords.
No associations
LandOfFree
A Decomposition Theory for Binary Linear Codes 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 A Decomposition Theory for Binary Linear Codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Decomposition Theory for Binary Linear Codes will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-297231