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)

Linear growing minimum distance of ultra-sparse non-binary cluster-LDPC codes

Valentin Savin, David Declercq

Published Jul 1, 2011• 9 citations
Publisher

Abstract

In this paper, we study the asymptotic minimum distance of non-binary cluster-LDPC codes whose subjacent binary parity-check matrix is composed of localized density of ones, concentrated in clusters of bits. A particular attention is given to cluster codes represented by ultra-sparse bipartite graphs, in the sense that each symbol-node is connected to exactly dv= 2 constraint-nodes. We derive a lower bound on the minimum distance of non-binary cluster-LDPC codes and we show that there exist ensembles of ultra-sparse codes whose minimum distance grows linearly with the code length (with probability going to 1 as the code length goes to infinity). This result is in contrast with “classical” non-binary LDPC codes based on graphs with strictly regular dv= 2 symbol-nodes, whose minimum distance grows at most logarithmically with the code length. We also show that one can build practical non-binary cluster-LDPC codes with various finite codeword lengths, whose minimum distance is close to the Gilbert-Varshamov bound.

DOI
10.1109/isit.2011.6034183

Related papers

Analysis and design of ultra-sparse non-binary cluster-LDPC codes

David Declercq, Valentin Savin, Lam Pham Sy

This paper continues a previous work on non-binary cluster-LDPC codes. Such codes are defined by locally dense parity-check matrices, with (possibly rectangular) dense clusters of bits, but which are cluster-wise sparse. We derive a lower bound on the minimum distance of non-binary cluster-LDPC codes that is based on the topological properties of the underlying bipartite graph. We also propose an optimization procedure, which allows designing finite length codes with large minimum distance, even in the extreme case of codes defined by ultra-sparse graphs, i.e. graphs with all symbol-nodes of degree dv= 2. Furthermore, we provide asymptotic thresholds of ensembles of non-binary cluster-LDPC codes, which are computed exactly under the Belief Propagation decoding, and upper-bounded under the Maximum a Posteriori (MAP) decoding. We show that the MAP-threshold upper bounds, which are conjunctured to be tight, quickly approach the channel capacity, which confirms the excellent minimal distance properties of non-binary cluster-LDPC codes.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2012•3 citations

On the Minimum Distance of Non Binary LDPC Codes

Rethnakaran Pulikkoonattu

Minimum distance is an important parameter of a linear error correcting code. For improved performance of binary Low Density Parity Check (LDPC) codes, we need to have the minimum distance grow fast with n, the codelength. However, the best we can hope for is a linear growth in dmin with n. For binary LDPC codes, the necessary and sufficient conditions on the LDPC ensemble parameters, to ensure linear growth of minimum distance is well established. In the case of non-binary LDPC codes, the structure of logarithmic weight codewords is different from that of binary codes. We have carried out a preliminary study on the logarithmic bound on the the minimum distance of non-binary LDPC code ensembles. In particular, we have investigated certain configurations which would lead to low weight codewords. A set of simulations are performed to identify some of these configurations. Finally, we have provided a bound on the logarithmic minimum distance of nonbinary codes, using a strategy similar to the girth bound for binary codes. This bound has the same asymptotic behaviour as that of binary codes.

arXiv:0906.2061•Jun 11, 2009•0 citations

Weight Distribution for Non-binary Cluster LDPC Code Ensemble

T. Nozaki, Masaki Maehara, Kenta Kasai +1 more

This paper derives the average symbol and bit weight distributions for the irregular non-binary cluster low-density parity-check (LDPC) code ensembles. Moreover, we give the exponential growth rates of the average weight distributions in the limit of large code length. We show the condition that the typical minimum distances linearly grow with the code length.

arXiv:1305.2480•IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jan 1, 2013•2 citations

Generalization of Tanner′s Minimum Distance Bounds for LDPC Codes

Shin Min Ho, 김준성, 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

Weight distribution for non-binary cluster LDPC code ensemble

T. Nozaki, Masaki Maehara, Kenta Kasai +1 more

In this paper, we derive the average weight distributions for the irregular non-binary cluster low-density parity-check (LDPC) code ensembles. Moreover, we give the exponential growth rate of the average weight distribution in the limit of large code length. We show that there exist (2, dc)-regular non-binary cluster LDPC code ensembles whose normalized typical minimum distances are strictly positive.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2013•1 citation

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
In this paper, we study the asymptotic minimum distance of non-binary cluster-LDPC codes whose subjacent binary parity-check matrix is composed of localized density of ones, concentrated in clusters of bits. A particular attention is given to cluster codes represented by ultra-sparse bipartite graphs, in the sense that each symbol-node is connected to exactly dv= 2 constraint-nodes. We derive a lower bound on the minimum distance of non-binary cluster-LDPC codes and we show that there exist ensembles of ultra-sparse codes whose minimum distance grows linearly with the code length (with probability going to 1 as the code length goes to infinity). This result is in contrast with “classical” non-binary LDPC codes based on graphs with strictly regular dv= 2 symbol-nodes, whose minimum distance grows at most logarithmically with the code length. We also show that one can build practical non-binary cluster-LDPC codes with various finite codeword lengths, whose minimum distance is close to the Gilbert-Varshamov bound.
This paper continues a previous work on non-binary cluster-LDPC codes. Such codes are defined by locally dense parity-check matrices, with (possibly rectangular) dense clusters of bits, but which are cluster-wise sparse. We derive a lower bound on the minimum distance of non-binary cluster-LDPC codes that is based on the topological properties of the underlying bipartite graph. We also propose an optimization procedure, which allows designing finite length codes with large minimum distance, even in the extreme case of codes defined by ultra-sparse graphs, i.e. graphs with all symbol-nodes of degree dv= 2. Furthermore, we provide asymptotic thresholds of ensembles of non-binary cluster-LDPC codes, which are computed exactly under the Belief Propagation decoding, and upper-bounded under the Maximum a Posteriori (MAP) decoding. We show that the MAP-threshold upper bounds, which are conjunctured to be tight, quickly approach the channel capacity, which confirms the excellent minimal distance properties of non-binary cluster-LDPC codes.
Minimum distance is an important parameter of a linear error correcting code. For improved performance of binary Low Density Parity Check (LDPC) codes, we need to have the minimum distance grow fast with n, the codelength. However, the best we can hope for is a linear growth in dmin with n. For binary LDPC codes, the necessary and sufficient conditions on the LDPC ensemble parameters, to ensure linear growth of minimum distance is well established. In the case of non-binary LDPC codes, the structure of logarithmic weight codewords is different from that of binary codes. We have carried out a preliminary study on the logarithmic bound on the the minimum distance of non-binary LDPC code ensembles. In particular, we have investigated certain configurations which would lead to low weight codewords. A set of simulations are performed to identify some of these configurations. Finally, we have provided a bound on the logarithmic minimum distance of nonbinary codes, using a strategy similar to the girth bound for binary codes. This bound has the same asymptotic behaviour as that of binary 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.
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.