5. Good Binary Linear Codes

Two of the important performance indicators for a linear code are the minimum Hamming distance and the weight distribution. Efficient algorithms for computing the minimum distance and weight distribution of linear codes are explored below. Using these methods, the minimum distances of all binary cyclic codes of length 129–189 have been enumerated. The results are presented in Chap. 4. Many improvements to the database of best-known codes are described below. In addition, methods of combining known codes to produce good codes are explored in detail. These methods are applied to cyclic codes, and many new binary codes have been found and are given below.

The quest of achieving Shannon’s limit for the AWGN channel has been approached in a number of different ways. Here we consider the problem formulated by Shannon of the construction of good codes which maximise the difference between the error rate performance for uncoded transmission and coded transmission. For uncoded, bipolar transmission with matched filtered reception, it is well known (see for example Proakis [20]) that the bit error rate, \(p_{b}\), is given byComparing this equation with the equation for the probability of error when using coding, viz. the probability of deciding on one codeword rather than another, Eq. (1.​4) given in Chap. 1, it can be seen that the improvement due to coding, the coding gain is indicated by the term \(d_{min}.\frac{k}{n}\), the product of the minimum distance between codewords and the code rate. This is not the end of the story in calculating the overall probability of decoder error because this error probability needs to be multiplied by the number of codewords distance \(d_{min}\) apart.

For a linear binary code, the Hamming distance between two codewords is equal to the Hamming weight of the codeword formed by adding the two codewords together. Moreover, as the probability of decoder error at high \(\frac{E_b}{N_0}\) values depends on the minimum Hamming distance between codewords, for a linear binary code, the performance of the code depends on the minimum Hamming weight codewords of the code, the \(d_{min}\) of the code and the number of codewords with this weight (the multiplicity). For a given code rate (\(\frac{k}{n}\)) and length n, the higher the weight of the minimum Hamming weight codewords of the code, the better the performance, assuming the multiplicity is not too high. It is for this reason that a great deal of research effort has been extended, around the world in determining codes with the highest minimum Hamming weight for a given code rate (\(\frac{k}{n}\)) and length n. These codes are called the best-known codes with parameters (n, k, d), where d is understood to be the \(d_{min}\) of the code, and the codes are tabulated in a database available online [12] with sometimes a brief description or reference to their method of construction.¹

In this approach, it is assumed that a decoding algorithm either exists or will be invented which realises the full performance of a best-known code. For binary codes of length less than 200 bits the Dorsch decoder described in Chap. 15 does realise the full performance of the code.

Computing the minimum Hamming weight codewords of a linear code is, in general, a Nondeterministic Polynomial-time (NP) hard problem, as conjectured by [2] and later proved by [24]. Nowadays, it is a common practice to use a multi-threaded algorithm which runs on multiple parallel computers (grid computing) for minimum Hamming distance evaluation. Even then, it is not always possible to evaluate the exact minimum Hamming distance for large codes. For some algebraic codes, however, there are some shortcuts that make it possible to obtain the lower and upper bounds on this distance. But knowing these bounds are not sufficient as the whole idea is to know explicitly the exact minimum Hamming distance of a specific constructed code. As a consequence, algorithms for evaluating the minimum Hamming distance of a code are very important in this subject area and these are described in the following section.

It is worth mentioning that a more accurate benchmark of how good a code is, in fact its Hamming weight distribution. Whilst computing the minimum Hamming distance of a code is in general NP-hard, computing the Hamming weight distribution of a code is even more complex. In general, for two codes of the same length and dimension but of different minimum Hamming distance, we can be reasonably certain that the code with the higher distance is the superior code. Unless we are required to decide between two codes with the same parameters, including minimum Hamming distance, it is not necessary to go down the route of evaluating the Hamming weight distribution of both codes.

The minimum distance of all binary cyclic codes of lengths less than or equal to 99 has been determined by Chen [7, 8] and Promhouse et al. [21].

