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

Distance Verification for LDPC Codes

Ilya I. Dumer, Alexey A. Kovalev, Leonid P. Pryadko, IEEE

Published Jan 1, 2016• 2 citations
OpenAlex

Abstract

The problem of finding code distance has been long studied for the generic\nensembles of linear codes and led to several algorithms that substantially\nreduce exponential complexity of this task. However, no asymptotic complexity\nbounds are known for distance verification in other ensembles of linear codes.\nOur goal is to re-design the existing generic algorithms of distance\nverification and derive their complexity for LDPC codes. We obtain new\ncomplexity bounds with provable performance expressed in terms of the\nerasure-correcting thresholds of long LDPC codes. These bounds exponentially\nreduce complexity estimates known for linear codes.

Related papers

Distance verification for LDPC codes

Ilya I. Dumer, Alexey A. Kovalev, Leonid P. Pryadko

The problem of finding code distance has been long studied for the generic ensembles of linear codes and led to several algorithms that substantially reduce exponential complexity of this task. However, no asymptotic complexity bounds are known for distance verification in other ensembles of linear codes. Our goal is to re-design the existing generic algorithms of distance verification and derive their complexity for LDPC codes. We obtain new complexity bounds with provable performance expressed in terms of the erasure-correcting thresholds of long LDPC codes. These bounds exponentially reduce complexity estimates known for linear codes.

arXiv:1605.02410•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2016•1 citation

Distance verification for classical and quantum LDPC codes

Ilya I. Dumer, Alexey A. Kovalev, Leonid P. Pryadko

The techniques of distance verification known for general linear codes are re-applied to quantum stabilizer codes. Then distance verification is addressed for classical and quantum LDPC codes. New complexity bounds for distance verification with provable performance are derived using the average weight spectra of the ensembles of LDPC codes. These bounds are expressed in terms of the erasure-correcting capacity of the corresponding ensemble. We also present a new irreducible-cluster technique that can be applied to any LDPC code and takes advantage of parity-checks' sparsity for both classical and quantum LDPC codes. This technique reduces complexity exponents of all existing deterministic techniques designed for generic stabilizer codes with small relative distances, which also include all known families of quantum LDPC codes.

arXiv:1611.07164•Nov 22, 2016•0 citations

Distance Verification for Classical and Quantum LDPC Codes

Ilya I. Dumer, Alexey A. Kovalev, Leonid P. Pryadko

The techniques of distance verification known for general linear codes are first applied to the quantum stabilizer codes. Then, these techniques are considered for classical and quantum (stabilizer) low-density-parity-check (LDPC) codes. New complexity bounds for distance verification with provable performance are derived using the average weight spectra of the ensembles of LDPC codes. These bounds are expressed in terms of the erasure-correcting capacity of the corresponding ensemble. We also present a new irreducible-cluster technique that can be applied to any LDPC code and takes advantage of parity-checks' sparsity for both the classical and quantum LDPC codes. This technique reduces complexity exponents of all existing deterministic techniques designed for generic stabilizer codes with small relative distances, which also include all known families of the quantum stabilizer LDPC codes.

IEEE Transactions on Information Theory•Mar 31, 2017•13 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

Searching the minimum distances of LDPC codes

Yang Xiao, Kiseon Kim

To find the minimum distance computation of LDPC codes is a NP problem, there has been no simple way to obtain the minimum distance of LDPC codes because of the code length being very long. To provide a solution to deal with this hard problem, this paper develops an algorithm to estimate the weights and distance of LDPC codes based on generator matrices. The paper establishes the upper bounds of weights and distances of LDPC codes by using the vectors of generator matrices, which is different from the existed probabilistic 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 can obtain some LDPC codes of great distances and being free girth 4. Simulations verify the algorithms to be valid.

IET International Conference on Wireless, Mobile and Multimedia Networks (ICWMMN)•Jan 1, 2008•3 citations

Low-complexity error correction of Hamming-code-based LDPC codes

