A Decomposition Theory for Binary Linear Codes

DOI10.1109/TIT.2008.924700zbMATH Open1328.94083arXivcs/0611028OpenAlexW2115769160MaRDI QIDQ3604516FDOQ3604516

N. Kashyap

Publication date: 24 February 2009

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: 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^{p}erp$. 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.

Full work available at URL: https://arxiv.org/abs/cs/0611028

Mathematics Subject Classification ID

Linear programming (90C05) Research exposition (monographs, survey articles) pertaining to information and communication theory (94-02) Combinatorial aspects of matroids and geometric lattices (05B35) Linear codes (general theory) (94B05) Decoding (94B35)

Cited In (5)

• On matroids from self-orthogonal codes and their properties
• On the Number of Circuits in Regular Matroids (with Connections to Lattices and Codes)
• Pseudocodeword-free criterion for codes with cycle-free Tanner graph
• The highly connected matroids in minor-closed classes
• Decomposition of modular codes for computing test sets and Graver basis

This page was built for publication: A Decomposition Theory for Binary Linear Codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3604516)