On the Probability of Incorrect Decoding for Linear Codes

Abstract

In the literature of Error Correcting Codes (ECC) there are many probabilistic characterizations of different events that happen in the decoding process. Historically, the most considered parameters in the performance of a linear code are the Probability of Undetected Error and the probability of incorrect decoding, also known as Probability of Miscorrected Error. While there is agreement about the first, starting from the Seventies, basically four definitions of the Probability of Miscorrected Error are present in literature; aim of this work is to show that they are equivalent and, although different in the mathematical formulation, they yield exactly the same result. The gap of this missing proof is herein fulfilled and two examples with interesting properties are given.

1 Introduction

The performance of a (linear) error correcting code can be evaluated on the basis of many parameters. Depending on the application studied, one can focus on the distance of the code, its dimension, the information rate; or one can investigate what happens when the number of errors in transmission is greater than the correction capability of the code. Those events are studied in terms of error probabilities. In the decoding process, the events of major interest have an associated probability, in particular, the Probability of Correct Decoding ($\mathbb {P}_{\mathrm {CD}}$), the Probability of Undetected Error ($\mathbb {P}_{\mathrm {UE}}$) and the Probability of Miscorrected Error ($\mathbb {P}_{\mathrm {ME}}$), [15]. The presence of an undetected error is especially important when related to safety, e.g. when the codewords represent a feedback for danger. A miscorrected error can have heavy consequences when the wrong information can corrupt a whole set of data, that is, the cost of incorrect decoding is high, for example in data storage applications or in the 3D reconstruction of a human body [1].

There are four formulations for the $\mathbb {P}_{\mathrm {ME}}$ and they have been derived by different authors from different points of view, also the mathematical expression is not the same but after a computer implementation and evaluation of the four formulas, it becomes clear that they give the same result. Therefore it is interesting to prove their equivalence, which is missing in literature.

The work has this structure: Sect. 2 gives a short review of the names, conventions and standard use of symbols for ECC that will be useful for Sect. 3, where the four formulations of $\mathbb {P}_{\mathrm {ME}}$ are stated and the equivalence theorem is proved. Section 4 presents a comparison of the results of bruteforce decoding (maximum likelihood) with the theoretical results of the probability of miscorrected error. Section 5 contains comments and conclusions on those four different formulas proposed in literature.

2 Background and Framework

Let $\mathcal {C}$ be an [n, k, d] linear code over $\mathbb {F}_{q}$ with weight distribution $A_0,A_1,\dots , A_n$ and let the symbol error probability on a $q-$ary alphabet be p. The probability that a symbol is correctly transmitted over the channel is then $1-p$. Assume that if an error does occur, then each of the $q-1$ symbols aside from the correct symbol is equally likely to be received, with probability $\frac{p}{q-1}$ each. This hypothetical channel is called the $q-$ary symmetric channel or $q-\mathrm {SC}$ for short, [4]. This is a standard framework in ECC.

Let $\tau$ be the number of errors that occurred in transmission. If $\tau =0$ the decoder does not detect any error and does not decode the received vector, as it is in the code already. If $1\le \tau \le t$, where $t:=\lfloor \frac{d-1}{2}\rfloor$, the decoder detects the error and corrects it to the unique codeword at distance less than t from the received vector. However, if $\tau >t$ three models of decoder must be considered: the ideal bounded distance decoder, the maximum likelihood decoder and other types (e.g. Berlekamp-Massey, etc.). If more than t errors occur, two situations can happen: (a) there is a unique codeword at distance at most t from the received vector; (b) there is no codeword at a distance lower than $t+1$ from the received vector. In case (a), every decoder will clearly correct the vector to that unique codeword, and the correction will be wrong, see Fig. 1. In case (b), the decoders exhibit different behaviours: the ideal bounded distance decoder will not attempt to correct the vector and will raise a flag of decoding failure; the maximum likelihood decoder will correct the vector to its closest codeword (which may not be unique); for other decoders the behaviour is not specified, see Figure 2.

Fig. 1.

Suppose to send v and receive $v+e$, i.e. the triangle inside the decoding sphere of $v_1$, in this case every decoder will correct $v+e$ to $v_1$ thus making a correction error.

Fig. 2.

