Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE International Symposium on Information Theory (ISIT)

Pseudocodeword weights and stopping sets

Christine A. Kelley, Deepak Sridhara, Jun Xu, Joachim Rosenthal

Published Dec 23, 2004• 24 citations
Publisher

Abstract

We examine the structure of pseudocodewords in Tanner graphs and derive lower bounds of pseudocodeword weights. The weight of a pseudocodeword is related to the size of its support set, which forms a stopping set in the Tanner graph.
DOI
10.1109/isit.2004.1365105

Related papers

Pseudocodewords of Tanner Graphs

Christine A. Kelley, Deepak Sridhara

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.

arXiv:cs/0504013•IEEE Transactions on Information Theory•Nov 1, 2007•95 citations

Structure of Pseudocodewords in Tanner Graphs

Christine A. Kelley, Deepak Sridhara

Abstract—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. Index Terms—Iterative decoding, low-density parity-check (LDPC) codes, min-sum iterative decoder, pseudocodewords. I.

•Jan 1, 2004•2 citations

Lower Bounds on Stopping Distance of Linear Codes and Their Applications

Mingrui Zhu, K.M. Chugg

One of the most important open problems in the communication society is to determine the performance of iterative message passing algorithms over loopy graphs.Some recent work addresses this problem for loopy Tanner graphs by introducing the concepts of stopping distance and stopping redundancy.By analyzing the eigenvalues and eigenvectors of the normalized incidence matrix representing a Tanner graph, we derive lower bounds on its stopping distance.Using these lower bounds, an upper bound on stopping redundancy of the difference-set codes is derived as well.

•Sep 28, 2005•0 citations

On Minimal Pseudo-Codewords of Tanner Graphs from Projective Planes

Pascal O. Vontobel, Roxana Smarandache

We would like to better understand the fundamental cone of Tanner graphs derived from finite projective planes. Towards this goal, we discuss bounds on the AWGNC and BSC pseudo-weight of minimal pseudo-codewords of such Tanner graphs, on one hand, and study the structure of minimal pseudo-codewords, on the other.

arXiv:cs/0510043•Oct 15, 2005•7 citations

Ensemble Pseudocodeword Weight Enumerators for Protograph-Based Generalized LDPC Codes

Shadi Abu‐Surra, D. Divsalar, W.E. Ryan

Recently, pseudocodewords of Tanner graphs of LDPC codes have been used to explain the behavior of iterative decoders for these codes. In this paper, finite-length pseudocodeword weight enumerators for protograph-based generalized-LDPC code ensembles are obtained. Then asymptotic results are derived from the finite-length results by letting the block length go to infinity. The asymptotic results allow us to determine whether or not the typical minimum pseudocodeword weight grows linearly with codeword length. We give examples with Hamming component codes.

Globecom•Nov 1, 2009•1 citation

Bounds on the Expansion Properties of Tanner Graphs

Mingrui Zhu, K.M. Chugg

This work focuses on the expansion properties of a Tanner Graph because they are known to be related to the performance of associated iterative message-passing algorithms over various channels. By analyzing the eigenvalues and corresponding eigenvectors of the normalized incidence matrix representing a Tanner Graph, lower bounds on these expansion properties are derived. Specifically, for the binary erasure channel, these results lead to two lower bounds on stopping distance for any given binary linear code and an upper bound on stopping redundancy for the family of difference-set codes (type-I 2-D projective geometry low-density parity-check (LDPC) codes).

IEEE Transactions on Information Theory•Dec 1, 2007•3 citations
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 valuetttthat 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.
Abstract—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. Index Terms—Iterative decoding, low-density parity-check (LDPC) codes, min-sum iterative decoder, pseudocodewords. I.
One of the most important open problems in the communication society is to determine the performance of iterative message passing algorithms over loopy graphs.Some recent work addresses this problem for loopy Tanner graphs by introducing the concepts of stopping distance and stopping redundancy.By analyzing the eigenvalues and eigenvectors of the normalized incidence matrix representing a Tanner graph, we derive lower bounds on its stopping distance.Using these lower bounds, an upper bound on stopping redundancy of the difference-set codes is derived as well.
Recently, pseudocodewords of Tanner graphs of LDPC codes have been used to explain the behavior of iterative decoders for these codes. In this paper, finite-length pseudocodeword weight enumerators for protograph-based generalized-LDPC code ensembles are obtained. Then asymptotic results are derived from the finite-length results by letting the block length go to infinity. The asymptotic results allow us to determine whether or not the typical minimum pseudocodeword weight grows linearly with codeword length. We give examples with Hamming component codes.
This work focuses on the expansion properties of a Tanner Graph because they are known to be related to the performance of associated iterative message-passing algorithms over various channels. By analyzing the eigenvalues and corresponding eigenvectors of the normalized incidence matrix representing a Tanner Graph, lower bounds on these expansion properties are derived. Specifically, for the binary erasure channel, these results lead to two lower bounds on stopping distance for any given binary linear code and an upper bound on stopping redundancy for the family of difference-set codes (type-I 2-D projective geometry low-density parity-check (LDPC) codes).