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

ISBN 0471-49581-6

**Download**(direct link)

**:**

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

(xn - 1) = 4>i(x)<j>2(x) ? --(jtiix). (3.1)

Also, note that over the field of binary numbers, a — b and a + b (modulo 2) give the same result. In the remainder of the text, as all the codes are defined over the binary field, or its extensions, no distinction is made between these operations.

As a consequence of the above, the polynomial g(x) is given by

s(x) = II (3'2)

Example 20 With coefficients over Z-> = {0.1}, the polynomial x7 + 1 factors as x7 + 1 = (x + l)(a;3 + x + l)(a;3 + x2 + 1).

Some examples of cyclic codes of length 7 are:

• A binary cyclic Hamming (7.4,3) code is generated by the polynomial

g{x) = x3 + x + 1.

• A binary cyclic parity-check (7,6,2) code is generated by

g{x) = (i3+x + l)(x3 + x2 + 1).

• A binary maximum-length-sequence (7.3,4) code is generated by

g(x) = (x + l)(x3 + x + 1).

BINARY CYCLIC CODES AND BCH CODES

35

3.1.3 Encoding and decoding of binary cyclic codes The dimension of a binary cyclic (n, k) code is given by

k = n - deg [<j(a:)],

where deg [•] denotes the degree of the argument. Since a cyclic code C is also linear, any set of k linearly independent (LI) vectors can be selected as a generator matrix. In particular, the binary vectors associated with g{x), xg{x), ? ? -, xk~lg(x) are LI. These vectors can be used as rows of a generator matrix of C. In this case a non-systematic encoding rule is achieved. That is, the message bits do not appear explicitly in any positions of the codewords.

Example 21 Consider the cyclic Hamming (7,4,3) code, with generator polynomial g{x) = x3 + x + 1 <=> g = (1101). A generator matrix for this code is

G =

1 1 0 1 0 0 0'

0 110 10 0 0 0 110 10 ,0 0 0 1 1 0 1,

Alternatively, the parity sub-matrix of a generator matrix of a cyclic code can be constructed with the vectors associated with the following polynomials:

xn~1 mod g(x),

xn-k+i mo(j g[x), xn~k mod g(x),

and a systematic encoding is obtained, as illustrated in the example below.

Example 22 Let C be the cyclic Hamming (7,4,3) code. Then g(x) = x3 + x + 1, and

x& mod (a;3 + x + 1) = x2 + 1,

x5 mod (a:3 + x -I- 1) = a:2 + a; + 1,

x4 mod (a;3 + x + 1) = a:2 + x,

x3 mod (a;3 + x + 1) = x + 1.

It follows that a systematic generator matrix of C is

G =

/1000101^ 0 10 0 111 0 0 10 110 \0 0 0 1 0 1 1/

Let u(x) be associated with a message to be encoded. Encoding of codewords of a binary cyclic code can be either non-systematic or systematic, depending on the way that the message is processed:

• Non-systematic encoding

v(x) = u(x)g(x). (3.3)

• Systematic encoding

v(x) = xn~ku(x) + [a;n_fcit(a;) mod <?(a;)]. (3.4)

36

THE ART OF ERROR CORRECTING CODING

3.1.4 The parity-check polynomial

Another polynomial, h(x), called the parity-check polynomial, can be associated with the parity-check matrix. The generator polynomial and the parity-check polynomial are related by _

g(x)h(x) = xn + 1. (3.5)

The parity-check polynomial can be computed from the generator polynomial as h(x) = (xn + 1 )/g{x) = ho + hix + ? ? ? + hkxk. Then, a parity-check matrix for C is given by using as rows the binary vectors associated with the first n — k — 1 nonzero cyclic shifts

(3.6)

Example 23 The parity-check polynomial for the cyclic Hamming (7,4,3) code, with gener-

x^h(x) mod (xn — 1)J = 0,1," ?,n — k - 1.

/ ho /ii hk 0 0 • ? °\

0 ho hi hk 0 • • 0

H = 0 0 ho hi hk * • 0

0 0 0 0

V 0 0 0 0 0 • hk)

ator polynomial g(x) = x3 -I- x + 1, is h(x) A parity-check matrix for this code is

(x7 + l)/{x3 + X + 1) = x4 -I- X2 + X + 1.

1110 10 0 #=10111010 0 0 1110^

In the same manner as with linear codes, systematic encoding can be also performed by a recursion with h(x) using

v(x)h{x) = 0 mod (xn + 1).

Systematic encoding can be performed as follows [PW, LC]. Suppose first that the code rate k/n < 0.5. Let ?(x) = u0 + uix + ? ? ? + ut-i denote a polynomial of degree k — 1, whose coefficients ue, ? = 0,1, • • •, k — 1, are the message bits to be encoded. Let v(x) denote the code polynomial polynomial in C corresponding to the information polynomial ?(x). In the first step, Vi = ue, for I = 0,1, • • •, k — 1.

From the cyclic structure of the code, it follows that the redundant bits V{, ? = k, k + 1, • • •, n — 1, are obtained recursively via the parity-check relations

ve —

1=0

(3.7)

where h,

denotes the j-th entry in the (? — fc)-th row of matrix (3.6).

In the case of high-rate cyclic (n, k) codes, say k/n > 0.5, encoding by division of xn~~ku(x) by g(x) is more efficient. Either way, by recursion with h(x) or by division by g{x), the coefficients of the code polynomials are in systematic form, so that the first k coefficients are the message bits, and the remaining n — k coefficients constitute the redundant bits.

Figure 17 shows the block diagram of an encoder for a binary cyclic code with generator polynomial g(x). Initially, the switch (lower right portion of the figure) is in position 1, and the message bits are both transmitted through the channel and simultaneously fed to a sequential

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