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

ISBN 0471-49581-6

**Download**(direct link)

**:**

**27**> 28 29 30 31 32 33 .. 86 >> Next

• Iteration 3: i = 2, d2 = a13 7^ 0, m = 0 maximizes (0 — 0) = 0 for do / 0.

0-^(2;) = a^2\x) + d2dg4 x^2~0^ (x) = (1 + ax) + a13(a-1)a;2(l) = 1 + ax + a12x2,

4 = max{4; 4 + 2 — 0} = 2,

?3 + 3 - 1 < 2 ? No :

d3 = S4 + S3(t[3^ + S2a ^ = a4 + a8{a) + a2{a12) = 0.

• Iteration 5: i = 4, d4 = 1 7^ 0, m = 2 maximizes (2 — 1) = 1 for d2 7^ 0.

<t(5)(x) = cr^4^(a;) + d^d^1 x^4~2^ a(2\x)

= (1 + ax + a12a:2) + (l)(a13)_1x2(l + ax)

= 1 + ax + ol1x2 + a3x3,

?3 = max{4, l2 + 4 — 2} = 3,

?5 + 3 - 1 < 4 ? No :

d5 = Se + Ssoj5^ + S4a^ + S3CT3^ = a + 1 ? a + a4(a7) + a8(a3) — 0. • Iteration 6: i = 5, d5 = 0,

a^\x) = (x) + dod_\x^° ^ l\x) = l + ax.

?\ = max{4, f-i + 0 — (—1)} = 1.

?1 + 3-1 <0 ?No: ’

di = S2 + 5i<t^ = a2 + a{a) = 0.

• Iteration 2: i — 1 ,di= 0,

cr(2) (2;) = <7^ (2;) = 1 + Q2:.

?2 — ?1,

?2 + 3 - 1 < 1 ? No :

d2 = S3 + s2<7i1) = a8 + a2 (a) = a13

• Iteration 4:i = 3,d3 = 0,

<7(2:) = (j^3^ (x) = 1 + ax + a12x2,

4 — ?3-,

4 + 3 - 1 < 3 ? No :

d4 = S3 + S4aJ4^ + S3<j^ = 1 + a4{a) + a8a12 = 1.

<y(6\x) = a^(x) = 1 + 02 + a7x2 + a3x3: 4=4=3, '

4 + 3 - 1 < 3 ? Yes : End.

52

THE ART OF ERROR CORRECTING CODING

Therefore cr(x) = 1 + ax + a7x2 + a3x3.

That the odd numbered iterations always gave di = 0 in the previous example is no accident. For binary BCH codes this is always the case. The iterations can proceed with only even values of i, with the same results. The only difference is that the stopping criterion needs to be changed to

As a result, decoding complexity is reduced. The reader is invited to solve <j{x) for the previous example, using only three iterations.

3.5.3 PGZ decoder

This decoding algorithm was first considered by [Pet]. A solution to the key equation (3.16) is to be found using standard techniques for solving a set of linear equations. This solution gives the coefficients of a{x). The decoding problem is that the number of actual errors is unknown. Therefore, a guess has to be made as to the actual number of errors, v, in the received word. Assume that not all the syndromes, S,, 1 < i < 2t, are equal to zero. (If all syndromes are zero, then the received word is a codeword and decoding finishes!)

The decoder assumes that the maximum number of errors has occurred, t/max = t,,i, and checks if the determinant Aj, for % = ;/max =

is equal to zero. If it is, then a smaller number of errors must have occurred. The value of i is decreased by one, and A* tested again, repeating the procedure if necessary, until i = 1. Otherwise, if A* i1 0, the inverse of the syndrome matrix is computed and the values of <7i, er2, • • •, <7„ are found, where v = i. In the event that A* = 0. i = 1,2, • ? •. , decoding is

unsuccessful and an uncorrectable error pattern has been detected.

Example 35 In this example, the error locator polynomial for the BCH (15.5,7) code in Example 34 is found by the PGZ decoding algorithm. First, assume that i = ta = 3 errors occurred. Then the determinant A3 is computed (using cofactors) as follows:

® ^ (-i+2 + td — 2.

A* = det

/Si S2 Si \

s2 s3 ••• Si+i

(3.22)

VSi si+1 s2i-xJ

Therefore A3 ^ 0 and three errors are assumed to have occurred. Substituting the syndromes found in Example 34 into the key equation (3.16),

a4 a2 a8

1 a8 a4

a a4 1

a a4 a8

a2 1 a4

00 e a 1

a a2 a4

a2 a8 1

a8 a4 a

BINARY CYCLIC CODES AND BCH CODES 53

Note that A.^1 = q-14 = a. The solution to (3.23) is found to be:

/ a4 a2 a8 \

— a(a7 + a12) = a3,

= a(a11 + a) = a7, o\ — a det I a2 a8 1 I = a(a15 + a15 + a15) = a.

It follows that o(x) = 1 + ax + a7x2 + a3x3, which is the same result as that obtained by the BMA in example 34.

3.5.4 Euclidean Algorithm (EA)

This algorithm is a well-known recursive procedure to find the greatest common divisor

(GCD) between two polynomials (or integers). Its application to BCH decoding is described

next.

Let an error evaluator polynomial be defined as A(x) = (t(x)S(x). with a syndrome polynomial

S(x) = 1 + Six + ? ? ? + S2tdx2td. (3.24)

From Equation (3.16), it follows that

A (a;) = o(x)S(x) mod x2td+1. (3.25)

The decoding problem can be translated into finding the polynomial A(ar) satisfying (3.25). This can be achieved by applying the extended EA to the polynomials ro(x) = x2td+1 and r\ {x) = S(x), such that if at the j-th step

rj(x) = aj(x)x2td+1 + bj(x)S{x),

with deg [rj (a:)] < td, then A (a;) = rj(x) and Oi(x) = bj(x). (Note that there is no interest, from the decoding viewpoint, in polynomial ai{x).)

The extended Euclidean algorithm for computing the GCD of two polynomials is:

Euclidean algorithm: Compute GCD(r0(a:),r1 (a;))

• Inputs: r0(a;),ri(a;).deg [r0(a;)] > deg [^(x)]

Initial conditions: oo(x) = 1, bo(x) = 0, ai(x) = 0, bi(x) = 1. At step j (j > 2), apply long division to rj-^(x) and rj-1 (x),

rj-2(x) = qj(x)rj-i (x) + rj(x), 0 < deg [ry(x)] < deg [rj-1 (x)] • and compute

aj(x) = a,j-2(x) - qj(x)aj-i(x), bj{x) = bj-2(x) - qj{x)bj-i{x).

54 THE ART OF ERROR CORRECTING CODING

• Stop at iteration j[aat when deg [rjlaat (x)] = 0.

**27**> 28 29 30 31 32 33 .. 86 >> Next