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

International Journal of Information and Coding Theory

Minimum distance and pseudodistance lower bounds for generalised LDPC codes

Christine A. Kelley

Published Jan 1, 2010• 1 citation
Publisher

Abstract

Two different ways of obtaining generalised low-density parity-check (LDPC) codes are considered. Lower bounds on the minimum distance, stopping distance and pseudodistance are derived for these codes using graph-based analysis. These bounds are generalisations of Tanner's bit- and parity-oriented bound for simple (LDPC) codes. The new bounds are useful in predicting the performance of generalised LDPC codes under maximum-likelihood decoding, graph-based iterative decoding and linear programming decoding, and rely on the connectivity of the Tanner graph.

DOI
10.1504/ijicot.2010.032546

Related papers

Generalization of Tanner′s Minimum Distance Bounds for LDPC Codes

Shin Min Ho, Kim Joon Sung, Song Hong-Yeop

LDPC(Low Density Parity Check) codes are described by bipartite graphs with bit nodes and parity-check nodes. Tanner derived minimum distance bounds of the regular LDPC code in terms of the eigenvalues of the associated adjacency matrix. In this paper we generalize the Tanner's results. We derive minimum distance bounds applicable to both regular and blockwise-irregular LDPC codes. The first bound considers the relation between bit nodes in a minimum-weight codeword, and the second one considers the connectivity between parity nodes adjacent to a minimum-weight codeword. The derived bounds make it possible to describe the distance property of the code in terms of the eigenvalues of the associated matrix.

한국통신학회논문지•Jan 1, 2004•0 citations

Eigenvalue bounds on the pseudocodeword weight of expander codes

Christine A. Kelley, Deepak Sridhara

Four different ways of obtaining low-density parity-check codesfrom expander graphs are considered. For each case, lower bounds on the minimum stopping set size and the minimum pseudocodeword weight of expander (LDPC) codes are derived. These bounds are compared with the known eigenvalue-based lower bounds on the minimum distance of expander codes. Furthermore, Tanner's parity-oriented eigenvalue lower bound on the minimumdistance is generalized to yield a new lower bound on the minimum pseudocodeword weight. These bounds are useful in predicting the performance of LDPC codes under graph-based iterative decoding and linear programming decoding.

arXiv:0708.2462•Advances in Mathematics of Communications•Jan 1, 2007•11 citations

Minimum Pseudoweight and Minimum Pseudocodewords of LDPC Codes

Shu‐Tao Xia, Fang‐Wei Fu

In this correspondence, we study the minimum pseudoweight and minimum pseudocodewords of low-density parity-check (LDPC) codes under linear programming (LP) decoding. First, we show that the lower bound of Kelley, Sridhara, Xu, and Rosenthal on the pseudoweight of a nonzero pseudocodeword of an LDPC code whose Tanner graph has girth greater than is tight if and only if this pseudocodeword is a real multiple of a codeword. Then, the lower bound of Kashyap and Vardy on the stopping distance of an LDPC code is proved to be also a lower bound on the pseudoweight of a nonzero pseudocodeword of an LDPC code whose Tanner graph has girth , and this lower bound is tight if and only if this pseudocodeword is a real multiple of a codeword. Using these results we further obtain that for some LDPC codes, there are no other minimum pseudocodewords except the real multiples of minimum weight codewords. This means that the LP decoding for these LDPC codes is asymptotically optimal in the sense that the ratio of the probabilities of decoding errors of LP decoding and maximum-likelihood decoding approaches as the signal-to-noise ratio (SNR) tends to infinity. Finally, some LDPC codes are listed to illustrate these results.

arXiv:cs/0606051•IEEE Transactions on Information Theory•Jan 1, 2008•25 citations

Performance of low-density parity-check codes with linear minimum distance

Hossein Pishro-Nik, Faramarz Fekri

This correspondence studies the performance of the iterative decoding of low-density parity-check (LDPC) code ensembles that have linear typical minimum distance and stopping set size. We first obtain a lower bound on the achievable rates of these ensembles over memoryless binary-input output-symmetric channels. We improve this bound for the binary erasure channel. We also introduce a method to construct the codes meeting the lower bound for the binary erasure channel. Then, we give upper bounds on the rate of LDPC codes with linear minimum distance when their right degree distribution is fixed. We compare these bounds to the previously derived upper bounds on the rate when there is no restriction on the code ensemble.

IEEE Transactions on Information Theory•Dec 28, 2005•13 citations

Minimum Pseudo-Codewords of LDPC Codes

Shu‐Tao Xia, Fang‐Wei Fu

In this paper, we study the minimum pseudo-weight and minimum pseudo-codewords of low-density parity-check (LDPC) codes under linear programming (LP) decoding. First, we show that the lower bound of Kelly, Sridhara, Xu and Rosenthal on the pseudo-weight of a pseudo-codeword of an LDPC code with girth greater than 4 is tight if and only if this pseudo-codeword is a real multiple of a codeword. Then, we show that the lower bound of Kashyap and Vardy on the stopping distance of an LDPC code is also a lower bound on the pseudo-weight of a pseudo-codeword of this LDPC code with girth 4, and this lower bound is tight if and only if this pseudo-codeword is a real multiple of a codeword. Using these results we further show that for some LDPC codes, there are no other minimum pseudo-codewords except the real multiples of minimum codewords. This means that LP decoding for these LDPC codes is asymptotically optimal in the sense that the ratio of the probabilities of decoding errors of LP decoding and maximum-likelihood (ML) decoding approaches to 1 as the signal-to-noise ratio leads to infinity. Finally, some LDPC codes are listed to illustrate these results