This was later extended to longer codes with the evaluation of the minimum distance of binary cyclic codes of lengths from 101 to 127 by Schomaker et al. [22]. We extend this work to include all cyclic codes of odd lengths from 129 to 189 in this book. The aim was to produce a Table of codes as a reference source for the highest minimum distance, with the corresponding roots of the generator polynomial, attainable by all cyclic codes over \(\mathbb {F}_2\) of odd lengths from 129 to 189. It is well known that the coordinate permutation \(\sigma : i \rightarrow \mu i\), where \(\mu \) is an integer relatively prime to n, produces equivalent cyclic codes [3, p. 141f]. With respect to this property, we construct a list of generator polynomials g(x) of all inequivalent and non-degenerate [16, p. 223f] cyclic codes of \(129 \le n \le 189\) by taking products of the irreducible factors of \(x^n-1\). Two trivial cases are excluded, namely \(g(x)=x+1\) and \(g(x)=(x^n-1)/(x+1)\), since these codes have trivial minimum distance and exist for any odd integer n. The idea is for each g(x) of cyclic codes of odd length n; the systematic generator matrix is formed and the minimum distance of the code is determined using Chen’s algorithm (Algorithm 5.3). However, due to the large number of cyclic codes and the fact that we are only interested in those of largest minimum distance for given n and k, we include a threshold distance \(d_{th}\) in Algorithm 5.3. Say, for given n and k, we have a list of generator polynomials g(x) of all inequivalent cyclic codes. Starting from the top of the list, the minimum distance of the corresponding cyclic code is evaluated. If a codeword of weight less than or equal to \(d_{th}\) is found during the enumeration, the computation is terminated immediately and the next g(x) is then processed. The threshold \(d_{th}\), which is initialised with 0, is updated with the largest minimum distance found so far for given n and k.

Table 4.​3 in Sect. 4.5 shows the highest attainable minimum distance of all binary cyclic codes of odd lengths from 129 to 189. The number of inequivalent and non-degenerate cyclic codes for a given odd integer n, excluding the two trivial cases mentioned above, is denoted by \(N_{\mathscr {C}}\).

Note that Table 4.​3 does not contain entries for primes \(n=8m \pm 3\). This is because for these primes, 2 is not a quadratic residue modulo n and hence, \(\text {ord}_2(n) = n-1\). As a consequence, \(x^n-1\) factors into two irreducible polynomials only, namely \(x+1\) and \((x^n-1)/(x+1)\) which generate trivial codes. Let \(\beta \) be a primitive nth root of unity, the roots of g(x) of a cyclic code (excluding the conjugate roots) are given in terms of the exponents of \(\beta \). The polynomial m(x) is the minimal polynomial of \(\beta \) and it is represented in octal format with most significant bit on the left. That is, \(m(x)=166761\), as in the case for \(n=151\), represents \(x^{15}+x^{14}+x^{13}+x^{11}+x^{10}+x^8+x^7+x^6+x^5+x^4+1\).

Constructing an [n, k] linear code possessing the largest minimum distance is one of the main problems in coding theory. There exists a database containing the lower and upper bounds of minimum distance of binary linear codes of lengths \(1 \le n \le 256\). This database appears in [6] and the updated version is accessible online.⁵

The lower bound corresponds to the largest minimum distance for a given \([n,k]_q\) code that has been found to date. Constructing codes which improves Brouwer’s lower bounds is an on-going research activity in coding theory. Recently, Tables of lower- and upper-bounds of not only codes over finite-fields, but also quantum error-correcting codes, have been published by Grassl [12]. These bounds for codes over finite-fields, which are derived from MAGMA [5], appear to be more up-to-date than those of Brouwer.

