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

ISBN 0471-49581-6

**Download**(direct link)

**:**

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

3.4 Polynomial codes

The important class of cyclic polynomial codes includes cyclic RM codes, BCH and Reed-Solomon codes, and finite-geometry codes [KLP, PW, LC]. Polynomial codes are also specified by setting conditions on their zeros:

Let a be a primitive element of GF{2ms). Let s be a positive integer, and b a divisor of 2s 1. Then ah is a root of the generator polynomial g(x) of a p-th order polynomial code if and only ifb divides h and

min W2{h2l) jb. with 0 < j < [^1 - p,

o<t<s ' L b J

where for an integer i, i = H-'V (i) is defined as the 2 s-ary weight of integer i,

m1

W2*{i) = H-

i=0

46

THE ART OF ERROR CORRECTING CODING

According to this definition, both BCH and Reed-Solomon codes are polynomial codes with b = m = 1. Reed-Muller codes are subcodes of polynomial codes with s = 1. Finite-geometry codes ([LC], Chapter 8) occur as dual codes of polynomial codes [PW]. Below, following [LC], the specifications of the zeros of finite-geometry codes are presented.

Euclidean geometry (EG) codes

Let a be a primitive element ofGF(2ms ). Let hbe a nonnegative integer less that 2ms 1. Thenah is a root of the generator polynomial g(x) of a (p. s)-order EG code of length 2ms 1 if and only if

0< max W2s(h{e)) < (m - u - 1)(2S - 1).

0<t<s 7

where = 2eh modulo 2ms 1.

For s = 1, EG codes become cyclic RM^ codes, and therefore EG codes are regarded as generalized RM codes.

Projective geometry (PG) codes

Let a be a primitive element of GF(2(m+1)s). Let h be a nonnegative integer less that 2(m+i)s _ p phen ah is a root of the generator polynomial g(x') of a {p. s)-order PG code of length n = (2 ms 1)/(2S 1) if and only ifh is divisible by 2s 1 and

0< max W2s(/iw) < j(2s-l).

0<?<s ~

where = 2lh modulo 2ms 1, and 0 < j < m u.

3.5 Decoding of binary BCH codes

The main idea in decoding binary BCH codes is to use the elements /3 GF(2m) to number the positions of a codeword (or, equivalently, the order of the coefficients of the associated polynomial). This numbering illustrated in Figure 20 for a vector f = (r0 ri rn_i) with corresponding f{x).

values r r, r ,

0 1 n-1

positions la a"'1

Figure 20 Codeword position numbering using elements of GF(2m).

Using GF(2TO) arithmetic, the positions of the errors can be found, by solving a set of equations. These equations can be obtained from the error polynomial e(x) and the zeros of the code, af for b < j < b + 2t,,i 1, as shown in the following.

Let f(x) v(x) + e(x) represent the polynomial associated with a received codeword, where the error polynomial is defined as

e(a;) = ejlxjl + ej2xh H b e^x^, (3.14)

BINARY CYCLIC CODES AND BCH CODES

47

and v < td is the number of errors. The sets {e^,, ej2, ? ? ?, e,jv}, and \aJ1, a?1, , a?1} are known as the error values and error positions, respectively, where ej ? {0,1} for binary BCH codes5 and a ? GF(2m).

The syndromes are the evaluation of r(x) at each of the zeros of the code:

-h Cjti OL

bj

S\ = r(ab) = eJ-1akj'1 +

S2 = r(af>+1) = + ? + ejva^b+1^'

S2td = r(ab+2id 1) = ej1a^b+2td 1)J'1 + ? ? ? + ejva

and are equivalent to s = HrT, with H given by (3.13).

Let the error locator polynomial be defined as

(b+2td-l)jv

a(x) = JJ(1 + ajex) = 1 + (j\X + a2x2 + ? ? ? + avxv,

(3.15)

e=i

with roots equal to the inverses of the error locations. Then the following relation between the coefficients of <t(x) and the syndromes holds (see, e.g., [Pet], [LC] p. 154, [PW] p. 284):

/S+i\ /Si

S+2

V s2v /

s2

\s Su+i

sv \

S,

+1

\

Gv l

(3.16)

S2V-I / \ <Ti /

Solving the key equation given by (3.16) constitutes the most computationally intensive operation in decoding BCH codes. Common methods to solve the key equation are:

1. Berlekamp-Massey algorithm (BMA)

The BMA was invented by Berlekamp [Berl] and Massey [Mas2], This is a computationally efficient method to solve the key equation, in terms of the number of operations in GF(2m). The BMA is a popular choice to simulate or implement BCH and RS decoders in software.

2. Euclidean algorithm (EA)

This method to solve the key equation, in polynomial form, was introduced in [SKHN] and further studied in [Man]. Due to its regular structure, the EA is widely used in hardware implementations of BCH and RS decoders.

3. Direct solution

Proposed first by Peterson [Pet], this method directly finds the coefficients of cr(a;), by solving (3.16) as a set of linear equations. The term PGZ (Peterson-Gorenstein-Zierler) decoder is often used in the literature. This is because in [GZ] Petersons method is applied in decoding nonbinary BCH codes, or RS codes. Naturally, as the complexity of inverting a matrix grows with the cube of the error-correcting capability, the direct solution method works only for small values of td- Solutions to

(3.16) up to td < 6 are given in [ML], sec. 5.3.

5 It will be seen later that for Reed-Solomon codes ej ? GF(2m).

48 THE ART OF ERROR CORRECTING CODING

3.5.1 General decoding algorithm for BCH codes

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