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 Communications Letters

Generalization of Tanner's minimum distance bounds for LDPC codes

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

Published Mar 1, 2005• 7 citations
Publisher

Abstract

Tanner derived minimum distance bounds of regular codes in terms of the eigenvalues of the adjacency matrix by using some graphical analysis on the associated graph of the code. In this letter, we generalize Tanner's results by deriving a bit-oriented bound and a parity-oriented bound on the minimum distances of both regular and block-wise irregular LDPC codes.

DOI
10.1109/lcomm.2005.03002

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

Minimum distance and pseudodistance lower bounds for generalised LDPC codes

Christine A. Kelley

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.

International Journal of Information and Coding Theory•Jan 1, 2010•1 citation

Minimum distance bounds of irregular QC-LDPC codes and their applications

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

We consider a design of quasicyclic LDPC codes which have irregular column weights. We derive bit-oriented bound and parity-oriented bound on the minimum distances of irregular quasicyclic codes using a similar technique to Tanner's simple lower bound

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

Permutation-block LDPC codes: influence of Tanner-graph structure on minimum hamming distance

Benjamin Michael Thorn

Only since the mid-1990s, with the increase in computational power, has the\nimportance been realized regarding low-density parity-check (LDPC) codes as leading error\ncorrecting codes. The work in this thesis primarily studies LDPC codes that are de???ned by a\nparity-check matrix comprised of r _ r permutation matrix blocks, that is, permutation-block\nLDPC codes. More specifically, we study their minimum Hamming distance, as this is a\nparameter that affects the performance of linear codes, and thus LDPC codes.\nIt has been proven that there are upper bounds on the minimum Hamming distance of\nquasi-cyclic codes, de???ned by a parity-check matrix comprised of r _ r circulant matrix\nblocks, regardless of how large we allow r. However, we show that if general permutation\nmatrices are used instead of circulant matrices, we are able to exceed the bounds allowed by\nquasi-cyclic codes. Graphical representations of the codes, called Tanner-graphs, are used in\nproving many useful results regarding permutation-block LDPC codes and their minimum\nHamming distance. We show a characterization of the minimum Hamming distance of these\ncodes and we produce an algorithm for constructing permutation-block LDPC codes with\nlarge minimum Hamming distance.

•Jun 28, 2011•0 citations

Minimum distance distribution of irregular generalized LDPC code ensembles

Ian P. Mulholland, Mark F. Flanagan, Enrico Paolini

In this paper, the minimum distance distribution of irregular generalized LDPC (GLDPC) code ensembles is investigated. Two classes of GLDPC code ensembles are analyzed; in one case, the Tanner graph is regular from the variable node perspective, and in the other case the Tanner graph is completely unstructured and irregular. In particular, for the former ensemble class we determine exactly which ensembles have minimum distance growing linearly with the block length with probability approaching unity with increasing block length. This work extends previous results concerning LDPC and regular GLDPC codes to the case where a hybrid mixture of check node types is used.

arXiv:1302.0522•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2013•2 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
Tanner derived minimum distance bounds of regular codes in terms of the eigenvalues of the adjacency matrix by using some graphical analysis on the associated graph of the code. In this letter, we generalize Tanner's results by deriving a bit-oriented bound and a parity-oriented bound on the minimum distances of both regular and block-wise irregular LDPC codes.
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.
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.
Only since the mid-1990s, with the increase in computational power, has the\nimportance been realized regarding low-density parity-check (LDPC) codes as leading error\ncorrecting codes. The work in this thesis primarily studies LDPC codes that are de???ned by a\nparity-check matrix comprised of r _ r permutation matrix blocks, that is, permutation-block\nLDPC codes. More specifically, we study their minimum Hamming distance, as this is a\nparameter that affects the performance of linear codes, and thus LDPC codes.\nIt has been proven that there are upper bounds on the minimum Hamming distance of\nquasi-cyclic codes, de???ned by a parity-check matrix comprised of r _ r circulant matrix\nblocks, regardless of how large we allow r. However, we show that if general permutation\nmatrices are used instead of circulant matrices, we are able to exceed the bounds allowed by\nquasi-cyclic codes. Graphical representations of the codes, called Tanner-graphs, are used in\nproving many useful results regarding permutation-block LDPC codes and their minimum\nHamming distance. We show a characterization of the minimum Hamming distance of these\ncodes and we produce an algorithm for constructing permutation-block LDPC codes with\nlarge minimum Hamming distance.
In this paper, the minimum distance distribution of irregular generalized LDPC (GLDPC) code ensembles is investigated. Two classes of GLDPC code ensembles are analyzed; in one case, the Tanner graph is regular from the variable node perspective, and in the other case the Tanner graph is completely unstructured and irregular. In particular, for the former ensemble class we determine exactly which ensembles have minimum distance growing linearly with the block length with probability approaching unity with increasing block length. This work extends previous results concerning LDPC and regular GLDPC codes to the case where a hybrid mixture of check node types is used.
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.