Bounds on the Probability of Undetected Error for q-Ary Codes

Abstract

We study the probability of an undetected error for general q-ary codes. We give upper and lower bounds on this quantity, by the Linear Programming and the Polynomial methods, as a function of the length, size, and minimum distance. Sharper bounds are obtained in the important special case of binary Hamming codes. Finally, several examples are given to illustrate the results of this paper.

1. Introduction

Let $A=\{a_1,\dots ,a_q\}$ be an alphabet with q distinct symbols, where $q⩾2$ and the alphabet do not have any structure. For instance, A can be ${\mathbb{F}}_q$, the finite field with q elements, or ${\mathbb{Z}}_q$, the ring of integers modulo q. Moreover, a linear $[n,k]$ code is a subspace of the vector space ${\mathbb{F}}_q^n$ and k is the dimension of the subspace. For every two vectors $\mathit{x}$, $\mathit{y}\in A^n$, the (Hamming) distance $d_H(\mathit{x},\mathit{y})$ between $\mathit{x}$ and $\mathit{y}$ is defined as the number of coordinates where they are different. A nonempty subset C of $A^n$ with cardinality M is called a q-ary $(n,M)$ code, whose elements are called codewords. The minimum distance d of the code C is the minimum distance between any two different codewords in C. The distance distribution of C is defined as

$$A_i=\frac{1}{M}\left|\{(\mathit{x},\mathit{y}):\mathit{x},\mathit{y}\in C,d_H(\mathit{x},\mathit{y})=i\}\right|,i=0, 1,\dots , n.$$

(1)

Assume that the code C is used for error detection on a discrete memoryless channel with q inputs and q outputs. Each symbol transmitted has a probability $1-p$ of being received correctly and a probability $p_q=p/(q-1)$ of being transformed into each of the $q-1$ other symbols. It is natural to let $0⩽p⩽(q-1)/q$. Such a channel model is called a q-ary symmetric channel $qSC\left(p\right)$. When such a code is used on the symmetric q-ary channel $qSC\left(p\right)$, errors occur with a probability $\frac{p}{q-1}$ per symbol.

Let $\mathit{x}\in C$ be the codeword transmitted and $\mathit{y}=\mathit{x}+\mathit{e}\in {\mathbb{F}}_q^n$ be the vector received, where $\mathit{e}=\mathit{y}-\mathit{x}$ is the error vector from the channel noise. Obviously, $\mathit{e}\in C$ if and only if $\mathit{y}\in C$. Note that the decoder will accept $\mathit{y}$ as error free if $\mathit{y}\in C$. Clearly, this decision is wrong, and such an error is not detected. Thus, when error detection is being used, the decoder will make a mistake and accept a codeword which is not the one transmitted if and only if the error vector is a nonzero codeword [1,2]. In this way, the probability that the decoder fails to detect the existence of an error is called the probability of undetected error and denoted by $P_{ue}(C,p)$, which is defined as

$$P_{ue}(C,p)=\sum _{j=1}^n{A}_j{\left(\frac{p}{q-1}\right)}^j{(1-p)}^{n-j}.$$

(2)

In general, the smaller the probability of undetected error $P_{ue}$ for some p, the better the code performs in error detection. However, this function is difficult to characterize in general.

As for the code C, comparing its $P_{ue}$ with the average probability $\overline{P_{ue}}$ [3,4] for the ensemble of all q-ary linear $[n,k]$ codes is a natural way to decide whether C is suitable for error detection or not, where

$$\overline{P_{ue}}\left(p\right)=q^{-(n-k)}\left(1-{(1-p)}^k\right).$$

According to [4], there exists a code C such that $P_{ue}(C,p)>q^{-(n-k)}$ and there are many codes, the $P_{ue}$ of each of whom is smaller than $q^{-(n-k)}$. In fact, it was commonly assumed that $P_{ue}(C,p)⩽q^{-(n-k)}$ for the linear $[n,k]$ code C in [5], where $q^{-(n-k)}=q^{-r}$ is called the $q^{-r}$ bound. The $q^{-r}$ bound is satisfied for certain specific codes, e.g., Hamming codes and binary perfect codes, when $0<p<1/2$.

For the worst channel condition, i.e., when $p=(q-1)/q$,

$$P_{ue}\left(C,\frac{q-1}{q}\right)=q^{-(n-k)}\left(1-{\left(1-\frac{q-1}{q}\right)}^k\right)=\overline{P_{ue}}\left(\frac{q-1}{q}\right).$$

From the above formula, a code C is called good if $P_{ue}(C,p)⩽P_{ue}((q-1)/q)$ for all $0<p<(q-1)/q$. In particular, if $P_{ue}(C,p)$ is an increasing function of p in the interval $[0,(q-1)/q]$, then the code is good, and the code is called proper. There are many proper codes [1], for example, perfect codes (and their extended codes and their dual codes), primitive binary 2-error correcting BCH codes, a class of punctured of Simplex codes, MDS codes, and near MDS codes (see [5,6,7,8,9] for details). Moreover, for practical purposes, a good binary code C may be defined a bit different, i.e., $P_{ue}(C,p)⩽c{P}_{ue}(C,1/2)$ for every $0⩽p⩽1/2$ and a reasonably small $c⩾1$. Furthermore, an infinite class $\mathcal{C}$ of binary codes is called uniformly good if there exists a constant c such that for every $0⩽p⩽1/2$ and $C\in \mathcal{C}$, the inequality $P_{ue}(C,p)⩽c{P}_{ue}(C,1/2)$ holds. Otherwise, it is called ugly, for example, some special Reed–Muller codes are ugly (see [10]).

Another way to assess the performance of a code for error detection is to give bounds of the probability of undetected error. In [11], Abdel-Ghaffar defined the combinatorial invariant $F_j$ of the code C and proved that

$$P_{ue}(C,p)=\sum _{j=1}^n{F}_j{\left(\frac{p}{q-1}\right)}^j{\left(1-\frac{qp}{q-1}\right)}^{n-j},$$

where

$$F_j=\sum _{i=1}^j{A}_i\left(\genfrac{}{}{0pt}{}{n-i}{n-j}\right),j=1, 2,\dots , n.$$

