Skip to main content
Top
Published in:
Cover of the book

Open Access 2017 | OriginalPaper | Chapter

1. Bounds on Error-Correction Coding Performance

Authors : Martin Tomlinson, Cen Jung Tjhai, Marcel A. Ambroze, Mohammed Ahmed, Mubarak Jibril

Published in: Error-Correction Coding and Decoding

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The theoretical performance of binary codes for the additive white Gaussian noise (AWGN) channel is discussed. In particular, Gallager’s coding theorem for binary codes is treated extensively. By assuming a binomial weight distribution for linear codes, it is shown that the decoder error probability performance of some of the best, known linear, binary codes is the same as the average performance of the ensemble of all randomly chosen, binary nonlinear codes having the same length and dimension. Assuming a binomial weight distribution, an upper bound is determined for the erasure performance of any code, and it is shown that this can be translated into an upper bound for code performance in the AWGN channel. Finally, theoretical bounds on the construction of error-correction codes are discussed.

1.1 Gallager’s Coding Theorem

The sphere packing bound by Shannon [18] provides a lower bound to the frame error rate (FER) achievable by an (nkd) code but is not directly applicable to binary codes. Gallager [4] presented his coding theorem for the average FER for the ensemble of all random binary (nkd) codes. There are \(2^n\) possible binary combinations for each codeword which in terms of the n-dimensional signal space hypercube corresponds to one vertex taken from \(2^n\) possible vertices. There are \(2^k\) codewords, and therefore \(2^{nk}\) different possible random codes. The receiver is considered to be composed of \(2^k\) matched filters, one for each codeword and a decoder error occurs if any of the matched filter receivers has a larger output than the matched filter receiver corresponding to the transmitted codeword. Consider this matched filter receiver and another different matched filter receiver, and assume that the two codewords differ in d bit positions. The Hamming distance between the two codewords is d. The energy per transmitted bit is \(E_s=\frac{k}{n}E_b\), where \(E_b\) is the energy per information bit. The noise variance per matched filtered received bit, \(\sigma ^2=\frac{N_0}{2}\), where \(N_0\) is the single sided noise spectral density. In the absence of noise, the output of the matched filter receiver for the transmitted codeword is \(n\sqrt{E_s}\) and the output of the other codeword matched filter receiver is \((n-2d)\sqrt{E_s}\). The noise voltage at the output of the matched filter receiver for the transmitted codeword is denoted as \(n_c - n_1\), and the noise voltage at the output of the other matched filter receiver will be \(n_c + n_1\). The common noise voltage \(n_c\) arises from correlation of the bits common to both codewords with the received noise and the noise voltages \(-n_1\) and \(n_1\) arise, respectively, from correlation of the other d bits with the received noise. A decoder error occurs if
$$\begin{aligned} (n-2d)\sqrt{E_s}+n_c+n_1>n\sqrt{E_s}+n_c-n_1 \end{aligned}$$
(1.1)
that is, a decoder error occurs when \(2n_1>2d\sqrt{E_s}\).
The average noise power associated with \(n_1\) is \(\text {d}\sigma ^2=\text {d}\frac{N_0}{2}\) and as the noise is Gaussian distributed, the probability of decoder error, \(p_{d}\), is given by
$$\begin{aligned} p_d = \dfrac{1}{\sqrt{\pi d N_0}}\int _{\text {d}\sqrt{E_s}}^{\infty } \text {e}^{\frac{-x^2}{dN_0}}\text {d}x \end{aligned}$$
(1.2)
This may be expressed in terms of the complementary error function (erfc)
$$\begin{aligned} \text {erfc}(y) = 2 \dfrac{1}{\sqrt{2\pi }}\int _{y}^{\infty } \text {e}^{\frac{-x^2}{2}}\text {d}x \end{aligned}$$
(1.3)
and
$$\begin{aligned} p_d = \dfrac{1}{2}\text {erfc}\left( \sqrt{d\dfrac{k}{n} \frac{E_b}{N_0}}\right) \end{aligned}$$
(1.4)
Each of the other \(2^k-2\) codewords may also cause a decoder error but the weight distribution of the code \(\mathscr {C}_i\) is usually unknown. However by averaging over all possible random codes, knowledge of the weight distribution of a particular code is not required. The probability of two codewords of a randomly chosen code \(\mathscr {C}_i\), differing in d bit positions, \(p(d|\mathscr {C}_i)\) is given by the binomial distribution
$$\begin{aligned} p(d|\mathscr {C}_i)=\dfrac{ \left( {\begin{array}{c}n\\ d\end{array}}\right) }{ 2^n }, \end{aligned}$$
(1.5)
where \(\left( {\begin{array}{c}a\\ b\end{array}}\right) = \frac{a!}{(a\,-\,b)!b!}\). A given linear code \(\mathscr {C}_i\) cannot have codewords of arbitrary weight, because the sum of a subset of codewords is also a codeword. However, for non linear codes, \(p_{d}\) may be averaged over all of the codes without this constraint. Thus, we have
$$\begin{aligned} \overline{p_{\text {C}}}=\sum _{i=1}^{2^{n2^k}}p(d|\mathscr {C}_i)p(\mathscr {C}_i) < \dfrac{1}{2^{n2^k}}\sum _{d=0}^n\sum _{i=1}^{2^{n2^k}} \dfrac{\left( {\begin{array}{c}n\\ d\end{array}}\right) }{2^{n+1}}\text {erfc}\left( \sqrt{d\dfrac{k}{n} \dfrac{E_b}{N_0}}\right) \end{aligned}$$
(1.6)
Rearranging the order of summation
$$\begin{aligned} \overline{p_{\text {C}}}<\dfrac{1}{2^{n2^k}}\sum _{i=1}^{2^{n2^k}} \sum _{d=0}^n \dfrac{\left( {\begin{array}{c}n\\ d\end{array}}\right) }{2^{n+1}} \text {erfc}\left( \sqrt{d\dfrac{k}{n} \dfrac{E_b}{N_0}}\right) \end{aligned}$$
(1.7)
and
$$\begin{aligned} \overline{p_{\text {C}}}<\dfrac{1}{2^{n+1}}\sum _{d=0}^n \left( {\begin{array}{c}n\\ d\end{array}}\right) \text {erfc}\left( \sqrt{d\dfrac{k}{n} \dfrac{E_b}{N_0}}\right) . \end{aligned}$$
(1.8)
Remembering that any of the \(2^k-1\) matched filters may cause a decoder error, the overall probability of decoder error averaged over all possible binary codes \(\overline{p_{\text {overall}}}\), is
$$\begin{aligned} \overline{p_{\text {overall}}}=1-(1-\overline{p_{\text {C}}})^{2^k-1}<2^k\overline{p_{\text {C}}} \end{aligned}$$
(1.9)
and
$$\begin{aligned} \overline{p_{\text {overall}}}<\dfrac{2^k}{2^{n+1}}\sum _{d=0}^n \left( {\begin{array}{c}n\\ d\end{array}}\right) \text {erfc}\left( \sqrt{d\dfrac{k}{n}\dfrac{E_b}{N_0}}\right) . \end{aligned}$$
(1.10)
An analytic solution may be obtained by observing that \(\frac{1}{2}\text {erfc}(y)\) is upper bounded by \(\text {e}^{-y^2}\) and therefore,
$$\begin{aligned} \overline{p_{\text {overall}}}<\dfrac{2^k}{2^n}\sum _{d=0}^n \left( {\begin{array}{c}n\\ d\end{array}}\right) \text {e}^{-d\frac{k}{n} \frac{E_b}{N_0}} \end{aligned}$$
(1.11)
and as observed in [21],
$$\begin{aligned} \left( 1 + \text {e}^{-\frac{k}{n}\frac{E_b}{N_0}}\right) ^n = \sum _{d=0}^n\left( {\begin{array}{c}n\\ d\end{array}}\right) \text {e}^{-d\frac{k}{n}\frac{E_b}{N_0}} \end{aligned}$$
(1.12)
and
$$\begin{aligned} \overline{p_{\text {C}}}<\dfrac{1}{2^n} \left( 1+\text {e}^{-\frac{k}{n} \frac{E_b}{N_0}}\right) ^n \end{aligned}$$
(1.13)
$$\begin{aligned} \overline{p_{\text {overall}}}<\dfrac{2^k}{2^n} \left( 1+\text {e}^{-\frac{k}{n} \frac{E_b}{N_0}}\right) ^n \end{aligned}$$
(1.14)
Traditionally, a cut-off rate \(R_0\) is defined after observing that
$$\begin{aligned} \dfrac{2^k}{2^n} \left( 1+\text {e}^{-\frac{k}{n} \frac{E_b}{N_0}}\right) ^n= 2^k\left( \dfrac{1+\text {e}^{-\frac{k}{n}\frac{E_b}{N_0}}}{2}\right) ^n \end{aligned}$$
(1.15)
with
$$\begin{aligned} 2^{R_0}=\dfrac{2}{1+ \text {e}^{-\frac{k}{n}\frac{E_b}{N_0}} } \end{aligned}$$
(1.16)
then
$$\begin{aligned} \overline{p_{\text {overall}}}<2^k2^{-nR_0}=2^{k-nR_0}=2^{-n(R_0-\frac{k}{n})} \end{aligned}$$
(1.17)
This result may be interpreted as providing the number of information bits of the code is less than the length of the code times the cut-off rate, then the probability of decoder error will approach zero as the length of the code approaches infinity. Alternatively, provided the rate of the code, \(\frac{k}{n}\), is less than the cut-off rate, \(R_0\), then the probability of decoder error will approach zero as the length of the code approaches infinity. The cut-off rate \(R_0\), particularly in the period from the late 1950s to the 1970s was used as a practical measure of the code rate of an achievable error-correction system [11, 2022]. However, plotting the exact expression for probability of decoder error, Eq. (1.10), in comparison to the cut-off rate approximation Eq. (1.17), shows a significant difference in performance, as shown in Fig. 1.1. The codes shown are the \((128,2^{64})\), \((256,2^{128})\) and \((512,2^{256})\) code ensembles of nonlinear, random binary codes. It is recommended that the exact expression, Eq. (1.10) be evaluated unless the code in question is a long code. As a consequence, in the following sections we shall only use the exact Gallager bound.
Shown in Fig. 1.2 is the sphere packing lower bound, offset by the loss attributable to binary transmission and the Gallager upper bound for the \((128,2^{64})\), \((256,2^{128})\) and \((512,2^{256})\) nonlinear binary codes. For each code, the exact Gallager upper bound given by (1.10), is shown. One reason why Gallager’s bound is some way from the sphere packing lower bound as shown in Fig. 1.2 is that the bound is based on the union bound and counts all error events as if these are independent. Except for orthogonal codes, this produces increasing inaccuracy as the \(\frac{E_b}{N_0}\) is reduced. Equivalently expressed, double counting is taking place since some codewords include the support of other codewords. It is shown in the next section that for linear codes the Gallager bound may be improved by considering the erasure correcting capability of codes, viz. no (nk) code can correct more than \(n-k\) erasures.

