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 Transactions on Information Theory

The Decoding Error Probability of Linear Codes Over the Erasure Channel

Linzhi Shen, Fang‐Wei Fu

Published Jul 1, 2019• 9 citations
Publisher

Abstract

In this paper, we study the decoding error probability of linear codes over the erasure channel under the list decoding. The notion of the qℓ-incorrigible sets of linear codes is introduced to characterize its decoding error probability under the list decoding or the maximum likelihood decoding. By calculating the qℓ-incorrigible set distributions, the decoding error probability of a linear code over the erasure channel under the list decoding or the maximum likelihood decoding is expressed by its support weight distributions. For the ensemble of all [n,k] linear codes, the average decoding error probability under the maximum likelihood decoding and the average unsuccessful decoding probability under unambiguous decoding are determined. Furthermore, the error exponent of the average unsuccessful decoding probability under the unambiguous decoding is determined for the ensemble of all [n,nR] linear codes.

DOI
10.1109/tit.2019.2926075

Related papers

The list decoding error probability of linear codes over the erasure channel

Linzhi Shen, Fang‐Wei Fu

In this paper, we study the list decoding error probability of a linear code over the erasure channel. The notion of L-incorrigible sets of a linear code is introduced to characterize its performance under list decoding. The L-incorrigible set distribution of a linear code can also be used to completely determine its decoding error probability under maximum likelihood decoding over the erasure channel. Furthermore, we show that the L-incorrigible set distribution of a linear code can be determined by its support weight distribution. Finally, the error exponent of the unsuccessful decoding probability under optimal decoding for the ensemble of all [n, nR] linear codes is determined.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2015•1 citation

Decoding Error Probability of the Random Code Ensemble over the Erasure Channel

Chin Hei Chan

In this paper, we provide explicit formulas for the average decoding error probabilities of the ensemble of all $(n,M)_q$ codes over the erasure channel under unambiguous, list and maximum-likelihood decoding principles. Moreover, we derive the asymptotic error exponents for the ensemble of all $(n,q^{Rn})_q$ codes.

arXiv:2609.04688•Sep 4, 2026•0 citations

Decoding error probability of random parity-check matrix ensemble over the erasure channel

Chin Hei Chan, Fang‐Wei Fu, Maosheng Xiong

Abstract In this paper we carry out an in-depth study on the average decoding error probability of the random parity-check matrix ensemble over the erasure channel under three decoding principles, namely unambiguous decoding, maximum likelihood decoding and list decoding. We obtain explicit formulas for the average decoding error probabilities of the random parity-check matrix ensemble under these three decoding principles and compute the error exponents. Moreover, for unambiguous decoding, we compute the variance of the decoding error probability of the random parity-check matrix ensemble and the error exponent of the variance, which implies a strong concentration result, that is, roughly speaking, the ratio of the decoding error probability of a random linear code in the ensemble and the average decoding error probability of the ensemble converges to 1 with high probability when the code length goes to infinity.

Designs Codes and Cryptography•Oct 16, 2024•0 citations

Incorrigible set distributions and unsuccessful decoding probability of linear codes

Yong Jiang, Shu‐Tao Xia, Xinji Liu +1 more

On a binary erasure channel (BEC) with erasing probability e, the performance of a binary linear code is determined by the incorrigible sets of the code. The incorrigible set distribution (ISD) {Ii}i=0nenumerates the number of incorrigible sets with size i of the code. The probability of unsuccessful decoding under optimal decoding for the code could be formulated by the ISD and ∈. In this paper, we determine the ISDs for the Simplex codes, the Hamming codes, the first order Reed-Muller codes, and the extended Hamming codes, which are some Reed-Muller codes or their shortening or puncturing versions. Then, we show that the probability of unsuccessful decoding under optimal decoding for any binary linear code is monotonously non-decreasing on ∈ in the interval [0,1].

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

Bounds on Maximum Likelihood Decoding Performance for Linear Codes at Low Rates

Hideki Yagi, H. Vincent Poor

For a given linear code (ensemble), upper bounds on the error probability under maximum likelihood decoding are investigated at low rates. A class of symmetric memoryless channels suitable for Bhattacharyya-type bounds, which are particularly of importance at low rates, is introduced. Over a symmetric channel, a lower bound on the error exponent is derived for a given linear code. A sufficient condition for achieving the expurgated exponent, which is the best among known error exponents at low rates, within a fixed discrepancy is given. Over a general discrete memoryless channel, the same analysis provides a lower bound on the average error exponent for an ensemble of coset codes generated by a given linear code. The bounding technique is extended to the case of generalized maximum likelihood decoding with erasure and list- decoding options.

IEEE Transactions on Information Theory•Mar 12, 2013•2 citations

