Books in black and white
 Books Biology Business Chemistry Computers Culture Economics Fiction Games Guide History Management Mathematical Medicine Mental Fitnes Physics Psychology Scince Sport Technics

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

Moreloz R.H. The art of error correcting coding - Wiley publishing , 2002. - 232 p.
ISBN 0471-49581-6 Previous << 1 .. 20 21 22 23 24 25 < 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. Previous << 1 .. 20 21 22 23 24 25 < 26 > 27 28 29 30 31 32 .. 86 >> Next 