We have presented in Sect. 5.3, the highest minimum distance attainable by all binary cyclic codes of odd lengths from 129 to 189 and found none of these cyclic codes has larger minimum distance than the corresponding Brouwer’s lower bound for the same n and k. The next step is to consider longer length cyclic codes, \(191 \le n \le 255\). For these lengths, unfortunately, we have not been able to repeat the exhaustive approach of Sect. 5.3 in a reasonable amount of time. This is due to the computation time to determine the minimum distance of these cyclic codes and also, for some lengths (e.g. 195 and 255), there are a tremendous number of inequivalent cyclic codes. Having said that, we can still search for improvements from lower rate cyclic codes of these lengths for which the minimum distance computation can be completed in a reasonable time. We have found many new cyclic codes that improve Brouwer’s lower bound and before we present these codes, we should first consider the evaluation procedure.

As before, let \(\beta \) be a primitive nth root of unity and let \(\varLambda \) be a set containing all distinct (excluding the conjugates) exponents of \(\beta \). The polynomial \(x^n-1\) can be factorised into irreducible polynomials \(f_i(x)\) over \(\mathbb {F}_2\), \(x^n-1 = \prod _{i\in \varLambda } f_i(x)\). For notational purposes, we denote the irreducible polynomial \(f_i(x)\) as the minimal polynomial of \(\beta ^i\). The generator and parity-check polynomials, denoted by g(x) and h(x) respectively, are products of \(f_i(x)\). Given a set \(\varGamma \subseteq \varLambda \), a cyclic code \(\mathscr {C}\) which has \(\beta ^i\), \(i\in \varGamma \), as the non-zeros can be constructed. This means the parity-check polynomial h(x) is given byand the dimension k of this cyclic code is \(\sum _{i \in \varGamma } \deg (f_i(x))\), where \(\deg (f(x))\) denotes the degree of f(x). Let \(\varGamma ^\prime \subseteq \varLambda \setminus \{0\}\), \(h^\prime (x) = \prod _{i \in \varGamma ^\prime } f_i(x)\) and \(h(x) = (1+x) h^\prime (x)\). Given \(\mathscr {C}\) with parity-check polynomial h(x), there exists an \([n,k-1,d^\prime ]\) expurgated cyclic code, \(\mathscr {C}^\prime \), which has parity-check polynomial \(h^\prime (x)\). For this cyclic code, \(\mathrm {wt}_H(\varvec{c}) \equiv 0 \pmod { 2}\) for all \(\varvec{c}\in \mathscr {C}^\prime \). For convenience, we call \(\mathscr {C}\) the augmented code of \(\mathscr {C}^\prime \).

Consider an \([n,k-1,d^\prime ]\) expurgated cyclic code \(\mathscr {C}^\prime \), let the set \(\varvec{\varGamma }=\{\varGamma _1,\varGamma _2,\ldots ,\varGamma _r\}\) where, for \(1 \le j \le r\), \(\varGamma _j \subseteq \varLambda \setminus \{0\}\) and \(\sum _{i \in \varGamma _j}\deg (f_i(x)) = k-1\). For each \(\varGamma _j \in \varvec{\varGamma }\), we compute \(h^\prime (x)\) and construct \(\mathscr {C}^\prime \). Having constructed the expurgated code, the augmented code can be easily obtained as shown below. Let \(\varvec{G}\) be a generator matrix of the augmented code \(\mathscr {C}\), and without loss of generality, it can be written aswhere \(\varvec{G}^\prime \) is a generator matrix of \(\mathscr {C}^\prime \) and the vector \(\varvec{v}\) is a coset of \(\mathscr {C}^\prime \) in \(\mathscr {C}\). Using the arrangement in (5.8), we evaluate \(d^\prime \) by enumerating codewords \(c\in \mathscr {C}^\prime \) from \(\varvec{G}^\prime \). The minimum distance of \(\mathscr {C}\), denoted by d, is simply \(\min _{\varvec{c}\in \mathscr {C}^\prime }\{d^\prime , \mathrm {wt}_H(\varvec{c} + \varvec{v})\}\) for all codewords \(\varvec{c}\) enumerated. We follow Algorithm 5.3 to evaluate \(d^\prime \). Let \(d_{Brouwer}\) and \(d^\prime _{Brouwer}\) denote the lower bounds of [6] for linear codes of the same length and dimension as those of \(\mathscr {C}\) and \(\mathscr {C}^\prime \) respectively. During the enumerations, as soon as \(d \le d_{Brouwer}\) and \(d^\prime \le d^\prime _{Brouwer}\), the evaluation is terminated and the next \(\varGamma _j\) in \(\varvec{\varGamma }\) is then processed. However, if \(d \le d_{Brouwer}\) and \(d^\prime > d^\prime _{Brouwer}\), only the evaluation for \(\mathscr {C}\) is discarded. Nothing is discarded if both \(d^\prime > d^\prime _{Brouwer}\) and \(d > d_{Brouwer}\). This procedure continues until an improvement is obtained; or the set in \(\varvec{\varGamma }\) has been exhausted, which means that there does not exist \([n,k-1]\) and [n, k] cyclic codes which are improvements to Brouwer’s lower bounds. In cases where the minimum distance computation is not feasible using a single computer, we switch to a parallel version using grid computers.

