Pseudocodewords of Parity-Check Codes Over Fields of Prime Cardinality
Wittawat Kositwattanarerk, Gretchen L. Matthews · IEEE Transactions on Information Theory · 2014
This paper considers pseudocodewords of lowdensity 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 Fp, 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 F2and F3and a necessary condition for those over larger alphabets. In addition, irreducible pseudocodewords of codes over F3are found as a Hilbert basis for the lifted fundamental cone.