© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

Journal of Communications Technology and Electronics

Estimating the fraction of erasure patterns correctable by linear codes

Valentin B. Afanassiev, Alexander A. Davydov, D. K. Zigangirov

Published Jun 1, 2017• 0 citations

Abstract

The conditional probability (fraction) of the successful decoding of erasure patterns of high (greater than the code distance) weights is investigated for linear codes with the partially known or unknown weight spectra of code words. The estimated conditional probabilities and the methods used to calculate them refer to arbitrary binary linear codes and binary Hamming, Panchenko, and Bose–Chaudhuri–Hocquenghem (BCH) codes, including their extended and shortened forms. Error detection probabilities are estimated under erasure-correction conditions. The product-code decoding algorithms involving the correction of high weight erasures by means of component Hamming, Panchenko, and BCH codes are proposed, and the upper estimate of decoding failure probability is presented.

DOI: 10.1134/s106422691706002x

Related papers

On the Error Rate of Binary BCH Codes under Error-and-erasure Decoding

Sisi Miao, Jonathan Mandelbaum, Holger Jäkel +1 more

Determining the exact decoding error probability of linear block codes is an interesting problem. For binary BCH codes, McEliece derived methods to estimate the error probability of a simple bounded distance decoding (BDD) for BCH codes. However, BDD falls short in many applications. In this work, we consider error-and-erasure decoding and its improved variants. We derive closed-form expressions for their error probabilities and validate them through simulations. Then, we illustrate their use in assessing concatenated coding schemes.

arXiv:2509.24794•Sep 29, 2025•0 citations

On the Decoder Error Probability for BCH Codes

Mingoo Kim, Jaehong Lee

A general formula is derived to obtain the decoder error probability for linear block codes. A bounded-distance decoder is assumed. It is shown that the decoder error probability for binary linear codes becomes a constant value if the weight distribution of the code is binomial-like. An exact decoder error probability for Reed-Solomon codes is obtained from this formula. Bounds on the decoder error probability for binary BCH codes are derived because the weight distributions of binary BCH codes are unknown except for some special codes. It is also shown that the decoder error probability approaches to (formula) rapidly in t-errors correcting (n, k) binary primitive BCH codes as code length n increases and the weight of word h approaches to n2.

International Symposium on Information Theory and its Applications•Jan 1, 1994•1 citation

Concerning a bound on undetected error probability (Corresp.)

S. Leung-Yan-Cheong, Martin E. Hellman

In the past, it has generally been assumed that the probability of undetected error for an(n,k)block code, used solely for error detection on a binary symmetric channel, is upperbounded by2^{-(n-k)}. In this correspondence, it is shown that Hamming codes do indeed obey this bound, but that the bound is violated by some more general codes. Examples of linear, cyclic, and Bose-Chaudhuri-Hocquenghem (BCH) codes which do not obey the bound are given.

IEEE Transactions on Information Theory•Mar 1, 1976•49 citations

Concerning a bound on undetected error probability

Kamal Gupta

In the past, it has generally been assumed that the probability of undetected error for an (n,k) block code, used solely for error detection on a binary symmetric channel, is upper bounded by 2-(n-k). In this correspondence, it is shown that Hamming codes do indeed obey this bound, but that the bound is violated by some more general codes. Examples of linear, cyclic, and Bose-Chaudhuri-Hocquenghem (BCH) codes which do not obey the bound are given.

International Journal of Statistics and Applied Mathematics•Jan 1, 2017•1 citation

Erasure correction by low-density codes

Victor Zyablov, Pavel S. Rybin

We generalize the method for computing the number of errors correctable by a low-density parity-check (LDPC) code in a binary symmetric channel, which was proposed by V.V. Zyablov and M.S. Pinsker in 1975. This method is for the first time applied for computing the fraction of guaranteed correctable erasures for an LDPC code with a given constituent code used in an erasure channel. Unlike previously known combinatorial methods for computing the fraction of correctable erasures, this method is based on the theory of generating functions, which allows us to obtain more precise results and unify the computation method for various constituent codes of a regular LDPC code. We also show that there exist an LDPC code with a given constituent code which, when decoded with a low-complexity iterative algorithm, is capable of correcting any erasure pattern with a number of erasures that grows linearly with the code length. The number of decoding iterations, required to correct the erasures, is a logarithmic function of the code length. We make comparative analysis of various numerical results obtained by various computation methods for certain parameters of an LDPC code with a constituent single-parity-check or Hamming code.