1.1.1 Linear Codes with a Binomial Weight Distribution

The weight enumerator polynomial of a code is defined as A(z) which is given by
$$\begin{aligned} A(z)=\sum _{i=0}^n A_i\; z^i \end{aligned}$$
(1.18)
For many good and exceptional, linear, binary codes including algebraic and quasi-cyclic codes, the weight distributions of the codes closely approximates to a binomial distribution where,
$$\begin{aligned} A(z)=\dfrac{1}{2^{n-k}}\sum _{i=0}^n \dfrac{n!}{(n-i)!i!}\; z^i \end{aligned}$$
(1.19)
with coefficients \(A_i\) given by
$$\begin{aligned} A_i=\dfrac{1}{2^{n-k}}\frac{n!}{(n-i)!i!}=\dfrac{1}{2^{n-k}}\left( {\begin{array}{c}n\\ i\end{array}}\right) . \end{aligned}$$
(1.20)
Tables of the best-known linear codes have been published from time to time [3, 10, 13, 16, 19] and a regularly updated database is maintained by Markus Grassl [5]. Remembering that for a linear code, the difference between any two codewords is also a codeword, and hence the distribution of the Hamming distances between a codeword and all other codewords is the same as the weight distribution of the code. Accordingly, the overall probability of decoder error, for the same system as before using a bank of \(2^k\) matched filters with each filter matched to a codeword is upper bounded by
$$\begin{aligned} p_{\text {overall}}<\dfrac{1}{2}\sum _{d=0}^n A_d \text {erfc}\left( \sqrt{d\dfrac{k}{n}\dfrac{E_b}{N_0}}\right) \end{aligned}$$
(1.21)
For codes having a binomial weight distribution
$$\begin{aligned} p_{\text {overall}}<\dfrac{1}{2}\sum _{d=0}^n \dfrac{1}{2^{n-k}} \left( {\begin{array}{c}n\\ d\end{array}}\right) \text {erfc}\left( \sqrt{d\dfrac{k}{n}\dfrac{E_b}{N_0}}\right) \end{aligned}$$
(1.22)
which becomes
$$\begin{aligned} p_{\text {overall}}<\dfrac{2^k}{2^{n+1}}\sum _{d=0}^n \left( {\begin{array}{c}n\\ d\end{array}}\right) \text {erfc}\left( \sqrt{d\dfrac{k}{n}\dfrac{E_b}{N_0}}\right) . \end{aligned}$$
(1.23)
It will be noticed that this equation is identical to Eq. (1.10). This leads to the somewhat surprising conclusion that the decoder error probability performance of some of the best-known, linear, binary codes is the same as the average performance of the ensemble of all randomly chosen, binary nonlinear codes having the same values for n and k. Moreover, some of the nonlinear codes must have better performance than their average, and hence some nonlinear codes must be better than the best-known linear codes.
A tighter upper bound than the Gallager bound may be obtained by considering the erasure correcting capability of the code. It is shown in Chap. 14 that for the erasure channel, given a probability of erasure, p, the probability of decoder error, \(P_{\text {code}}(p)\), is bounded by
$$\begin{aligned} P_{\text {code}}(p)<\sum _{s=d_{min}}^{n-k} \sum _{j=d_{min}}^{s} A_j \dfrac{(n-j)!\;(n-s)!}{(s-j)!}p^s(1-p)^{(n-s)}{+}\sum _{s=n-k+1}^{n}p^s(1-p)^{(n-s)}. \end{aligned}$$
(1.24)
In Eq. (1.24), the first term depends upon the weight distribution of the code while the second term is independent of the code. The basic principle in the above equation is that an erasure decoder error is caused if an erasure pattern includes the support of a codeword. Since no erasure pattern can be corrected if it contains more than \(n-k\) errors, only codewords with weight less than or equal to \(n-k\) are involved. Consequently, a much tighter bound is obtained than a bound based on the union bound as there is less likelihood of double counting error events.
Considering the maximum likelihood decoder consisting of a bank of correlators, a decoder error occurs if one correlator has a higher output than the correlator corresponding to the correct codeword where the two codewords differ in s bit positions. To the decoder, it makes no difference if the decoder error event is due to erasures, from the erasure channel, or Gaussian noise from the AWGN channel; the outcome is the same. For the erasure channel, the probability of this error event due to erasures, \(P_{\text {erasure}}(p)\) is
$$\begin{aligned} P_{\text {erasure}}(p)=p^s \end{aligned}$$
(1.25)
The probability of this error event due to noise, \(P_{\text {noise}}\left( \dfrac{E_b}{N_0}\right) \) is
$$\begin{aligned} P_{\text {noise}}\left( \dfrac{E_b}{N_0}\right) =\dfrac{1}{2}\text {erfc}\left( \sqrt{s\dfrac{k}{n} \dfrac{E_b}{N_0}}\right) \end{aligned}$$
(1.26)
Equating Eqs. (1.25) to (1.26), for these probabilities gives a relationship between the erasure probability, p and \(\frac{E_b}{N_0}\) and the Hamming distance, s.
$$\begin{aligned} p^s=\dfrac{1}{2}\text {erfc}\left( \sqrt{s\dfrac{k}{n} \dfrac{E_b}{N_0}}\right) \end{aligned}$$
(1.27)
For many codes, the erasure decoding performance is determined by a narrow range of Hamming distances and the variation in \(\frac{E_b}{N_0}\) as a function of s is insignificant. This is illustrated in Fig. 1.3 which shows the variation in \(\frac{E_s}{N_0}\) as a function of s and p.
It is well known that the distance distribution for many linear, binary codes including BCH codes, Goppa codes, self-dual codes [7, 8, 10, 14] approximates to a binomial distribution. Accordingly,
$$\begin{aligned} A_j \approx \frac{n!}{(n-j)!\,j!\,2^{n-k}} . \end{aligned}$$
(1.28)
Substituting this into Eq. (1.24) produces
$$\begin{aligned} P_{\text {code}}(p)<\sum _{s=1}^{n-k} \dfrac{2^s-1}{2^{n-k}} \left( {\begin{array}{c}n\\ s\end{array}}\right) p^s(1-p)^{(n-s)}+\sum _{s=n-k+1}^{n}p^s(1-p)^{(n-s)} \end{aligned}$$
(1.29)
With the assumption of a binomial weight distribution, an upper bound may be determined for the erasure performance of any (nk) code, and in turn, equating Eq. (1.25) with Eq. (1.26) produces an upper bound for the AWGN channel. For example, Fig. 1.4 shows an upper bound of the erasure decoding performance of a (128, 64) code with a binomial weight distribution.
Using Eq. (1.27), the decoding performance may be expressed in terms of \(\frac{E_b}{N_0}\) and Fig. 1.5 shows the upper bound of the decoding performance of the same code against Gaussian noise, as a function of \(\frac{E_b}{N_0}\).
The comparison of the sphere packing bound and the Gallager bounds is shown in Fig. 1.6. Also shown in Fig. 1.6 is the performance of the BCH (128, 64, 22) code evaluated using the modified Dorsch decoder. It can be seen from Fig. 1.6 that the erasure-based upper bound is very close to the sphere packing lower bound and tighter than the Gallager bound.
Figure 1.7 gives the bounds for the (512, 256) and (256, 128) codes. It will be noticed that the gap between the sphere packing bound and the erasure-based upper bound increases with code length, but is tighter than the Gallager bound.