Suppose to send v and receive $v+e$, i.e. the triangle outside any decoding sphere (in gray around each codeword). In this case the ideal decoder will raise a message of decoding failure, whereas the maximum likelihood decoder will decode to the closest codeword around $v+e$, that is $v_2$ in that picture.

Remark 1

As a remark, notice that the algorithm of Berlekamp-Massey can be approximated with an ideal decoder. This algorithm is based on the error locator polynomial, which has the properties that its roots give the locations of the errors occurred in transmission (for instance [3] for a Gröbner Basis derivation). For a number of errors $\tau \le t$ the roots of the locator polynomial are valid positions and the correction is unambiguous. If there are more than t errors, the following cases can happen: 1. there exists a codeword at distance lower than t from the received vector and this produces a wrong correction; 2a. there does not exist any codeword at distance lower than $t+1$ from the received vector and the decoder corrects wrong, 2b. as in 2a but the decoder corrects to the sent codeword, 2c. there does not exist any codeword at distance lower than $t+1$ from the received vector, but not all the roots of the locator polynomial are valid positions, the decoder sends a message of decoding failure. The case 2b cannot happen in practice because in this instance the locator polynomial will have a degree higher than t, but in an implementation, the decoding process will be stopped after degree t.

After these considerations about the decoders, we are interested in the probability of the miscorrected error for bounded distance decoders. It is important to notice that this decoding scheme is incomplete because not all possible received vectors will have a distance less than t from a codeword, that is, inside a decoding sphere, [12]. An example where the sent codeword is outside of any decoding sphere is presented in Section 4, see also [10] for details about the decoding spheres. Consider the reliability of a bounded distance decoder. A codeword c sent over the channel is correctly decoded at the receiving end by the decoder if the decoder receives any vector in the sphere of radius $t=\lfloor \frac{d-1}{2}\rfloor$ around c, yielding a lower bound on the probability that a transmitted codeword is correctly decoded.

There are several different ways to characterize the error detecting and correcting capabilities of codes at the output of the channel decoder. Those are widely accepted definitions and they can be found in many references e.g. in [2, 5, 7, 11, 14].

$\mathbb {P}_{\mathrm {CD}}(p)$ is the probability of correct decoding, which is the probability that a codeword c sent over the channel is correctly decoded at the receiving end by the decoder, and can be computed by:

$$\begin{aligned} \mathbb {P}_{\mathrm {CD}}(p)=\sum _{i=0}^t\left( {\begin{array}{c}n\\ i\end{array}}\right) p^i(1-p)^{n-i}. \end{aligned}$$

Note that this probability is independent of the size of the alphabet. $\mathbb {P}_{\mathrm {UE}}(p)$ is the probability of undetected error, the probability that errors occurring in a codeword are not detected. An error vector moves the transmitted codeword into another codeword, and this probability is therefore

$$\begin{aligned} \mathbb {P}_{\mathrm {UE}}(p)=\sum _{i=d}^nA_i \left( \dfrac{p}{q-1}\right) ^i(1-p)^{n-i}. \end{aligned}$$

$\mathbb {P}_{\mathrm {E}}(w)$ is the probability of miscorrected error conditioned to an error of weight w. This is the probability that the codeword at the output of the decoder is not the same as the codeword produced by the encoder, with the condition that an error of weight w occurred. $\mathbb {P}_{\mathrm {ME}}(p)$ is the probability of miscorrected error. This is the probability that the decoder outputs a wrong codeword. It depends only on the code (it is important to note that knowledge of the weight distribution is required) and on the channel.

Whereas for the probabilities of correct decoding and undetected error there is agreement in the definition among all authors, the situation is very different for the $\mathbb {P}_{\mathrm {ME}}$. In the literature there are four definitions of $\mathbb {P}_{\mathrm {ME}}$, only one of them (proposed by [5]) involves the definition of $\mathbb {P}_{\mathrm {E}}(w)$, the others directly assume the presence of the $q-$ary symmetric channel. The study of the $\mathbb {P}_{\mathrm {ME}}$ in terms of the $\mathbb {P}_{\mathrm {E}}(w)$ brings more insight in what happens when the number of errors increases, therefore it is herein briefly summarized.

