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)

On the Minimum Distance of Generalized LDPC Codes

Ayoub Otmani, Jean–Pierre Tillich, Iryna Andriyanova

Published Jun 1, 2007• 10 citations
Publisher

Abstract

We study necessary conditions which have to be satisfied in order to have LDPC codes with linear minimum distance. We give two conditions of this kind in this paper. These conditions are not met for several interesting code families: this shows that they are not asymptotically good. The second one concerns LDPC codes that have a Tanner graph in which there are cycles linking variable nodes of degree 2 together and provides some insight about the combinatorial structure of some low-weight codewords in such a case. When the LDPC code family is obtained from the lifts of a given protograph and if there are such cycles in the protograph, the second condition seems to capture really well the linear minimum distance character of the code. This is illustrated by a code family which is asymptotically good for which there is a cycle linking all the variable nodes of degree 2 together. Surprisingly, this family is only a slight modification of a family which does not satisfy the second condition.

DOI
10.1109/isit.2007.4557106

Related papers

On the Minimum Distance of Generalized LDPC Codes

Ayoub Otmani, Jean–Pierre Tillich, Iryna Andriyanova

Abstract — We study necessary conditions which have to be satisfied in order to have LDPC codes with linear minimum distance. We give two conditions of this kind in this paper. These conditions are not met for several interesting code families: this shows that they are not asymptotically good. The second one concerns LDPC codes that have a Tanner graph in which there are cycles linking variable nodes of degree 2 together and provides some insight about the combinatorial structure of some low-weight codewords in such a case. When the LDPC code family is obtained from the lifts of a given protograph and if there are such cycles in the protograph, the second condition seems to capture really well the linear minimum distance character of the code. This is illustrated by a code family which is asymptotically good for which there is a cycle linking all the variable nodes of degree 2 together. Surprisingly, this family is only a slight modification of a family which does not satisfy the second condition. I.

•Jun 24, 2007•0 citations

On the typical minimum distance of protograph-based generalized LDPC codes

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

Protograph-based generalized LDPC (GLDPC) codes have the advantages of a simple design procedure and highly structured encoders and decoders. Recently, a technique for computing ensemble weight enumerators for GLDPC codes has been published. In the current paper, we investigate the existence of typical minimum distance for protograph-based GLDPC codes. That is, we first upper bound the ensemble weight enumerators for finite-length GLDPC codes based on protographs, and then we consider the sum of weight enumerators. The results allow us to determine whether or not the typical minimum distance in the ensemble grows linearly with codeword length. We provide conditions on the connections of degree-2 variable nodes to constraint nodes (short block codes) to have typical minimum distance. These conditions are related to the minimum distances of the constraint nodes.

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

On a Low-Rate TLDPC Code Ensemble and the Necessary Condition on the Linear Minimum Distance for Sparse-Graph Codes

Iryna Andriyanova, Jean–Pierre Tillich

This paper addresses the issue of design of low-rate sparse-graph codes with linear minimum distance in the blocklength. First, we define a necessary condition which needs to be satisfied when the linear minimum distance is to be ensured. The condition is formulated in terms of degree-1 and degree-2 variable nodes and of low-weight codewords of the underlying code, and it generalizies results known for turbo codes [8] and LDPC codes. Then, we present a new ensemble of low-rate codes, which itself is a subclass of TLDPC codes [4], [5], and which is designed under this necessary condition. The asymptotic analysis of the ensemble shows that its iterative threshold is situated close to the Shannon limit. In addition to the linear minimum distance property, it has a simple structure and enjoys a low decoding complexity and a fast convergence.

arXiv:1010.1911•Oct 10, 2010•0 citations

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

On the typical minimum distance of protograph-based non-binary LDPC codes

D. Divsalar, Lara Dolecek

This paper proves the existence of the typical minimum distance for certain ensembles of the protograph-based nonbinary (PB NB) LDPC codes with degree-2 variable nodes. Using recently obtained ensemble weight enumerators for the PB NB LDPC codes, we show that asymptotically in the code length N, the entries in the weight enumerators up to some weight d* = δ* N (δ* >; 0) vanish under certain conditions on degree-2 nodes. As a consequence, the probability that the code minimum distance is less than d* goes to zero as the code length goes to infinity. Results of this type advance the understanding of structured non-binary LDPC codes.

Information Theory and Applications Workshop (ITA)•Feb 1, 2012•8 citations

Construction of Protograph LDPC Codes with Linear Minimum Distance

D. Divsalar, Sam Dolinar, Christopher Jones