1.1.2 Covering Radius of Codes

The covering radius of a code, \(c_r\) if it is known, together with the weight spectrum of the low-weight codewords may be used to tighten the Union bound upper bound on decoder performance given by Eq. (1.23). The covering radius of a code is defined as the minimum radius which when placed around each codeword includes all possible \(q^n\) vectors. Equivalently, the covering radius is the maximum number of hard decision errors that are correctable by the code. For a perfect code, such as the Hamming codes, the covering radius is equal to \(\frac{d_{min}-1}{2}\). For the \([2^m-1,2^m-m-1,3]\) Hamming codes, the covering radius is equal to 1 and for the (23, 12, 7) Golay code the covering radius is equal to 3. As a corollary, for any received vector in Euclidean space, there is always a codeword within a Euclidean distance of \(c_r+0.5\). It follows that the summation in Eq. (1.23) may be limited to codewords of weight \(2c_r+1\) to produce
$$\begin{aligned} p_{\text {overall}}<\dfrac{2^k}{2^{n+1}}\sum _{d=0}^{2c_r+1} \left( {\begin{array}{c}n\\ d\end{array}}\right) \text {erfc}\left( \sqrt{d\dfrac{k}{n}\dfrac{E_b}{N_0}}\right) . \end{aligned}$$
(1.30)

