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

ISBN 0471-49581-6

**Download**(direct link)

**:**

**24**> 25 26 27 28 29 30 .. 86 >> Next

Ci = {i. 2i. 4i. . 2K_1i}.

Cyclotomic cosets (also called cycle sets in [PW], p. 209) have the property that they partition the set l2m - i of integers modulo 2m 1. That is, cyclotomic cosets are disjoint, that is, their intersection is the empty set Ct n Cj = 0, i ^ j, and and the union of all cyclotomic cosets

U

Example 29 The cyclotomic sets modulo 7 are:

Co = {0}

Gx = {1,2,4}

C3 = {3,6,5}

The primitive element a of GF(2m) satisfies the equation a2*-1 = 1, and all elements can be expressed as powers of a. From this it follows that the polynomial (a?2'-1 + 1) factors over the binary field as

M

(x2-1 + 1) = JJ<^(a:),

1=0

and splits completely over GF(2m) as

2m-2

(a;2"*-1 + 1) = JJ(x + a4). (3.9)

l=o

The order m of an element f3 = a1 of GF(2m) is the smallest positive integer such that

i3ru = 1. The order ri j of every element in GF(2rn) divides 2m 1.

Importantly, the degree of a minimal polynomial <f>i(x) is equal to the cardinality (number of elements) of the cyclotomic coset Cj,

deg [4>i(x)] = |Cj|.

This suggests the following method of finding all factors of (a;2-1 + 1):

1. Generate the cyclotomic cosets modulo 2m 1.

2. For each cyclotomic coset Cs, compute the minimal polynomial (ps(x) as the product of linear factors (x a1), where is E Cs,

4>s(x) = JJ(ar + cCs). (3.10)

i,eca

This method can be used in computing the generator polynomial of any cyclic code of length n = 2m 1. It is used in the computer simulation programs for BCH codes available on the ECC web site, to compute the generator polynomial given the zeros of the code.

44

THE ART OF ERROR CORRECTING CODING

Example 30 Consider GF(23) with p{x) = x3 + x + 1. The roots of each of the factors of the polynomial x7 + 1 are shown in the following table. The reader is invited to verify that in fact the products of the linear factors in (3.10) give the resulting binary polynomials.

Cs Conjugate elements Minimal polynomial, <f>s{x)

Co = {0} 1 4>o{x) = X + 1

Ci = {1,2,4} 9 4 a,a 9a (j>l(x) = X3 + X + 1

C3 = {3,6,5} a3,a6,a5 <f)3{x) = 2;3 + X2 + 1

3.3 Binary BCH codes

BCH codes are cyclic codes that are constructed by specifying their zeros, i.e., the roots of their generator polynomials:

A BCH code of drnjn > 2t,,i + 1 is a cyclic code whose generator polynomialg(x) has 2tj consecutive roots ab, ab, ab+1, o.b+2>d"1.

Therefore, a binary BCH (n, k, dmin) code has a generator polynomial

g(x) = LCM{(f)b{x).,4>b+i{x), - ? ? ,4>b+2td~i{x)}.

length n LCM{nb,nb+1, ? ? ?, nb+2td-i}, and dimension k = n deg [<7(2;)]. A binary

BCH code has a designed minimum distance equal to 2t,i + 1. However, it should be noted

that its true minimum distance may be larger.

Example 31 With GF{23), p(x) = x3 + x + 1, td = 1 and 6=1, the polynomial

g{x) LCM{(j>i(x).(f>2(x)} = x3 + x + 1.

generates a binary BCH (7,4,3) code. (This is actually a binary cyclic Hamming code!) Note that the Hamming weight of g(x) is equal to 3, so that in this case, but not always the designed distance is equal to the true minimum distance of the code.

Example 32 Consider GF(24), p(x) = xA + x + 1, with tj = 2 and 6=1. Then

g(x) = LCM{(f>i{x),(j)Z{x)}

= (x4 + X + l)(x4 + x3 + x2 + X + 1)

= a;8 + X7 + x6 + x4 + 1

generates a double-error-correcting binary BCH (15,7,5) code.

Example 33 With GF( 24), p(x) = x4 + x + \,td % and 6 = 1, the polynomial

g(x) - LCM{4>i{x),4>3(x)4>5(x)}

(x4 + x + l)(a;4 + x3 + x2 + x + 1)

(x2 + x + 1)

= 2;10 + x8 + x5 + X4 + X2 + X + 1

generates a triple-error-correcting binary BCH (15,5,7) code.

BINARY CYCLIC CODES AND BCH CODES

45

The lower bound on the minimum distance of a BCH code, known as the BCH bound, is derived next. This is useful not only to estimate the error correcting capabilities of cyclic codes in general, but also serves to point out particular features of BCH codes. Note that the elements ab. ab+1.

, ab+2td-i are roots of the generator polynomial g(x), and that every codeword v in the BCH code is associated with a polynomial v(x) which is a multiple of g{x). It follows that

V{x) Ş C Ž(ŕ4) = 0, b<i<b + 2td. (3.11)

Codeword v then satisfies the following set of 2td equations, expressed in matrix form, based on (3.11):

( 1 1 1 \

ab Qb+1 ? . ab+2td-l

(ať)2 (a6+1)2 ? (ab+2td~1)2

V (a6)-1 (a6+1)-1 ? (ab+2td~1)n~ 4

( Ť0 Vi V2

v_i) =0. (3.12)

Consequently, a parity-check matrix of a binary cyclic BCH code is given by

/i ,b ... (ab)n-1

1 a6+1 (a6+1)2 (

H = .

Vl Q^-1 (ab+2t-1)2

\

(ab+2td-1)n-1 /

(3.13)

This matrix H has the characteristic that every 2td x 2td submatrix (formed by an arbitrary set of 2td columns of H) is a Vandermonde matrix (see, e.g, [GG], p. 95). Therefore (see Section 2.1), any 2td columns of H are linearly independent, from which it follows that the minimum distance of the code is d > 2td + 1. ([PW] p. 270, [MS] p. 201, and [LC] p. 149.) Another interpretation of the results above is the following:

(BCH bound.) If the generator polynomial g{x) of a cyclic (n, k, d) code has I consecutive roots, say ab,ab+1. ? ?. ab+e~1, then d > 21 + 1.

**24**> 25 26 27 28 29 30 .. 86 >> Next