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:1511.00125

Computing the minimum distance of nonbinary LDPC codes using block Korkin-Zolotarev method

Vasiliy S. Usatyuk

Published Oct 31, 2015• 1 citation
arXivHTMLPDF

Abstract

In article present measure code distance algorithm of binary and ternary linear block code using block Korkin-Zolotarev (BKZ). Proved the upper bound on scaling constant for measure code distance of non-systematic linear block code using BKZ-method for different value of the block size. Introduced method show linear decrease of runtime from number of threads and work especially good under not dense lattices of LDPC-code. These properties allow use this algorithm to measure the minimal distance of code with length several thousand. The algorithm can further improve by transform into probabilistic algorithm using lattice enumerating pruning techniques

DOI
10.48550/arxiv.1511.00125

Related papers

Computing the Minimum Distance of Nonbinary LDPC Codes

Lei Liu, Jie Huang, Wuyang Zhou +1 more

Finding the minimum distance of low-density-parity-check (LDPC) codes is an NP-hard problem. Different from all existing works that focus on binary LDPC codes, we in this paper aim to compute the minimum distance of nonbinary LDPC codes, motivated by the fact that operating in a large Galois field provides one important degree of freedom to achieve both good waterfall and error-floor performance. Our method is based on the existing nearest nonzero codeword search (NNCS) method, but several modifications are incorporated for nonbinary LDPC codes, including the modified error impulse pattern, the dithering method, and the nonbinary decoder. Numerical results on the estimated minimum distances show that a code's minimum distance can be increased by careful selection of nonzero elements of the parity check matrix, or by increasing the mean column weight, or by increasing the size of the Galois field. These results support observations that have been made based on simulated performance in the literature. Finally, we provide an upper bound on the minimum distance for nonbinary quasi-cyclic LDPC codes.

IEEE Transactions on Communications•Jul 1, 2012•8 citations

Improved Linear Programming Decoding of LDPC Codes and Bounds on the Minimum and Fractional Distance

David Burshtein, Idan Goldenberg

We examine LDPC codes decoded using linear programming (LP). Four contributions to the LP framework are presented. First, a new method of tightening the LP relaxation, and thus improving the LP decoder, is proposed. Second, we present an algorithm which calculates a lower bound on the minimum distance of a specific code. This algorithm exhibits complexity which scales quadratically with the block length. Third, we propose a method to obtain a tight lower bound on the fractional distance, also with quadratic complexity, and thus less than previously-existing methods. Finally, we show how the fundamental LP polytope for generalized LDPC codes and nonbinary LDPC codes can be obtained.

arXiv:1012.1425•IEEE Transactions on Information Theory•Jul 21, 2011•17 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

Evaluations of Good LDPC Codes Based on Generator Matrices

Yang Xiao

Since the weight and distance computations of LDPC codes is a NP problem, most presented evaluations of LDPC codes are based on the girth numbers of the codes, and the computation for the distance of the codes is also depended on the girth numbers. There has been no simple way to obtain the distance of LDPC codes because of the code length. Based on generation matrices, this paper develops an algorithm to estimate the upper bound of minimum weights and minimum distance of LDPC codes. The paper establishes the upper bounds of minimum weights and distances of LDPC codes by using the vectors of generation matrices, which is different from the presented probabilitistic search methods for the weights' and distances of LCPC codes. The proposed algorithm can greatly reduce the searching time of weights and distances. Applying the algorithm we find that some LDPC codes get good BER performance although they are only free girth 4 but of great distances. Simulations verify the algorithms to be valid.

•Jan 1, 2006•6 citations

Iterative Linear Programming Decoding of Nonbinary LDPC Codes With Linear Complexity

Dina Goldin, David Burshtein

The problem of low-complexity linear programming (LP) decoding of nonbinary low-density parity-check (LDPC) codes is considered, and an iterative LP decoding algorithm is presented. Results that were previously derived for binary LDPC codes are extended to the nonbinary case. Both simple and generalized nonbinary LDPC codes are considered. It is shown how the algorithm can be implemented efficiently using a finite-field fast Fourier transform. Then, the convergence rate of the algorithm is analyzed. The complexity of the algorithm scales linearly in the block length, and it can approximate, up to an arbitrarily small relative error, the objective function of the exact LP solution. When applied to a typical code from an appropriate nonbinary LDPC code ensemble, the algorithm can correct a constant fraction of errors in linear (in the block length) computational complexity. Computer experiments with the new iterative LP decoding algorithm show that, in the error floor region, it can have better performance compared to belief propagation decoding, with similar computational requirements.