1.1.3 Usefulness of Bounds

The usefulness of bounds may be realised from Fig. 1.8 which shows the performance of optimised codes and decoders all (512, 256) codes for a turbo code, LDPC code and a concatenated code.

1.2 Bounds on the Construction of Error-Correcting Codes

A code (linear or nonlinear), \(\mathscr {C}\), defined in a finite field of size q can be described with its length n, number of codewords1 M and minimum distance d. We use \((n,M,d)_q\) to denote these four important parameters of a code. Given any number of codes defined in a field of size q with the same length n and distance d, the code with the maximum number of codewords M is the most desirable. Equivalently, one may choose to fix n, M and q and maximise d or fix M, d and q and maximise n. As a result, it is of interest in coding theory to determine the maximum number of codewords possible of any code defined in a field of size q, with minimum distance d and length n. This number is denoted by \(A_q(n,d)\). Bounds on \(A_q(n,d)\) are indicators to the maximum performance achievable from any code with parameters \((n,M,d)_q\). As a result, these bounds are especially useful when one constructs good error-correcting codes. The tables in [5] contain the best-known upper and lower bounds on \(A_q(n,d)\) for linear codes. The tables in [9] contain bounds on \(A_2(n,d)\) for nonlinear binary codes. Lower bounds on \(A_q(n,d)\) tend to be code specific; however, there are several generic upper bounds. As an example, consider the best-known upper and lower bounds on \(A_2(128,d)\) obtained from the tables in [5]. These are shown in Fig. 1.9 for the range \(1\le d\le 128\). Optimal codes of length \(n=128\) are codes whose lower and upper bounds on \(A_2(128,d)\) coincide. The two curves coincide when k is small and d is large or vice versa. The gap between the upper and lower bounds that exists for other values of k and d suggests that one can construct good codes with a larger number of codewords and improve the lower bounds. An additional observation is that extended BCH codes count as some of the known codes with the most number of codewords.
It is often useful to see the performance of codes as their code lengths become arbitrarily large. We define the information rate
$$\begin{aligned} \alpha _q(\delta )=\lim _{n\rightarrow \infty }\frac{\log _q(A_q(n,\delta n))}{n}, \end{aligned}$$
(1.31)
where \(\delta =\frac{d}{n}\) is called the relative distance. Since the dimension of the code is defined as \(k=\log _q(A_q(n,\delta n))\), then a bound on the information rate \(\alpha _q(\delta )\) is a bound on \(\frac{k}{n}\), as \(n\rightarrow \infty \).