Table 5.1 presents the results of the search for new binary cyclic codes having lengths \(195 \le n \le 255\). The cyclic codes in this table are expressed in terms of the parity-check polynomial h(x), which is given in the last column by the exponents of \(\beta \) (excluding the conjugates). Note that the polynomial m(x), which is given in octal with the most significant bit on the left, is the minimal polynomial of \(\beta \). In many cases, the entries of \(\mathscr {C}\) and \(\mathscr {C}^\prime \) are combined in a single row and this is indicated by “a / b” where the parameters a and b are for \(\mathscr {C}^\prime \) and \(\mathscr {C}\), respectively. The notation “[0]” indicates that the polynomial \((1+x)\) is to be excluded from the parity-check polynomial of \(\mathscr {C}^\prime \).

Some of these tabulated cyclic codes have a minimum Hamming distance which coincides with the lower bounds given in [12]. These are presented in Table 5.1 with the indicative mark “\(\dagger \)”.

In the late 1970s, computing the minimum distance of extended Quadratic Residue (QR) codes was posed as an open research problem by MacWilliams and Sloane [16]. Since then, the minimum distance of the extended QR code for the prime 199 has remained an open question. For this code, the bounds of the minimum distance were given as \(16-32\) in [16] and the lower bound was improved to 24 in [9]. Since \(199\equiv -1 \pmod { 8}\), the extended code is a doubly even self-dual code and its automorphism group contains a projective special linear group, which is known to be doubly transitive [16]. As a result, the minimum distance of the binary [199, 100] QR code is odd, i.e.  \(d \equiv 3 \pmod { 4}\), and hence, \(d=23\), 27 or 31. Due to the cyclic property and the rate of this QR code [7], we can safely assume that a codeword of weight d has maximum information weight of \(\lfloor {d/2}\rfloor \). If a weight d codeword does not satisfy this property, there must exist one of its cyclic shifts that does. After enumerating all codewords up to (and including) information weight 13 using grid computers, no codeword of weight less than 31 was found, implying that d of this binary [199, 100] QR code is indeed 31.

Without exploiting the property that \(d \equiv 3 \pmod { 4}\), an additional \(\left( {\begin{array}{c}100\\ 14\end{array}}\right) + \left( {\begin{array}{c}100\\ 15\end{array}}\right) \) codewords (88,373,885,354,647,200 codewords) would need to be enumerated in order to establish the same result and beyond available computer resources. Accordingly, we now know that there exists the [199, 99, 32] expurgated QR code and the [200, 100, 32] extended QR code.