Average Bit Erasure Probability of Regular LDPC Code Ensembles under MAP Decoding over BEC

Takayuki Itsui, K. KASAI, Ryoji Ikegaya +2 more

The average bit erasure probability of a binary linear code ensemble under maximum a-posteriori probability (MAP) decoding over binary erasure channel (BEC) can be calculated with the average support weight distribution of the ensemble via the EXIT function and the shortened information function. In this paper, we formulate the relationship between the average bit erasure probability under MAP decoding over BEC and the average support weight distribution for a binary linear code ensemble. Then, we formulate the average support weight distribution and the average bit erasure probability under MAP decoding over BEC for regular LDPC code ensembles.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Sep 1, 2007•0 citations
In this paper, we study the decoding error probability of linear codes over the erasure channel under the list decoding. The notion of the qℓ-incorrigible sets of linear codes is introduced to characterize its decoding error probability under the list decoding or the maximum likelihood decoding. By calculating the qℓ-incorrigible set distributions, the decoding error probability of a linear code over the erasure channel under the list decoding or the maximum likelihood decoding is expressed by its support weight distributions. For the ensemble of all [n,k] linear codes, the average decoding error probability under the maximum likelihood decoding and the average unsuccessful decoding probability under unambiguous decoding are determined. Furthermore, the error exponent of the average unsuccessful decoding probability under the unambiguous decoding is determined for the ensemble of all [n,nR] linear codes.
In this paper, we study the list decoding error probability of a linear code over the erasure channel. The notion of L-incorrigible sets of a linear code is introduced to characterize its performance under list decoding. The L-incorrigible set distribution of a linear code can also be used to completely determine its decoding error probability under maximum likelihood decoding over the erasure channel. Furthermore, we show that the L-incorrigible set distribution of a linear code can be determined by its support weight distribution. Finally, the error exponent of the unsuccessful decoding probability under optimal decoding for the ensemble of all [n, nR] linear codes is determined.
In this paper, we provide explicit formulas for the average decoding error probabilities of the ensemble of all (n,M)q(n,M)_q(n,M)q​ codes over the erasure channel under unambiguous, list and maximum-likelihood decoding principles. Moreover, we derive the asymptotic error exponents for the ensemble of all (n,qRn)q(n,q^{Rn})_q(n,qRn)q​ codes.
Abstract In this paper we carry out an in-depth study on the average decoding error probability of the random parity-check matrix ensemble over the erasure channel under three decoding principles, namely unambiguous decoding, maximum likelihood decoding and list decoding. We obtain explicit formulas for the average decoding error probabilities of the random parity-check matrix ensemble under these three decoding principles and compute the error exponents. Moreover, for unambiguous decoding, we compute the variance of the decoding error probability of the random parity-check matrix ensemble and the error exponent of the variance, which implies a strong concentration result, that is, roughly speaking, the ratio of the decoding error probability of a random linear code in the ensemble and the average decoding error probability of the ensemble converges to 1 with high probability when the code length goes to infinity.
On a binary erasure channel (BEC) with erasing probability e, the performance of a binary linear code is determined by the incorrigible sets of the code. The incorrigible set distribution (ISD) {Ii}i=0nenumerates the number of incorrigible sets with size i of the code. The probability of unsuccessful decoding under optimal decoding for the code could be formulated by the ISD and ∈. In this paper, we determine the ISDs for the Simplex codes, the Hamming codes, the first order Reed-Muller codes, and the extended Hamming codes, which are some Reed-Muller codes or their shortening or puncturing versions. Then, we show that the probability of unsuccessful decoding under optimal decoding for any binary linear code is monotonously non-decreasing on ∈ in the interval [0,1].
For a given linear code (ensemble), upper bounds on the error probability under maximum likelihood decoding are investigated at low rates. A class of symmetric memoryless channels suitable for Bhattacharyya-type bounds, which are particularly of importance at low rates, is introduced. Over a symmetric channel, a lower bound on the error exponent is derived for a given linear code. A sufficient condition for achieving the expurgated exponent, which is the best among known error exponents at low rates, within a fixed discrepancy is given. Over a general discrete memoryless channel, the same analysis provides a lower bound on the average error exponent for an ensemble of coset codes generated by a given linear code. The bounding technique is extended to the case of generalized maximum likelihood decoding with erasure and list- decoding options.
The average bit erasure probability of a binary linear code ensemble under maximum a-posteriori probability (MAP) decoding over binary erasure channel (BEC) can be calculated with the average support weight distribution of the ensemble via the EXIT function and the shortened information function. In this paper, we formulate the relationship between the average bit erasure probability under MAP decoding over BEC and the average support weight distribution for a binary linear code ensemble. Then, we formulate the average support weight distribution and the average bit erasure probability under MAP decoding over BEC for regular LDPC code ensembles.