A construction method for protograph-based LDPC codes that simultaneously achieve low iterative decoding threshold and linear minimum distance is proposed. We start with a high-rate protograph LDPC code with variable node degrees of at least 3. Lower rate codes are obtained by splitting check nodes and connecting them by degree-2 nodes. This guarantees the linear minimum distance property for the lower-rate codes. Excluding checks connected to degree-1 nodes, we show that the number of degree-2 nodes should be at most one less than the number of checks for the protograph LDPC code to have linear minimum distance. Iterative decoding thresholds are obtained by using the reciprocal channel approximation. Thresholds are lowered by using either precoding or at least one very high-degree node in the base protograph. A family of high- to low-rate codes with minimum distance linearly increasing in block size and with capacity-approaching performance thresholds is presented. FPGA simulation results for a few example codes show that the proposed codes perform as predicted

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2006•92 citations
We study necessary conditions which have to be satisfied in order to have LDPC codes with linear minimum distance. We give two conditions of this kind in this paper. These conditions are not met for several interesting code families: this shows that they are not asymptotically good. The second one concerns LDPC codes that have a Tanner graph in which there are cycles linking variable nodes of degree 2 together and provides some insight about the combinatorial structure of some low-weight codewords in such a case. When the LDPC code family is obtained from the lifts of a given protograph and if there are such cycles in the protograph, the second condition seems to capture really well the linear minimum distance character of the code. This is illustrated by a code family which is asymptotically good for which there is a cycle linking all the variable nodes of degree 2 together. Surprisingly, this family is only a slight modification of a family which does not satisfy the second condition.
Abstract — We study necessary conditions which have to be satisfied in order to have LDPC codes with linear minimum distance. We give two conditions of this kind in this paper. These conditions are not met for several interesting code families: this shows that they are not asymptotically good. The second one concerns LDPC codes that have a Tanner graph in which there are cycles linking variable nodes of degree 2 together and provides some insight about the combinatorial structure of some low-weight codewords in such a case. When the LDPC code family is obtained from the lifts of a given protograph and if there are such cycles in the protograph, the second condition seems to capture really well the linear minimum distance character of the code. This is illustrated by a code family which is asymptotically good for which there is a cycle linking all the variable nodes of degree 2 together. Surprisingly, this family is only a slight modification of a family which does not satisfy the second condition. I.
Protograph-based generalized LDPC (GLDPC) codes have the advantages of a simple design procedure and highly structured encoders and decoders. Recently, a technique for computing ensemble weight enumerators for GLDPC codes has been published. In the current paper, we investigate the existence of typical minimum distance for protograph-based GLDPC codes. That is, we first upper bound the ensemble weight enumerators for finite-length GLDPC codes based on protographs, and then we consider the sum of weight enumerators. The results allow us to determine whether or not the typical minimum distance in the ensemble grows linearly with codeword length. We provide conditions on the connections of degree-2 variable nodes to constraint nodes (short block codes) to have typical minimum distance. These conditions are related to the minimum distances of the constraint nodes.
This paper addresses the issue of design of low-rate sparse-graph codes with linear minimum distance in the blocklength. First, we define a necessary condition which needs to be satisfied when the linear minimum distance is to be ensured. The condition is formulated in terms of degree-1 and degree-2 variable nodes and of low-weight codewords of the underlying code, and it generalizies results known for turbo codes [8] and LDPC codes. Then, we present a new ensemble of low-rate codes, which itself is a subclass of TLDPC codes [4], [5], and which is designed under this necessary condition. The asymptotic analysis of the ensemble shows that its iterative threshold is situated close to the Shannon limit. In addition to the linear minimum distance property, it has a simple structure and enjoys a low decoding complexity and a fast convergence.
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.
This paper proves the existence of the typical minimum distance for certain ensembles of the protograph-based nonbinary (PB NB) LDPC codes with degree-2 variable nodes. Using recently obtained ensemble weight enumerators for the PB NB LDPC codes, we show that asymptotically in the code length N, the entries in the weight enumerators up to some weight d* = δ* N (δ* >; 0) vanish under certain conditions on degree-2 nodes. As a consequence, the probability that the code minimum distance is less than d* goes to zero as the code length goes to infinity. Results of this type advance the understanding of structured non-binary LDPC codes.
A construction method for protograph-based LDPC codes that simultaneously achieve low iterative decoding threshold and linear minimum distance is proposed. We start with a high-rate protograph LDPC code with variable node degrees of at least 3. Lower rate codes are obtained by splitting check nodes and connecting them by degree-2 nodes. This guarantees the linear minimum distance property for the lower-rate codes. Excluding checks connected to degree-1 nodes, we show that the number of degree-2 nodes should be at most one less than the number of checks for the protograph LDPC code to have linear minimum distance. Iterative decoding thresholds are obtained by using the reciprocal channel approximation. Thresholds are lowered by using either precoding or at least one very high-degree node in the base protograph. A family of high- to low-rate codes with minimum distance linearly increasing in block size and with capacity-approaching performance thresholds is presented. FPGA simulation results for a few example codes show that the proposed codes perform as predicted