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

ISBN 0471-49581-6

**Download**(direct link)

**:**

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

BINARY CYCLIC CODES AND BCH CODES

39

Code m 9(x)

CRC-12 12 X12 + X11 + X3 -I- X2 + X + 1

CRC-16 16 X16 + X15 + X2 + 1

CRC-CCITT 16 x16 + X12 + X5 + 1

CRC-32 32 X32 + X26 + X23 + X22 + X16 + X12 + X11 +X10 + X8 + X7 + +X5 + X4 + X2 + X + 1

3.2 General decoding of cyclic codes

Let f(x) = v(x) + e(x), where e(x) is the error polynomial associated with an error vector produced after transmission over a BSC channel. Then the syndrome polynomial is defined as

s(x) = f(x) mod g(x) = e(x) mod g{x). (3.8)

Figure 18 shows the general architecture of a decoder for cyclic codes. The syndrome polynomial s(x) is used to determine the error polynomial e(x). Since a cyclic code is first of all a linear code, this architecture can be thought of as a “standard array approach” to the decoding of cyclic codes.

s(x) = r(x) mod g(x)

Figure 18 General architecture of a decoder for cyclic codes.

The decoding problem amounts to finding the (unknown) error polynomial e(x) from the (known) syndrome polynomial s(x). These two polynomials are related by equation (3.8), which is the basis of a syndrome decoder (also referred to as a Meggit decoder [Meg]) for cyclic codes. A related decoder is the error-trapping decoder [Kasm], which checks if the error polynomial e(x) is contained (“trapped”) in the syndrome polynomial s(x). Only a limited number of classes of codes have relatively simple decoders, e.g., cyclic Hamming and Golay codes. As the error correcting capability t = [{dmin — 1)/2J increases, however, the complexity of an architecture based only on (combinatorial) detection of errors becomes too large.

Suppose that an error in the position corresponding to x”“1 (the first received bit) occurs. In other words, e(x) = a;”-1. The corresponding syndrome polynomial is s(x) = x"~ Lmod<)(x). The code is cyclic, and thus if an error pattern affecting a given position is detected, any other error can be detected as well, by cyclically shifting the contents of the syndrome polynomial and the error polynomial. The syndrome decoder checks the syndrome for each received position and, if the pattern xn~1 modg(x) is detected, that position is corrected.

Example 25 In this example, the decoding of a cyclic (7,4,3) Hamming code is illustrated. For this code, g(x) = x3 + x + 1. The syndrome decoding circuit is shown in Figure 19. The

40

THE ART OF ERROR CORRECTING CODING

received bits are stored in a shift register and at the same time fed to a divide-by-<)(x) circuit. After all the seven bits have been received, the shift register contents are shifted one at a time, and a combinatorial gate checks if the syndrome polynomial x6mod(l + x + x3) = 1 + x2, or (101) in binary vector notation, is present in the shift register when the output of the gate is equal to one, the error is at the position X6 and is corrected. At the same time, the error is fed back to the divide-by-<?(x) circuit to bring the contents of the register equal to all zeros, upon successful completion of decoding. This also allows detection of any anomalies at the end of the decoding process, by checking that the contents of the shift register are not all equal to zero.

Figure 19 Syndrome decoder for a binary cyclic Hamming (7,4) code.

Attention is now focused on cyclic codes with large error correcting capabilities, for which the decoding problem can be treated as that of solving sets of equations. Because of this, the notion of a field, a set in which one can multiply, add and find inverses, is required. Cyclic codes have a rich algebraic structure. It will be shown later that powerful decoding algorithms can be implemented efficiently when the roots of the generator polynomial are invoked and arithmetic over a finite field used.

Recall that the generator polynomial is the product of binary irreducible polynomials:

3(z) = II

jˆdC{l,2,•••,<}

The algebraic structure of a cyclic codes enables one to find the factors (roots) of each 4>j (x) in a splitting field (also known as extension field). In the case of interest, that is, when the underlying symbols are bits, the splitting field becomes a Galois field3. Some authors refer to Galois fields as finite fields. The standard notation that will be used in the text is GF{q), where q = 2m. (Although, in general, q can be the power of any prime number.)

Example 26 In this example, the reader is reminded that the concept of splitting field is very familiar. Consider the field of real numbers. Over this field, it is well known that the

3 After the famous French mathematician Evariste Galois (1811-1832).

BINARY CYCLIC CODES AND BCH CODES

41

polynomial x2 + 1 is irreducible. However, over the complex field, it splits into (x + i)(x — i), where i = >/—1. Thus the complex field is the splitting field of the real field!

3.2.1 GF(2m) arithmetic

It can be shown, with basic abstract algebra [PW, LC] concepts, that, in the field of binary numbers, any polynomial of degree m can be split over GF(2m). For the purposes of this book, it is sufficient to learn basic computational aspects of finite fields. Serious readers are urged to study a good textbook on abstract algebra4.

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