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

ISBN 0471-49581-6

**Download**(direct link)

**:**

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

Figure 21 shows the block diagram of a decoder for BCH codes (both binary and non-binary). The decoder consists of digital circuits and processing elements to accomplish the following tasks:

• Compute the syndromes, by evaluating the received polynomial at the zeros of the code 6

Si^fia1), i = b,b+l,---,b + 2td-l. (3.17)

• Find the coefficients of the error locator polynomial a{x)

• Find the inverses of the roots ofcr(x), i.e., the locations of the errors, a31, • ? a3'1.

• Find the values of the errors eJ}, • • •, eju. (Not needed for binary codes.)

• Correct the received word with the error locations and values found.

FORNEY

POWER SUMS EA, BMA CHIEN SEARCH ALGORITHM

Figure 21 Architecture of a BCH decoder with GF(2m) arithmetic.

One of the advantages gained in introducing GF(2m) arithmetic is that the decoding operations can be implemented with relatively simple circuitry and processing elements. As an example, Figure 22 shows how the computation of a syndrome Sj can be implemented in hardware. The multiplier is over GF{2m), and can be constructed with relatively simple combinatorial logic. Some details on the hardware design of processing elements over GF(2r" ) can be found, for example, in [PW], and Chapters 5 and 10 of [WB],

ab+j"1

Figure 22 Example of a circuit for computing a syndrome.

6 For binary BCH codes, it holds that S2i = Sf, which is useful in reducing the number of computations.

BINARY CYCLIC CODES AND BCH CODES

49

3.5.2 The Berlekamp-Massey algorithm (BMA)

The BMA is best understood as an iterative procedure to construct a minimum linear feedback shift-register (LFSR) structure, like the one shown in Figure 23, that reproduces the known syndrome sequence Si, S2, - ? •, S2td ?

j = v+1, v+2,2v Figure 23 LFSR with taps o\, 02, ••• ov and output Si, S2, S21/.

The goal of the BMA is to find a (connection) polynomial o^+1^ (x) of minimal degree that satisfies the following equations, derived from (3.16):

V‘T*

y Sk-j(Tjt+1^ =0, ?i < k < i + 1. 3=0

(3.18)

This is equivalent to requiring that tr^l+1)(x) = 1 + <j^+1'>x + ? ? ? + xti+1 be the LFSR connection polynomial that produces the partial sequence of syndromes.

The discrepancy at iteration i defined as

di = Si+i + SiO^ + ? ? ? + Sj-^+icr^,

measures how well the LFSR reproduces the syndrome sequence, and constitutes a correction term used in computing the value of rr<l+11 in the next iteration. There are two cases to consider in the algorithm [Pet]7:

If di = 0, then the equations (3.18) are satisfied for

cr(*+1)(;z.) _ cr*(x), ?i+i = li.

If di 7^ 0: Let cr(m) (x) be the solution at iteration m, such that — 1 < rn < *, drn ^ 0, and (m — lm) is maximal. Then

(3.19)

Tv ’

^3/J — u J ~r

li+1 = max{?j,C + i - m}.

7 There is a variation of the BMA, inspired by [Mas2], that is used in some references. This variation will be described in the next chapter. Of course, both versions of the BMA will give the same result!

50

THE ART OF ERROR CORRECTING CODING

With an initial value of i = 0, the computation of rr(i+11 (x) continues until either

i > ?i+1 + td — 1 or i = 2td — 1, or both conditions, are satisfied.

The initial conditions of the algorithm are:

a^~4\x) = 1, ?-i = 0, d-1 = 1,

?7(0)(z) = 1, ?0 = 0, do = Si. (3.21)

Also note that the BMA has control flow instructions (if-else). For this reason, it is not favored in hardware implementations. However, in terms of number of GF(2m) operations, it is very efficient. This version of the algorithm is implemented in most of the C programs to simulate BCH codes that can be found on the ECC web site.

Example 34 Let C be the triple-error correcting BCH (15,5,7) code of Example 33. As a reference, to check the numerical computations, the power and vector representations of GF(24), with primitive polynomial p(x) — 1 + x + x4, are listed below:

Table of elements of GF(24), p(x) = x4 + x + 1.

Power Vector

0 0000

1 0001

a 0010

a2 0100

a3 1000

a4 0011

a5 0110

a6 1100

a7 1011

a8 0101

a9 1010

a10 0111

a11 1110

a12 1111

a13 1101

a14 1001

A generator polynomial for C is g(x) = x10 + x8 + x5 + x4 + x2 + x + 1. Suppose that the information polynomial is ?(x) = x + x1 + x4. Then the corresponding code polynomial is given by ?(a:) = x + x2 + x3 + x4 + x8 + a;11 + x12 + x14.

Let r(x) = 1 + x + x2 + x3 + x4 + x6 + x8 + x11 + x14 be the polynomial associated with a vector r — v + ? received after transmission of codeword v over a BSC channel. (Vector ? corresponds to the error polynomial ?(x) = 1 + x6 + x12. Obviously, the decoder does not know this. However, in computing the syndromes below, this knowledge is used to simplify expressions.)

The syndromes are:

51 = r(a) = 1 + a6 + a12 = a

52 = S2 = a2

BINARY CYCLIC CODES AND BCH CODES

51

53 = r(a3) = 1 + a3 + a6 = a'

54 = Sl = a4

55 ==1

56 =

= 1

Berlekamp-Massey algorithm:

• Iteration 0: Initialize. o(~1'l(x) = 1, l_4 = 0, cLi = 1, a(0)(x) = 1, 4 = 0, and do = Si = a.

• Iteration 1: i = 0, d0 = a 7^ 0, m = —1 maximizes (—1 + 0) = —1 for d-1 / 0.

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