Victor Zyablov, Rolf Johannesson, Matea Lončar

Ensembles of binary random LDPC block codes constructed using Hamming codes as constituent codes are studied for communicating over the binary symmetric channel. These ensembles are known to contain codes that asymptotically almost meet the Gilbert-Varshamov bound. It is shown that in these ensembles there exist codes which can correct a number of errors that grows linearly with the code length, when decoded with a low-complexity iterative decoder, which requires a number of iterations that is a logarithmic function of the code length. The results are supported by numerical examples, for various choices of the code parameters.

Problems of Information Transmission•Jun 1, 2009•17 citations
The problem of finding code distance has been long studied for the generic\nensembles of linear codes and led to several algorithms that substantially\nreduce exponential complexity of this task. However, no asymptotic complexity\nbounds are known for distance verification in other ensembles of linear codes.\nOur goal is to re-design the existing generic algorithms of distance\nverification and derive their complexity for LDPC codes. We obtain new\ncomplexity bounds with provable performance expressed in terms of the\nerasure-correcting thresholds of long LDPC codes. These bounds exponentially\nreduce complexity estimates known for linear codes.
The problem of finding code distance has been long studied for the generic ensembles of linear codes and led to several algorithms that substantially reduce exponential complexity of this task. However, no asymptotic complexity bounds are known for distance verification in other ensembles of linear codes. Our goal is to re-design the existing generic algorithms of distance verification and derive their complexity for LDPC codes. We obtain new complexity bounds with provable performance expressed in terms of the erasure-correcting thresholds of long LDPC codes. These bounds exponentially reduce complexity estimates known for linear codes.
The techniques of distance verification known for general linear codes are re-applied to quantum stabilizer codes. Then distance verification is addressed for classical and quantum LDPC codes. New complexity bounds for distance verification with provable performance are derived using the average weight spectra of the ensembles of LDPC codes. These bounds are expressed in terms of the erasure-correcting capacity of the corresponding ensemble. We also present a new irreducible-cluster technique that can be applied to any LDPC code and takes advantage of parity-checks' sparsity for both classical and quantum LDPC codes. This technique reduces complexity exponents of all existing deterministic techniques designed for generic stabilizer codes with small relative distances, which also include all known families of quantum LDPC codes.
The techniques of distance verification known for general linear codes are first applied to the quantum stabilizer codes. Then, these techniques are considered for classical and quantum (stabilizer) low-density-parity-check (LDPC) codes. New complexity bounds for distance verification with provable performance are derived using the average weight spectra of the ensembles of LDPC codes. These bounds are expressed in terms of the erasure-correcting capacity of the corresponding ensemble. We also present a new irreducible-cluster technique that can be applied to any LDPC code and takes advantage of parity-checks' sparsity for both the classical and quantum LDPC codes. This technique reduces complexity exponents of all existing deterministic techniques designed for generic stabilizer codes with small relative distances, which also include all known families of the quantum stabilizer 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.
To find the minimum distance computation of LDPC codes is a NP problem, there has been no simple way to obtain the minimum distance of LDPC codes because of the code length being very long. To provide a solution to deal with this hard problem, this paper develops an algorithm to estimate the weights and distance of LDPC codes based on generator matrices. The paper establishes the upper bounds of weights and distances of LDPC codes by using the vectors of generator matrices, which is different from the existed probabilistic 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 can obtain some LDPC codes of great distances and being free girth 4. Simulations verify the algorithms to be valid.
Ensembles of binary random LDPC block codes constructed using Hamming codes as constituent codes are studied for communicating over the binary symmetric channel. These ensembles are known to contain codes that asymptotically almost meet the Gilbert-Varshamov bound. It is shown that in these ensembles there exist codes which can correct a number of errors that grows linearly with the code length, when decoded with a low-complexity iterative decoder, which requires a number of iterations that is a logarithmic function of the code length. The results are supported by numerical examples, for various choices of the code parameters.