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

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.

Introduction

Background

In digital communication, it is common that messages transmitted through a public channel may be distorted by the channel noise. The theory of error-correcting codes is the study of mechanisms to cope with this problem. This is an important research area with many applications in modern life. For example, error-correcting codes are widely employed in cell phones to correct errors arising from fading noise during high frequency radio transmission. One of the major challenges in coding theory remains to construct new error-correcting codes with good properties and to study their decoding and encoding algorithms.

In a binary erasure channel (BEC), a binary symbol is either received correctly or totally erased with probability $\epsilon$. The concept of BEC was first introduced by Elias in 1955 [3]. Together with the binary symmetric channel (BSC), they are frequently used in coding theory and information theory because they are among the simplest channel models, and many problems in communication theory can be reduced to problems in a BEC. Here we consider more generally a q-ary erasure channel in which a q-ary symbol is either received correctly, or totally erased with probability $\epsilon$.

The problem of decoding linear codes over the erasure channel has received renewed attention in recent years due to their wide application in the internet and the distributed storage system in analyzing random packet losses [2, 11, 12]. Three important decoding principles, namely unambiguous decoding, maximum likelihood decoding and list decoding, were studied in recent years for linear codes over the erasure channel, the corresponding decoding error probabilities under these principles were also investigated (see [5, 9, 14, 17] and reference therein).

In particular in [14], upon improving previous results, the authors provided a detailed study on the decoding error probabilities of a general q-ary linear code over the erasure channel under the three decoding principles. Via the notion of $q^{\ell }$-incorrigible sets for linear codes, they showed that all these decoding error probabilities can be expressed explicitly by the r-th support weight distribution of the linear codes. As applications they obtained explicit formulas of the decoding error probabilities for some of the most interesting linear codes such as MDS codes, the binary Golay code, the simplex codes and the first-order Reed-Muller codes etc. where the r-support weight distributions were known. They also computed the average decoding error probabilities of a random ${[n,k]}_q$ code over the erasure channel and obtained the error exponent of a random ${[n,nR]}_q$ code ($0<R<1$) under unambiguous decoding. The error exponents of a random [n, nR] code under list and maximum likelihood decoding were obtained in [18].

Statement of the main results

In this paper we consider a different code ensemble, namely the random parity-check matrix ensemble${\mathcal{R}}_{m,n}$, that is, the set of all $m\times n$ matrices over ${\mathbb{F}}_q$ endowed with uniform probability, each of which is associated with a parity-check code as follows: for each $H\in {\mathcal{R}}_{m,n}$, the corresponding parity-check code $C_H$ is given by

1

$$\begin{array}{c}\hfill C_H=\left\{\mathbf{x},\in ,{\mathbb{F}}_q^n,:,H,{\mathbf{x}}^T,=,\mathbf{0}\right\}.\end{array}$$Here boldface letters such as $\mathbf{x}$ denote row vectors.

The ensemble ${\mathcal{R}}_{m,n}$ has been studied for a long time and many strong results have been obtained. For example, in the classical work of Gallager [7], an upper bound of the average number of codewords of a given weight in ${\mathcal{R}}_{m,n}$ was obtained, from which information about the minimum-distance distribution of ${\mathcal{R}}_{m,n}$ can be derived (see [7, Theorems 2.1$-$2.2]); in [1] (see also [4]) union bounds on the block erasure probabilities of the ensemble ${\mathcal{R}}_{m,n}$ was obtained under the maximum likelihood decoding (see [1, 4]). More recently, the undetected error probability of the ensemble ${\mathcal{R}}_{m,n}$ was studied in the binary symmetric channel by Wadayama [16] (i.e. $q=2$), and some bounds on the error probability under the maximum likelihood decoding principle were obtained in the q-ary erasure channel [6, 10]. It is easy to see that ${\mathcal{R}}_{m,n}$ contains all linear codes in the random ${[n,n-m]}_q$ code ensemble considered in [14], but these two ensembles are different for two reasons: first, in the random ${[n,k]}_q$ code ensemble considered in [14], each ${[n,k]}_q$ code is counted exactly once, while in ${\mathcal{R}}_{m,n}$ each code is counted with some multiplicity as different choices for the matrix H may give rise to the same code; second, some codes in ${\mathcal{R}}_{m,n}$ may have rates strictly larger than $1-\frac{m}{n}$ as the rows of H may not be linearly independent.

It is conceivable that most of the codes in ${\mathcal{R}}_{m,n}$ have rate $1-\frac{m}{n}$, and the average behavior of codes in ${\mathcal{R}}_{m,n}$ should be similar to that of the random ${[n,n-m]}_q$ code ensemble considered in [14]. We will show that this is indeed the case. Actually we will obtain stronger results, taking advantage of the fine algebraic structure of the ensemble ${\mathcal{R}}_{m,n}$, which may not be readily available in the random ${[n,k]}_q$ code ensemble. Such structure has been exploited in [16].

We first obtain explicit formulas for the average decoding error probability of the ensemble ${\mathcal{R}}_{m,n}$ over the erasure channel under the three different decoding principles. This is comparable to [14, Theorem 2] for the random ${[n,k]}_q$ code ensemble. Such formulas are useful as they allow explicit evaluations of the average decoding error probabilities for any given m and n, hence giving us a meaningful guidance as to what to expect for a good ${[n,n-m]}_q$ code over the erasure channel.

Theorem 1

Let ${\mathcal{R}}_{m,n}$ be the random matrix ensemble described above. Denote by the Gaussian q-binomial coefficient and denote

2

$$\begin{array}{c}\hfill {\psi }_m(i):=\prod _{k=0}^{i-1}(1-q^{k-m}),1\le i\le m.\end{array}$$

1. The average unsuccessful decoding probability of ${\mathcal{R}}_{m,n}$ under list decoding with list size $q^{\ell }$, where $\ell$ is a non-negative integer, is given by

   3

2. The average unsuccessful decoding probability of ${\mathcal{R}}_{m,n}$ under unambiguous decoding is given by

   4

   $$\begin{array}{c}\hfill P_{\text{ud}}({\mathcal{R}}_{m,n},\epsilon )=\sum _{i=1}^n\left(1,-,{\psi }_m,(i)\right)\left(\begin{array}{c}n\\ i\end{array}\right){\epsilon }^i{(1-\epsilon )}^{n-i};\end{array}$$

3. The average decoding error probability of ${\mathcal{R}}_{m,n}$ under maximum likelihood decoding is given by

   5

Remark 1

By using the elementary identitywe see that $P_{\text{ud}}({\mathcal{R}}_{m,n},\epsilon )=P_{\text{ld}}({\mathcal{R}}_{m,n},0,\epsilon )$. We list the formula for $P_{\text{ud}}({\mathcal{R}}_{m,n},\epsilon )$ here to emphasis the unambiguous decoding, which we will study further later.

Remark 2

In Table 1, we use Mathematica to compute the numerical values of $P_{\text{ud}}({\mathcal{R}}_{m,n},\epsilon ),P_{\text{mld}}({\mathcal{R}}_{m,n},\epsilon )$ and $P_{\text{ld}}({\mathcal{R}}_{m,n},\ell ,\epsilon )$ ($\ell =1,2$) for $m=50,n=100,q=2$ and $\epsilon =i\ast 0.05$ with $1\le i\le 10$. It can be seen that when $\epsilon$ is much smaller than the rate of the code which is $\frac{1}{2}$, the decoding error probabilities are all very small, in particular $P_{\text{mld}}({\mathcal{R}}_{m,n},\epsilon )$ and $P_{\text{ud}}({\mathcal{R}}_{m,n},\epsilon )$ are of the same magnitude, and $P_{\text{ld}}({\mathcal{R}}_{m,n},\ell ,\epsilon )$ decreases even much further as $\ell$ increases. The fact that these decoding error probabilities are small will be captured by the error exponents which we will study in Theorem 2.

Table 1. Decoding error probability for ${\mathcal{R}}_{m,n}$ where $m=50,n=100,q=2,ϵ=i\ast 0.05$ with $1\le i\le 10$

$ϵ$	$P_{\text{ud}}({\mathcal{R}}_{m,n},\epsilon )$	$P_{\text{ld}}({\mathcal{R}}_{m,n},1,\epsilon )$	$P_{\text{ld}}({\mathcal{R}}_{m,n},2,\epsilon )$	$P_{\text{mld}}({\mathcal{R}}_{m,n},\epsilon )$
0.05	$1.16\times {10}^{-13}$	$1.54\times {10}^{-25}$	$4.50\times {10}^{-35}$	$5.80\times {10}^{-14}$
0.10	$1.22\times {10}^{-11}$	$3.26\times {10}^{-20}$	$3.83\times {10}^{-25}$	$6.12\times {10}^{-12}$
0.15	$1.04\times {10}^{-9}$	$1.74\times {10}^{-15}$	$6.59\times {10}^{-18}$	$5.21\times {10}^{-10}$
0.20	$7.35\times {10}^{-8}$	$2.02\times {10}^{-11}$	$8.03\times {10}^{-13}$	$3.67\times {10}^{-8}$
0.25	$4.26\times {10}^{-6}$	$3.43\times {10}^{-8}$	$3.95\times {10}^{-9}$	$2.14\times {10}^{-6}$
0.30	$1.78\times {10}^{-4}$	$1.01\times {10}^{-5}$	$2.16\times {10}^{-6}$	$9.20\times {10}^{-5}$
0.35	$4.12\times {10}^{-3}$	$7.03\times {10}^{-4}$	$2.33\times {10}^{-4}$	$2.27\times {10}^{-3}$
0.40	$0.044797$	$0.015130$	$7.06\times {10}^{-3}$	$0.027361$
0.45	$0.226807$	$0.121768$	$0.074765$	$0.15745$
0.50	$0.580678$	$0.429632$	$0.328953$	$0.463703$