It is interesting to note that many of the code improvements are contributed by low-rate cyclic codes of length 255 and there are 16 cases of this. Furthermore, it is also interesting that Table 5.1 includes a [255, 55, 70] cyclic code and a [255, 63, 65] cyclic code, which are superior to the BCH codes of the same length and dimension. Both of these BCH codes have minimum distance 63 only.

It is difficult to explicitly construct a new code with large minimum distance. However, the alternative approach, which starts from a known code which already has large minimum distance, seems to be more fruitful. Some of these methods are described below and in the following subsections, we present some new binary codes constructed using these methods, which improve on Brouwer’s lower bound.

Construction X is due to Sloane et al. [23] and it basically adds a tail, which is a codeword of the auxiliary code \(\mathscr {A}\), to \(\mathscr {B}_1\) so that the minimum distance is increased. The effect of Construction X can be visualised as follows. Let \(\varvec{G}_{\mathscr {C}}\) be the generator matrix of code \(\mathscr {C}\). Since \(\mathscr {B}_1 \supset \mathscr {B}_2\), we may express \(\varvec{G}_{\mathscr {B}_1}\) aswhere \(\varvec{V}\) is a \((k_1 - k_2) \times n\) matrix which contains the cosets of \(\mathscr {B}_2\) in \(\mathscr {B}_1\). We can see that the code generated by \(\varvec{G}_{\mathscr {B}_2}\) has minimum distance \(d_2\), and the set of codewords \(\{\varvec{v} + \varvec{c}_2\}\), for all \(\varvec{v}\in \varvec{V}\) and all codewords \(\varvec{c}_2\) generated by \(\varvec{G}_{\mathscr {B}_2}\), have minimum weight of \(d_1\). By appending non-zero weight codewords of \(\mathscr {A}\) to the set \(\{\varvec{v} + \varvec{c}_2\}\), and all zeros codeword to each codeword of \(\mathscr {B}_2\), we have a lengthened code of larger minimum distance, \(\mathscr {C}_X\), whose generator matrix is given byWe can see that, for binary cyclic linear codes of odd minimum distance, code extension by annexing an overall parity-check bit is an instance of Construction X. In this case, \(\mathscr {B}_2\) is the even-weight subcode of \(\mathscr {B}_1\) and the auxiliary code \(\mathscr {A}\) is the trivial \([1,1,1]_2\) code.

Construction X given in Theorem 5.1 considers a chain of two codes only. There also exists a variant of Construction X, called Construction XX, which makes use of Construction X twice and it was introduced by Alltop [1].

The relationship among \(\mathscr {B}_1\), \(\mathscr {B}_2\), \(\mathscr {B}_3\) and \(\mathscr {B}_4\) can be illustrated as a lattice shown below [11].

Since \(\mathscr {B}_1\supset \mathscr {B}_2\), \(\mathscr {B}_1\supset \mathscr {B}_3\), \(\mathscr {B}_4\subset \mathscr {B}_2\) and \(\mathscr {B}_4\subset \mathscr {B}_3\), the generator matrices of \(\mathscr {B}_2\), \(\mathscr {B}_3\) and \(\mathscr {B}_1\) can be written asrespectively, where \(\varvec{V}_i\), \(i=2,3\), is the coset of \(\mathscr {B}_4\) in \(\mathscr {B}_i\), and \(\varvec{V}\) contains the cosets of \(\mathscr {B}_2\) and \(\mathscr {B}_3\) in \(\mathscr {B}_1\). Construction XX starts by applying Construction X to the pair of codes \(\mathscr {B}_1 \supset \mathscr {B}_2\) using \(\mathscr {A}_1\) as the auxiliary code. The resulting code is \(\mathscr {C}_X = [n + n_1, k_1, \min \{d_2, d_1 + d^\prime _1\}]\), whose generator matrix is given byThis generator matrix can be rearranged such that the codewords formed from the first n coordinates are cosets of \(\mathscr {B}_3\) in \(\mathscr {B}_1\). This rearrangement results in the following generator matrix of \(\mathscr {C}_X\),where \(\varvec{G}_{\mathscr {A}_1} \,{=}\, \left[ \dfrac{\varvec{G}^{(1)}_{\mathscr {A}_1}}{\varvec{G}^{(2)}_{\mathscr {A}_1}}\right] \). Next, using \(\mathscr {A}_2\) as the auxiliary code, applying Construction X to the pair \(\mathscr {B}_1 \supset \mathscr {B}_3\) with the rearrangement above, we obtain \(\mathscr {C}_{XX}\) whose generator matrix isWhile Constructions X and XX result in a code with increased length, there also exists a technique to obtain a shorter code with known minimum distance lower bounded from a longer code whose minimum distance and also that of its dual code are known explicitly. This technique is due to Sloane et al. [23] and it is called Construction Y1.