IEEE Information Theory Workshop (ITW)•Oct 1, 2006•7 citations

Analysis of the relation between properties of LDPC codes and the tanner graph

Victor Zyablov, Pavel S. Rybin

A new method for estimating the number of errors guaranteed to be corrected by a low-density parity-check code is proposed. The method is obtained by analyzing edges with special properties of an appropriate Tanner graph. In this paper we consider binary LDPC codes with constituent single-parity-check and Hamming codes and an iterative decoding algorithm. Numerical results obtained for the proposed lower bound exceed similar results for the best previously known lower bounds.

Problems of Information Transmission•Oct 1, 2012•8 citations
Two different ways of obtaining generalised low-density parity-check (LDPC) codes are considered. Lower bounds on the minimum distance, stopping distance and pseudodistance are derived for these codes using graph-based analysis. These bounds are generalisations of Tanner's bit- and parity-oriented bound for simple (LDPC) codes. The new bounds are useful in predicting the performance of generalised LDPC codes under maximum-likelihood decoding, graph-based iterative decoding and linear programming decoding, and rely on the connectivity of the Tanner graph.
LDPC(Low Density Parity Check) codes are described by bipartite graphs with bit nodes and parity-check nodes. Tanner derived minimum distance bounds of the regular LDPC code in terms of the eigenvalues of the associated adjacency matrix. In this paper we generalize the Tanner's results. We derive minimum distance bounds applicable to both regular and blockwise-irregular LDPC codes. The first bound considers the relation between bit nodes in a minimum-weight codeword, and the second one considers the connectivity between parity nodes adjacent to a minimum-weight codeword. The derived bounds make it possible to describe the distance property of the code in terms of the eigenvalues of the associated matrix.
Four different ways of obtaining low-density parity-check codesfrom expander graphs are considered. For each case, lower bounds on the minimum stopping set size and the minimum pseudocodeword weight of expander (LDPC) codes are derived. These bounds are compared with the known eigenvalue-based lower bounds on the minimum distance of expander codes. Furthermore, Tanner's parity-oriented eigenvalue lower bound on the minimumdistance is generalized to yield a new lower bound on the minimum pseudocodeword weight. These bounds are useful in predicting the performance of LDPC codes under graph-based iterative decoding and linear programming decoding.
In this correspondence, we study the minimum pseudoweight and minimum pseudocodewords of low-density parity-check (LDPC) codes under linear programming (LP) decoding. First, we show that the lower bound of Kelley, Sridhara, Xu, and Rosenthal on the pseudoweight of a nonzero pseudocodeword of an LDPC code whose Tanner graph has girth greater than is tight if and only if this pseudocodeword is a real multiple of a codeword. Then, the lower bound of Kashyap and Vardy on the stopping distance of an LDPC code is proved to be also a lower bound on the pseudoweight of a nonzero pseudocodeword of an LDPC code whose Tanner graph has girth , and this lower bound is tight if and only if this pseudocodeword is a real multiple of a codeword. Using these results we further obtain that for some LDPC codes, there are no other minimum pseudocodewords except the real multiples of minimum weight codewords. This means that the LP decoding for these LDPC codes is asymptotically optimal in the sense that the ratio of the probabilities of decoding errors of LP decoding and maximum-likelihood decoding approaches as the signal-to-noise ratio (SNR) tends to infinity. Finally, some LDPC codes are listed to illustrate these results.
This correspondence studies the performance of the iterative decoding of low-density parity-check (LDPC) code ensembles that have linear typical minimum distance and stopping set size. We first obtain a lower bound on the achievable rates of these ensembles over memoryless binary-input output-symmetric channels. We improve this bound for the binary erasure channel. We also introduce a method to construct the codes meeting the lower bound for the binary erasure channel. Then, we give upper bounds on the rate of LDPC codes with linear minimum distance when their right degree distribution is fixed. We compare these bounds to the previously derived upper bounds on the rate when there is no restriction on the code ensemble.
In this paper, we study the minimum pseudo-weight and minimum pseudo-codewords of low-density parity-check (LDPC) codes under linear programming (LP) decoding. First, we show that the lower bound of Kelly, Sridhara, Xu and Rosenthal on the pseudo-weight of a pseudo-codeword of an LDPC code with girth greater than 4 is tight if and only if this pseudo-codeword is a real multiple of a codeword. Then, we show that the lower bound of Kashyap and Vardy on the stopping distance of an LDPC code is also a lower bound on the pseudo-weight of a pseudo-codeword of this LDPC code with girth 4, and this lower bound is tight if and only if this pseudo-codeword is a real multiple of a codeword. Using these results we further show that for some LDPC codes, there are no other minimum pseudo-codewords except the real multiples of minimum codewords. This means that LP decoding for these LDPC codes is asymptotically optimal in the sense that the ratio of the probabilities of decoding errors of LP decoding and maximum-likelihood (ML) decoding approaches to 1 as the signal-to-noise ratio leads to infinity. Finally, some LDPC codes are listed to illustrate these results