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

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

Chin Hei Chan

Published Sep 4, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2609.04688

Related papers

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

The Decoding Error Probability of Linear Codes Over the Erasure Channel

Linzhi Shen, Fang‐Wei Fu

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.

IEEE Transactions on Information Theory•Jul 1, 2019•9 citations

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

On Approximation, Bounding & Exact Calculation of Block Error Probability for Random Code Ensembles

Ralf R. Müller

This paper presents a method to calculate the exact average block error probability of some random code ensembles under maximum-likelihood decoding. The proposed method is applicable to various channels and ensembles. The focus is on both spherical and Gaussian random codes on the additive white Gaussian noise channel as well as binary random codes on both the binary symmetric channel and the binary erasure channel. While for the uniform spherical ensemble Shannon, in 1959, argued with solid angles in $N$-dimensional space, the presented approach projects the problem into two dimensions and applies standard trigonometry. This simplifies the derivation and also allows for the analysis of the independent identically distributed (i.i.d.) Gaussian ensemble which turns out to perform better for short blocklengths and high rates. Moreover, a new lower bound on the average block error probability of the uniform spherical ensemble is found. For codes with more than three codewords, it is tighter than the sphere packing bound, but requires exactly the same computing effort. Furthermore, tight approximations are proposed to simplify the computation of both the exact average error probability and the two bounds. For the binary symmetric channel and the binary erasure channel, bounds on the average block error probability for i.i.d.\ random coding are derived and compared to the exact calculations.

arXiv:2003.06807•Mar 15, 2020•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

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
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.
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.
This paper presents a method to calculate the exact average block error probability of some random code ensembles under maximum-likelihood decoding. The proposed method is applicable to various channels and ensembles. The focus is on both spherical and Gaussian random codes on the additive white Gaussian noise channel as well as binary random codes on both the binary symmetric channel and the binary erasure channel. While for the uniform spherical ensemble Shannon, in 1959, argued with solid angles in NNN-dimensional space, the presented approach projects the problem into two dimensions and applies standard trigonometry. This simplifies the derivation and also allows for the analysis of the independent identically distributed (i.i.d.) Gaussian ensemble which turns out to perform better for short blocklengths and high rates. Moreover, a new lower bound on the average block error probability of the uniform spherical ensemble is found. For codes with more than three codewords, it is tighter than the sphere packing bound, but requires exactly the same computing effort. Furthermore, tight approximations are proposed to simplify the computation of both the exact average error probability and the two bounds. For the binary symmetric channel and the binary erasure channel, bounds on the average block error probability for i.i.d.\ random coding are derived and compared to the exact calculations.
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.
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.