In order to proceed, define the quantity $N(\ell ,w;s)$ as the number of vectors of weight w that are at distance s from a fixed codeword of weight $\ell$. If w is not such that $\ell -s \le w \le \ell +s$, then $N(\ell ,w;s)=0$. $N(\ell ,w;s)$ is independent of the given codeword of weight $\ell$ and is hence well defined ([5]). For $s\le t$, spheres of radius s about codewords are disjoint and hence the number of vectors of weight w at distance exactly s from a codeword of weight $\ell$ is $A_\ell \cdot N(\ell ,w;s)$. Now received vectors which will be improperly decoded are those which lie within a sphere of radius t about some codeword other than that which was sent. Call $C_w$ the number of these vectors, clearly

$$\begin{aligned} C_w=\sum _{\ell =0}^n A_\ell \sum _{s=0}^t N(\ell ,w;s) \quad \text{ for } t+1\le w \le n. \end{aligned}$$

This leads easily to the next lemma.

Lemma 1

The probability $\mathbb {P}_{\mathrm {E}}(w)$ is the probability of miscorrected error conditioned to an error of weight w and is characterized by

$$\begin{aligned} \mathbb {P}_{\mathrm {E}}(w)=\displaystyle \dfrac{C_w}{(q-1)^w\left( {\begin{array}{c}n\\ w\end{array}}\right) }. \end{aligned}$$

Proof

$\mathbb {P}_{\mathrm {E}}(w)$ is given by the ratio of the decodable vectors of weight w (i.e. $C_w$) by all possible vectors of weight w, which are $(q-1)^w\left( {\begin{array}{c}n\\ w\end{array}}\right)$.

The following lemma finds out the number $N(\ell ,w;s)$.

Lemma 2

The number $N(\ell ,w;s)$ of vectors of weight w that are at distance s from a fixed codeword of weight $\ell$ is zero if w is not such that $\ell -s \le w \le \ell +s$, otherwise is

$$\begin{aligned} N(\ell ,w;s)=\!\!\displaystyle \sum _{r=r_1}^{r_2}\left( {\begin{array}{c}\ell \\ \ell -s+r\end{array}}\right) \left( {\begin{array}{c}s-r\\ w-\ell +s-2r\end{array}}\right) \left( {\begin{array}{c}n-\ell \\ r\end{array}}\right) (q-2)^{w-\ell +s-2r} (q-1)^r, \end{aligned}$$

where $r_1:=\max \{0,w-\ell \}$ and $r_2:=\lfloor \frac{w-\ell +s}{2} \rfloor$. Note that $\lfloor x \rfloor$ is the larger integer less than or equal to x and that $\left( {\begin{array}{c}x\\ y\end{array}}\right)$ is zero if $y \not \in \mathbb {N}$.

Proof

See [5].    $\square$

Corollary 1

In the case of binary linear codes $q=2$ and the previous lemma simplifies to