Remark 3

To make a comparison of Theorem 1 with corresponding results for the random ${[n,k]}_q$ code ensemble, we take $k=n-m$ and rewrite the explicit formulas obtained in [14, 18] as follows (see [14, Theorem 2] and [18, Section 6]): Denote by ${\mathcal{C}}_{m,n}$ the random ${[n,n-m]}_q$ code ensemble.

1. The average unsuccessful decoding probability of ${\mathcal{C}}_{m,n}$ under list decoding with list size $q^{\ell }$, where $\ell$ is a non-negative integer, is given by

   6

2. The average unsuccessful decoding probability of ${\mathcal{C}}_{m,n}$ under unambiguous decoding is given by

   7

   $$\begin{array}{c}\hfill P_{\text{ud}}({\mathcal{C}}_{m,n},\epsilon )=\sum _{i=1}^n\left(1,-,\frac{{\psi }_m(i)}{{\psi }_n(i)}\right)\left(\begin{array}{c}n\\ i\end{array}\right){\epsilon }^i{(1-\epsilon )}^{n-i};\end{array}$$

3. The average decoding error probability of ${\mathcal{C}}_{m,n}$ under maximum likelihood decoding is given by

   8

It is easy to check that for all indices i, j appearing in (3) and (6) we have $0<\frac{{\psi }_{n-m}(j)}{{\psi }_n(i)}<1$, this shows that$$\begin{array}{c}\hfill P_{\text{ld}}({\mathcal{C}}_{m,n},\ell ,\epsilon )<P_{\text{ld}}({\mathcal{R}}_{m,n},\ell ,\epsilon ).\end{array}$$Similarly we also have$$\begin{array}{c}\hfill P_{\text{ud}}({\mathcal{C}}_{m,n},\epsilon )<P_{\text{ud}}({\mathcal{R}}_{m,n},\epsilon ),P_{\text{mld}}({\mathcal{C}}_{m,n},\epsilon )<P_{\text{mld}}({\mathcal{R}}_{m,n},\epsilon ).\end{array}$$With this respect, the random code ensemble ${\mathcal{C}}_{m,n}$ behaves slightly better than ${\mathcal{R}}_{m,n}$ in terms of the average decoding error probabilities. On the other hand, the difference between these two ensembles seems to be rather small: we use Mathematica to compute the numerical values of the corresponding decoding error probabilities for ${\mathcal{C}}_{m,n}$ but these values appear exactly the same as those in Table 1. As it turns out, the difference of the decoding error probabilities between these two ensembles are much smaller in magnitude, as can be seen in Table 2.

Table 2. Difference of decoding error probability between ${\mathcal{R}}_{m,n}$ and ${\mathcal{C}}_{m,n}$ where $m=50,n=100,q=2,ϵ=i\ast 0.05$ with $1\le i\le 10$

$ϵ$	$P_{\text{ud}}({\mathcal{R}}_{m,n},\epsilon )$	$P_{\text{ld}}({\mathcal{R}}_{m,n},1,\epsilon )$	$P_{\text{ld}}({\mathcal{R}}_{m,n},2,\epsilon )$	$P_{\text{mld}}({\mathcal{R}}_{m,n},\epsilon )$
	$-P_{\text{ud}}({\mathcal{C}}_{m,n},\epsilon )$	$-P_{\text{ld}}({\mathcal{C}}_{m,n},1,\epsilon )$	$-P_{\text{ld}}({\mathcal{C}}_{m,n},2,\epsilon )$	$-P_{\text{mld}}({\mathcal{C}}_{m,n},\epsilon )$
0.05	$1.03\times {10}^{-28}$	$4.13\times {10}^{-40}$	$2.89\times {10}^{-49}$	$5.14\times {10}^{-29}$
0.10	$1.09\times {10}^{-26}$	$9.63\times {10}^{-35}$	$2.16\times {10}^{-39}$	$5.44\times {10}^{-27}$
0.15	$9.26\times {10}^{-25}$	$4.14\times {10}^{-30}$	$2.70\times {10}^{-32}$	$4.63\times {10}^{-25}$
0.20	$6.52\times {10}^{-23}$	$4.52\times {10}^{-26}$	$2.12\times {10}^{-27}$	$3.26\times {10}^{-23}$
0.25	$3.70\times {10}^{-21}$	$5.96\times {10}^{-23}$	$8.27\times {10}^{-24}$	$1.87\times {10}^{-21}$
0.30	$1.37\times {10}^{-19}$	$1.36\times {10}^{-20}$	$3.39\times {10}^{-21}$	$7.21\times {10}^{-20}$
0.35	$2.45\times {10}^{-18}$	$5.42\times {10}^{-19}$	$1.63\times {10}^{-19}$	$1.41\times {10}^{-18}$
0.40	$1.81\times {10}^{-17}$	$5.20\times {10}^{-18}$	$3.47\times {10}^{-18}$	$1.19\times {10}^{-17}$
0.45	$5.39\times {10}^{-17}$	$2.78\times {10}^{-17}$	$2.77\times {10}^{-17}$	$4.23\times {10}^{-17}$
0.50	$6.47\times {10}^{-17}$	$5.55\times {10}^{-17}$	$5.55\times {10}^{-17}$	$6.45\times {10}^{-17}$

Next, letting $m=(1-R)n$ for $0<R<1$, we compute the error exponents of the average decoding error probability of the ensemble series $\{{\mathcal{R}}_{(1-R)n,n}\}$ as $n\to \infty$ under these decoding principles.

Theorem 2

Let the rate $0<R<1$ be fixed and $n\to \infty$.

1. For any fixed integer $\ell \ge 0$, the error exponent $T_{\text{ld}}(\ell ,\epsilon )$ for average unsuccessful decoding probability of $\{{\mathcal{R}}_{(1-R)n,n}\}$ under list decoding with list size $q^{\ell }$ is given by

   9

   $$\begin{array}{c}\hfill T_{\text{ld}}(\ell ,\epsilon )=\left\{\begin{array}{cc}0\hfill & (1-\epsilon \le R<1)\hfill \\ (1-R){log}_q\left(\frac{1-R}{\epsilon }\right)+R{log}_q\left(\frac{R}{1-\epsilon }\right)\hfill & \left(\frac{1-\epsilon }{1-\epsilon +q^{\ell +1}\epsilon },<,R,<,1,-,\epsilon \right)\hfill \\ (\ell +1)(1-R)-{log}_q\left(1,-,\epsilon ,+,q^{\ell +1},\epsilon \right)\hfill & \left(0,<,R,\le ,\frac{1-\epsilon }{1-\epsilon +q^{\ell +1}\epsilon }\right).\hfill \end{array}\right)\end{array}$$

2. The error exponents for average unsuccessful decoding probability of $\{{\mathcal{R}}_{(1-R)n,n}\}$ under unambiguous decoding and maximum likelihood decoding (respectively) are both given by

   10

   $$\begin{array}{c}\hfill T_{\text{ud}}(\epsilon )=T_{\text{mld}}(\epsilon )=\left\{\begin{array}{cc}0\hfill & (1-\epsilon \le R<1)\hfill \\ (1-R){log}_q\left(\frac{1-R}{\epsilon }\right)+R{log}_q\left(\frac{R}{1-\epsilon }\right)\hfill & \left(\frac{1-\epsilon }{1-\epsilon +q\epsilon },<,R,<,1,-,\epsilon \right)\hfill \\ 1-R-{log}_q\left(1,-,\epsilon ,+,q,\epsilon \right)\hfill & \left(0,<,R,\le ,\frac{1-\epsilon }{1-\epsilon +q\epsilon }\right).\hfill \end{array}\right)\end{array}$$

A plot of the function $T_{\text{ld}}(\ell ,\epsilon )$ for $q=2,\epsilon =0.25,\ell =0,1,2$ in the range $0<R<1$ is given by Fig. 1.

[See PDF for image]

Fig. 1

The error exponent $T_{\text{ld}}(\ell ,\epsilon )$ for $0<R<1$ where $\ell =0,1,2$ and $q=2,\epsilon =0.25$

It turns out that the error exponents obtained here under these decoding principles are identical with those for the random ${[n,nR]}_q$ code ensemble obtained in [14, Theorem 3] and [18, Theorems 1.3 and 1.4].

We establish a strong concentration result for the unsuccessful decoding probability of a random code in the ensemble ${\mathcal{R}}_{(1-R)n,n}$ towards the mean under unambiguous decoding.

Theorem 3

Let the rate $0<R<1$ be fixed and $n\to \infty$. Then as $H_n$ runs over the ensemble ${\mathcal{R}}_{(1-R)n,n}$, we have

11

$$\begin{array}{c}\hfill \frac{P_{\text{ud}}(H_n,\epsilon )}{P_{\text{ud}}({\mathcal{R}}_{(1-R)n,n},\epsilon )}\to 1\mathbf{WHP},\end{array}$$under either of the following conditions:

1. if $\frac{1-\epsilon }{1+(q-1){\epsilon }^2}\le R<1-\epsilon$ for any $q\ge 2$, or

2. if $\frac{1-\epsilon }{1+(q-1)\epsilon }\le R<1-\epsilon$ for $q=2,3,4$.

Here the notion WHP in (11) refers to “with high probability”, that is, for any $\delta >0$, there is $c>0$ and $n_0>0$ such that$$\begin{array}{c}\hfill \mathbb{P}\left(\left|\frac{P_{\text{ud}}(H_n,\epsilon )}{P_{\text{ud}}({\mathcal{R}}_{(1-R)n,n},\epsilon )},-,1\right|,<,\delta \right)>1-q^{-nc}\forall n>n_0.\end{array}$$Noting that in the range $0<R<1-\epsilon$, it was known that $T_{\text{ud}}(\epsilon )>0$ (see Theorem 2), hence$$\begin{array}{c}\hfill P_{\text{ud}}({\mathcal{R}}_{(1-R)n,n},\epsilon )=q^{-n(T_{\text{ud}}(\epsilon )+o(1))}\to 0,\text{as}n\to \infty ,\end{array}$$so (11) shows that $P_{\text{ud}}(H_n,\epsilon )$ also tends to zero exponentially fast with high probability for the ensemble ${\mathcal{R}}_{(1-R)n,n}$ under either Condition (1) or (2) of Theorem 3.

