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

PRIKLADNAYa DISKRETNAYa MATEMATIKA

Weight distribution of low-density periodic random errors and their correcting codes with error decoding probability

Letminthang Haokip, Pankaj Kumar Das

Published Jan 1, 2023• 0 citations
Publisher

Abstract

We present weight distribution of low-density periodic random errors in the space of all q-ary n-tuples along with the average Hamming weight of the error set. We also provide necessary and sufficient conditions for the existence of linear codes correcting such error pattern. Examples of such codes are given. Finally, probability of decoding error of such codes over a binary symmetric channel is derived.

DOI
10.17223/20710410/62/8

Related papers

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

On the asymptotic performance of low-complexity decoded LDPC codes with constituent hamming codes

Victor Zyablov, Maja Lončar, Rolf Johannesson +1 more

Hamming code-based LDPC (H-LDPC) block codes are obtained by replacing single parity-check codes in Gallager’s LDPC codes with Hamming constituent codes. This paper investigates the asymptotic error-correcting capabilities of ensembles of random H-LDPC codes, used over the binary symmetric channel and decoded with a low-complexity hard-decision iterative decoding algorithm. The number of required decoding iterations is a logarithmic function of the code length. It is shown that there exist H-LDPC codes for which such an iterative decoding corrects any error pattern with a number of errors that grows linearly with the code length. For various choices of code parameters the results are supported by numerical examples.

International Symposium on Turbo Codes and Iterative Information Processing•Sep 1, 2008•5 citations

Bounds on the decoding error probability of binary linear codes via their spectra

Gregory Poltyrev

Bounds on the error probability of maximum likelihood decoding of a binary linear code are considered. The bounds derived use the weight spectrum of the code and they are tighter than the conventional union bound in the case of large noise in the channel. The bounds derived are applied to a code with an average spectrum, and the result is compared to the random coding exponent. The author shows that the bound considered for the binary symmetrical channel case coincides asymptotically with the random coding bound. For the case of AWGN channel the author shows that Berlekamp's (1980) tangential bound can be improved, but even this improved bound does not coincide with the random coding bound, although it can be very close to it.>

IEEE Transactions on Information Theory•Jul 1, 1994•230 citations

Bounds on the maximum likelihood decoding error probability of low density parity check codes

G. Miller, D. Burshtein

We derive bounds on the error probability of ML decoded LDPC (low density parity check) codes, for any binary-input symmetric-output channel. For appropriately chosen ensembles of LDPC codes, reliable communication is possible up to channel capacity. The lower and upper bounds coincide asymptotically, indicating a polynomially decreasing ensemble averaged error probability. For ensembles with suitably chosen parameters, the error probability of almost all codes is exponentially decreasing. Furthermore, the error exponent can be set arbitrarily close to the standard random coding exponent.

IEEE International Symposium on Information Theory (ISIT)•Nov 7, 2002•7 citations

Bounds on the undetected error probabilities of linear codes for both error correction and detection

Mao‐Chao Lin

The author investigates the (n, k, d>or=2t+1) binary linear codes, which are used for correcting error patterns of weight at most t and detecting other error patterns over a binary symmetric channel. In particular, for t=1, it is shown that there exists one code whose probability of undetected errors is upper-bounded by (n+1) (2/sup n-k/-n)/sup -1/ when used on a binary symmetric channel with transition probability less than 2/n.>

IEEE Transactions on Information Theory•Jan 1, 1990•0 citations

Bounds on the maximum-likelihood decoding error probability of low-density parity-check codes

G. Miller, David Burshtein

We derive both upper and lower bounds on the decoding error probability of maximum-likelihood (ML) decoded low-density parity-check (LDPC) codes. The results hold for any binary-input symmetric-output channel. Our results indicate that for various appropriately chosen ensembles of LDPC codes, reliable communication is possible up to channel capacity. However, the ensemble averaged decoding error probability decreases polynomially, and not exponentially. The lower and upper bounds coincide asymptotically, thus showing the tightness of the bounds. However, for ensembles with suitably chosen parameters, the error probability of almost all codes is exponentially decreasing, with an error exponent that can be set arbitrarily close to the standard random coding exponent.

IEEE Transactions on Information Theory•Jan 1, 2001•157 citations
We present weight distribution of low-density periodic random errors in the space of all q-ary n-tuples along with the average Hamming weight of the error set. We also provide necessary and sufficient conditions for the existence of linear codes correcting such error pattern. Examples of such codes are given. Finally, probability of decoding error of such codes over a binary symmetric channel is derived.
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.
Hamming code-based LDPC (H-LDPC) block codes are obtained by replacing single parity-check codes in Gallager’s LDPC codes with Hamming constituent codes. This paper investigates the asymptotic error-correcting capabilities of ensembles of random H-LDPC codes, used over the binary symmetric channel and decoded with a low-complexity hard-decision iterative decoding algorithm. The number of required decoding iterations is a logarithmic function of the code length. It is shown that there exist H-LDPC codes for which such an iterative decoding corrects any error pattern with a number of errors that grows linearly with the code length. For various choices of code parameters the results are supported by numerical examples.
Bounds on the error probability of maximum likelihood decoding of a binary linear code are considered. The bounds derived use the weight spectrum of the code and they are tighter than the conventional union bound in the case of large noise in the channel. The bounds derived are applied to a code with an average spectrum, and the result is compared to the random coding exponent. The author shows that the bound considered for the binary symmetrical channel case coincides asymptotically with the random coding bound. For the case of AWGN channel the author shows that Berlekamp's (1980) tangential bound can be improved, but even this improved bound does not coincide with the random coding bound, although it can be very close to it.>
We derive bounds on the error probability of ML decoded LDPC (low density parity check) codes, for any binary-input symmetric-output channel. For appropriately chosen ensembles of LDPC codes, reliable communication is possible up to channel capacity. The lower and upper bounds coincide asymptotically, indicating a polynomially decreasing ensemble averaged error probability. For ensembles with suitably chosen parameters, the error probability of almost all codes is exponentially decreasing. Furthermore, the error exponent can be set arbitrarily close to the standard random coding exponent.
We derive both upper and lower bounds on the decoding error probability of maximum-likelihood (ML) decoded low-density parity-check (LDPC) codes. The results hold for any binary-input symmetric-output channel. Our results indicate that for various appropriately chosen ensembles of LDPC codes, reliable communication is possible up to channel capacity. However, the ensemble averaged decoding error probability decreases polynomially, and not exponentially. The lower and upper bounds coincide asymptotically, thus showing the tightness of the bounds. However, for ensembles with suitably chosen parameters, the error probability of almost all codes is exponentially decreasing, with an error exponent that can be set arbitrarily close to the standard random coding exponent.