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

arXiv:cs/0510043

On Minimal Pseudo-Codewords of Tanner Graphs from Projective Planes

Pascal O. Vontobel, Roxana Smarandache

Published Oct 15, 2005• 7 citations
arXivHTMLPDF

Abstract

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.
DOI
10.48550/arxiv.cs/0510043

Related papers

On minimal pseudo-codewords

Roxana Smarandache

The performance of linear-programming decoding of a binary linear code described by a parity-check matrix depends on the set of pseudo-codewords associated to this matrix and in particular, on the set of minimal pseudo-codewords. This paper attempts to provide an algebraic characterization of the minimal pseudo-codewords. It also provides a connection between the fundamental cone of a Tanner graph and the fundamental cone of its Forney-style factor graph.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2010•2 citations

On the minimal pseudo-codewords of codes from finite geometries

Pascal O. Vontobel, Roxana Smarandache, Negar Kiyavash +2 more

In order to understand the performance of a code under maximum-likelihood (ML) decoding, it is crucial to know the minimal codewords. In the context of linear programming (LP) decoding, it turns out to be necessary to know the minimal pseudo-codewords. This paper studies the minimal codewords and minimal pseudo-codewords of some families of codes derived from projective and Euclidean planes. Although our numerical results are only for codes of very modest length, they suggest that these code families exhibit an interesting property. Namely, all minimal pseudo-codewords that are not multiples of a minimal codeword have an AWGNC pseudo-weight that is strictly larger than the minimum Hamming weight of the code. This observation has positive consequences not only for LP decoding but also for iterative decoding

arXiv:cs/0508019•IEEE International Symposium on Information Theory (ISIT)•Jan 1, 2005•17 citations

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

Pseudocodeword weights and stopping sets

Christine A. Kelley, Deepak Sridhara, Jun Xu +1 more

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.

IEEE International Symposium on Information Theory (ISIT)•Dec 23, 2004•24 citations

Pseudo-Codeword Analysis of Tanner Graphs From Projective and Euclidean Planes

Roxana Smarandache, Pascal O. Vontobel

We consider coded data transmission over a binary-input output-symmetric memoryless channel using a binary linear code. In order to understand the performance of maximum-likelihood (ML) decoding, one studies the codewords, in particular the minimal codewords, and their Hamming weights. In the context of linear programming (LP) decoding, one's attention needs to be shifted to the pseudo-codewords, in particular, to the minimal pseudo-codewords and their pseudo-weights. In this paper, we investigate some families of codes that have good properties under LP decoding, namely certain families of low-density parity-check (LDPC) codes that are derived from projective and Euclidean planes: we study the structure of their minimal pseudo-codewords and give lower bounds on their pseudo-weight. Besides this main focus, we also present some results that hold for pseudo-codewords and minimal pseudo-codewords of any Tanner graph, and we highlight how the importance of minimal pseudo-codewords under LP decoding varies depending on which binary-input output-symmetric memoryless channel is used.

arXiv:cs/0602089•IEEE Transactions on Information Theory•Jun 28, 2007•50 citations
In order to understand the performance of a code under maximum-likelihood (ML) decoding, it is crucial to know the minimal codewords. In the context of linear programming (LP) decoding, it turns out to be necessary to know the minimal pseudo-codewords. This paper studies the minimal codewords and minimal pseudo-codewords of some families of codes derived from projective and Euclidean planes. Although our numerical results are only for codes of very modest length, they suggest that these code families exhibit an interesting property. Namely, all minimal pseudo-codewords that are not multiples of a minimal codeword have an AWGNC pseudo-weight that is strictly larger than the minimum Hamming weight of the code. This observation has positive consequences not only for LP decoding but also for iterative decoding
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.
We consider coded data transmission over a binary-input output-symmetric memoryless channel using a binary linear code. In order to understand the performance of maximum-likelihood (ML) decoding, one studies the codewords, in particular the minimal codewords, and their Hamming weights. In the context of linear programming (LP) decoding, one's attention needs to be shifted to the pseudo-codewords, in particular, to the minimal pseudo-codewords and their pseudo-weights. In this paper, we investigate some families of codes that have good properties under LP decoding, namely certain families of low-density parity-check (LDPC) codes that are derived from projective and Euclidean planes: we study the structure of their minimal pseudo-codewords and give lower bounds on their pseudo-weight. Besides this main focus, we also present some results that hold for pseudo-codewords and minimal pseudo-codewords of any Tanner graph, and we highlight how the importance of minimal pseudo-codewords under LP decoding varies depending on which binary-input output-symmetric memoryless channel is used.