Problems of Information Transmission•Sep 1, 2009•6 citations

Good error-detection codes satisfying the expurgated bound

Takeshi Hashimoto

A q-ary (n, k) linear code is said to be proper if, as an error-detection code, the probability of undetectable error P/sub ud/ satisfies P/sub ud//spl les/q/sup -(n-k)/ for completely symmetric channels. We show that a proper code, as an error-correction code, satisfies the expurgated bound on the decoding error probability for a class of channels with the associated Bhattacharyya distance being completely symmetric. Known results on the undetectable error probability then immediately imply that the expurgated exponent is satisfied exactly by, for example, all the binary perfect codes, binary first-order Reed-Muller codes, binary (extended) Hamming code, binary 2-error correcting primitive BCH code, and all the maximum distance separable (MDS) codes, and asymptotically by some class of the binary t-error-correcting primitive BCH codes.>

IEEE Transactions on Information Theory•Jan 1, 1995•5 citations

The conditional probability (fraction) of the successful decoding of erasure patterns of high (greater than the code distance) weights is investigated for linear codes with the partially known or unknown weight spectra of code words. The estimated conditional probabilities and the methods used to calculate them refer to arbitrary binary linear codes and binary Hamming, Panchenko, and Bose–Chaudhuri–Hocquenghem (BCH) codes, including their extended and shortened forms. Error detection probabilities are estimated under erasure-correction conditions. The product-code decoding algorithms involving the correction of high weight erasures by means of component Hamming, Panchenko, and BCH codes are proposed, and the upper estimate of decoding failure probability is presented.

Determining the exact decoding error probability of linear block codes is an interesting problem. For binary BCH codes, McEliece derived methods to estimate the error probability of a simple bounded distance decoding (BDD) for BCH codes. However, BDD falls short in many applications. In this work, we consider error-and-erasure decoding and its improved variants. We derive closed-form expressions for their error probabilities and validate them through simulations. Then, we illustrate their use in assessing concatenated coding schemes.

A general formula is derived to obtain the decoder error probability for linear block codes. A bounded-distance decoder is assumed. It is shown that the decoder error probability for binary linear codes becomes a constant value if the weight distribution of the code is binomial-like. An exact decoder error probability for Reed-Solomon codes is obtained from this formula. Bounds on the decoder error probability for binary BCH codes are derived because the weight distributions of binary BCH codes are unknown except for some special codes. It is also shown that the decoder error probability approaches to (formula) rapidly in t-errors correcting (n, k) binary primitive BCH codes as code length n increases and the weight of word h approaches to n2.

We generalize the method for computing the number of errors correctable by a low-density parity-check (LDPC) code in a binary symmetric channel, which was proposed by V.V. Zyablov and M.S. Pinsker in 1975. This method is for the first time applied for computing the fraction of guaranteed correctable erasures for an LDPC code with a given constituent code used in an erasure channel. Unlike previously known combinatorial methods for computing the fraction of correctable erasures, this method is based on the theory of generating functions, which allows us to obtain more precise results and unify the computation method for various constituent codes of a regular LDPC code. We also show that there exist an LDPC code with a given constituent code which, when decoded with a low-complexity iterative algorithm, is capable of correcting any erasure pattern with a number of erasures that grows linearly with the code length. The number of decoding iterations, required to correct the erasures, is a logarithmic function of the code length. We make comparative analysis of various numerical results obtained by various computation methods for certain parameters of an LDPC code with a constituent single-parity-check or Hamming code.

A q-ary (n, k) linear code is said to be proper if, as an error-detection code, the probability of undetectable error P/sub ud/ satisfies P/sub ud//spl les/q/sup -(n-k)/ for completely symmetric channels. We show that a proper code, as an error-correction code, satisfies the expurgated bound on the decoding error probability for a class of channels with the associated Bhattacharyya distance being completely symmetric. Known results on the undetectable error probability then immediately imply that the expurgated exponent is satisfied exactly by, for example, all the binary perfect codes, binary first-order Reed-Muller codes, binary (extended) Hamming code, binary 2-error correcting primitive BCH code, and all the maximum distance separable (MDS) codes, and asymptotically by some class of the binary t-error-correcting primitive BCH codes.>