$$\begin{aligned} N(\ell ,w;s)=\left\{ \begin{array}{cc} \displaystyle \left( {\begin{array}{c}n-\ell \\ \frac{s+w-\ell }{2}\end{array}}\right) \left( {\begin{array}{c}\ell \\ \frac{s-w+\ell }{2}\end{array}}\right) &{}\textit{ if } \displaystyle |w-\ell |\le s\\ &{} \\ 0 &{} \textit{ if } |w-\ell |> s. \\ \end{array} \right. \end{aligned}$$

Once the weight distribution of $\mathcal {C}$ and $\mathbb {P}_{\mathrm {E}}(w)$ are known, the formula for the probability that the decoder outputs a wrong codeword is given by the next theorem.

Theorem 1

The probability of miscorrected error $\mathbb {P}_{\mathrm {ME}}(p)$ depends only on the code $\mathcal {C}$ and on the channel $\phi$, and is

$$\begin{aligned} \mathbb {P}_{\mathrm {ME}}(p):=\mathbb {P}_{\mathrm {ME}}(\mathcal {C},\phi )= \sum _{w=t+1}^n\mathbb {P}_{\mathrm {E}}(w)\phi (w), \end{aligned}$$

(1)

where $\phi (w)$ is the probability of w errors in transmission. In the case of the $q-$ary symmetric channel $\phi (w)$ has the classic form

$$\begin{aligned} \phi (w)=\left( {\begin{array}{c}n\\ w\end{array}}\right) (q-1)^w \left( \dfrac{p}{q-1}\right) ^w(1-p)^{n-w}. \end{aligned}$$

Corollary 2

In the $q-$ary symmetric channel, the probability of miscorrected error (1) simplifies to

$$\begin{aligned} \mathbb {P}_{\mathrm {ME}}(\mathcal {C},q-\mathrm {SC})= \sum _{w=t+1}^nC_w \left( \dfrac{p}{q-1}\right) ^w\left( 1-p\right) ^{n-w}. \end{aligned}$$

It may be difficult to compute exactly this probability because the weight distribution of a linear code (or even just the minimum distance) is in general not known, [9]. In these cases the weight distribution can be approximated by suitable estimates and (1) becomes a bound.

3 Unified Probability of Miscorrected Error

This section collects the four formulations of the $\mathbb {P}_{\mathrm {ME}}$ found from different authors in literature. They are reported in four lemmas identified with the letters A, B, C and D. The corresponding expression for the $\mathbb {P}_{\mathrm {ME}}$ has a superscript with the matching letter. In the previous section the approach of [5] was presented, which turns out to be the most followed (Lemma 5), maybe because it was the first proposed. In [2] there is a historical description and bibliography of the papers and previous results that yield to [5]. With the aim of keeping the paper contained, the derivation of the four characterizations is skipped, but can be easily retrieved in each of the cited references.

Lemma 3

([13]).

$$\begin{aligned} \mathbb {P}_{\mathrm {ME}}^A(p)= & {} \sum _{\ell =2t+1}^n A_{\ell }\sum _{s=0}^t \sum _{r=0}^{t-s} \left( {\begin{array}{c}n-\ell \\ s\end{array}}\right) \left( {\begin{array}{c}\ell \\ r\end{array}}\right) \\&\cdot (q-1)^{r-\ell }\left( 1-\dfrac{p}{q-1}\right) ^r (1-p)^{n-\ell -s}p^{\ell +s-r}. \end{aligned}$$

Lemma 4

([8, 12, 14]).

$$\begin{aligned} \mathbb {P}_{\mathrm {ME}}^B(p)= & {} \sum _{\ell =2t+1}^n A_{\ell }\sum _{s=0}^t \sum _{r=0}^{s} \left( {\begin{array}{c}n-\ell \\ r\end{array}}\right) \left( {\begin{array}{c}\ell \\ s-r\end{array}}\right) \\&\cdot \left( \dfrac{p}{q-1}\right) ^{\ell -s+r}\left( 1-\dfrac{p}{q-1}\right) ^{s-r} (1-p)^{n-\ell -r}p^{r}. \end{aligned}$$

Lemma 5

([2, 5, 6]). For $r_1$ and $r_2$ as defined in Lemma 2,

$$\begin{aligned} \mathbb {P}_{\mathrm {ME}}^C(p)= & {} \sum _{\ell =0}^n A_{\ell }\sum _{s=0}^t \sum _{w=t+1}^{n} \sum _{r=r_1}^{r_2} \left( {\begin{array}{c}n-\ell \\ r\end{array}}\right) \\&\cdot \left( {\begin{array}{c}\ell \\ \ell -s+r\end{array}}\right) \left( {\begin{array}{c}s-r\\ w-\ell +s-2r\end{array}}\right) \left( \dfrac{p}{q-1}\right) ^w (1-p)^{n-w}\\&\cdot (q-2)^{w-\ell +s-2r}(q-1)^r. \end{aligned}$$

Lemma 6

([11]).

$$\begin{aligned} \mathbb {P}_{\mathrm {ME}}^D(p)= & {} \sum _{w=t+1}^n \left( \dfrac{p}{q-1}\right) ^w (1-p)^{n-w}\\&\sum _{\ell =\max (w-t,d)}^{\min (w+t,n)}A_{\ell } \sum _{s=|l-w|}^{t} \sum _{r=0}^{s} \left( {\begin{array}{c}\ell \\ r\end{array}}\right) \left( {\begin{array}{c}n-\ell \\ r+w-\ell \end{array}}\right) \left( {\begin{array}{c}\ell -r\\ s+\ell -w-2r\end{array}}\right) \\&\cdot (q-2)^{s+\ell -w-2r}(q-1)^{r+w-\ell }. \end{aligned}$$

A final technical lemma is needed in order to prove the main theorem of this section.

Lemma 7

The following identity holds:

$$\begin{aligned} \quad \sum _{j=0}^{s-r}\left( {\begin{array}{c}s-r\\ j\end{array}}\right) (q-2)^j(1-p)^{s-r-j}(q-1)^{r-s}\\ =\sum _{j=0}^{s-r}\left( {\begin{array}{c}s-r\\ j\end{array}}\right) \left( \dfrac{p}{q-1}\right) ^j(q-2)^j(1-p)^{s-r-j}, \end{aligned}$$

which, in particular, is equal to $\left( \frac{q-p-1}{q-1}\right) ^{s-r}$.

Proof

Follows easily with Newton’s Binomial Theorem.    $\square$

Theorem 2

(Unified Error Probability). The four Lemmas 3, 4, 5 and 6 are equivalent.

Proof

The proof is divided in three parts: Lemma 3 $\iff$ Lemma 4, then Lemma 5 $\iff$ Lemma 6 and finally Lemma 4 $\iff$ Lemma 5. First consider the equivalence of Lemma 3 and Lemma 4. The outer sum over $\ell$ is the same in (3) and (4), hence look at the inner part only. Starting from the binomial part of equation (4), the first observation is that $s\le t$ and $r\le s$, otherwise the binomial $\left( {\begin{array}{c}\ell \\ s-r\end{array}}\right)$ would become zero because of $s-r<0$. It is possible to rewrite (4) as

$$\begin{aligned} \sum _{\ell =2t+1}^n A_{\ell }\sum _{s=0}^t \sum _{r=0}^{t} \left( {\begin{array}{c}n-\ell \\ r\end{array}}\right) \left( {\begin{array}{c}\ell \\ s-r\end{array}}\right) \left( \dfrac{p}{q-1}\right) ^{\ell -s+r}\!\!\!\left( 1-\dfrac{p}{q-1}\right) ^{s-r} (1-p)^{n-\ell -r}p^{r} \end{aligned}$$

and the swap r with s yields

$$\begin{aligned} \sum _{\ell =2t+1}^n A_{\ell }\sum _{s=0}^t \sum _{r=0}^{t} \left( {\begin{array}{c}n-\ell \\ s\end{array}}\right) \left( {\begin{array}{c}\ell \\ r-s\end{array}}\right) \left( \dfrac{p}{q-1}\right) ^{\ell -r+s}\!\!\!\left( 1-\dfrac{p}{q-1}\right) ^{r-s} (1-p)^{n-\ell -s}p^{s} \end{aligned}$$

Observing that the terms of the sum for the index $r=0,1,\ldots , s-1$ are zero, the previous expression is simplified (with the index substitution $k=r-s$, $r=k+s$) in

$$\begin{aligned} \sum _{\ell =2t+1}^n A_{\ell }\sum _{s=0}^t \sum _{k=0}^{t-s} \left( {\begin{array}{c}n-\ell \\ s\end{array}}\right) \left( {\begin{array}{c}\ell \\ k\end{array}}\right) \cdot (q-1)^{k-\ell }\left( 1-\dfrac{p}{q-1}\right) ^{k} (1-p)^{n-\ell -s}p^{\ell +s-k}. \end{aligned}$$

After relabelling k with r, the result is exactly the same as $\mathbb {P}_{\mathrm {ME}}^A(p)$ given in (3). Thus Lemma B is equivalent to Lemma A.

Equivalence of Lemmas 5 and 6. Consider now Lemma 5, a preventive simplification shows that the index of the outer sum over $\ell$ can be made start from $d=2t+1$ because for $\ell =0$ the binomial term $\left( {\begin{array}{c}\ell \\ \ell -s+r\end{array}}\right) =0$. Then for $\ell =1,\ldots , 2t$ the weights $A_\ell$ of the code are all zero. The same binomial can be substituted by symmetry with $\left( {\begin{array}{c}\ell \\ s-r\end{array}}\right)$. With similar reasoning on the binomials, it is possible to make the summation over r run from $r_1=w-l$ or 0 to $r_2=w-l+s$. In fact, e.g. for $r_2$, the binomial $\left( {\begin{array}{c}s-r\\ (w-l+s)-2r\end{array}}\right)$ will have a negative argument and thus is zero. Similarly, when $r_1$ is negative the first binomial has a negative argument, and for $0\le r_1 < |w-l|$ the last binomial is zero. Hence the bounds $r_1$ and $r_2$ by [5] are very accurate and reduce the effort of computation over dummy indexes. Rewrite Lemma 5 as

$$\begin{aligned} \mathbb {P}_{\mathrm {ME}}^C(p)= & {} \sum _{\ell =2t+1}^n A_{\ell }\sum _{s=0}^t \sum _{w=t+1}^{n} \sum _{r=w-l}^{w-l+s} \left( {\begin{array}{c}n-\ell \\ r\end{array}}\right) \left( {\begin{array}{c}\ell \\ s-r\end{array}}\right) \left( {\begin{array}{c}s-r\\ w-\ell +s-2r\end{array}}\right) \nonumber \\&\cdot \left( \dfrac{p}{q-1}\right) ^w (1-p)^{n-w} \cdot (q-2)^{w-\ell +s-2r}(q-1)^r.\qquad \end{aligned}$$

(2)

In the formula (6) of Lemma 6, notice that $r,s\le t$ so that $r+s< 2t+1 = d$. The sum over $\ell$ can run just over $\ell =d,\ldots ,n$, because if $\ell -w>t$ the binomial $\left( {\begin{array}{c}n-\ell \\ r+w-\ell \end{array}}\right) =\left( {\begin{array}{c}n-l\\ r-(l-w)\end{array}}\right)$ will have a negative argument and is therefore zero, when $\ell -w < -t$, the third binomial has a negative argument. Thus it is possible to swap the sum over $\ell$ with the sum over w and obtain,

$$\begin{aligned} \mathbb {P}_{\mathrm {ME}}^D(p)= & {} \sum _{\ell =2t+1}^n A_{\ell }\sum _{w=t+1}^{n} \sum _{s=|l-w|}^{t} \sum _{r=0}^{s} \left( {\begin{array}{c}\ell \\ r\end{array}}\right) \left( {\begin{array}{c}n-\ell \\ r+w-\ell \end{array}}\right) \left( {\begin{array}{c}\ell -r\\ s+\ell -w-2r\end{array}}\right) \\&\cdot \left( \dfrac{p}{q-1}\right) ^w (1-p)^{n-w} \cdot (q-2)^{s+\ell -w-2r}(q-1)^{r+w-\ell }. \end{aligned}$$

Now with the change of variable $r\rightarrow r+w-\ell$ the new sum over r runs from $w-\ell$ to $s+w-l$, and the first binomial becomes, by symmetry, $\left( {\begin{array}{c}\ell \\ w-\ell \end{array}}\right)$. Observe then that the index s runs from t to zero, therefore it is possible to reorder the sum for $s=0,\ldots , t$. Those simplifications lead to

$$\begin{aligned} \mathbb {P}_{\mathrm {ME}}^D(p)= & {} \sum _{\ell =2t+1}^n A_{\ell }\sum _{w=t+1}^{n} \sum _{s=0}^{t} \sum _{r=w-\ell }^{s+w-\ell } \left( {\begin{array}{c}\ell \\ w-r\end{array}}\right) \left( {\begin{array}{c}n-\ell \\ r\end{array}}\right) \left( {\begin{array}{c}w-r\\ s+w-\ell -2r\end{array}}\right) \\&\left( \dfrac{p}{q-1}\right) ^w (1-p)^{n-w} \cdot (q-2)^{r}(q-1)^{s+w-\ell -2r}, \end{aligned}$$

which resembles equation (2) apart from the role of w in the three binomials. After a sharp look, it is possible to substitute the missing s with the w without changing the result, because of a combined simplification of the binomials, in particular:

$$\begin{aligned} \quad \left( {\begin{array}{c}n-\ell \\ r\end{array}}\right) \left( {\begin{array}{c}\ell \\ w-r\end{array}}\right) \left( {\begin{array}{c}w-r\\ s+w-\ell -2r\end{array}}\right) = \left( {\begin{array}{c}n-\ell \\ r\end{array}}\right) \left( {\begin{array}{c}\ell \\ s-r\end{array}}\right) \left( {\begin{array}{c}s-r\\ w-\ell +s-2r\end{array}}\right) , \end{aligned}$$

which can be easily verified expanding with factorials. Therefore $\mathbb {P}_{\mathrm {ME}}^C(p)=\mathbb {P}_{\mathrm {ME}}^D(p)$.

The last part of the proof is that Lemma 4 is equivalent to Lemma 5: in Lemma 4 consider the quantity $1-p/(q-1)$, it can be recast into $[(q-2)+(1-p)]/(q-1)$. Therefore, with Newton’s Binomial Theorem, $[1-p/(q-1)]^{s-r}$ becomes

$$\begin{aligned} \dfrac{1}{(q-1)^{s-r}}\sum _{j=0}^{s-r}\left( {\begin{array}{c}s-r\\ j\end{array}}\right) (q-2)^j(1-p)^{s-r-j}. \end{aligned}$$

Hence, Lemma 4 can be expanded as,

$$\begin{aligned} \mathbb {P}_{\mathrm {ME}}^B(p)= \sum _{\ell =2t+1}^n A_{\ell }\sum _{s=0}^t \sum _{r=0}^{s}\sum _{j=0}^{s-r} \left( {\begin{array}{c}n-\ell \\ r\end{array}}\right) \left( {\begin{array}{c}\ell \\ s-r\end{array}}\right) \left( {\begin{array}{c}s-r\\ j\end{array}}\right) \\ \cdot \left( \dfrac{p}{q-1}\right) ^{\ell -s+r} (q-1)^{r-s}(q-2)^j(1-p)^{n-\ell -2r+s-j}p^r, \end{aligned}$$

where, after collecting terms,

$$\begin{aligned} \mathbb {P}_{\mathrm {ME}}^B(p)= & {} \sum _{\ell =2t+1}^n A_{\ell }\sum _{s=0}^t \sum _{r=0}^{s} \left( {\begin{array}{c}n-\ell \\ r\end{array}}\right) \left( {\begin{array}{c}\ell \\ s-r\end{array}}\right) \\&\cdot \left( \dfrac{p}{q-1}\right) ^{\ell -s+2r}(q-1)^r(1-p)^{n-\ell -r}\\&\cdot \sum _{j=0}^{s-r} \left( {\begin{array}{c}s-r\\ j\end{array}}\right) (q-1)^{r-s-j}(q-2)^j(1-p)^{s-r-j}. \end{aligned}$$

It is now possible to make use of Lemma 7 and substitute the last sum over j as follows:

$$\begin{aligned} \mathbb {P}_{\mathrm {ME}}^B(p)= & {} \sum _{\ell =2t+1}^n A_{\ell }\sum _{s=0}^t \sum _{r=0}^{s}\sum _{j=0}^{s-r}\left( {\begin{array}{c}n-\ell \\ r\end{array}}\right) \left( {\begin{array}{c}\ell \\ s-r\end{array}}\right) \left( {\begin{array}{c}s-r\\ j\end{array}}\right) \\&\cdot \left( \dfrac{p}{q-1}\right) ^{j+\ell -s+2r}(q-1)^r(q-2)^j(1-p)^{n-(j+\ell -s+2r)}. \end{aligned}$$

The substitution $w=j+\ell -s+2r$ yields something that is almost equal to the modified version of Lemma 5 in equation (2):

$$\begin{aligned} \sum _{\ell =d}^n A_{\ell }\sum _{s=0}^t \sum _{r=0}^{s}\sum _{w=\ell -s+2r}^{\ell +r} \left( {\begin{array}{c}n-\ell \\ r\end{array}}\right) \left( {\begin{array}{c}\ell \\ s-r\end{array}}\right) \left( {\begin{array}{c}s-r\\ w-\ell +s-2r\end{array}}\right) \\ \cdot \left( \dfrac{p}{q-1}\right) ^{w}(q-1)^{r}(q-2)^{w-\ell +s-2r}(1-p)^{n-w}. \end{aligned}$$

The differences with (2) are the order of the inner sums. To exchange the sum over r with the sum over w, the new indexes must be $w=\ell -s,\ldots ,\ell +s$ and $r=w-\ell ,\ldots ,w-\ell +s$, where the upper limit of r was simplified using the same consideration on the third binomial discussed above for $r_2$. With similar considerations it is possible to extend the range of w to $w=t+1,\ldots ,n$, because for values smaller than $\ell -s$ the first binomial will have a negative r and for values greater than $\ell +s$ the other binomials will have negative argument. The result is exactly $\mathbb {P}_{\mathrm {ME}}^C(p)$ and the proof is complete.    $\square$

4 An Application with Numerical Results

$\mathbb {P}_{\mathrm {D}}(p)$ is the probability of detected codeword error, the probability that one or more errors occurring in a codeword are detected. $\mathbb {P}_{\mathrm {F}}(p)$ is the probability of decoder failure, which is the probability that the decoder is unable to decode the received vector (and is able to determine that it cannot decode). The following check is performed: comparison between the theoretical $\mathbb {P}_{\mathrm {E}}(w)$ and the “real” one, obtained by bruteforce decoding, this last identified as $\mathbb {P}_{\mathrm {E}}^\mathrm {r}(w)$. Suppose to send the zero codeword, if an arbitrary error occurs, it is possible to receive every possible vector of $( \mathbb {F}_{q})^n$. After the correction, five cases can happen:

• 1. the received vector lies in the correct decoding sphere and is decoded to the sent word;

• 2. the received vector lies in a wrong decoding sphere and is decoded to a wrong codeword;

• 3. the vector is outside of any decoding sphere but is close to only one codeword and is decoded to the sent word;

• 4. the vector is outside of any decoding sphere but is close to only one codeword and is decoded to a wrong codeword;

• 5. the vector is outside of any decoding sphere and there are more codewords at the same distance, so a decoding failure happens.

In the next examples all decoded vectors (according to the weight w of the error) are divided in three sets: the set $D_w$ of the vectors correctly decoded (cases 1 and 3), the set $S_w$ of the miscorrected vectors (cases 2 and 4), and the set of the failures $F_w$ (case 5). The number $C_w$ gives the number of elements of case 2, hence they are expected to be $|S_w|\ge C_w$. Furthermore $|S_0|, \dots , |S_t|$ should be all zero. The next two toy examples show a case on $\mathbb {F}_{2}$ where $|S_w|= C_w$ and a case on $\mathbb {F}_{3}$ where $|S_w|> C_w$.

4.1 Example over $\mathbb {F}_{2}$

Let C be the linear code [5, 2, 3] over $\mathbb {F}_{2}$ with generator matrix

$$ G=\left( \begin{array}{ccccc} 1 &{} 0 &{} 1 &{} 0 &{} 1\\ 0 &{} 1 &{} 0 &{} 1 &{} 1\\ \end{array} \right) . $$

In this example there is no difference between the theorical formula and the bruteforce, see Table 1.

Table 1. Results for the linear code [5, 2, 3] over $\mathbb {F}_{2}$. $A_w$ is the weight distribution, $|D_w|$ is the number of the vectors correctly decoded, $|F_w|$ the number of failures, $|S_w|$ the number of miscorrected vectors, $|C_w|$ the number of vectors in the wrong decoding sphere.

4.2 Example over $\mathbb {F}_{3}$

Let C be the linear code [5, 2, 3] over $\mathbb {F}_{3}$ with generator matrix

$$ G=\left( \begin{array}{ccccc} 1 &{} 0 &{} 1 &{} 2 &{} 0 \\ 0 &{} 1 &{} 0 &{} 1 &{} 1\\ \end{array} \right) $$

In this example there are some vectors outside the decoding spheres, the results are collected in Table 2. Notice that $|S_w|>C_w$ and so $\mathbb {P}_{\mathrm {E}}^\mathrm {r}(w) \ge \mathbb {P}_{\mathrm {E}}(w)$.

Table 2. Results for the linear code [5, 2, 3] over $\mathbb {F}_{3}$. $A_w$ is the weight distribution, $|D_w|$ is the number of the vectors correctly decoded, $|F_w|$ the number of failures, $|S_w|$ the number of miscorrected vectors, $|C_w|$ the number of vectors in the wrong decoding sphere.

5 Comments and Conclusions

In the literature of ECC there are at least four different formulations of the probability of miscorrected error. They have been presented in Lemmas 3, 4, 5 and 6, with some comments for Lemma 5, probably the most known. It has been proved that they are equivalent, hence it is useful to point out what is the most practical formula in terms of complexity. The complexity of Lemmas 3 and 4 is the same, the number of iterations of the sums required to evaluate the $\mathbb {P}_{\mathrm {ME}}(p)$ is $\gamma =\frac{1}{2}(n-2t)(t+2)(t+1)\le n^3$, whereas for Lemmas 5 and 6 a rough estimate is $\gamma (n-t)\le n^4$, which is one factor greater. Nevertheless, formulation of $\mathbb {P}_{\mathrm {ME}}^C(p)$ gives information on the $\mathbb {P}_{\mathrm {E}}(w)$ which can be useful in some applications, where the number of errors beyond t has importance.