# The art of error correcting coding - Moreloz R.H.

ISBN 0471-49581-6

**Download**(direct link)

**:**

**21**> 22 23 24 25 26 27 .. 86 >> Next

BINARY CYCLIC CODES AND BCH CODES

37

circuit that multiplies by xn~k and divides by g(x). After k cycles, the shift register contains the remainder of the division, the switch moves to position 2 and the contents of the register are sent through the channel.

Figure 17 Circuit for systematic encoding: Division by g(x).

Duals of cyclic codes and maximum-Iength-sequence codes

By analogy with linear codes, the dual code of a cyclic code C with generator polynomial g(x) is the cyclic code CL generated by the polynomial h{ x). The important class of maximum-Iength-sequence (MLS) cyclic codes [PW] has as members the duals of the cyclic Hamming codes. An MLS cyclic (2m - 1, m, 2m~1) code is generated by the polynomial g(x) — (xn + l)/p(x), where p(x) is a primitive polynomial'.

3.1.5 Shortened cyclic codes and CRC codes

There are many practical applications in which an error correcting code with simple encoding and decoding procedures is desired, but existing constructions do not give the desired length, dimension and minimum distance.

The following is an example from an email recently sent to the author: We plan to use a simple FEC/ECC scheme to detect/correct single-bit errors in a 64-bit data block. The objective is to find or choose an ECC scheme to correct single-bit errors with up to 8 bits of overhead, giving a maximum of 72 bits ( 64 data bits plus 8 redundant bits) in total.

Naturally, since 72 is not of the form 2TO — 1, none of the cyclic codes studied so far can be applied directly. One possible solution is to use a cyclic Hamming (127,120,3) code and to shorten it until a dimension k = 64 is reached. This yields a shortened Hamming (71,64,3) code2.

Shortening is accomplished by not using all the information bits of a code. Let s

1 For a definition of primitive polynomial, see page 41.

2 This is an example to introduce the concept of shortening. A (72,64,4) single-error-correcting/double-error-detecting (SEC/DED) code, based on a shortened Hamming code, and adding an overall parity-check bit, was proposed for the IBM model 360 mainframe ([Hsia] and Chapter 16 of [LC]).

38

THE ART OF ERROR CORRECTING CODING

denote the number of information bits not used, referred to as the shortening depth. Let C denote a cyclic (n, k, d) code. A shortened message is obtained by fixing s (arbitrary) message positions to zero. This leaves k — s positions available for the message bits. Without loss of generality, let the highest positions in a message be set to zero. Then u(x) = uq + U\X + • • • + Uk~i-Sxk~1~s? The output of a systematic encoder, when the input is the message polynomial ?(x), produces the code polynomial v(x) = xn~ku(x) + [xn~k?(x) mod y{x)}. of degree up to n — 1 — s. This shows that the resulting shortened code Cs is a linear (n — s,k — s,ds) code with ds > d. In general, the shortened code Cs is no longer cyclic.

Example 24 Let C denote the cyclic Hamming (7,4,3) code with generator polynomial g(x) = 1 + x + x3. A new code is derived from C by sending 2 leading zeros followed by two information bits and the same three redundant bits computed by an encoder in C. This process gives a set of codewords that forms a shortened linear (5,2,3) code.

The fundamental property of a shortened code Cs obtained from a cyclic code is that, although the code is generally no longer cyclic, the same encoder and decoder can be used, after the leading zeros are properly taken into account. In computer simulations, it is easy to simply pad the codewords with zeros followed by the codeword in Cs and use the same encoding and decoding algorithms discussed in the book. This method is widely used in hardware implementations of Reed-Solomon decoders. Alternatively, the leading zeros in a message do not need to be included in the codeword. Instead, the decoder circuit is modified to multiply the incoming received polynomial f (x) by xn~k+s modulo g(x), instead of xn~k modulo g(x) in the conventional decoder. More details on the modified encoder and decoder structures for shortened cyclic code can be found in [PW, LC, Wic], among other references.

Another possible solution is to try to construct other classes of cyclic codes with the desired parameters. Interesting classes of cyclic codes not covered in the text are the non-primitive BCH codes [PW] and the Euclidean geometry (EG) and projective geometry (PG) codes [LC]. Yet another possibility is to use a non-binary cyclic code, such as a Reed-Solomon code discussed in the next chapter, and to express it in terms of bits. This binary image of a RS code will have the additional feature of being able to correct many bursts of errors. See Chapter 4 for more information.

CRC codes

One of the most popular forms of ECC are the cyclic redundancy check codes, or CRC codes. These cyclic codes are used to detect errors in blocks of data. CRC codes are cyclic codes of length n < 2m — 1. Typically, CRC codes have generator polynomials of the form (1 + x)g(x), where g(x) is the generator polynomial of a cyclic Hamming code. Common values of m are 12, 16 and 32. The choice of the generator polynomials is dictated by the undetected error probability, which depends on the weight distribution of the code. The computation of the undetected error probability of a cyclic code is tantamount to determining its weight distribution. This has remained an elusive task, even after 50 years of coding theory, with some progress reported in [FKKL, Kaz] and references therein. Below is a list of the most popular generator polynomials of CRC codes, or CRC polynomials:

**21**> 22 23 24 25 26 27 .. 86 >> Next