IEEE Transactions on Information Theory•Aug 6, 2012•17 citations

Efficient methods for bounding the fractional distance of LDPC codes and obtaining fundamental polytopes of nonbinary and generalized codes

David Burshtein, Idan Goldenberg

A method which obtains a tight lower bound on the fractional distance of LDPC codes is proposed. This algorithm exhibits complexity which scales quadratically with the block length, and thus less than currently-known methods. We also show how the fundamental LP polytope for generalized LDPC codes and nonbinary LDPC codes can be obtained.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2011•0 citations
In article present measure code distance algorithm of binary and ternary linear block code using block Korkin-Zolotarev (BKZ). Proved the upper bound on scaling constant for measure code distance of non-systematic linear block code using BKZ-method for different value of the block size. Introduced method show linear decrease of runtime from number of threads and work especially good under not dense lattices of LDPC-code. These properties allow use this algorithm to measure the minimal distance of code with length several thousand. The algorithm can further improve by transform into probabilistic algorithm using lattice enumerating pruning techniques
Finding the minimum distance of low-density-parity-check (LDPC) codes is an NP-hard problem. Different from all existing works that focus on binary LDPC codes, we in this paper aim to compute the minimum distance of nonbinary LDPC codes, motivated by the fact that operating in a large Galois field provides one important degree of freedom to achieve both good waterfall and error-floor performance. Our method is based on the existing nearest nonzero codeword search (NNCS) method, but several modifications are incorporated for nonbinary LDPC codes, including the modified error impulse pattern, the dithering method, and the nonbinary decoder. Numerical results on the estimated minimum distances show that a code's minimum distance can be increased by careful selection of nonzero elements of the parity check matrix, or by increasing the mean column weight, or by increasing the size of the Galois field. These results support observations that have been made based on simulated performance in the literature. Finally, we provide an upper bound on the minimum distance for nonbinary quasi-cyclic LDPC codes.
We examine LDPC codes decoded using linear programming (LP). Four contributions to the LP framework are presented. First, a new method of tightening the LP relaxation, and thus improving the LP decoder, is proposed. Second, we present an algorithm which calculates a lower bound on the minimum distance of a specific code. This algorithm exhibits complexity which scales quadratically with the block length. Third, we propose a method to obtain a tight lower bound on the fractional distance, also with quadratic complexity, and thus less than previously-existing methods. Finally, we show how the fundamental LP polytope for generalized LDPC codes and nonbinary LDPC codes can be obtained.
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.
Since the weight and distance computations of LDPC codes is a NP problem, most presented evaluations of LDPC codes are based on the girth numbers of the codes, and the computation for the distance of the codes is also depended on the girth numbers. There has been no simple way to obtain the distance of LDPC codes because of the code length. Based on generation matrices, this paper develops an algorithm to estimate the upper bound of minimum weights and minimum distance of LDPC codes. The paper establishes the upper bounds of minimum weights and distances of LDPC codes by using the vectors of generation matrices, which is different from the presented probabilitistic search methods for the weights' and distances of LCPC codes. The proposed algorithm can greatly reduce the searching time of weights and distances. Applying the algorithm we find that some LDPC codes get good BER performance although they are only free girth 4 but of great distances. Simulations verify the algorithms to be valid.
The problem of low-complexity linear programming (LP) decoding of nonbinary low-density parity-check (LDPC) codes is considered, and an iterative LP decoding algorithm is presented. Results that were previously derived for binary LDPC codes are extended to the nonbinary case. Both simple and generalized nonbinary LDPC codes are considered. It is shown how the algorithm can be implemented efficiently using a finite-field fast Fourier transform. Then, the convergence rate of the algorithm is analyzed. The complexity of the algorithm scales linearly in the block length, and it can approximate, up to an arbitrarily small relative error, the objective function of the exact LP solution. When applied to a typical code from an appropriate nonbinary LDPC code ensemble, the algorithm can correct a constant fraction of errors in linear (in the block length) computational complexity. Computer experiments with the new iterative LP decoding algorithm show that, in the error floor region, it can have better performance compared to belief propagation decoding, with similar computational requirements.