Given an [n, k, d] code, with standard code shortening, we obtain an \([n-i,k-i,\ge d]\) code where i indicates the number of coordinates to shorten. With Construction Y1, however, we can gain an additional dimension in the resulting shortened code. This can be explained as follows. Without loss of generality, we can assume the parity-check matrix of \(\mathscr {C}\), which is also the generator matrix of \(\mathscr {C}^\perp \), \(\varvec{H}\) contains a codeword \(\varvec{c}^\perp \) of weight \(d^\perp \). If we delete the coordinates which form the support of \(\varvec{c}^\perp \) from \(\varvec{H}\), now \(\varvec{H}\) becomes an \((n-k) \times n-d^\perp \) matrix and there is a row which contains all zeros among these \(n-k\) rows. Removing this all zeros row, we have an \((n-k-1)\times (n-d^\perp )\) matrix \(\varvec{H}^\prime \), which is the parity-check matrix of an \([n-d^\perp , n-d^\perp -(n-k-1), \ge d] = [n-d^\perp , k-d^\perp +1, \ge d]\) code \(\mathscr {C}^\prime \).

In the search for error-correcting codes with large minimum distance, having a fast, efficient algorithm to compute the exact minimum distance of a linear code is important. The evolution of various algorithms to evaluate the minimum distance of a binary linear code, from the naive approach to Zimmermann’s efficient approach, have been explored in detail. In addition to these algorithms, Chen’s approach in computing the minimum distance of binary cyclic codes is a significant breakthrough.

The core basis of a minimum distance evaluation algorithm is codeword enumeration. As we increase the weight of the information vector, the number of codewords grows exponentially. Zimmermann’s very useful algorithm may be improved by omitting generator matrices with overlapping information sets that never contribute to the lower bound throughout the enumeration. Early termination is important in the event that a new minimum distance is found that meets the lower bound value of the previous enumeration step. In addition, if the code under consideration has the property that every codeword weight is divisible by 2 or 4, the number of codewords that need to be enumerated can be considerably reduced.

With some simple modifications, these algorithms can also be used to collect and hence, count all codewords of a given weight to determine all or part of the weight spectrum of a code.

Given a generator matrix, codewords may be efficiently generated by taking linear combinations of rows of this matrix. This implies the faster we can generate the combinations, the less time the minimum distance evaluation algorithm will take. One such efficient algorithm to generate these combinations is called the revolving-door algorithm. The revolving-door algorithm has a nice property that allows the problem of generating combinations to be readily implemented in parallel. Having an efficient minimum distance computation algorithm, which can be computed in parallel on multiple computers has allowed us to extend earlier research results [8, 21, 22] in the evaluation of the minimum distance of cyclic codes. In this way, we obtained the highest minimum distance attainable by all binary cyclic codes of odd lengths from 129 to 189. We found that none of these cyclic codes has a minimum distance that exceeds the minimum distance of the best-known linear codes of the same length and dimension, which are given as lower bounds in [6]. However there are 134 cyclic codes that meet the lower bounds, see Sect. 5.3 and encoders and decoders may be easier to implement for the cyclic codes.