TY - JOUR
T1 - Pseudocodewords of tanner graphs
AU - Kelley, Christine A.
AU - Sridhara, Deepak
N1 - Funding Information:
Manuscript received April 5, 2005; revised July 15, 2007.The work of C. A. Kelley was supported by a Center for Applied Mathematics fellowship from the University of Notre Dame and also in part by the National Science Foundation (NSF) under Grant CCR-ITR-02–05310. The work of D. Sridhara was supported by the Indian Institute of Science Institute of Mathematics Initiative fellowship and by a DRDO-India grant and also in part by the National Science Foundation under Grant CCR-ITR-02–05310. The material in this paper was presented in part at IEEE International Symposium on Information Theory Chicago, IL, Jun./Jul. 2004 and the International Symposium on Information Theory and Its Applications, Parma, Italy, 2004. This work was performed while C. A. Kelley was with the University of Notre Dame and the Institute of Mathematics, University of Zurich, and when D. Sridhara was with the Indian Institute of Science.
PY - 2007/11
Y1 - 2007/11
N2 - This paper presents a detailed analysis of pseudocodewords of Tanner graphs. Pseudocodewords arising on the iterative decoder's computation tree are distinguished from pseudocodewords arising on finite degree lifts. Lower bounds on the minimum pseudocodeword weight are presented for the BEC, BSC, and AWGN channel. Some structural properties of pseudocodewords are examined, and pseudocodewords and graph properties that are potentially problematic with min-sum iterative decoding are identified. An upper bound on the minimum degree lift needed to realize a particular irreducible lift-realizable pseudocodeword is given in terms of its maximal component, and it is shown that all irreducible lift-realizable pseudocodewords have components upper bounded by a finite value t that is dependent on the graph structure. Examples and different Tanner graph representations of individual codes are examined and the resulting pseudocodeword distributions and iterative decoding performances are analyzed. The results obtained provide some insights in relating the structure of the Tanner graph to the pseudocodeword distribution and suggest ways of designing Tanner graphs with good minimum pseudocodeword weight.
AB - This paper presents a detailed analysis of pseudocodewords of Tanner graphs. Pseudocodewords arising on the iterative decoder's computation tree are distinguished from pseudocodewords arising on finite degree lifts. Lower bounds on the minimum pseudocodeword weight are presented for the BEC, BSC, and AWGN channel. Some structural properties of pseudocodewords are examined, and pseudocodewords and graph properties that are potentially problematic with min-sum iterative decoding are identified. An upper bound on the minimum degree lift needed to realize a particular irreducible lift-realizable pseudocodeword is given in terms of its maximal component, and it is shown that all irreducible lift-realizable pseudocodewords have components upper bounded by a finite value t that is dependent on the graph structure. Examples and different Tanner graph representations of individual codes are examined and the resulting pseudocodeword distributions and iterative decoding performances are analyzed. The results obtained provide some insights in relating the structure of the Tanner graph to the pseudocodeword distribution and suggest ways of designing Tanner graphs with good minimum pseudocodeword weight.
KW - Iterative decoding
KW - Low-density parity-check (LDPC) codes
KW - Min-sum iterative decoder
KW - Pseudocodewords
UR - http://www.scopus.com/inward/record.url?scp=36348999345&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=36348999345&partnerID=8YFLogxK
U2 - 10.1109/TIT.2007.907501
DO - 10.1109/TIT.2007.907501
M3 - Article
AN - SCOPUS:36348999345
SN - 0018-9448
VL - 53
SP - 4013
EP - 4038
JO - IEEE Transactions on Information Theory
JF - IEEE Transactions on Information Theory
IS - 11
ER -