The paper is now organized as follows. In Sect. 2, we introduce the three decoding principles and the Gaussian q-binomial coefficient in more details. Then in Sect. 3, we provide three counting results regarding $m\times n$ matrices of certain rank over ${\mathbb{F}}_q$. Afterwards in Sects. 4, 5 and 6, we give the proofs of Theorems 1, 2 and 3 respectively. The proofs of Theorem 3 involves some technical calculus computations on the error exponent of the variance. In order to streamline the proofs, we put some of the arguments in Sect. 7 in Appendix. Finally we conclude this paper in Sect. 8.

Preliminaries

Three decoding principles, the average decoding error probability, and the error exponent

The three decoding principles have been well studied in the literature. For the sake of readers, we explain these terms here, following the presentation outlined in [14].

In a q-ary erasure channel, the channel input alphabet is a finite field ${\mathbb{F}}_q$ of order q, and during transmission, each symbol $x\in {\mathbb{F}}_q$ is either received correctly with probability $1-\epsilon$ or erased with probability $\epsilon$$(0<\epsilon <1)$.

Let C be a code of length n over ${\mathbb{F}}_q$. For a codeword $\mathbf{c}=(c_1,c_2,\dots ,c_n)\in C$ that was transmitted through the channel, suppose the word $\mathbf{r}=(r_1,r_2,\dots ,r_n)$ is received. Denote by E the set of i’s such that $r_i=\square$, i.e., the i-th symbol was erased during the transmission. In this case, we say that an erasure set E occurs. The probability P(E) that this erasure set E occurs for $\mathbf{c}$ is clearly ${\epsilon }^{\#E}{(1-\epsilon )}^{n-\#E}$. Here $\#E$ denote the cardinality of the set E.

Let $C(E,\mathbf{r})$ be the set of all codewords of C that match the received word $\mathbf{r}$, that is,$$\begin{array}{c}\hfill C(E,\mathbf{r})=\{\mathbf{c}\in C:c_i=r_i\forall i\in [n]\backslash E\}.\end{array}$$Here $[n]=\{1,2,\dots ,n\}$. The decoding problem is about how to choose one or more possible codewords in the set $C(E,\mathbf{r})$ when a word $\mathbf{r}$ is received. Now we consider three decoding principles:

• In unambiguous decoding, the decoder outputs the only one codeword in $C(E,\mathbf{r})$ if $\#C(E,\mathbf{r})=1$ and declares “failure” otherwise. The unsuccessful decoding probability $P_{\text{ud}}(C,\epsilon )$ of C under unambiguous decoding is defined to be the probability that the decoder declares “failure”.

• In list decoding, the decoder with list size $q^{\ell }$ outputs all the codewords in $C(E,\mathbf{r})$ if $\#C(E,\mathbf{r})\le q^{\ell }$ and declares “failure” otherwise. The unsuccessful decoding probability $P_{\text{ld}}(C,\ell ,\epsilon )$ of C under list decoding with list size $q^{\ell }$ is defined to be the probability that the decoder declares “failure”.

• In maximum likelihood decoding, the decoder randomly choose a codeword in $C(E,\mathbf{r})$ uniformly and outputs this codeword. The decoding error probability $P_{\text{mld}}(C,\epsilon )$ of C under maximum likelihood decoding is defined to be the probability that the codeword outputted by the decoder is not the sent codeword.

The computation of $P_{\text{ud}}(C,\epsilon ),P_{\text{ld}}(C,\ell ,\epsilon )$ and $P_{\text{mld}}(C,\epsilon )$ can be made much easier if C is a linear code.

Now assume that C is an ${[n,k]}_q$ linear code, that is, C is a k-dimensional subspace of ${\mathbb{F}}_q^n$. For any $E\subset [n]$, define$$\begin{array}{c}\hfill C(E):=\left\{\mathbf{c},=,(c_1,\dots ,c_n),\in ,C,:,c_i,=,0,,,\forall ,i,\in ,[n],\backslash ,E\right\}.\end{array}$$It is easy to see that if the set $C(E,\mathbf{r})$ is not empty, then the cardinality of $C(E,\mathbf{r})$ is the same as that of C(E), which is a vector space over ${\mathbb{F}}_q$. Denote by ${\{I_i^{(\ell )}(C)\}}_{i=1}^n$ the $q^{\ell }$-incorrigible set distribution of C, and ${\{I_i(C)\}}_{i=1}^n$ the incorrigible set distribution of C, which are defined respectively as follows:

12

$$\begin{array}{cc}\hfill I_i^{(\ell )}(C)=& \#\left\{E,\subset ,[,n,],:,\#,E,=,i,,,dim,C,(,E,),>,\ell \right\},\hfill \\ \hfill I_i(C)=& \#\left\{E,\subset ,[,n,],:,\#,E,=,i,,,C,(,E,),\ne ,\{,0,\}\right\}.\hfill \end{array}$$Here $dimC(E)$ denotes the dimension of C(E) as a vector space over ${\mathbb{F}}_q$. We see that $dimC(E)\le min\{k,\#E\}$, so if $\ell \ge min\{k,\#E\}$, then $I_i^{(\ell )}(C)=\mathrm{\varnothing }$. We also define

13

$$\begin{array}{c}\hfill {\lambda }_i^{(\ell )}(C)=\#\left\{E,\subset ,[,n,],:,\#,E,=,i,,,dim,C,(,E,),=,\ell \right\}.\end{array}$$It is easy to see that $I_i^{(0)}(C)=I_i(C)$, ${\lambda }_i^{(\ell )}(C)=0$ if $\ell >min\{i,k\}$ and

14

$$\begin{array}{c}\hfill \sum _{\ell =0}^i{\lambda }_i^{(\ell )}(C)=\left(\begin{array}{c}n\\ i\end{array}\right).\end{array}$$We also have the identity

15

$$\begin{array}{c}\hfill I_i^{(\ell )}(C)=\sum _{j=\ell +1}^i{\lambda }_i^{(j)}(C),\forall i,\ell .\end{array}$$Recall from [14] that the values $P_{\text{ud}}(C,\epsilon ),P_{\text{mld}}(C,\epsilon )$ and $P_{\text{ld}}(C,\ell ,\epsilon )$ can all be expressed in terms of $I_i^{(\ell )}(C)$, $I_i(C)$ and ${\lambda }_i^{(\ell )}(C)$ as follows:$$\begin{array}{cc}\hfill P_{\text{ud}}(C,\epsilon )=& \sum _{i=1}^n{I}_i(C){\epsilon }^i{(1-\epsilon )}^{n-i},\hfill \\ \hfill P_{\text{ld}}(C,\ell ,\epsilon )=& \sum _{i=1}^n{I}_i^{(\ell )}(C){\epsilon }^i{(1-\epsilon )}^{n-i},\hfill \\ \hfill P_{\text{mld}}(C,\epsilon )=& \sum _{i=1}^n\sum _{\ell =1}^i{\lambda }_i^{(\ell )}(C)(1-q^{-\ell }){\epsilon }^i{(1-\epsilon )}^{n-i}.\hfill \end{array}$$For $H\in {\mathcal{R}}_{m,n}$, we write $P_{\text{ld}}(H,\ell ,\epsilon ):=P_{\text{ld}}(C_H,\ell ,\epsilon )$ and $P_{\ast }^{}(H,\epsilon ):=P_{\ast }^{}(C_H,\epsilon )$ for $\ast \in \{\text{ud},\text{mld}\}$, where $C_H$ is the parity-check code defined by (1). The average decoding error probabilities over the ensemble ${\mathcal{R}}_{m,n}$ are given by$$\begin{array}{c}\hfill P_{\text{ld}}({\mathcal{R}}_{m,n},\ell ,\epsilon ):=\mathbb{E}[P_{\text{ld}}(H,\ell ,\epsilon )],\end{array}$$and$$\begin{array}{c}\hfill P_{\ast }^{}({\mathcal{R}}_{m,n},\epsilon ):=\mathbb{E}[P_{\ast }^{}(H,\epsilon )],\ast \in \{\text{ud},\text{mld}\}.\end{array}$$Here the expectation $\mathbb{E}$ is taken over the ensemble ${\mathcal{R}}_{m,n}$.

Let $0<R,\epsilon <1$ be fixed constants. The error exponent $T_{\text{ud}}(\epsilon )$ for average unsuccessful decoding probability of the family of ensembles $\{{\mathcal{R}}_{(1-R)n,n}\}$ under unambiguous decoding is defined as$$\begin{array}{c}\hfill T_{\text{ud}}(\epsilon ):=-\underset{n\to \infty }{lim}\frac{1}{n}{log}_q{P}_{\text{ud}}({\mathcal{R}}_{(1-R)n,n},\epsilon ),\end{array}$$provided that the limit exists [8, 14, 15]. The error exponents of $\{{\mathcal{R}}_{(1-R)n,n}\}$ for the other two decoding principles are defined similarly.

Gaussian binomial coefficients

For integers $n\ge k\ge 0$, the Gaussian binomial coefficients is defined aswhere ${(q)}_n:={\prod }_{i=1}^n\left(1,-,q^i\right)$. By convention ${(q)}_0=1$, for any $n\ge 0$ and if $k<0$ or $k>n$. The function ${\psi }_m(i)$ defined in (2) can be written asWe may define ${\psi }_m(0)=1$ for $m\ge 0$ and ${\psi }_m(i)=0$ if $i<0$ or $i>m$. Next, recall the well-known combinatorial interpretation of :

Lemma 1

([13]) The number of k-dimensional subspaces of an n-dimensional vector space over ${\mathbb{F}}_q$ is .

The Gaussian binomial coefficient satisfies the propertyand the identity

16

Three counting results for the ensemble ${\mathcal{R}}_{m,n}$

In this section we provide three counting results about matrices of certain rank in the ensemble ${\mathcal{R}}_{m,n}$. Such results may not be new, but since it is not easy to locate them in the literature, we prove them here. These results will be used repeatedly in the proofs later on.

For $H\in {\mathcal{R}}_{m,n}$, denote by $\text{rk}(H)$ the rank of the matrix H over ${\mathbb{F}}_q$.

Lemma 2

Let H be a random matrix in the ensemble ${\mathcal{R}}_{m,n}$. Then for any integer j, we have

17

Proof

We may assume that j satisfies $0\le j\le n$, because if j is not in the range, then both sides of Equation (17) are obviously zero.

Denote by $\text{Hom}(m,n)$ the set of ${\mathbb{F}}_q$-linear transformations from ${\mathbb{F}}_q^m$ to ${\mathbb{F}}_q^n$. Writing vectors in ${\mathbb{F}}_q^m$ and ${\mathbb{F}}_q^n$ as row vectors, we see that the random matrix ensemble ${\mathcal{R}}_{m,n}$ can be identified with the set $\text{Hom}(m,n)$ via the relation

18

$$\begin{array}{c}\hfill H\leftrightarrow G:\begin{array}{c}{\mathbb{F}}_q^m\to {\mathbb{F}}_q^n\\ \mathbf{x}\mapsto \mathbf{x}H\end{array}.\end{array}$$Since $\text{rk}(H)=j$ if and only if $dim(\text{Im}G)=j$, and $\#{\mathcal{R}}_{m,n}=q^{\mathit{mn}}$, we have$$\begin{array}{cc}\hfill \mathbb{P}(\text{rk}(H)=j)& =q^{-mn}\sum _{\begin{array}{c}G\in \text{Hom}(m,n)\\ dim(\text{Im}G)=j\end{array}}1\hfill \\ \hfill & =q^{-mn}\sum _{\begin{array}{c}V\le {\mathbb{F}}_q^n\\ dimV=j\end{array}}\sum _{\begin{array}{c}G\in \text{Hom}(m,n)\\ \text{Im}G=V\end{array}}1.\hfill \end{array}$$The inner sum ${\sum }_{G\in \text{Hom}(m,n),\text{Im}G=V}1$ counts the number of surjective linear transformations from ${\mathbb{F}}_q^m$ to V, a j-dimensional subspace of ${\mathbb{F}}_q^n$. Since $V\cong {\mathbb{F}}_q^j$, this is also the number of surjective linear transformations from ${\mathbb{F}}_q^m$ to ${\mathbb{F}}_q^j$, or, equivalently, the number of $m\times j$ matrices K over ${\mathbb{F}}_q$ such that the columns of K are linearly independent. The number of such matrices K can be counted as follows: the first column of K can be any nonzero vector over ${\mathbb{F}}_q$, there are $q^m-1$ choices; given the first column, the second column can be any vector lying outside the space of scalar multiples of the first column, so there are $q^m-q$ choices; inductively, given the first k columns, the $(k+1)$-th column lies outside a k-dimensional subspace, so the number of choices for the $(k+1)$-th column is $q^m-q^k$. Thus we have

19

$$\begin{array}{c}\hfill \sum _{\begin{array}{c}G\in {\text{Hom}}_q(m,n)\\ \text{Im}G=V\end{array}}1=\prod _{k=0}^{j-1}(q^m-q^k)=q^{\mathit{mj}}{\psi }_m(j),dimV=j.\end{array}$$Together with Lemma 1, we obtainwhich is the desired result. $\square$

Lemma 3

Let H be a random matrix in the ensemble ${\mathcal{R}}_{m,n}$. Let $A\subset [n]:=\{1,2,\dots ,n\}$ be a subset with cardinality s. Denote by $H_A$ the $m\times s$ submatrix formed by columns of H indexed from A. Then for any integers j and r, we have

20

Proof

We may assume that $0\le j\le n$ and $max\{0,s-n+j\}\le r\le min\{j,s\}$, because if j or r does not satisfy this condition, then both sides of Equation (20) are zero.

Using the relations (18) and (19), we can expand the term $\mathbb{P}(\text{rk}(H)=j\cap \text{rk}(H_A)=r)$ as

21

$$\begin{array}{c}\hfill \mathbb{P}(\text{rk}(H)=j\cap \text{rk}(H_A)=r)=q^{-mn}\sum _{\begin{array}{c}V\le {\mathbb{F}}_q^n\\ dimV=j\\ dim{V}_A=r\end{array}}\sum _{\begin{array}{c}G\in \text{Hom}(m,n)\\ \text{Im}G=V\end{array}}1=q^{-m(n-j)}{\psi }_m(j)\sum _{\begin{array}{c}V\le {\mathbb{F}}_q^n\\ dimV=j\\ dim{V}_A=r\end{array}}1.\end{array}$$Here $V_A$ is the subspace of ${\mathbb{F}}_q^A$ formed by restricting V to coordinates with indices from A. We may consider the projection given by$$\begin{array}{cc}\hfill {\pi }_A:& V\to V_A\hfill \\ \hfill & {(v_k)}_{k=1}^n\mapsto {(v_k)}_{k\in A}.\hfill \end{array}$$The kernel of ${\pi }_A$ has dimension $j-r$ and is of the form $W\times \{{(0)}_A\}$ for some subspace $W\le {\mathbb{F}}_q^{[n]-A}$. So we can further decompose the sum on the right hand side of (21) as

22

$$\begin{array}{c}\hfill \sum _{\begin{array}{c}V\le {\mathbb{F}}_q^n\\ dimV=j\\ dim{V}_A=r\end{array}}1=\sum _{\begin{array}{c}W\le {\mathbb{F}}_q^{[n]-A}\\ dimW=j-r\end{array}}\sum _{\begin{array}{c}V\le {\mathbb{F}}_q^n\\ dimV=j\\ ker({\pi }_A)=W\times \{{(0)}_A\}\end{array}}1.\end{array}$$Now we compute the inner sum on the right hand side of (22). Suppose we are given an ordered basis of the $(j-r)$-dimensional subspace $W\times \{{(0)}_A\}$ of ${\mathbb{F}}_q^n$. We extend it to an ordered basis of some j-dimensional subspace V as follows: first we need r other basis vectors ${\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_r$ to be linearly independent. At the same time, they have to be linearly independent with any nonzero vector in ${\mathbb{F}}_q^{[n]-A}\times \{{(0)}_A\}$ due to the kernel condition. This requires the set $\{{\pi }_A({\mathbf{v}}_1),{\pi }_A({\mathbf{v}}_2),\dots ,{\pi }_A({\mathbf{v}}_r)\}$ to be linearly independent in ${\mathbb{F}}_q^A$. On the other hand, if this condition is satisfied, then the r vectors ${\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_r$ are also linearly independent with one another as well as with any nonzero vector in $W\times \{{(0)}_A\}$. Therefore it reduces to counting the number of ordered linearly independent sets of r vectors in ${\mathbb{F}}_q^A$. This number is clearly given by ${\prod }_{k=0}^{r-1}(q^s-q^k)$, so the total number of different ordered bases is given by $q^{r(n-s)}{\prod }_{k=0}^{r-1}(q^s-q^k)$.

On the other hand, given a fixed j-dimensional subspace V with $ker({\pi }_A)=W\times \{{(0)}_A\}$, we count the number of ordered bases of V of the form stated in previous paragraph as follows: we choose ${\mathbf{v}}_1$ to be any vector in V but not in $W\times \{{(0)}_A\}$, which gives $q^j-q^{j-r}$ many choices for ${\mathbf{v}}_1$; similarly ${\mathbf{v}}_2$ is any vector in V but not in the span of $W\times \{{(0)}_A\}$ and ${\mathbf{v}}_1$, this gives us $q^j-q^{j-r+1}$ many choices for ${\mathbf{v}}_2$; using this argument, we see that the number of such ordered bases is given by ${\prod }_{k=0}^{r-1}(q^j-q^{j-r+k})$.

We conclude from the above arguments thatPutting this into the right hand side of (22) and using Lemma 1 again, we getThe desired result is obtained immediately by plugging this into the right hand side of (21). This completes the proof of Lemma 3. $\square$

Lemma 4

Let H be a random matrix in the ensemble ${\mathcal{R}}_{m,n}$. Let $E,E^{\prime }$ be subsets of [n] such that$$\begin{array}{c}\hfill i=\#E,i^{\prime }=\#E^{\prime },s=\#(E\cap E^{\prime }).\end{array}$$Then

23

$$\begin{array}{c}\hfill \mathbb{P}(\text{rk}(H_E)=i\cap \text{rk}(H_{E^{\prime }})=i^{\prime })=\frac{{\psi }_m(i){\psi }_m(i^{\prime })}{{\psi }_m(s)}.\end{array}$$

Proof

It is clear that if a matrix H has full rank, then so is the submatrix $H_A$ for any index subset A. Hence we have$$\begin{array}{cc}\hfill \mathbb{P}(\text{rk}(H_E)& =i\cap \text{rk}(H_{E^{\prime }})=i^{\prime })\hfill \\ \hfill & =\mathbb{P}(\text{rk}(H_E)=i\cap \text{rk}(H_{E^{\prime }})=i^{\prime }|\text{rk}(H_{E\cap E^{\prime }})=s)\mathbb{P}(\text{rk}(H_{E\cap E^{\prime }})=s).\hfill \end{array}$$It is easy to see that the two events $\text{rk}(H_E)=i$ and $\text{rk}(H_{E^{\prime }})=i^{\prime }$ are conditionally independent given $\text{rk}(H_{E\cap E^{\prime }})=s$, since columns of $H_E$ and $H_{E^{\prime }}$ are independent as random vectors over ${\mathbb{F}}_q$. Hence we get$$\begin{array}{cc}& \mathbb{P}(\text{rk}(H_E)=i\cap \text{rk}(H_{E^{\prime }})=i^{\prime })\hfill \\ \hfill & =\mathbb{P}(\text{rk}(H_E)=i|\text{rk}(H_{E\cap E^{\prime }})=s)\mathbb{P}(\text{rk}(H_E)=i^{\prime }|\text{rk}(H_{E\cap E^{\prime }})=s)\mathbb{P}(\text{rk}(H_{E\cap E^{\prime }})=s)\hfill \\ \hfill & =\frac{\mathbb{P}(\text{rk}(H_E)=i\cap \text{rk}(H_{E\cap E^{\prime }})=s)\mathbb{P}(\text{rk}(H_E)=i^{\prime }\cap \text{rk}(H_{E\cap E^{\prime }})=s)}{\mathbb{P}(\text{rk}(H_{E\cap E^{\prime }})=s)}\hfill \\ \hfill & =\frac{{\psi }_m(i){\psi }_m(i^{\prime })}{{\psi }_m(s)}.\hfill \end{array}$$Here we have applied Lemmas 2 and 3 in the last equality with $j=i,j^{\prime }=i^{\prime }$ and $r=s,H=H_E$ and $A=E\cap E^{\prime }$. $\square$

Proof of Theorem 1

Let C be an ${[n,k]}_q$ linear code. Recall from Sect. 2 that the values $P_{\text{ud}}(C,\epsilon ),P_{\text{mld}}(C,\epsilon )$ and $P_{\text{ld}}(C,\ell ,\epsilon )$ can all be expressed explicitly as

24

$$\begin{array}{cc}\hfill P_{\text{ud}}(C,\epsilon )=& \sum _{i=1}^n{I}_i(C){\epsilon }^i{(1-\epsilon )}^{n-i},\hfill \end{array}$$

25

$$\begin{array}{cc}\hfill P_{\text{ld}}(C,\ell ,\epsilon )=& \sum _{i=1}^n{I}_i^{(\ell )}(C){\epsilon }^i{(1-\epsilon )}^{n-i},\hfill \end{array}$$

26

$$\begin{array}{cc}\hfill P_{\text{mld}}(C,\epsilon )=& \sum _{i=1}^n\sum _{\ell =1}^i{\lambda }_i^{(\ell )}(C)(1-q^{-\ell }){\epsilon }^i{(1-\epsilon )}^{n-i},\hfill \end{array}$$where $I_i(C)$ and $I_i^{(\ell )}(C)$ are the incorrigible set distribution of C and the $q^{\ell }$-incorrigible set distribution of C respectively, and ${\lambda }_i^{(\ell )}(C)$ is defined in (13) also in Sect. 2.

Now we can start the proof of Theorem 1. For $H\in {\mathcal{R}}_{m,n}$, we denote$$\begin{array}{c}\hfill I_i:=I_i(C_H),I_i^{(\ell )}:=I_i^{(\ell )}(C_H),{\lambda }_i^{(\ell )}:={\lambda }_i^{(\ell )}(C_H).\end{array}$$Taking expectations on both sides of Equations (24)-(26) over the ensemble ${\mathcal{R}}_{m,n}$, we obtain

27

$$\begin{array}{cc}\hfill P_{\text{ud}}({\mathcal{R}}_{m,n},\epsilon )=& \sum _{i=1}^n\mathbb{E}[I_i]{\epsilon }^i{(1-\epsilon )}^{n-i},\hfill \end{array}$$

28

$$\begin{array}{cc}\hfill P_{\text{ld}}({\mathcal{R}}_{m,n},\ell ,\epsilon )=& \sum _{i=1}^n\mathbb{E}[I_i^{(\ell )}]{\epsilon }^i{(1-\epsilon )}^{n-i},\hfill \end{array}$$

29

$$\begin{array}{cc}\hfill P_{\text{mld}}({\mathcal{R}}_{m,n},\epsilon )=& \sum _{i=1}^n\sum _{\ell =1}^i\mathbb{E}[{\lambda }_i^{(\ell )}](1-q^{-\ell }){\epsilon }^i{(1-\epsilon )}^{n-i}.\hfill \end{array}$$We now compute $\mathbb{E}[{\lambda }_i^{(\ell )}]$. Noting that for $H\in {\mathcal{R}}_{m,n}$ and $E\subset [n]$, we have $\text{rk}(H_E)+dim{C}_H(E)=\#E$, thus$$\begin{array}{cc}\hfill \mathbb{E}[{\lambda }_i^{(\ell )}]=& \frac{1}{\#{\mathcal{R}}_{m,n}}\sum _{\begin{array}{c}H\in {\mathcal{R}}_{m,n}\end{array}}\sum _{\begin{array}{c}E\subset [n]\\ \#E=i\end{array}}{\mathbb{1}}_{dim{C}_H(E)=\ell }\hfill \\ \hfill =& \frac{1}{\#{\mathcal{R}}_{m,n}}\sum _{\begin{array}{c}E\subset [n]\\ \#E=i\end{array}}\sum _{\begin{array}{c}H\in {\mathcal{R}}_{m,n}\\ \text{rk}(H_E)=i-\ell \end{array}}1.\hfill \end{array}$$By the symmetry of the ensemble ${\mathcal{R}}_{m,n}$, the inner sum on the right hand side depends only on the cardinality of E, so we may assume $E=[i]$ to obtain$$\begin{array}{c}\hfill \mathbb{E}[{\lambda }_i^{(\ell )}]=\frac{1}{\#{\mathcal{R}}_{m,i}}\left(\begin{array}{c}n\\ i\end{array}\right)\sum _{\begin{array}{c}H\in {\mathcal{R}}_{m,i}\\ \text{rk}(H)=i-\ell \end{array}}1.\end{array}$$The right hand side is exactly $\left(\begin{array}{c}n\\ i\end{array}\right)\mathbb{P}(\text{rk}(H)=i-\ell )$ where the probability is over the ensemble ${\mathcal{R}}_{m,i}$. So from Lemma 2 we have

30

Using this and (15), we also obtainInserting the above values $\mathbb{E}[I_i^{(\ell )}]$ and $\mathbb{E}[{\lambda }_i^{(\ell )}]$ into (28) and (29) respectively, we obtain explicit expressions of $P_{\text{ld}}({\mathcal{R}}_{m,n},\ell ,\epsilon )$ and $P_{\text{mld}}({\mathcal{R}}_{m,n},\epsilon )$, which agree with (3) and (5) of Theorem 1.

As for $P_{\text{ud}}({\mathcal{R}}_{m,n},\epsilon )$, noting by (14) that ${\sum }_{\ell =0}^i\mathbb{E}[{\lambda }_i^{(\ell )}]=\left(\begin{array}{c}n\\ i\end{array}\right)$ and by (30) that $\mathbb{E}[{\lambda }_i^{(0)}]={\psi }_m(i)\left(\begin{array}{c}n\\ i\end{array}\right)$, therefore

31

$$\begin{array}{c}\hfill \mathbb{E}[I_i]=\sum _{j=1}^i\mathbb{E}[{\lambda }_i^{(j)}]=\left(\begin{array}{c}n\\ i\end{array}\right)-\mathbb{E}[{\lambda }_i^{(0)}]=\left(1,-,{\psi }_m,(i)\right)\left(\begin{array}{c}n\\ i\end{array}\right).\end{array}$$Inserting this value into (27), we also obtain the desired expression of $P_{\text{ud}}({\mathcal{R}}_{m,n},\epsilon )$. This completes the proof of Theorem 1.

Proof of Theorem 2

First recall that the error exponents of the average decoding error probability of the ensemble ${\mathcal{R}}_{(1-R)n,n}$ over the erasure channel under the three decoding principles are defined by

32

$$\begin{array}{c}\hfill T_{\text{ld}}(\ell ,\epsilon ):=-\underset{n\to \infty }{lim}\frac{1}{n}{log}_q{P}_{\text{ld}}({\mathcal{R}}_{(1-R)n,n},\ell ,\epsilon ),\end{array}$$and$$\begin{array}{c}\hfill T_{\ast }^{}(\epsilon ):=-\underset{n\to \infty }{lim}\frac{1}{n}{log}_{q}P_{\ast }^{}({\mathcal{R}}_{(1-R)n,n},\epsilon ),\ast \in \{\text{ud},\text{mld}\},\end{array}$$provided that the three limits exist [8, 14, 15].

Unambiguous decoding corresponds to list decoding with $\ell =0$, and it is also easy to see that$$\begin{array}{c}\hfill \frac{1}{2}{P}_{\text{ud}}(C,\epsilon )\le P_{\text{mld}}(C,\epsilon )\le P_{\text{ud}}(C,\epsilon ),\end{array}$$hence we have$$\begin{array}{c}\hfill T_{\text{ud}}(\epsilon )=T_{\text{mld}}(\epsilon )=T_{\text{ld}}(0,\epsilon ),\end{array}$$if the limit exists say in (32) for $\ell =0$. So we only need to prove Part 1) of Theorem 2 for the case of list decoding.

Write $m=(1-R)n$, and we defineIt is easy to see that $f_{i,j}\ge 0$ for all integers i, j. In addition, $f_{i,j}\ne 0$ if and only if $1\le i\le n,1\le j\le i$ and $i-j\le m$.

We can rewrite (3) as$$\begin{array}{c}\hfill P_{\text{ld}}({\mathcal{R}}_{m,n},\ell ,\epsilon )=\sum _{i,j}{f}_{i,j},\end{array}$$where i, j are integers satisfying the conditions

33

$$\begin{array}{c}\hfill \ell +1\le i\le n,max\{i-m,\ell +1\}\le j\le i.\end{array}$$The number of such integer pairs (i, j) is at most mn. Noting that ${lim}_{n\to \infty }\frac{{log}_q(mn)}{n}=0$, we have

34

$$\begin{array}{c}\hfill \frac{1}{n}{log}_q{P}_{\text{ld}}({\mathcal{R}}_{m,n},\ell ,\epsilon )=o(1)+\frac{1}{n}\underset{i,j}{max}{log}_q{f}_{i,j}.\end{array}$$Now we focus on the quantity $f_{i,j}$. First, set $T=q^{-1}$ so that $0<T<1$. It is easy to verify that for $0\le j\le i$,

35

Hence we haveThe infinite product ${(T)}_{\infty }:={\prod }_{r=1}^{\infty }(1-T^r)$ converges absolutely to some positive real number M which only depends on q, and $M={(T)}_{\infty }<{(T)}_m\le 1$ for any m. This implies thatand thusTherefore we have$$\begin{array}{c}\hfill \frac{1}{n}{log}_q{f}_{i,j}=-\frac{j(m-i+j)}{n}+\frac{1}{n}{log}_q\left(\begin{array}{c}n\\ i\end{array}\right)+\frac{i}{n}{log}_q\epsilon +\frac{n-i}{n}{log}_q(1-\epsilon )+o(1).\end{array}$$We want to maximize this quantity over i, j satisfying (33). Since the term $-\frac{j(m-i+j)}{n}$ is always non-positive, it is easy to see that for any fixed i, to maximize the term $\frac{1}{n}{log}_q{f}_{i,j}$, we shall take$$\begin{array}{c}\hfill j=\left\{\begin{array}{ccc}\ell +1\hfill & :& \text{if}\ell +1>i-m,\text{or}\text{equivalently}\text{if}i<m+\ell +1,\hfill \\ i-m\hfill & :& \text{otherwise}.\hfill \end{array}\right)\end{array}$$So we can simplify (34) as$$\begin{array}{cc}& \frac{1}{n}{log}_q{P}_{\text{ld}}({\mathcal{R}}_{m,n},\ell ,\epsilon )\hfill \\ & =o(1)+\underset{\ell +1\le i\le n}{max}\left[-,\frac{(\ell +1){(m-i+\ell +1)}_{+}}{n}\right)\hfill \\ & \left(+,\frac{1}{n},{log}_q,\left(\begin{array}{c}n\\ i\end{array}\right),+,\frac{i}{n},{log}_q,\epsilon ,+,\frac{n-i}{n},{log}_q,(1-\epsilon )\right],\hfill \end{array}$$where ${(x)}_{+}:=max\{0,x\}$.

Let $i=tn$ with $0<t\le 1$. Using the result (see [13] and [14, Lemma 3] for example)

36

$$\begin{array}{c}\hfill \frac{1}{n}{log}_q\left(\begin{array}{c}n\\ tn\end{array}\right)=h(t)+o(1),\end{array}$$where $h(t)=-t{log}_{q}t-(1-t){log}_q(1-t)$ is the binary entropy function (in q-its), and taking $n\to \infty$, we obtain$$\begin{array}{c}\hfill T_{\text{ld}}(\ell ,\epsilon )=-\underset{0<t\le 1}{sup}f(t),\end{array}$$where

37

$$\begin{array}{c}\hfill f(t)=-(\ell +1){(1-R-t)}_{+}+h(t)+t{log}_q\epsilon +(1-t){log}_q(1-\epsilon ).\end{array}$$Note that f(t) is continuous on the interval (0, 1).

Differentiating (37) with respect to t, we get$$\begin{array}{c}\hfill \frac{\text{d}f}{\text{d}t}=\left\{\begin{array}{cc}\ell +1+{log}_q\left(\frac{\epsilon }{t}\right)-{log}_q\left(\frac{1-\epsilon }{1-t}\right)\hfill & (0<t<1-R)\hfill \\ {log}_q\left(\frac{\epsilon }{t}\right)-{log}_q\left(\frac{1-\epsilon }{1-t}\right)\hfill & (1-R<t<1).\hfill \end{array}\right)\end{array}$$It is easy to check from the right hand side that $\frac{\text{d}f}{\text{d}t}=0$ at$$\begin{array}{c}\hfill t_1=\frac{q^{\ell +1}\epsilon }{1+(q^{\ell +1}-1)\epsilon },t_2=\epsilon ,\end{array}$$and at these points the function f(t) has a local maximum. There are three cases to consider:

Case 1:$0<R\le \frac{1-\epsilon }{1+(q^{\ell +1}-1)\epsilon }$

In this case we have $\epsilon <t_1\le 1-R$, then f(t) is maximized at $t=t_1$, so$$\begin{array}{c}\hfill T_{\text{ld}}(\ell ,\epsilon )=-f(t_1)=(\ell +1)(1-R)-{log}_q[1+(q^{\ell +1}-1)\epsilon ].\end{array}$$Case 2:$\frac{1-\epsilon }{1+(q^{\ell +1}-1)\epsilon }<R<1-\epsilon$

In this case we have $\epsilon <1-R<t_1$, then f(t) is maximized at $t=1-R$, so$$\begin{array}{c}\hfill T_{\text{ld}}(\ell ,\epsilon )=-f(1-R)=(1-R){log}_q\left(\frac{1-R}{\epsilon }\right)+R{log}_q\left(\frac{R}{1-\epsilon }\right).\end{array}$$Case 3:$1-\epsilon \le R<1$

In this case we get $1-R\le \epsilon <t_1$, then f(t) is maximized at $t=t_2=\epsilon$, so$$\begin{array}{c}\hfill T_{\text{ld}}(\ell ,\epsilon )=-f(\epsilon )=0.\end{array}$$Combining Cases 1–3 above gives Equation (9). This completes the proof of Theorem 2.

Proof of Theorem 3

The proof of Theorem 3 depend on the computation of the variance of the unsuccessful decoding probability under unambiguous decoding and its error exponent.

The variance of unsuccessful decoding probability and its error exponent

Note from (24) that the variance ${\sigma }_{\text{ud}}^2({\mathcal{R}}_{m,n},\epsilon )$ of the unsuccessful decoding probability under unambiguous decoding can be expressed as$$\begin{array}{cc}\hfill {\sigma }_{\text{ud}}^2({\mathcal{R}}_{m,n},\epsilon )& =\mathbb{E}[P_{\text{ud}}{(H,\epsilon )}^2]-{\left(\mathbb{E},[,P_{\text{ud}},(H,\epsilon ),]\right)}^2\hfill \\ \hfill & =\mathbb{E}\left[{\left(\sum _{i=1}^n,I_i,{\epsilon }^i,{(1-\epsilon )}^{n-i}\right)}^2\right]-{\left(\sum _{i=1}^n,\mathbb{E},[I_i],{\epsilon }^i,{(1-\epsilon )}^{n-i}\right)}^2\hfill \\ \hfill & =\sum _{i,i^{\prime }=1}^n\text{Cov}(I_i,I_{i^{\prime }}){\epsilon }^{i+i^{\prime }}{(1-\epsilon )}^{2n-i-i^{\prime }},\hfill \end{array}$$where the term $\text{Cov}(I_i,I_{i^{\prime }})$ is given by$$\begin{array}{c}\hfill \text{Cov}(I_i,I_{i^{\prime }})=\mathbb{E}[I_i{I}_{i^{\prime }}]-\mathbb{E}[I_i]\mathbb{E}[I_{i^{\prime }}].\end{array}$$We first obtain:

Lemma 5

For $1\le i,i^{\prime }\le n$, we have

38

$$\begin{array}{cc}& \text{Cov}(I_i,I_{i^{\prime }})\hfill \\ \hfill & ={\psi }_m(i){\psi }_m(i^{\prime })\sum _{s=1}^{min\{i,i^{\prime }\}}\left(\frac{1}{{\psi }_m(s)},-,1\right)\left(\begin{array}{c}n\\ s,i-s,i^{\prime }-s,n-i-i^{\prime }+s\end{array}\right).\hfill \end{array}$$Here the multinomial coefficient $\left(\begin{array}{c}n\\ a,b,c,d\end{array}\right)$ for any non-negative integers a, b, c, d, n such that $a+b+c+d=n$ is given by$$\begin{array}{c}\hfill \left(\begin{array}{c}n\\ a,b,c,d\end{array}\right):=\frac{n!}{a!b!c!d!}.\end{array}$$

Proof of Lemma 5

Obviously if i or $i^{\prime }$ does not satisfy the relation $1\le i,i^{\prime }\le m$, then both sides of (38) are zero. So we may assume that $1\le i,i^{\prime }\le m$.

For any $H\in {\mathcal{R}}_{m,n}$, from (12) we see that$$\begin{array}{c}\hfill I_i(C_H)=\sum _{\begin{array}{c}E\subset [n]\\ \#E=i\end{array}}\left(1,-,{\mathbb{1}}_{dim{C}_H(E)=0}\right)=\sum _{\begin{array}{c}E\subset [n]\\ \#E=i\end{array}}\left(1,-,{\mathbb{1}}_{\text{rk}(H_E)=i}\right).\end{array}$$So we can expand the term $\text{Cov}(I_i,I_{i^{\prime }})$ as

39

$$\begin{array}{cc}& \text{Cov}(I_i,I_{i^{\prime }})\hfill \\ \hfill & =\mathbb{E}[I_i{I}_{i^{\prime }}]-\mathbb{E}[I_i]\mathbb{E}[I_{i^{\prime }}]\hfill \\ \hfill & =\sum _{\begin{array}{c}E\subset [n]\\ \#E=i\end{array}}\sum _{\begin{array}{c}{E}^{\prime }\subset [n]\\ \#E^{\prime }=i^{\prime }\end{array}}\mathbb{E}[{\mathbb{1}}_{\text{rk}(H_E)=i}{\mathbb{1}}_{\text{rk}(H_E^{\prime })=i^{\prime }}]-\mathbb{E}[{\mathbb{1}}_{\text{rk}(H_E)=i}]\mathbb{E}[{\mathbb{1}}_{\text{rk}(H_E^{\prime })=i^{\prime }}]\hfill \\ \hfill & =\sum _{\begin{array}{c}E\subset [n]\\ \#E=i\end{array}}\sum _{\begin{array}{c}{E}^{\prime }\subset [n]\\ \#E^{\prime }=i^{\prime }\end{array}}[\mathbb{P}(\text{rk}(H_E)=i\cap \text{rk}(H_{E^{\prime }})=i^{\prime })-\mathbb{P}(\text{rk}(H_E)=i)\mathbb{P}(\text{rk}(H_{E^{\prime }})=i^{\prime })].\hfill \end{array}$$Applying Lemmas 2 and 4 to the terms in the inner sums on the right hand side of (39), we have

40

$$\begin{array}{c}\hfill \text{Cov}(I_i,I_{i^{\prime }})=\sum _s\sum _{\begin{array}{c}E,E^{\prime }\subset [n]\\ \#E=i,\#E^{\prime }=i^{\prime }\\ \#(E\cap E^{\prime })=s\end{array}}\left(\frac{{\psi }_m(i){\psi }_m(i^{\prime })}{{\psi }_m(s)},-,{\psi }_m,(i),{\psi }_m,(i^{\prime })\right).\end{array}$$Together with the combinatorial identity

41

$$\begin{array}{c}\hfill \sum _{\begin{array}{c}E,E^{\prime }\subset [n]\\ \#E=i,\#E^{\prime }=i^{\prime }\\ \#(E\cap E^{\prime })=s\end{array}}1=\left(\begin{array}{c}n\\ i\end{array}\right)\left(\begin{array}{c}i\\ s\end{array}\right)\left(\begin{array}{c}n-i\\ i^{\prime }-s\end{array}\right)=\left(\begin{array}{c}n\\ s,i-s,i^{\prime }-s,n-i-i^{\prime }+s\end{array}\right),\end{array}$$we obtain the desired result as described by Lemma 5. $\square$

From Lemma 5, the variance ${\sigma }_{\text{ud}}^2({\mathcal{R}}_{m,n},\epsilon )$ can be obtained easily, which we summarize below:

Theorem 4

$$\begin{array}{cc}& {\sigma }_{\text{ud}}^2({\mathcal{R}}_{m,n},\epsilon )\hfill \\ & =\sum _{i,i^{\prime }=1}^m\sum _{s=1}^{min\{i,i^{\prime }\}}{\psi }_m(i){\psi }_m(i^{\prime })\left(\frac{1}{{\psi }_m(s)},-,1\right)\left(\begin{array}{c}n\\ s,i-s,i^{\prime }-s,n-i-i^{\prime }+s\end{array}\right)\hfill \\ & \times {\epsilon }^{i+i^{\prime }}{(1-\epsilon )}^{2n-i-i^{\prime }}.\hfill \end{array}$$

For $0<R<1$, the error exponent of the variance ${\sigma }_{\text{ud}}^2({\mathcal{R}}_{(1-R)n,n},\epsilon )$ is defined by

42

$$\begin{array}{c}\hfill S_{\text{ud}}(\epsilon ):=-\underset{n\to \infty }{lim}\frac{1}{n}{log}_q{\sigma }_{\text{ud}}^2({\mathcal{R}}_{(1-R)n,n},\epsilon ),\end{array}$$if the limit exists. We obtain:

Theorem 5

$$\begin{array}{c}\hfill S_{\text{ud}}(\epsilon )=\left\{\begin{array}{cc}1-R-{log}_q[1+(q-1){\epsilon }^2]\hfill & \left(0,<,R,\le ,\frac{1-\epsilon }{1+(q-1){\epsilon }^2}\right)\hfill \\ (1-R){log}_q\left(\frac{{\kappa }_0}{{\epsilon }^2}\right)+R{log}_q\left(\frac{2R-1+{\kappa }_0}{{(1-\epsilon )}^2}\right)\hfill & \left(\frac{1-\epsilon }{1+(q-1){\epsilon }^2},<,R,<,1\right)\hfill \end{array}\right),\end{array}$$where ${\kappa }_0:={\kappa }_0(R)$ is given by

43

$$\begin{array}{c}\hfill {\kappa }_0(R):=1-R-\frac{\sqrt{4R(1-R)(q-1)+1}-1}{2(q-1)}.\end{array}$$

A plot of the function $S_{\text{ud}}(\epsilon )$ for $q=2,\epsilon =0.25$ in the range $0<R<1$ is given by Fig.2.

[See PDF for image]

Fig. 2

The error exponent $S_{\text{ud}}(\epsilon )$ for $0<R<1$, where $q=2,\epsilon =0.25$

We remark that the proof of Theorem 5 follows a similar argument as that of Theorem 2, though here the computation of $S_{\text{ud}}(\epsilon )$ is much more complex as it involves a lot more technical manipulations. In order to streamline the idea of the proof in this section, we first assume Theorem 5 and leave its proof to Sect. 7 in Appendix. Then Theorem 3 can be proved easily by using the standard Chebyshev’s inequality.

Proof of Theorem 3

We have, by definition of error exponents,$$\begin{array}{c}\hfill P_{\text{ud}}({\mathcal{R}}_{(1-R)n,n},\epsilon )=q^{-n(T_{\text{ud}}(\epsilon )+o(1))},\end{array}$$and$$\begin{array}{c}\hfill {\sigma }_{\text{ud}}^2({\mathcal{R}}_{(1-R)n,n},\epsilon )=q^{-n(S_{\text{ud}}(\epsilon )+o(1))}.\end{array}$$These imply$$\begin{array}{c}\hfill \frac{{\sigma }_{\text{ud}}^2({\mathcal{R}}_{(1-R)n,n},\epsilon )}{P_{\text{ud}}^2({\mathcal{R}}_{(1-R)n,n},\epsilon )}=\frac{q^{-n(S_{\text{ud}}(\epsilon )+o(1))}}{q^{-2n(T_{\text{ud}}(\epsilon )+o(1))}}=q^{-n(S_{\text{ud}}(\epsilon )-2T_{\text{ud}}(\epsilon )+o(1))}.\end{array}$$The right hand side of the above will tend to 0 as $n\to \infty$ if

44

$$\begin{array}{c}\hfill c(\epsilon ,R):=S_{\text{ud}}(\epsilon )-2T_{\text{ud}}(\epsilon )>0.\end{array}$$Thus under (44), by Chebyshev’s inequality, we have, for any fixed $\delta >0$,$$\begin{array}{c}\hfill {\mathbb{P}}_{{\mathcal{R}}_{(1-R)n,n}}\left[\left|\frac{P_{\text{ud}}(H,\epsilon )}{P_{\text{ud}}({\mathcal{R}}_{(1-R)n,n},\epsilon )},-,1\right|,\ge ,\delta \right]\le \frac{{\sigma }_{\text{ud}}^2({\mathcal{R}}_{(1-R)n,n},\epsilon )}{{\delta }^2{P}_{\text{ud}}^2({\mathcal{R}}_{(1-R)n,n},\epsilon )}=q^{-n(c(\epsilon ,R)+o(1))},\end{array}$$that is, $\frac{P_{\text{ud}}(H,\epsilon )}{P_{\text{ud}}({\mathcal{R}}_{(1-R)n,n},\epsilon )}\to 1$WHP as $n\to \infty$.

To prove Theorem 3, it remains to verify that (44) holds true under the assumptions of either (1) or (2) of Theorem 3.

Case 1.$\frac{1-\epsilon }{1+(q-1){\epsilon }^2}\le R<1-\epsilon$

Since $\frac{1-\epsilon }{1+(q-1)\epsilon }<\frac{1-\epsilon }{1+(q-1){\epsilon }^2}$, by a simple calculation, we have$$\begin{array}{cc}\hfill c(\epsilon ,R)& =(1-R){log}_q\left(\frac{{\kappa }_0}{{\epsilon }^2}\right)-R{log}_q\left(\frac{2R-1+{\kappa }_0}{{(1-\epsilon )}^2}\right)\hfill \\ \hfill & +-2\left[(1-R),{log}_q,\left(\frac{1-R}{\epsilon }\right),+,R,{log}_q,\left(\frac{R}{1-\epsilon }\right)\right]\hfill \\ \hfill & =(1-R){log}_q\left(\frac{{\kappa }_0}{{(1-R)}^2}\right)+R{log}_q\left(\frac{2R-1+{\kappa }_0}{R^2}\right)\hfill \\ \hfill & >(1-R){log}_q\left(\frac{{(1-R)}^2}{{(1-R)}^2}\right)+R{log}_q\left(\frac{2R-1+{(1-R)}^2}{R^2}\right)=0,\hfill \end{array}$$so (44) always holds true in this case.

Case 2.$\frac{1-\epsilon }{1+(q-1)\epsilon }\le R<\frac{1-\epsilon }{1+(q-1){\epsilon }^2}$

We can actually obtain a slightly more general result than (2) of Theorem 3 as follows:

Lemma 6

If (44) holds for $R=R_0$ where $R_0$ satisfies $0<R_0\le \frac{1-\epsilon }{1+(q-1){\epsilon }^2}$, then (44) also holds true for any $R\in \left[R_0,,,\frac{1-\epsilon }{1+(q-1){\epsilon }^2}\right]$.

Proof of Lemma 6

First, from Case 1 and the continuity of $S_{\text{ud}}(\epsilon )$ and $T_{\text{ud}}(\epsilon )$, we know that (44) holds for $R=\frac{1-\epsilon }{1+(q-1){\epsilon }^2}$. Hence such $R_0$ always exists.

Now if $R\in \left[\frac{1-\epsilon }{1+(q-1)\epsilon },,,\frac{1-\epsilon }{1+(q-1){\epsilon }^2}\right]$, then we have$$\begin{array}{c}\hfill c(\epsilon ,R)=1-R-{log}_q[1+(q-1){\epsilon }^2]-2\left[(1-R),{log}_q,\left(\frac{1-R}{\epsilon }\right),+,R,{log}_q,\left(\frac{R}{1-\epsilon }\right)\right].\end{array}$$Differentiating $c(\epsilon ,R)$ twice with respect to R, we have$$\begin{array}{c}\hfill \frac{{\partial }^{2}c(\epsilon ,R)}{\partial R^2}=-\frac{2}{R(1-R)lnq},\end{array}$$which is negative for $R\in \left[\frac{1-\epsilon }{1+(q-1)\epsilon },,,\frac{1-\epsilon }{1+(q-1){\epsilon }^2}\right]$, and thus $c(\epsilon ,R)$ is convex $\cap$ for R within that interval.

Next, for $0<R<\frac{1-\epsilon }{1+(q-1)\epsilon }$, we note that$$\begin{array}{cc}\hfill c(\epsilon ,R)& =1-R-{log}_q[1+(q-1){\epsilon }^2]-2\{1-R-{log}_q[1+(q-1)\epsilon ]\}\hfill \\ \hfill & =R-1-{log}_q[1+(q-1){\epsilon }^2]+2{log}_q[1+(q-1)\epsilon ]\hfill \end{array}$$is a linear function in R with positive slope. Hence the function $c(\epsilon ,R)$ is convex $\cap$ for R within the whole interval $\left[R_0,,,\frac{1-\epsilon }{1+(q-1){\epsilon }^2}\right]$, and Lemma 6 follows. $\square$

Now we let $q\in \{2,3,4\}$. Consider $R=\frac{1-\epsilon }{1+(q-1)\epsilon }$. Under this special value,$$\begin{array}{c}\hfill Q(\epsilon ):=c(\epsilon ,R)=-\frac{q\epsilon }{1+(q-1)\epsilon }-{log}_q[1+(q-1){\epsilon }^2]+2{log}_q[1+(q-1)\epsilon ].\end{array}$$Differentiating $Q(\epsilon )$ with respect to $\epsilon$, we have$$\begin{array}{cc}\hfill Q^{\prime }(\epsilon )& =-\frac{q}{{[1+(q-1)\epsilon ]}^2}-\frac{2(q-1)\epsilon }{[1+(q-1){\epsilon }^2]lnq}+\frac{2(q-1)}{[1+(q-1)\epsilon ]lnq}\hfill \\ \hfill & =-\frac{(q-1)(qlnq+2q-2)}{{[1+(q-1)\epsilon ]}^2[1+(q-1){\epsilon }^2]lnq}\left({\epsilon }^2,-,\frac{2(q-2)}{qlnq+2q-2},,\epsilon ,-,\frac{2-\frac{qlnq}{q-1}}{qlnq+2q-2}\right).\hfill \end{array}$$It is easy to check that when $q\in \{2,3,4\}$, then we have$$\begin{array}{c}\hfill 0\le \frac{2(q-2)}{qlnq+2q-2}<1,Q^{\prime }(0)>0,Q^{\prime }(1)<0.\end{array}$$Therefore exactly one of the two roots for $Q^{\prime }(\epsilon )$ lies in the desired range $0<\epsilon <1$, and $Q(\epsilon )$ attains local maximum at that point. Since $Q(0)=Q(1)=0$, we conclude that $Q(\epsilon )$ is positive for $0<\epsilon <1$, and therefore (44) holds for $R=\frac{1-\epsilon }{1+(q-1)\epsilon }$.

Now by Lemma 6, we see that Eq. (44) holds for $R\in \left[\frac{1-\epsilon }{1+(q-1)\epsilon },,,\frac{1-\epsilon }{1+(q-1){\epsilon }^2}\right]$ when $q=2,3,4$. This completes the proof of Theorem 3.

Acknowledgements

The authors would like to acknowledge the editor and anonymous reviewers for their valuable comments and suggestions to improve our manuscript.

Author contributions

First draft: C. H. Chan and M. Xiong wrote the statements of main theorems, lemmas as well as their proofs and also prepared Figures 1 and 2. M. Xiong wrote the background part of the introduction section. F.-W. Fu provided the main initiation and motivation of doing this work. All authors reviewed the manuscript. Revision: C. H. Chan responded to and made most of the required revisions suggested by Reviewer 1, except for Point 7. M. Xiong responded to Point 7 of Reviewer 1 by inserting two tables of simulating data on the error probabilities under the three different decoding principles after the statement of the main theorem, and also responded to most of the comments from Reviewer 2. F.-W. Fu provided some extra ideas on the responses to the comments from Reviewer 2. All authors reviewed the manuscript again to make sure it is typo-free and contents (especially formulas) not far beyond margin after making the above revisions.

Funding

Open access funding provided by Hong Kong University of Science and Technology.

Data availability

No datasets were generated or analysed during the current study.

Declarations

Conflict of interest

The authors declared that they hav no conflict of interest.

L. Mérai

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

References

1. Berlekamp, ER. The technology of error-correcting codes. Proc. IEEE; 1980; 68, 5 pp. 564-593. [DOI: https://dx.doi.org/10.1109/PROC.1980.11696] 0166.04803

2. Byers, J.W., Luby, M., Mitzenmacher, M., Rege, A.: A digital fountain approach to reliable distribution of bulk data. In: Proc. ACM SIGCOMM Conf. Appl., Technol., pp. 56–67. Architectures, Protocols Comput. Commun., Vancouver (1998).

3. Cover, TM; Thomas, JA. Elements of Information Theory; 1991; 1 New York, Wiley-Interscience: 0762.94001

4. Di, C; Proietti, D; Telatar, IE; Richardson, TJ; Urbanke, RL. Finite-length analysis of low-density parity-check codes on the binary erasure channel. Special issue on Shannon theory: perspective, trends, and applications. IEEE Trans. Inform. Theory; 2002; 48, 6 pp. 1570-1579.1909473 [DOI: https://dx.doi.org/10.1109/TIT.2002.1003839] 1061.94081

5. Didier, F. A new upper bound on the block error probability after decoding over the erasure channel. IEEE Trans. Inform. Theory; 2006; 52, 10 pp. 4496-4503.2300833 [DOI: https://dx.doi.org/10.1109/TIT.2006.881719] 1263.94041

6. Fashandi, S., Gharan, S.O., Khandani, A.K.: Coding over an erasure channel with a large alphabet size. In: Proc. 2008 IEEE Int. Symp. Inform. Theory, pp. 1053–1057 (2008).

7. Gallager, R.G.: Low Density Parity Check Codes. MIT Press (1963); IRE Trans. IT-8, pp. 21–28. Cambridge (1962).

8. Gallager, RG. Information Theory and Reliable Communication; 1968; New York, Wiley: 0198.52201

9. Lemes, L.C., Firer, M.: Generalized weights and bounds for error probability over erasure channels. In: Proc. Inf. Theory Appl. Workshop (ITA), p. 108. San Diego (2014).

10. Liva, G; Paolini, E; Chiani, M. Bounds on the error probability of block codes over the $q$-ary erasure channel. IEEE Trans. Inform. Theory; 2013; 61, 6 pp. 2156-2165.1473.94155

11. Luby, M., Mitzenmacher, M., Shokrollahi, A., Sipelman, D.A., Stemann, V.: Practical loss-recilient codes. In: Proc. 29th Annual ACM Symp. Theory Comput., pp. 150–159 (1997).

12. Lun, DS; Médard, M; Koetter, R; Effros, M. On coding for reliable communication over packet networks. Phys. Commun.; 2008; 1, 1 pp. 3-20. [DOI: https://dx.doi.org/10.1016/j.phycom.2008.01.006] 1328.94076

13. MacWilliams, F.J., Sloane,N.J.A.: The Theory of Error-Correcting Codes. North-Holland Mathematical Library, vol. 16. Amsterdam (1981).

14. Shen, L; Fu, F-W. The decoding error probability of linear codes over the erasure channel. IEEE Trans. Inform. Theory; 2019; 65, 10 pp. 6194-6203.4009198 [DOI: https://dx.doi.org/10.1109/TIT.2019.2926075] 1432.94217

15. Viterbi, AJ; Omura, JK. Principles of Digital Communication and Coding; 1979; New York, McGraw-Hill: 0495.94002

16. Wadayama, T. On the undetected error probability of binary matrix ensemblesl. IEEE Trans. Inform. Theory; 2010; 56, 5 pp. 2168-2176.2729778 [DOI: https://dx.doi.org/10.1109/TIT.2010.2043872] 1366.94770

17. Weber, JH; Abdel-Ghaffar, KAS. Results on parity-check matrices with optimal stopping and/or dead-end set enumerators. IEEE Trans. Inform. Theory; 2008; 54, 3 pp. 1368-1374.2450129 [DOI: https://dx.doi.org/10.1109/TIT.2007.915923] 1311.94122

18. Xiong, M. Decoding error probability in the erasure channel and the $r$-th support weight distribution. Sci. Sin. Math.; 2021; 51, pp. 1-14. [DOI: https://dx.doi.org/10.1360/SSM-2021-0019] 1456.76161 (in Chinese)