Using combinatorial arguments, Abdel-Ghaffar [11] obtained a lower bound on the undetected error probability $P_{ue}(C,p)$. Later, Ashikhmin and Barg called $F_j$ the binomial moments of the distance function and derived more bounds for $P_{ue}$ (see [12,13]).

In particular, constant weight codes are attractive and many bounds are developed, for example, binary constant weight codes (see [14,15]) and q-ary constant weight codes (see [16]). In fact, the probability of an undetected error for binary constant weight codes has been studied and can be given explicitly (see [14,16]).

Note that when $A={\mathbb{F}}_q$ and $p\to 0$, according to Equation (2), we have

$$P_{ue}(C,p)\sim A_d{p_q}^d{(1-p)}^{n-d},$$

(3)

where $p_q=p/(q-1)$, d is the minimum distance of C and $A_d$ is called the kissing number of the linear code C. In 2021, Solé et al. [17] studied the kissing number by Linear Programming and the Polynomial Method. They gave bounds for $A_d$ under different conditions and made tables for some special parameters. Motivated by the work, this paper is devoted to studying the function $P_{ue}$ using the same techniques.

The rest of this paper is organized as follows. In Section 2, we briefly give the definition of the (dual) distance distribution of q-ary codes and give some trivial bounds of the probability of an undetected error. In Section 3.1, linear programming bounds are discussed. The applications of Krawtchouk polynomial (Polynomial Method) to error detection are given in Section 3.2. In Section 4, some bounds better than the $2^{-m}$ bound are given for binary Hamming codes. Finally, we end with some concluding remarks in Section 5.

2. Preliminaries

Recall some basic definitions and notations from [2,18,19,20]. Throughout this paper, to simplify some formulas, we let $p_q=\frac{p}{q-1}$ and $k={log}_q\left|C\right|$ for some real k. Furthermore, in this paper, it is natural to define $p<(q-1)(1-p)$, equivalently, $p_q<1-p$.

2.1. Dual Distance Distribution

Assume that $A={\mathbb{F}}_q$ is the finite field of size q and C is a subspace of ${\mathbb{F}}_q^n$, i.e., C is a linear code over ${\mathbb{F}}_q$. Then, the dual code $C^{\perp }$ of C is the orthogonal complement of the subspace C. That is to say,

$$C^{\perp }=\{\mathit{v}\in {\mathbb{F}}_q^n:\mathit{v}·\mathit{u}=0for all\mathit{u}\in C\},$$

where $\mathit{v}·\mathit{u}={\sum }_{i=1}^n{v}_i{u}_i$, $\mathit{u}=(u_1,\dots ,u_n)$ and $\mathit{v}=(v_1,\dots ,v_n)$. The distance distribution $A_i^{\prime }$ of $C^{\perp }$ can be determined similarly. It is well known (see Chapter 5. §2. in [2]) that

$$A_i^{\prime }=\frac{1}{\left|C\right|}\sum _{i=0}^n{A}_j{P}_i\left(j\right),$$

(4)

where $P_i\left(j\right)$ denotes the Krawtchouk polynomial of degree i. For each integer $q⩾2$, the Krawtchouk polynomial$P_k(x;n)$ is defined as

$$P_k(x;n)=\sum _{j=0}^k{(-1)}^j\left(\genfrac{}{}{0pt}{}{x}{j}\right)\left(\genfrac{}{}{0pt}{}{n-x}{k-j}\right){(q-1)}^{k-j}.$$

When there is no ambiguity for n, the function $P_k(x;n)$ is often simplified to $P_k\left(x\right)$.

Note that Equation (4) holds when C is linear. When C is nonlinear, the dual distance distribution $A_i^{\prime }$ is defined by Equation (4). Furthermore, by the MacWilliams–Delsarte inequality,

$$A_i^{\prime }⩾0,$$

(5)

holds for all $i=0, 1,\cdots , n.$ Moreover, $A_0=1$ and

$$q^k=1+\sum _{j=1}^n{A}_j,\mathrm{when}\left|C\right|=q^k.$$

(6)

2.2. Probability of Undetected Error

The q-ary symmetric channel with symbol probability p, where $0⩽p⩽(q-1)/q$, is defined as follows: symbols from some alphabet A with q elements are transmitted over the channel, and

