Publication: Pseudocodewords of parity-check codes over fields of prime cardinality
Issued Date
2014-01-01
Resource Type
ISSN
00189448
Other identifier(s)
2-s2.0-84906658486
Rights
Mahidol University
Rights Holder(s)
SCOPUS
Bibliographic Citation
IEEE Transactions on Information Theory. Vol.60, No.9 (2014), 5215-5227
Suggested Citation
Wittawat Kositwattanarerk, Gretchen L. Matthews Pseudocodewords of parity-check codes over fields of prime cardinality. IEEE Transactions on Information Theory. Vol.60, No.9 (2014), 5215-5227. doi:10.1109/TIT.2014.2331677 Retrieved from: https://repository.li.mahidol.ac.th/handle/20.500.14594/33755
Research Projects
Organizational Units
Authors
Journal Issue
Thesis
Title
Pseudocodewords of parity-check codes over fields of prime cardinality
Other Contributor(s)
Abstract
This paper considers pseudocodewords of low-density parity-check codes over alphabets with prime cardinality p for use over the p-ary symmetric channel. Pseudocodewords are decoding algorithm outputs that may not be legitimate codewords. Here, we consider pseudocodewords arising from graph cover decoding and linear programming decoding. For codes over the binary alphabet, such pseudocodewords correspond to rational points of the fundamental polytope. They can be characterized via the fundamental cone, which is the conic hull of the fundamental polytope; the pseudocodewords are precisely those integer vectors within the fundamental cone that reduce modulo 2 to a codeword. In this paper, we determine a set of conditions that pseudocodewords of codes over F p , the finite field of prime cardinality p, must satisfy. To do so, we introduce a class of critical multisets and a mapping, which associates a real number to each pseudocodeword over Fp. The real numbers associated with pseudocodewords are subject to lower bounds imposed by the critical multisets. The inequalities are given in terms of the parity-check matrix entries and critical multisets. This gives a necessary and sufficient condition for pseudocodewords of codes over F2 and F3 and a necessary condition for those over larger alphabets. In addition, irreducible pseudocodewords of codes over F3 are found as a Hilbert basis for the lifted fundamental cone. © 1963-2012 IEEE.