1.2.1 Upper Bounds

1.2.1.1 Sphere Packing (Hamming) Bound

Let \(V_q(n,t)\) represent the number of vectors in each sphere then,
$$\begin{aligned} V_q(n,t)=\sum _{i=0}^t \left( {\begin{array}{c}n\\ i\end{array}}\right) (q-1)^i. \end{aligned}$$
(1.32)
Theorem 1.1
(Sphere Packing Bound) The maximum number of codewords \(A_q(n,d)\) is upper bounded by,
$$\begin{aligned} A_q(n,d)\le \dfrac{q^n}{\displaystyle \sum _{i=0}^t \left( {\begin{array}{c}n\\ i\end{array}}\right) (q-1)^i} \end{aligned}$$
Proof
A code \(\mathscr {C}\) is a subset of a vector space \(\text {GF}(q)^n\). Each codeword of \(\mathscr {C}\) has only those vectors \(\text {GF}(q)^n\) but not in \(\mathscr {C}\) lying at a hamming distance \(t=\left\lfloor \frac{d-1}{2}\right\rfloor \) from it since codewords are spaced at least d places apart. In other words, no codewords lie in a sphere of radius t around any codeword of \(\mathscr {C}\). As such, for counting purposes, these spheres can represent individual codewords. The Hamming bound counts the number of such non-overlapping spheres in the vector space \(\text {GF}(q)^n\).
Codes that meet this bound are called perfect codes. In order to state the asymptotic sphere packing bound, we first define the qary entropy function, \(H_q(x)\), for the values \(0\le x \le r\),
$$\begin{aligned} H_q(x)={\left\{ \begin{array}{ll} 0 &{} \text {if}\quad x=0\\ x\log _q(q-1)-x\log _q x -(1-x)\log _q(1-x) &{} \text {if}\quad 0<x \le r \end{array}\right. } \end{aligned}$$
(1.33)
Theorem 1.2
(Asymptotic Sphere Packing Bound) The information rate of a code \(\alpha _q(\delta )\) is upper bounded by,
$$\begin{aligned} \alpha _{q}(\delta )\le 1- H_q\left( \frac{\delta }{2}\right) \end{aligned}$$
for the range \(0 < \delta \le 1-q^{-1}\).

1.2.1.2 Plotkin Bound

Theorem 1.3
(Plotkin Bound) Provided \(d>\theta n\), where \(\theta =1-q^{-1}\), then,
$$\begin{aligned} A_q(n,d)\le \left\lfloor \dfrac{d}{d-\theta n}\right\rfloor \end{aligned}$$
Proof
Let \(S=\sum d(\mathbf {x},\mathbf {y})\) for all codewords \(\mathbf {x},\mathbf {y}\in \mathscr {C}\), and \(\mathbf {x}\ne \mathbf {y}\), and \(d(\mathbf {x},\mathbf {y})\) denotes the hamming distance between codewords \(\mathbf {x}\) and \(\mathbf {y}\). Assume that all the codewords of \(\mathscr {C}\) are arranged in an \(M\times n\) matrix D. Since \(d(\mathbf {x},\mathbf {y})\ge d\),
$$\begin{aligned} S\ge \frac{M!}{(M-2)!}d=M(M-1)d. \end{aligned}$$
(1.34)
Let \(n_{i,\alpha }\) be the number of times an element \(\alpha \) in the defining field of the code \(\text {GF}(q)\) occurs in the ith column of the matrix D. Then, \({\displaystyle \sum _{\alpha \in \text {GF}(q)}n_{i,\alpha }=M}\). For each \(n_{i,\alpha }\) there are \(M-n_{i,\alpha }\) entries of the matrix D in column i that have elements other than \(\alpha \). These entries are a hamming distance 1 from the \(n_{i,\alpha }\) entries and there are n possible columns. Thus,
$$\begin{aligned} S&=n\sum _{i=1}^n \sum _{\alpha \in \text {GF}(q)}n_{i,\alpha }(M-n_{i,\alpha })\nonumber \\&=nM^2-\sum _{i=1}^n \sum _{\alpha \in \text {GF}(q)}n_{i,\alpha }^2. \end{aligned}$$
(1.35)
From the Cauchy–Schwartz inequality,
$$\begin{aligned} \left( \sum _{\alpha \in \text {GF}(q)}n_{i,\alpha }\right) ^2\le q\sum _{\alpha \in \text {GF}(q)}n_{i,\alpha }^2. \end{aligned}$$
(1.36)
Equation (1.35) becomes,
$$\begin{aligned} S\le nM^2-\sum _{i=1}^n q^{-1}\left( \sum _{\alpha \in \text {GF}(q)}n_{i,\alpha }\right) ^2 \end{aligned}$$
(1.37)
Let \(\theta =1-q^{-1}\),
$$\begin{aligned} S&\le nM^2-\sum _{i=1}^n q^{-1}\left( \sum _{\alpha \in \text {GF}(q)}n_{i,\alpha }\right) ^2\nonumber \\&\le nM^2-q^{-1}nM^2\nonumber \\&\le n\theta M^2. \end{aligned}$$
(1.38)
Thus from (1.34) and (1.38) we have,
$$\begin{aligned}&M(M-1)d\le S\le n\theta M^2\end{aligned}$$
(1.39)
$$\begin{aligned}&M\le \left\lfloor \dfrac{d}{d-\theta n}\right\rfloor \end{aligned}$$
(1.40)
and clearly \(d>\theta n\).
Corollary 1.1
(Asymptotic Plotkin Bound) The asymptotic Plotkin bound is given by,
$$\begin{aligned} \alpha _q(\delta )&=0 \qquad&\mathrm{if}\quad \theta \le \delta \le 1\\ \alpha _q(\delta )&\le 1-\dfrac{\delta }{\theta } \qquad&\mathrm{if}\quad 0\le \delta \le \theta . \end{aligned}$$

1.2.1.3 Singleton Bound

Theorem 1.4
(Singleton Bound) The maximum number of codewords \(A_q(n,d)\) is upper bounded by,
$$\begin{aligned} A_q(n,d)\le q^{n-d+1}. \end{aligned}$$
Codes that meet this bound with equality, i.e. \(d=n-k+1\), are called maximum distance separable codes (MDS). The asymptotic Singleton bound is given Theorem 1.5.
Theorem 1.5
(Asymptotic Singleton Bound) The information rate \(\alpha _q(\delta )\) is upper bounded by,
$$\begin{aligned} \alpha _q(n,\delta )\le 1-\delta . \end{aligned}$$
The asymptotic Singleton bound does not depend on the field size q and is a straight line with a negative slope in a plot of \(\alpha _q(\delta )\) against \(\delta \) for every field.

1.2.1.4 Elias Bound

Another upper bound is the Elias bound [17]. This bound was discovered by P. Elias but was never published by the author. We only state the bound here as the proof is beyond the scope of this text. For a complete treatment see [6, 10].
Theorem 1.6
(Elias Bound) A code \(\mathscr {C}\) of length n with codewords having weight at most w, \(w<\theta n\) with \(\theta =1-q^{-1}\) has,
$$\begin{aligned} d\le \frac{Mw}{M-1}\left( 2-\frac{w}{\theta n}\right) \end{aligned}$$
Theorem 1.7
(Asymptotic Elias Bound) The information rate \(\alpha _q(\delta )\) is upper bounded by,
$$\begin{aligned} \alpha _q(\delta )\le 1-H_q(\theta -\sqrt{\theta (\theta -\delta )}) \end{aligned}$$
provided \(0<\delta <\theta \) where \(\theta =1-q^{-1}\).

1.2.1.5 MRRW Bounds

The McEliece–Rodemich–Rumsey–Welch (MRRW) bounds are asymptotic bounds obtained using linear programming.
Theorem 1.8
(Asymptotic MRRW Bound I) Provided \(0<r<\theta \), \(\theta =1-{q^{-1}}\) then,
$$\begin{aligned} \alpha _q(\delta )\le H_q\left( \frac{1}{q}(q-1-(q-2)\delta -2\sqrt{\delta (1-\delta )(q-1)})\right) \end{aligned}$$
The second MRRW bound applies to the case when \(q=2\).
Theorem 1.9
(MRRW Bound II) Provided \(0<\delta <\frac{1}{2}\) and \(q=2\) then,
$$\begin{aligned} \alpha _2(\delta )\le \min _{0\le u\le 1-2\delta }\{1+g(u^2)-g(u^2+2\delta u+2\delta )\} \end{aligned}$$
where
$$\begin{aligned} g(x)=H_2\left( \frac{1-\sqrt{1-x}}{2}\right) . \end{aligned}$$
The MRRW bounds are the best-known upper bound on the information rate for the binary case. The MRRW-II bound is better than the MRRW-I bound when \(\delta \) is small and \(q=2\). An in depth treatment and proofs of the bounds can be found in [12].

1.2.2 Lower Bounds

1.2.2.1 Gilbert–Varshamov Bound

Theorem 1.10
(Gilbert–Varshamov Bound) The maximum number of codewords \(A_q(n,d)\) is lower bounded by,
$$\begin{aligned} A_q(n,d)\ge \frac{q^n}{V_q(n,d-1)}=\dfrac{q^n}{\displaystyle \sum _{i=0}^{d-1} \left( {\begin{array}{c}n\\ i\end{array}}\right) (q-1)^i}. \end{aligned}$$
Proof
We know that \(V_q(n,d-1)\) represents the volume of a sphere centred on a codeword of \(\mathscr {C}\) of radius \(d-1\). Suppose \(\mathscr {C}\) has \(A_q(n,d)\) codewords. Every vector \(\mathbf {v}\in \mathbb {F}_q^n\) lies within a sphere of volume \(V_q(n,d-1)\) centred at a codeword of \(\mathscr {C}\) as such,
$$\begin{aligned} \left|\bigcup _{i=1}^{A_q(n,d)} S_i \right|= |\mathbb {F}_{q}^n |, \end{aligned}$$
where \(S_i\) is a set containing all vectors in a sphere of radius \(d-1\) centred on a codeword of \(\mathscr {C}\). The spheres \(S_i\) are not mutually disjoint. If we assume \(S_i\) are mutually disjoint then,
$$\begin{aligned} A_q(n,d)V_q(n,d-1)\ge |\mathbb {F}_{q}^n |. \end{aligned}$$
Theorem 1.11
The information rate of a code is lower bounded by,
$$\begin{aligned} \alpha _q(\delta )\ge 1- H_q(\delta ) \end{aligned}$$
for \(0\le \delta \le \theta \), \(\theta =1-q^{-1}\).
Figures 1.10 and 1.11 show the asymptotic upper and lower bounds for the cases where \(q=2\) and \(q=32\), respectively. Figure 1.11 shows that the MRRW bounds are the best-known upper bounds when \(q=2\). Observe that the Plotkin bound is the best upper bound for the case when \(q=32\).

1.2.3 Lower Bounds from Code Tables

Tables of best-known codes are maintained such that if a code defined in a field q is constructed with an evaluated and verifiable minimum Hamming distance d that exceeds a previously best-known code with the same length n and dimension, the dimension of the new code is a lower bound on \(A_q(n,d)\). The first catalogue of best-known codes was presented by Calabi and Myrvaagnes [2] containing binary codes of length n and dimension k in the range \(1\le k \le n \le 24\). Brouwer and Verhoeff [1] subsequently presented a comprehensive update to the tables which included codes with finite fields up to size 9 with the ranges for k and n.
Table 1.1
Ranges for codes
Finite field
Range
\(\mathbb {F}_{2}\)
\(1 \le k \le n\le 256\)
\(\mathbb {F}_{3}\)
\(1 \le k \le n\le 243\)
\(\mathbb {F}_{4}\)
\(1 \le k \le n\le 256\)
\(\mathbb {F}_{5}\)
\(1 \le k \le n\le 130\)
\(\mathbb {F}_{7}\)
\(1 \le k \le n\le 100\)
\(\mathbb {F}_{8}\)
\(1 \le k \le n\le 130\)
\(\mathbb {F}_{9}\)
\(1 \le k \le n\le 130\)
At present, Grassl [5] maintains a significantly updated version of the tables in [1]. The tables now contain codes with k and n in ranges from Table 1.1. Finally, Schimd and Shurer [15] provide an online database for optimal parameters of (tms)-nets, (ts)-sequences, orthogonal arrays, linear codes and ordered orthogonal arrays. These are relatively new tables and give the best-known codes up to finite fields of size 256. The search for codes whose dimension exceeds the best-known lower bounds on \(A_q(n,d)\) is an active area of research with the research community constantly finding improvements.

1.3 Summary

In this chapter we discussed the theoretical performance of binary codes for the additive white Gaussian noise (AWGN) channel. In particular the usefulness of Gallager’s coding theorem for binary codes was explored. By assuming a binomial weight distribution for linear codes, it was shown that the decoder error probability performance of some of the best, known linear, binary codes is the same as the average performance of the ensemble of all randomly chosen, binary nonlinear codes having the same length and dimension. Assuming a binomial weight distribution, an upper bound was determined for the erasure performance of any code, and it was shown that this can be translated into an upper bound for code performance in the AWGN channel. Different theoretical bounds on the construction of error-correction codes were discussed. For the purpose of constructing good error-correcting codes, theoretical upper bounds provide fundamental limits beyond which no improvement is possible.
Open Access This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://​creativecommons.​org/​licenses/​by/​4.​0/​), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.
The images or other third party material in this chapter are included in the book’s Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the book’s Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.
Footnotes
1
Where the code dimension \(k=\log _qM\).
 
Literature
1.
go back to reference Brouwer, A., Verhoeff, T.: An updated table of minimum-distance bounds for binary linear codes. IEEE Trans. Inf. Theory 39(2), 662–677 (1993)MathSciNetCrossRefMATH Brouwer, A., Verhoeff, T.: An updated table of minimum-distance bounds for binary linear codes. IEEE Trans. Inf. Theory 39(2), 662–677 (1993)MathSciNetCrossRefMATH
2.
go back to reference Calabi, L., Myrvaagnes, E.: On the minimal weight of binary group codes. IEEE Trans. Inf. Theory 10(4), 385–387 (1964)CrossRef Calabi, L., Myrvaagnes, E.: On the minimal weight of binary group codes. IEEE Trans. Inf. Theory 10(4), 385–387 (1964)CrossRef
3.
go back to reference Chen, C.L.: Computer results on the minimum distance of some binary cyclic codes. IEEE Trans. Inf. Theory 16(3), 359–360 (1970)CrossRef Chen, C.L.: Computer results on the minimum distance of some binary cyclic codes. IEEE Trans. Inf. Theory 16(3), 359–360 (1970)CrossRef
4.
go back to reference Gallager, R.G.: A simple derivation of the coding theorem and some applications. IEEE Trans. Inf. Theory 11(1), 459–470 (1960)MathSciNet Gallager, R.G.: A simple derivation of the coding theorem and some applications. IEEE Trans. Inf. Theory 11(1), 459–470 (1960)MathSciNet
6.
go back to reference Huffman, W.C., Pless, V.S.: Fundamentals of Error-Correcting Codes. Cambridge University Press, Cambridge (2003). ISBN 0 521 78280 5 Huffman, W.C., Pless, V.S.: Fundamentals of Error-Correcting Codes. Cambridge University Press, Cambridge (2003). ISBN 0 521 78280 5
8.
go back to reference Krasikov, I., Litsyn, S.: On the accuracy of the binomial approximation to the distance distribution of codes. IEEE Trans. Inf. Theory 41(5), 1472–1474 (1995)MathSciNetCrossRefMATH Krasikov, I., Litsyn, S.: On the accuracy of the binomial approximation to the distance distribution of codes. IEEE Trans. Inf. Theory 41(5), 1472–1474 (1995)MathSciNetCrossRefMATH
10.
go back to reference MacWilliams, F.J., Sloane, N.J.A.: The Theory of Error-Correcting Codes. North-Holland, Amsterdam (1977) MacWilliams, F.J., Sloane, N.J.A.: The Theory of Error-Correcting Codes. North-Holland, Amsterdam (1977)
11.
go back to reference Massey, J.: Coding and modulation in digital communication. In: Proceedings of International Zurich Seminar on Digital Communication, pp. E2(1)–E2(24) (1974) Massey, J.: Coding and modulation in digital communication. In: Proceedings of International Zurich Seminar on Digital Communication, pp. E2(1)–E2(24) (1974)
12.
go back to reference McEliece, R., Rodemich, E., Rumsey, H., Welch, L.: New upper bounds on the rate of a code via the delsarte-macwilliams inequalities. IEEE Trans. Inf. Theory 23(2), 157–166 (1977)MathSciNetCrossRefMATH McEliece, R., Rodemich, E., Rumsey, H., Welch, L.: New upper bounds on the rate of a code via the delsarte-macwilliams inequalities. IEEE Trans. Inf. Theory 23(2), 157–166 (1977)MathSciNetCrossRefMATH
13.
go back to reference Promhouse, G., Tavares, S.E.: The minimum distance of all binary cyclic codes of odd lengths from \(69\) to \(99\). IEEE Trans. Inf. Theory 24(4), 438–442 (1978)CrossRefMATH Promhouse, G., Tavares, S.E.: The minimum distance of all binary cyclic codes of odd lengths from \(69\) to \(99\). IEEE Trans. Inf. Theory 24(4), 438–442 (1978)CrossRefMATH
14.
go back to reference Roychowdhury, V.P., Vatan, F.: Bounds for the weight distribution of weakly self-dual codes. IEEE Trans. Inf. Theory 47(1), 393–396 (2001)MathSciNetCrossRefMATH Roychowdhury, V.P., Vatan, F.: Bounds for the weight distribution of weakly self-dual codes. IEEE Trans. Inf. Theory 47(1), 393–396 (2001)MathSciNetCrossRefMATH
16.
go back to reference Schomaker, D., Wirtz, M.: On binary cyclic codes of odd lengths from \(101\) to \(127\). IEEE Trans. Inf. Theory 38(2), 516–518 (1992)CrossRefMATH Schomaker, D., Wirtz, M.: On binary cyclic codes of odd lengths from \(101\) to \(127\). IEEE Trans. Inf. Theory 38(2), 516–518 (1992)CrossRefMATH
17.
go back to reference Shannon, C., Gallager, R., Berlekamp, E.: Lower bounds to error probability for coding on discrete memoryless channels, i. Inf. Control 10(1), 65–103 (1967)MathSciNetCrossRefMATH Shannon, C., Gallager, R., Berlekamp, E.: Lower bounds to error probability for coding on discrete memoryless channels, i. Inf. Control 10(1), 65–103 (1967)MathSciNetCrossRefMATH
18.
go back to reference Shannon, C.E.: Probability of error for optimal codes in a Gaussian channel. Bell Syst. Tech. J. 38(3), 611–656 (1959)MathSciNetCrossRef Shannon, C.E.: Probability of error for optimal codes in a Gaussian channel. Bell Syst. Tech. J. 38(3), 611–656 (1959)MathSciNetCrossRef
19.
go back to reference Tjhai, C., Tomlinson, M.: Results on binary cyclic codes. Electron. Lett. 43(4), 234–235 (2007)CrossRef Tjhai, C., Tomlinson, M.: Results on binary cyclic codes. Electron. Lett. 43(4), 234–235 (2007)CrossRef
20.
go back to reference Wozencraft, J.: Sequential decoding for reliable communications. Technical Report No. 325 Research Laboratory of Electronics, MIT (1957) Wozencraft, J.: Sequential decoding for reliable communications. Technical Report No. 325 Research Laboratory of Electronics, MIT (1957)
21.
go back to reference Wozencraft, J., Jacobs, I.: Principles of Communication Engineering. Wiley, New York (1965) Wozencraft, J., Jacobs, I.: Principles of Communication Engineering. Wiley, New York (1965)
22.
go back to reference Wozencraft, J., Kennedy, R.: Modulation and demodulation for probabilistic coding. IEEE Trans. Inf. Theory IT 12, 291–297 (1966) Wozencraft, J., Kennedy, R.: Modulation and demodulation for probabilistic coding. IEEE Trans. Inf. Theory IT 12, 291–297 (1966)
Metadata
Title
Bounds on Error-Correction Coding Performance
Authors
Martin Tomlinson
Cen Jung Tjhai
Marcel A. Ambroze
Mohammed Ahmed
Mubarak Jibril
Copyright Year
2017
DOI
https://doi.org/10.1007/978-3-319-51103-0_1