$$\mathcal{P}(b\mathrm{received}\mid a\mathrm{sent})=\left\{\begin{array}{cc}1-p,\hfill & b=a,\hfill \\ \frac{p}{q-1},\hfill & b\ne a,\hfill \end{array}\right.$$

where $\mathcal{P}(b\mathrm{received}\mid a\mathrm{sent})$ is the conditional probability that b is received, given that a is sent. For a q-ary code C, when it is used on such a channel, it is possible that the decoder fails to detect the existence of the errors. Thus, $P_{ue}$, the function in terms of the weight distribution of C is given in Equation (2). Clearly, this is a difficult computational problem for large parameters n, k, d, and q (see [2]). Hence, it is better to give bounds for $P_{ue}$. For example, here are some trivial bounds.

Theorem 1.

For every q-ary code C with $\left|C\right|=q^k$, if $p<(q-1)(1-p)$, then

$$(q^k-1){p_q}^n⩽P_{ue}(C,p)⩽(q^k-1){p_q}^d{(1-p)}^{n-d},$$

where $p_q=\frac{p}{q-1}$. Especially, when $q=2$ and $0<p<\frac{1}{2}$, we have

$$(2^k-1)p^n⩽P_{ue}(C,p)⩽(2^k-1)p^d{(1-p)}^{n-d}.$$

Proof. 

It is easy to check that ${p_q}^j{(1-p)}^{n-j}>{p_q}^{j+1}{(1-p)}^{n-j-1}$ if and only if $p<(q-1)(1-p)$. Hence,

$$P_{ue}=\sum _{j=d}^n{A}_j{p_q}^j{(1-p)}^{n-j}⩽{p_q}^d{(1-p)}^{n-d}\sum _{j=d}^n{A}_j=(q^k-1){p_q}^d{(1-p)}^{n-d},$$

since ${p_q}^j{(1-p)}^{n-j}⩽{p_q}^d{(1-p)}^{n-d}$ when $j⩾d$. The lower bound can be obtained similarly. □

The above bounds are trivial. However, they are both tight, because simplex codes over the finite field ${\mathbb{F}}_q$ attain these bounds.

2.3. Some Special Bounds

It is clear that the general bounds given by Theorem 1 will be much larger (or smaller) than the true value of $P_{ue}$ for a fixed code. If the distance distribution is known, one computes $P_{ue}(C,p)$ (as a function of p), and if we know some particular information about the distance distribution, then we may get some bounds. The following is a special case and more thoughts can be seen in Section 4.

Theorem 2.

Let C be a binary code with $A_n=1$ and $A_i=A_{n-i}$ for $1⩽i⩽n-1$, then

$$P_{ue}=\left\{\begin{array}{cc}{p}^n+\sum _{j=d}^t{A}_j\left(p^j{(1-p)}^{n-j}+p^{n-j}{(1-p)}^j\right),\hfill & n=2t+1,\hfill \\ p^n+A_t{p}^t{(1-p)}^t+\sum _{j=d}^{t-1}{A}_j\left(p^j{(1-p)}^{n-j}+p^{n-j}{(1-p)}^j\right),\hfill & n=2t.\hfill \end{array}\right.$$

(7)

Moreover, when $d⩽t$, we have

$$P_{ue}⩽\left\{\begin{array}{cc}{p}^n+\left(2^{k-1}-1\right)\left(p^d{(1-p)}^{n-d}+p^{t+1}{(1-p)}^t\right),\hfill & n=2t+1,\hfill \\ p^n+A_t{p}^t{(1-p)}^t+\left(2^{k-1}-\frac{A_t}{2}-1\right)\left(p^d{(1-p)}^{n-d}+p^{t+1}{(1-p)}^{t-1}\right),\hfill & n=2t,\hfill \end{array}\right.$$

and

$$P_{ue}⩾\left\{\begin{array}{cc}{p}^n+\left(2^{k-1}-1\right)\left(p^t{(1-p)}^{t+1}+p^{n-d}{(1-p)}^d\right),\hfill & n=2t+1,\hfill \\ p^n+A_t{p}^t{(1-p)}^t+\left(2^{k-1}-\frac{A_t}{2}-1\right)\left(p^{t-1}{(1-p)}^{t+1}+p^{n-d}{(1-p)}^d\right),\hfill & n=2t,\hfill \end{array}\right.$$

where $0<p<\frac{1}{2}$ and $d⩽t$.

Proof. 

By the definition of $P_{ue}$, Equation (7) holds if $A_i=A_{n-i}$ and $A_n=1$. Due to $0<p<\frac{1}{2}$, It is easy to check that $p^{n-j}{(1-p)}^j⩽p^j{(1-p)}^{n-j}$, where $0⩽j⩽\lfloor n/2\rfloor$. In addition, if $n=2t+1$, then ${\sum }_{j=d}^t{A}_j=(2^k-2)/2=2^{k-1}-1$. Similarly for the case $n=2t$. Hence, we get the bounds. □

Remark 1.

If the binary code C satisfies $A_i=A_{n-i}$ and $A_n=0$, we can get the following bounds:

$$P_{ue}⩽\left\{\begin{array}{cc}{2}^{k-1}\left(p^d{(1-p)}^{n-d}+p^{t+1}{(1-p)}^t\right),\hfill & n=2t+1,\hfill \\ A_t{p}^t{(1-p)}^t+\left(2^{k-1}-\frac{A_t+A_0}{2}\right)\left(p^d{(1-p)}^{n-d}+p^{t+1}{(1-p)}^{t-1}\right),\hfill & n=2t,\hfill \end{array}\right.$$

and

$$P_{ue}⩾\left\{\begin{array}{cc}{2}^{k-1}\left(p^t{(1-p)}^{t+1}+p^{n-d}{(1-p)}^d\right),\hfill & n=2t+1,\hfill \\ A_t{p}^t{(1-p)}^t+\left(2^{k-1}-\frac{A_t+A_0}{2}\right)\left(p^{t-1}{(1-p)}^{t+1}+p^{n-d}{(1-p)}^d\right),\hfill & n=2t.\hfill \end{array}\right.$$

Here, $\mathbf{0}$, the all zero vector, may not be a codeword.

Example 1.

For a binary linear code, if the all-one vector $\mathbf{1}$ is a codeword, then $A_i=A_{n-i}$. So, Theorem 2 can be applied to many codes, for example, Hamming codes. It is known that the binary Hamming code ${\mathcal{H}}_m$ is a linear $[n=2^m-1,k=2^n-1-m,3]$ code. The distance distribution of the $[15,11,3]$ Hamming code ${\mathcal{H}}_4$ is listed in

Table 1. Distance Distribution of the Hamming Code ${\mathcal{H}}_4$.

i	0	3	4	5	6	7	8	9	10	11	12	15
$A_i$	1	35	105	168	280	435	435	280	168	105	35	1

. According to Theorem 2, the values of the bounds and true probability can be seen in Figure 1.

3. Universal Bounds for q-Ary Codes

In this section, we will discuss the bounds for $P_{ue}$ using different methods. These bounds are for general codes, thus they do not look so good. Meanwhile, compared with some known bounds, they do not perform better. However, it is the first as far as we know to give bounds for $P_{ue}$ using the following two methods, though they have been shown in [21,22] due to different thoughts.

3.1. Linear Programming Bounds

Consider the linear programming problem $M(n,k,d,p)$ that maximizes the objec- tive function

$$\sum _{j=1}^n{A}_j{p_q}^j{(1-p)}^{n-j}$$

under the constraints:

(1)

$A_j⩾0,$

(2)

${\sum }_{j=1}^n{A}_j=q^k-1$,

(3)

${\sum }_{j=1}^n{A}_j{P}_i\left(j\right)⩾-P_i\left(0\right)$,

(4)

$A_1=A_2=\cdots =A_{d-1}=0$.

Likewise, let $m(n,k,d,p)$ be the minimization of the same objective function under the same constraints.

Theorem 3.

If C is a q-ary code of parameters $(n,q^k,d),$ then $m(n,k,d,p)⩽P_{ue}⩽M(n,k,d,p).$

Proof. 

The objective function expression comes from (2). Constraint $\left(1\right)$ is immediate by the definition of the distance distribution. Constraints $\left(2\right)$ and $\left(3\right)$ come from Equation (6) and Equation (5), respectively. Constraint $\left(4\right)$ is a consequence of the definition of minimum distance. □

Remark 2.

Let $f\left(x\right)$ and $g\left(x\right)$ be two functions of x, then $f\lesssim g$ if $f<g$ or $f\sim g$, when $x\to 0$, where $0<x<1$. For example, let $f\left(x\right)=x^2+x$ and $g\left(x\right)=x^3+x$, then $f\left(x\right)>g\left(x\right)$ when $0<x<1$. But $f\left(x\right)\sim g\left(x\right)$, then $f\left(x\right)\lesssim g\left(x\right)$ when $0<x<1$ and $x\to 0$.

Motivated by Equation (3) and [17], we have the following result.

Theorem 4.

Let C be a q-ary ${[n,k,d]}_q$ linear code, then when $p\to 0$,

$$(q^k-1-\lfloor L\rfloor ){p_q}^d{(1-p)}^{n-d}⩽P_{ue}(C,p)\lesssim (q^k-1-\lceil S\rceil ){p_q}^d{(1-p)}^{n-d},$$

(8)

where L (resp. S) denotes the maximum (resp. minimum) of ${\sum }_{j=d+1}^n{A}_j$ subject to the $2n-d$ constraints

$$-P_i\left(0\right)-(q^k-1)P_i\left(d\right)⩽\sum _{j=d+1}^n{A}_j\left(P_i\left(j\right)-P_i\left(d\right)\right),$$

for $i=1, 2,\dots , n$ and $j=d+1, d+2,\dots , n$.

Proof. 

It is clear that $P_{ue}(C,p)⩾A^d{p_q}^d{(1-p)}^{n-d}$, then by [17], we get the left side of Equation (8). As for the right side, if $A_d<q^k-1-\lceil S\rceil$ and p is small enough, then by Equation (3), $P_{ue}(C,p)<(q^k-1-\lceil S\rceil ){p_q}^d{(1-p)}^{n-d}$. Otherwise, $A_d=q^k-1-\lceil S\rceil$ and then, $P_{ue}(C,p)\sim (q^k-1-\lceil S\rceil ){p_q}^d{(1-p)}^{n-d}$. □

Table 2. Bounds of $A_d$ for Some Binary Codes.

Parameters	$[9,4,4]$	$[10,4,4]$	$[11,4,5]$	$[12,4,6]$	$[13,4,6]$	$[14,4,7]$	$[15,4,8]$
Upper Bound	14	15	7	14	14	8	15
Lower Bound	6	12	5	11	4	8	15

is a part of Table I in [17], which is helpful to give bounds for $P_{ue}$.

Example 2.

Let $C_1$ be a binary $[15,4,8]$ code, then

$$P_{ue}(C_1,p)\sim 15p^8{(1-p)}^7.$$

As for the binary $[12,4,6]$ code $C_2$, we have

$$11p^6{(1-p)}^6<P_{ue}(C_2,p)<14p^6{(1-p)}^6.$$

Obviously, for any $[n,k,d]$ code, one can give bounds for its $P_{ue}$.

Remark 3.

From the above discussion, it is clear that our bounds depend solely on the three parameters $[n,k,d]$ of the code, and $[n,k,d]$ is the minimal requirement to use a code in practice.

3.2. Polynomial Method

In this section, we will give some general bounds for $P_{ue}$ for any binary $(n,2^k,d)$ code. Recall the definition of the Krawtchouk polynomials and some properties. The following identity is a Polynomial Method of expressing the duality of LP.

Lemma 1.

Let $\beta \left(x\right)\in \mathbb{Q}\left[x\right]$ be the polynomial whose Krawtchouk expansion is

$$\beta \left(x\right)=\sum _{j=0}^n{\beta }_j{P}_j\left(x\right).$$

Then we have the following identity

$$\sum _{i=0}^n\beta \left(i\right)A_i=q^k\sum _{j=0}^n{\beta }_j{A}_j^{\prime }.$$

(9)

Proof. 

Immediate by Equation (4), upon swapping the order of summation. □

From now on, we denote the coefficient of Krawtchouk expansion of the polynomial $f\left(x\right)$ of degree n by $f_j$, $j=0, 1,\cdots , n$, i.e., $f\left(x\right)={\sum }_{j=0}^n{f}_j{P}_j\left(x\right)$.

The first main result of this section is inspired by Theorem 1 in [23], and given as follows.

Theorem 5.

Let $\beta \left(x\right)$ and $\gamma \left(x\right)$ be polynomials over $\mathbb{Q}$ such that ${\beta }_j⩽0$, ${\gamma }_j⩾0$ for $j⩾1$ and $\gamma \left(i\right)⩽{p_q}^i{(1-p)}^{n-i}⩽\beta \left(i\right)$ for all i with $A_i\ne 0$. Then we have the upper bound

$$P_{ue}⩽q^k{\beta }_0-\beta \left(0\right),$$

(10)

and the lower bound

$$P_{ue}⩾q^k{\gamma }_0-\gamma \left(0\right).$$

(11)

Proof. 

By Lemma 1, we have

$$\sum _{j=0}^n{A}_j\beta \left(j\right)⩽{\beta }_0{q}^k.$$

Returning to the definition of $P_{ue}$ and using the property of $\beta \left(j\right)⩾{p_q}^j{(1-p)}^{n-j}$, we get

$$P_{ue}=\sum _{j=1}^n{A}_j{p_q}^j{(1-p)}^{n-j}⩽\sum _{j=1}^n{A}_j\beta \left(j\right)⩽q^k{\beta }_0-\beta \left(0\right).$$

The proof of the lower bound is analogous and ommitted. □

Remark 4.

The above result is a special case of Proposition 5 in [22]. More general setting of the linear programming bounds from Section 3 (Theorem 5) were already considered in [21,22].

The following are some properties of the Krawtchouk expansion, and we omit the proof, since they are not difficult.

Lemma 2

([24] Corollary 3.13). Let $f\left(x\right)={\sum }_{j=0}^n{f}_j{P}_j\left(x\right)$ and $g\left(x\right)={\sum }_{j=0}^n{g}_j{P}_j\left(x\right)$ be polynomials over $\mathbb{Q}$, where $f_j⩾0, g_j⩾0$, $0⩽j⩽n$. Then the coefficients of the Krawtchouk expansion of $\lambda f\left(x\right)+\mu g\left(x\right)$ are nonnegative, where $\lambda ,\mu$ are nonnegative rational numbers.

3.2.1. Upper Bounds

For convenience, let ${\delta }_{i,j}$ be the Kronecker symbol, i.e.,

$${\delta }_{i,j}=\left\{\begin{array}{cc}1,\hfill & \mathrm{if}i=j,\hfill \\ 0,\hfill & \mathrm{if}i\ne j.\hfill \end{array}\right.$$

Lemma 3.

For general q, the coefficients of the Krawtchouk expansion of the following polynomial

$$g_i\left(x\right)=\frac{{(-1)}^{i-1}}{(i-1)!(n-i)!}\frac{{\prod }_{j=1}^n(j-x)}{i-x},$$

are all nonnegative if and only if i is odd, where $1⩽i⩽n$ is an integer and $0!=1$. Moreover, $g_i\left(j\right)={\delta }_{i,j}$.

Proof. 

Let

$$h\left(x\right)=\frac{q^{n-d+1}}{s-x}\prod _{j=d}^n\left(1-\frac{x}{j}\right)=\sum _{j=0}^n{h}_j{P}_j\left(x\right),$$

where $d⩽s⩽n$. Then, by Proposition 5.8.2 in [20],

$$\begin{array}{cc}\hfill h_i& =\frac{1}{q^n}\sum _{j=0}^{n}h\left(j\right)P_j\left(i\right)=\frac{1}{q^{d-1}}\sum _{j=0}^{d-1}\left(\genfrac{}{}{0pt}{}{n-j}{n-d+1}\right)\frac{P_j\left(i\right)}{s-j}/\left(\genfrac{}{}{0pt}{}{n}{d-1}\right)\hfill \\ & ⩾\frac{1}{q^{d-1}s}\sum _{j=0}^{d-1}\left(\genfrac{}{}{0pt}{}{n-j}{n-d+1}\right)P_j\left(i\right)/\left(\genfrac{}{}{0pt}{}{n}{d-1}\right)\hfill \\ & =\frac{1}{s}\left(\genfrac{}{}{0pt}{}{n-i}{d-1}\right)/\left(\genfrac{}{}{0pt}{}{n}{d-1}\right)⩾0.\hfill \end{array}$$

Note that if $d=1$, we have

$$h\left(x\right)=\frac{q^n}{n!}{(-1)}^{i-1}(i-1)!(n-i)!g_s\left(x\right).$$

According to Lemma 2, the coefficients of the Krawtchouk expansion of ${(-1)}^{i-1}{g}_i\left(x\right)$ are all nonnegative.

Obviously, for any $j\ne i$, $g_i\left(j\right)=0$, because j is a root of $g_i\left(x\right)$. Moreover,

$$\begin{array}{cc}\hfill g_i\left(i\right)& =\frac{{(-1)}^{i-1}}{(i-1)!(n-i)!}\prod _{\ell =1}^{i-1}(\ell -i)\prod _{\ell =i+1}^n(\ell -i)\hfill \\ & =\frac{{(-1)}^{i-1}}{(i-1)!(n-i)!}\left({(-1)}^{i-1}(i-1)!(n-i)!\right)=1,\hfill \end{array}$$

which means $g_i\left(j\right)={\delta }_{i,j}$. □

Theorem 6.

Let C be a binary code with the distance distribution $A_j$, where $A_j=0$ for all possible odd j, then

$$P_{ue}⩽\sum _{eveni}{p}^i{(1-p)}^{n-i}\left(\genfrac{}{}{0pt}{}{n}{i}\right)\left(\frac{1}{2^{n-k}}+1\right),$$

(12)

where even i means that i runs through the even intergers between d and n.

Proof. 

According to Lemma 3, the coefficients of the Krawtchouk expansion of the following polynomial:

$$g_i\left(x\right)=\frac{{(-1)}^{i-1}}{(i-1)!(n-i)!}\frac{{\prod }_{j=1}^n(j-x)}{i-x}$$

are nonnegative if and only if i is odd. Then, let

$$f\left(x\right)=\sum _{\mathrm{even}i}{p}^i{(1-p)}^{n-i}{g}_i\left(x\right)=\sum _{j=0}^n{f}_j{P}_j\left(x\right).$$

Hence, $f_j⩽0$, $f\left(i\right)=p^i{(1-p)}^{n-i}$ for even i and $f\left(i\right)=0$ for odd i. By the proof of Theorem 5,

$$P_{ue}⩽2^k{f}_0-f\left(0\right),$$

where

$$f\left(0\right)=\sum _{\mathrm{even}i}(-1)p^i{(1-p)}^{n-i}\left(\genfrac{}{}{0pt}{}{n}{i}\right),$$

and

$$f_0=\frac{1}{2^n}\sum _{\mathrm{even}i}{p}^i{(1-p)}^{n-i}\left(\genfrac{}{}{0pt}{}{n}{i}\right).$$

Thus, the upper bound follows from Theorem 5. □

Remark 5.

If C is linear, then $A_i$ is the number of codewords of weight i, which implies that $A_i⩽\left(\genfrac{}{}{0pt}{}{n}{i}\right)$. Hence,

$$P_{ue}⩽\sum _{i\in I}{p}^i{(1-p)}^{n-i}\left(\genfrac{}{}{0pt}{}{n}{i}\right),$$

where $I=\left\{i\right|A_i\ne 0\}$. Moreover, if $A_i=0$ for all odd i, then

$$P_{ue}⩽\sum _{\mathrm{even}i}{p}^i{(1-p)}^{n-i}\left(\genfrac{}{}{0pt}{}{n}{i}\right).$$

(13)

Example 3.

Consider the Nordstrom–Robinson code, it is a binary nonlinear code with the distance distribution in

Table 3. Distance Distribution of the Nordstrom–Robinson Code.

i	0	6	8	10	16
$A_i$	1	112	30	112	1

. Moreover, the weight distribution is the same as the distance distribution. By Equation (2),

$$P_{ue}=112p^6{(1-p)}^{10}+30p^8{(1-p)}^8+112p^{10}{(1-p)}^6+p^{16}.$$

According to Theorem 6, the values of the upper bound and true probability can be seen in Figure 2.

Example 4.

Let $\mathcal{E}$ be the set of binary vectors of length n and even weight, then it is actually the Reed–Muller code $RM(n-1,n)$ in Problem 5 in [2] and is generated by all the binary vectors of weight 2. Hence,

$$P_{ue}(\mathcal{E},p)=\sum _{i=1}^{\lfloor n/2\rfloor }\left(\genfrac{}{}{0pt}{}{n}{2i}\right)p^{2i}{(1-p)}^{n-2i}.$$

Remark 6.

The bound is suitable for many codes, and thus it seems not good. In fact, there exists some code C, whose $P_{ue}$ is very large.

Motivated by [17], we have the following upper bounds for linear codes over ${\mathbb{F}}_2$.

Proposition 1.

When C is a q-ary linear $[n,k,d]$ code and p is small enough, we have the following statements:

(1) 

If $n+1+qd-nq>0$, then

$$P_{ue}\lesssim \frac{q^k+nq-n-1}{n-nq+1+qd}{p_q}^d{(1-p)}^{n-d};$$

(2) 

If $n+qd-nq-1<0$, then

$$P_{ue}\lesssim \frac{q^{k-2}n(qn-n-qd+1)+n(d-1)}{n-d}{p_q}^d{(1-p)}^{n-d};$$

(3) 

If $q=2$, $n-2d>0$, ${(n-2d+2)}^2>n$, and $A_i\ne 0$ only if $d⩽i⩽n-2d$, then

$$P_{ue}\lesssim \frac{2^{k-2}({(n-2d+2)}^2-n)+(d-1)(n-d+1)}{n+1-2d}{p}^d{(1-p)}^{n-d}.$$

Proof. 

These three bounds can be deduced easily by Equation (3) and Corollaries 4–6 in [17]. □

Remark 7.

The results in Corollary 4–6 in [17] are actually the upper bounds of $A_d$ under different conditions. Considering Equation (3), it is necessary to make p small enough. According to the proof of Theorem 4, if $A_d$ does not meet such bounds, then “<” holds.

3.2.2. Lower Bounds

Similar to Proposition 1, by Corollaries 1–3 in [17], we have

Proposition 2.

If C is a q-ary linear code, then we have the following statements:

(1) 

If $d=\lceil (n-1)(q-1)/q\rceil$, then

$$P_{ue}⩾\frac{q^k-nq+n-1}{(n-d)q-n+1}{p_q}^d{(1-p)}^{n-d};$$

(2) 

If $qd>nq-n-2q+1$, then

$$P_{ue}⩾\frac{q^{k-2}n(n-qn+qd+2q-1)-nd-n}{n-d}{p_q}^d{(1-p)}^{n-d};$$

(3) 

If $q=2$ and all weights of C are in $[d,n-d]$, with $n-2d>0$ and ${(n-2d-1)}^2<n+1$, then

$$P_{ue}⩾\left(\frac{2^{k-2}(n^2-4nd-3n)+(2^k+1)d(d+1)}{2d-n}-d-1\right)p^d{(1-p)}^{n-d}.$$

When using quadratic polynomials, we have the following bound.

Proposition 3.

Let $f_0$, $f_1$ and $f_2$ be nonnegative rational numbers such that

$$f_0-f_{1}n+f_2\left(\genfrac{}{}{0pt}{}{n}{2}\right)⩽p^d{(1-p)}^{n-d}\mathrm{and}{f}_1+n{f}_2⩽2d{f}_2,$$

then, for a binary $(n,2^k,d)$ code, we have

$$P_{ue}⩾2^k{f}_0-p^d{(1-p)}^{n-d}-2f_{1}n,$$

where $0⩽p⩽\frac{1}{2}$.

Proof. 

It is known that, when $q=2$, $P_0\left(x\right)=1$, $P_1\left(x\right)=n-2x$ and $P_2\left(x\right)=2x^2-2nx+\left(\genfrac{}{}{0pt}{}{n}{2}\right)$. Let $f\left(x\right)=f_0{P}_0\left(x\right)+f_1{P}_1\left(x\right)+f_2{P}_2\left(x\right)$ and then it is a quadratic function whose axis of symmetry is $\frac{f_1+n{f}_2}{2f_2}$. Considering that $p^{i+1}{(1-p)}^{n-i-1}⩾p^i{(1-p)}^{n-i}$, it is sufficient to show that

$$f\left(n\right)⩽p^d{(1-p)}^{n-d}\mathrm{and}\frac{f_1+n{f}_2}{2f_2}⩽d,$$

i.e., $f\left(i\right)⩽f\left(n\right)⩽p^d{(1-p)}^{n-d}⩽p^i{(1-p)}^{n-i}$ for $i⩾d$. Equivalently,

$$f_0-f_{1}n+f_2\left(\genfrac{}{}{0pt}{}{n}{2}\right)⩽p^d{(1-p)}^{n-d},f_1+n{f}_2⩽2d{f}_2.$$

The result follows from Theorem 5. □

4. Good Bounds for Hamming Codes

Recall that the weight enumerator of the code C is the homogeneous polynomial

$$W_C(x,y)=\sum _{\mathit{c}\in C}{x}^{n-wt\left(\mathit{u}\right)}{y}^{wt\left(\mathit{u}\right)},$$

where $wt\left(\mathit{u}\right)$ means the Hamming weight the codeword $\mathit{u}$. The binary Hamming code ${\mathcal{H}}_m$ is a $[n=2^m-1,k=n-m,d=3]$ code, with the weight enumerator

$$\frac{{(x+y)}^n+n{(x+y)}^{(n-1)/2}{(x-y)}^{(n+1)/2}}{n+1},$$

whose distance distribution $A_i$ satisfies

$$\sum _{i=1}^{n}i{A}_i{y}^{i-1}+\sum _{i=0}^n{A}_i{y}^i+\sum _{i=0}^{n-1}(n-i)A_i{y}^{i+1}={(1+y)}^n,$$

and the recurrence $A_0=1$, $A_1=0$,

$$(i+1)A_{i+1}+A_i+(n-i+1)A_{i-1}=\left(\genfrac{}{}{0pt}{}{n}{i}\right).$$

Moreover,

$$\begin{array}{cc}\hfill {(1+y)}^n& =\frac{{\sum }_{i=1}^{n}i{A}_i{y}^i}{y}+\sum _{i=0}^n{A}_i{y}^i+ny\sum _{i=0}^{n-1}{A}_i{y}^i-y\sum _{i=0}^{n-1}i{A}_i{y}^i\hfill \\ \hfill & =\sum _{i=1}^{n-1}{A}_i{y}^i\left(\frac{i}{y}-iy\right)+(ny+1)\sum _{i=1}^{n-1}{A}_i{y}^i+y^n+n{y}^{n-1}+ny+1.\hfill \end{array}$$

Let $\alpha \in {\mathbb{F}}_{2^m}$ be a primitive element and let $g\left(x\right)\in {\mathbb{F}}_2\left[x\right]$ be the minimal polynomial of $\alpha$ with respect to ${\mathbb{F}}_2$. According to Exercise 7.20 in [20], $g\left(x\right)$ can be regarded as the generator polynomial of a Hamming code. Since $deg\left(g\right(x\left)\right)=m>1$, then

$$g\left(x\right)\left|\frac{x^n-1}{x-1}\right.=1+x+x^2+\cdots +x^{n-1},$$

which implies that the all-one vector is a codeword of the Hamming code and $A_n=1$.

Note that

$$P_{ue}=\sum _{i=1}^n{A}_i{p}^i{(1-p)}^{n-i}={(1-p)}^n\sum _{i=1}^n{A}_i{\left(\frac{p}{1-p}\right)}^i.$$

Hence,

$$\sum _{i=1}^{n-1}{A}_i{\left(\frac{p}{1-p}\right)}^i=\frac{P_{ue}-p^n}{{(1-p)}^n}.$$

Let $y=\epsilon =\frac{p}{1-p}$, where $p\in (0,1/2)$, then

$$\begin{array}{cc}\hfill & (n\epsilon +1)\left(P_{ue}-p^n\right)+{(1-p)}^n\sum _{i=1}^{n-1}{A}_i{\epsilon }^i\left(\frac{i}{\epsilon }-i\epsilon \right)\hfill \\ \hfill & =1-p^n-np{(1-p)}^{n-1}-n{p}^{n-1}(1-p)-{(1-p)}^n.\hfill \end{array}$$

According to Chapter 6, Exercise(E2), page 157 in [2], there are $n-4$ nonzero weights of ${\mathcal{H}}_m$. Considering that $A_n=1$, we have $A_i=0$ if and only if $i=1, 2, n-1, n-2$. Since $0<p<1/2$, then $0<\epsilon <1$ and we have

$$\frac{3}{\epsilon }-3\epsilon ⩽\frac{i}{\epsilon }-i\epsilon ⩽\frac{n-3}{\epsilon }-(n-3)\epsilon .$$

Obviously,

$$\begin{array}{cc}\hfill {(1-p)}^n\sum _{i=1}^{n-1}{A}_i{\epsilon }^i\left(\frac{i}{\epsilon }-i\epsilon \right)& ⩽{(1-p)}^n\sum _{i=1}^{n-1}{A}_i{\epsilon }^i\left(\frac{n-3}{\epsilon }-(n-3)\epsilon \right)\hfill \\ \hfill & =\left(\frac{n-3}{\epsilon }-(n-3)\epsilon \right)\sum _{i=1}^{n-1}{A}_i{p}^i{(1-p)}^{n-i}\hfill \\ \hfill & =\left(\frac{n-3}{\epsilon }-(n-3)\epsilon \right)(P_{ue}-p^n).\hfill \end{array}$$

Similarly,

$${(1-p)}^n\sum _{i=1}^{n-1}{A}_i{\epsilon }^i\left(\frac{i}{\epsilon }-i\epsilon \right)⩾\left(\frac{3}{\epsilon }-3\epsilon \right)(P_{ue}-p^n).$$

Thus,

$$\begin{array}{cc}\hfill P_{ue}& ⩽\frac{1-p^n-np{(1-p)}^{n-1}-n{p}^{n-1}(1-p)-{(1-p)}^n}{\frac{3}{\epsilon }-3\epsilon +n\epsilon +1}+p^n\hfill \\ \hfill & =\frac{p(1-p)-p^{n+1}(1-p)-n{p}^2{(1-p)}^n-n{p}^n{(1-p)}^2-p{(1-p)}^{n+1}}{(n-1)p^2-5p+3}+p^n\hfill \end{array}$$

(14)

and

$$\begin{array}{cc}\hfill P_{ue}& ⩾\frac{1-p^n-np{(1-p)}^{n-1}-n{p}^{n-1}(1-p)-{(1-p)}^n}{\frac{n-3}{\epsilon }-(n-3)\epsilon +n\epsilon +1}+p^n\hfill \\ \hfill & =\frac{p(1-p)-p^{n+1}(1-p)-n{p}^2{(1-p)}^n-n{p}^n{(1-p)}^2-p{(1-p)}^{n+1}}{(n-1)p^2-(2n-7)p+n-3}+p^n.\hfill \end{array}$$

(15)

Summarize the above discussions, we get

Theorem 7.

Let ${\mathcal{H}}_m$ be the binary $[n=2^m-1,k=n-m,3]$ Hamming code, then when $0<p<1/2$ and $m⩾3$, we have the upper bound Equation (14) and the lower bound Equation (15) for $P_{ue}$, respectively.

Proof. 

Note that the upper bound should be larger or equal than the lower bound, then

$$\left(-(2n-7)p+n-3\right)-\left(-5p+3\right)=(n-6)(1-2p)⩾0.$$

It is sufficient to solve the inequality $n=2^m-1>6$, due to $1-2p>0$. Hence, $m⩾3$. □

Remark 8.

The difference of the upper bound and the lower bound is small.

Let $U(n,p)=H_1/H$ and $L(n,p)=H_2/H$ be the bound given by Equation (14) and Equation (15), respectively, where $H_1=(n-1)p^2-5p+3$, $H_2=(n-1)p^2-(2n-7)p+n-3$ and

$$H=p(1-p)-p^{n+1}(1-p)-n{p}^2{(1-p)}^n-n{p}^n{(1-p)}^2-p{(1-p)}^{n+1}.$$

In fact, H is a polynomial of p whose degree $n+2$ and the leading coefficient is

$$h_{n+2}=1+{(-1)}^{n+2}n-n+{(-1)}^{n+2}=\left(1+{(-1)}^n\right)+n\left({(-1)}^n-1\right)\ne 0,$$

while the product $H_1{H}_2$ is just a polynomial whose degree is 4. Then,

$$\begin{array}{cc}\hfill U(n,p)-L(n,p)& =\frac{(H_2-H_1)H}{H_1{H}_2}=\frac{(n-6)(1-2p)H}{H_1{H}_2}\hfill \\ \hfill & ⟶\frac{(n-6)(1-2p)h_{n+2}{p}^{n+2}}{{(n-1)}^2{p}^4}⟶0(n\to +\infty ).\hfill \end{array}$$

That is to say, the lower bound and the upper bound are very close. On the other hand,

$$H_1⩾\frac{12n-37}{4(n-1)}and{H}_2⩾\frac{n+1}{4}.$$

Then,

$$\begin{array}{cc}\hfill U(n,p)-L(n,p)& =\frac{(H_2-H_1)H}{H_1{H}_2}=\frac{(n-6)(1-2p)H}{H_1{H}_2}\hfill \\ \hfill & <\frac{(n-6)(1-2p)p(1-p)}{H_1{H}_2}<\frac{(n-6)(1-2p)p(1-p)}{\frac{12n-37}{4(n-1)}\frac{n+1}{4}}\hfill \\ \hfill & =\frac{16(n-1)(n-6)}{(n+1)(12n-37)}p(1-p)(1-2p)\hfill \\ \hfill & ⩽\frac{\sqrt{3}}{18}\frac{16(n-1)(n-6)}{(n+1)(12n-37)}⟶\frac{2\sqrt{3}}{27}\approx 0.1283(n\to +\infty ).\hfill \end{array}$$

Here, let $F\left(p\right)=p(1-p)(1-2p)$, then its derivative is $F^{\prime }\left(p\right)=6p^2-6p+1$. Note that the roots of $F^{\prime }\left(p\right)$ are $\frac{3\pm \sqrt{3}}{6}$. Since $0<p<1/2$, then we choose the root $p_0=\frac{3-\sqrt{3}}{6}$. Hence,

$$F\left(p\right)⩽F\left(p_0\right)=\frac{\sqrt{3}}{18}\approx 0.0962.$$

Thus the difference of the upper bound and the lower bound is about $0.1283$ at most, and tends to 0 when $n\to +\infty$.

Example 5.

Using the bounds in Theorem 7, the results in Figure 1 can be improved. See Figure 3.

When $m=5$, the bounds Equations (15) and (14) are also valid. See Figure 4.

Note that the difference of the bounds Equations (15) and (14) is about $0.05$, which is much smaller than the given $0.1283$.

It is known that the Hamming codes satisfy the $2^{-m}$ bound when $0<p<1/2$ i.e., $P_{ue}⩽2^{-m}$. See [5] for more details. In fact, the obtained new bound is better than the ordinary $2^{-m}$ bound, when p is not large.

Theorem 8.

Let ${\mathcal{H}}_m$ be the binary $[n=2^m-1,k=n-m,3]$ Hamming code, then when $0<p<1/2$ and $m\ge 3$, we have

$$P_{ue}⩽\frac{p-p^2}{(n-1)p^2-5p+3}+p^n.$$

(16)

Moreover, if $p<p_0$, this upper bound is better than the $2^{-m}$ bound, where $p_0$ is the smaller root of the equation $(2^{m+1}-2)x^2-(2^m+5)x+3=0$.

Proof. 

Assume that

$$\frac{p-p^2}{(n-1)p^2-5p+3}<\frac{1}{2^m},$$

then it is sufficient to solve the inequality

$$(2^{m+1}-2)p^2-(2^m+5)p+3>0.$$

Obviously, the inequality holds when $p<p_0$, where

$$p_0=\frac{(2^m+5)-\sqrt{{(2^m+5)}^2-12(2^{m+1}-2)}}{2(2^{m+1}-2)}$$

is the smaller root of the equation $(2^{m+1}-2)x^2-(2^m+5)x+3=0$. □

Example 6.

It is clear that when p is small enough, the new upper bound Equation (14) is smaller than the $2^{-m}$ bound in Figure 3 and Figure 4.

Remark 9.

Of course, the weight distribution of the binary Hamming codes can be computed and expressed by the sum of combinatorial numbers, which are usually very large when m is large. So, the method in this section is to estimate $P_{ue}$ quickly. Compared with the $2^{-m}$ bound, our bounds are better when p is small enough.

5. Conclusions

In this paper, we studied the probability of an undetected error $P_{ue}$ and gave many bounds for $P_{ue}$. The main contributions of this paper are the following:

(1)

The bounds obtained from the linear programming problem are given in Theorem 4. The bounds obtained from the Polynomial Method are given. According to the main Theorem 5, we get Theorem 6 (applied to the codes with even distances) and Proposition 3.

(2)

Combining the results of [17], we give the bounds in Propositions 1 and 2.

(3)

We find sharper bounds for binary Hamming codes (see Theorems 7 and 8).

To the best of our knowledge, that is the very first time that the LP method has been applied to bound $P_{ue}$. Even though computing $P_{ue}$ exactly requires knowledge of the code weight spectrum, our bounds depend solely on the three parameters $[n,k,d]$, of the code. The weight frequencies are only used as variables in the LP program. Knowing the three parameters $[n,k,d]$ is the minimal requirement to use a code in applications.

To sum up, our bounds are most useful when the exact weight distribution is too hard to compute. Our bounds perform well when p is small enough and the kissing number $A_d$ is known, and there are many such codes.

We mention the following open problems. The readers interested in Hamming codes are suggested to derive bounds for general q-ary Hamming codes with $q>2.$ Moreover, it is worth mentioning that the linear programming problem works better numerically than the Polynomial Method. The interest of the latter lies in producing bounds with closed formulas. It is a challenging open problem to derive better bounds with polynomials of degree higher than 2.