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

ISBN 0471-49581-6

**Download**(direct link)

**:**

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

Then GCD(ra (x), n (x)) = r* (x), with k the largest nonzero integer such that r* (x) ^ 0 and k < jiast.

Example 36 In this example, the error locator polynomial a(x) for the BCH (15,5,7) code in Example 34 is computed using the EA.

• Initial conditions

r0(x) = x7,

ri(x) = S(x) = 1 + ax + a2x2 + a8x3 + a4x4 + x5 + ax6. bo(x) = 0,

bi{x) - 1.

• j = 2:

x7 = (l+ax+a2x2+a8x3+a4x4+x5+ax6)(a14x+a13)+a8x5+a12x4+anx3+a13.

r2(x) = a8 x5 + a12x4 + anx3 + a13.

52 (x) = a14x + a13, and

b2{x) = 60(x) + 52(x)&i(x) = a14x + a13.

• j = 3:

S(x) = (a8x5 +a12x4 + a41x3 +q13)(q8x + Q!2) +q14x4 + a3x3 +a2x2 +axlx.

r3(x) = a14x4 + a3x3 + a2x2 + a11x,

q3(x) = a8x + a2, and

63 (x) = bi(x) + q3{x)b2{x) = a7x2 + a41x.

• j = 4:

a8x5 + q12x4 +anx3 +a13 = (a14x4 + Q!3x3 + Q:2x2 + a11x)(a9x) + a5x + a13.

r4(x) = a5x + a13,

54 (x) = a9x, and

64 (x) = b2(x) + q4,(x)b3(x) = ax3 + a5x2 + a14x + a13.

Because deg[r4(x)] = 1 < 3, the algorithm stops.

It follows that cr(x) = 64(x) = a13(l + ax + a7x2 + a3x3), which has the same roots as the polynomial obtained by the BMA and PGZ decoder (see example 37 below), and differs only by a constant factor8.

As the example above illustrates, generally the error-locator polynomial obtained with the EA will differ from that obtained by BMA or PGZ decoding by a constant factor. In decoding, however, interest is in the roots of these polynomials and not their coefficients, and thus any of the three methods discussed so far can be used to determine cr(x).

8 The normalized polynomial anorm(x) = aQ 1 rj{x) is identical to the one obtained in the BMA and PGZ

procedures.

BINARY CYCLIC CODES AND BCH CODES

55

3.5.5 Chien search and error correction

To find the roots of a{x), a simple trial-and-error procedure — called Chien search — is performed. All nonzero elements /3 of GF(2rn) are generated in sequence 1, a, a2, ... and the condition o(/3~1) = 0 tested. This process is easy to implement in hardware. Moreover, finding roots (factoring) of polynomials over GF(2m) is a challenging mathematical problem that remains to be solved.

For binary BCH codes, once the error locations j\,..., jv are known, the corresponding bits in the received word are complemented

Vjt = vn + 1> 1 < ^ y

and the estimated codeword v(x) generated.

Example 37 Continuing with Example 34, the roots of a{x) are 1, a9 = or6 and a3 = a~12. Stated in a different way, a(x) factors as

a(x) = (1 + x)(l + q6x)( 1 + a12x).

Consequently, the estimated error polynomial is e(x) = 1 + x6 + x12, and

f{x) = x + x2 + x3 + x4 + x6 + x8 + x11 + X14.

Three errors have been corrected.

3.5.6 Errors-and-erasures decoding

There are many situations in which a decision on a received symbol is not considered reliable. An example is binary transmission over an AWGN channel, with bits mapped to real amplitudes, e.g., BPSK with 0h>+1 and 1 i-> — 1. If the received values are too close to zero, then it may be more advantageous, from the viewpoint of minimizing the probability of a decoding error, to declare a “no-decision”. In such a case, the received symbol is “erased” and it is called an erasure9. Declaring erasures is the simplest form of soft-decision, which will be the focus of attention in Chapter 7.

Introduction of erasures has the advantage, with respect to errors-only decoding, that the positions are known to the decoder. Let d be the minimum distance of a code, u be the number of errors and p be the number of erasures contained in a received word. Then, the minimum Hamming distance between codewords is reduced to at least d - p in the non-erased positions. It follows that the error-correcting capability is \_(d — p — 1)/2J and the following relation holds

d > 2v + p. (3.26)

The above inequality is intuitively satisfying: For a fixed minimum distance, it is twice as difficult to correct an error than to correct an erasure, because the erased positions are already known.

For binary linear codes, including binary BCH codes, erasures can be corrected with the following method:

9 In information theoretical terms, the BSC channel becomes a two-input three-output binary erasure

channel (BEC) [CoT].

56

THE ART OF ERROR CORRECTING CODING

1. Place zeros in all erased positions and decode to a codeword vo(x).

2. Place ones in all erased positions and decode to a codeword vi (x).

3. Chose as decoded word the closest vj (x) to the received word f(x) in the non-erased positions, j = 0,1. (Alternatively, the codeword that required the smallest number of error corrections [ML].)

As a result, erasures can be corrected with two rounds of errors-only decoding.

Example 38 Consider a cyclic Hamming (7,4,3) code with g(x) = 1 + x + x3, and GF(23) with a primitive element a such that p(a) = 1 + a + a3 =0. Suppose that v(x) = x + x2 + x4 is transmitted and that // = 2 erasures are introduced at the receiver. Since d = 3 > g, these erasures can be corrected. Let r(x) = f + x + x2 + fx3 + x4 be polynomial associated with the received vector, where / denotes an erasure.

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