article · TigerPrints (Clemson University) · 2011

Pseudocodewords of Parity-Check Codes

Cited by 0Open access

Abstract

The success of modern algorithms for the decoding problem such as message-passing iterative decoding and linear programming decoding lies in their local nature. This feature allows the algorithms to be extremely fast and capable of correcting more errors than guaranteed by the classical minimum distance of the code. Nonetheless, the performance of these decoders depends crucially on the Tanner graph representation of the code. In order to understand this choice of representation, we need to analyze the pseudocodewords of the Tanner graph of a code. These pseudocodewords are outputs of local decoding algorithms which may not be legitimate codewords. In this dissertation, we introduce a lifted fundamental cone and show that there is a one-to-one correspondence between graph cover pseudocodewords of a binary code and integer points in the lifted fundamental cone. We use this fact to prove the rationality of the generating function of the pseudocodewords for a general binary parity-check code. Our approach also yields algorithms for producing this generating function and provides tools for studying the irreducible pseudocodewords. Understanding irreducible pseudocodewords is crucial to determining the best representation of a code. Moreover, combining these techniques with the recent characterization of fundamental cone over F_3, we can analyze ternary parity-check codes. Finally, we make progress in the study of more general nonbinary codes by determining constraints satisfied by all pseudocodewords of a code over F_p where p is prime.

Cite this paper

APA 7

Kositwattanarerk, W. (2011). Pseudocodewords of Parity-Check Codes. TigerPrints (Clemson University).

MLA 9

Kositwattanarerk, Wittawat. “Pseudocodewords of Parity-Check Codes.” TigerPrints (Clemson University), 2011.

Chicago

Kositwattanarerk, Wittawat. 2011. “Pseudocodewords of Parity-Check Codes.” TigerPrints (Clemson University).

Harvard

Kositwattanarerk, W. (2011) ‘Pseudocodewords of Parity-Check Codes’, TigerPrints (Clemson University).

BibTeX

@article{kositwattanarerk2011pseudocodewords,
  title = {{Pseudocodewords of Parity-Check Codes}},
  author = {Kositwattanarerk, Wittawat},
  journal = {TigerPrints (Clemson University)},
  year = {2011}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.