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

ISBN 0471-49581-6

**Download**(direct link)

**:**

**32**> 33 34 35 36 37 38 .. 86 >> Next

Then the error value is computed as [Berl]

(?ah)l~bz{a*)

°Je

(4.7)

Ή

i = 1

aJ

e)

where 1 < I < v.

Yet another alternative to Forney algorithm, for small values of t,i, is to determine the error values directly as follows. For 1 < I < v, the error values ejt are related to the syndromes 5, by the set of linear equations:

5i = e(a6+<-1) = ^<

(4.8)

i=i

where 1 < i < 2td-

Each v x v submatrix formed by the (known) terms forms a Vandermonde

matrix. After all the v error locations jt are known, any set of v equations of the form (4.8) can be used to find the error values. In particular, choosing the first v syndromes:

fS i\

\sj

( (ajl)6

(Qii)6+i

(a^)b

(ai2)6+l

(aL)6+i

{a^y ^ ,ejl\

\ (a^1 )6+"-1 (ah)b+

V-l

[aF)b+v~1)

(4.9)

W j

is a system of linear equations that can be solved using GF(2m) arithmetic.

Example 42 Consider the same RS code and received polynomial in Examples 40 and 41. Then (4.9) gives:

a

1 1

The determinant of the 2x2 matrix is A = a4 + a2 = a. From this it follows that

NON-BINARY BCH CODES: REED-SOLOMON CODES

67

and

64 ex. Met

which are the same error values as those obtained with Forney algorithm. Again, it is emphasized that this can only be done efficiently (and practically) for relatively small values of the error correcting capability, td, of the RS code.

4.3.1 Remarks on decoding algorithms

Unlike the BMA, in the EA all the syndromes are used in the first computation step. However, in terms of the number of GF{2m) operations, the BMA is generally more efficient than the EA. On the other hand, all the steps in the EA are identical, which translates into a more efficient hardware implementation. Also, the three decoding methods discussed here for (binary and nonbinary) BCH codes are examples of incomplete or bounded distance decoding. That is, they are able to detect situations in which the number of errors exceeds the capability of the code.

There are other approaches to decoding BCH codes, the most notable being the use of a discrete Fourier transform over GF(2m). This is covered extensively in [Blah], where the reader is referred to for details. Recently, Sudan [Sud] has introduced an algorithm that allows correction of errors beyond the minimum distance of the code. It applies to RS codes and more generally to AG codes. This algorithm produces a list of codewords (it is a list-decoding algorithm) and is based on interpolation and factorization of polynomials over GF(2m) and its extensions. Sudan algorithm was improved in [Gur].

4.3.2 Errors-and-erasures decoding

For the correction of erasures, the main change to the RS decoding procedures described above is that an erasure locator polynomial t(x) needs to be introduced, defined as

where yit = ate, for 1 < ? < p, denotes the position of an erasure.

By definition, the positions of the erasures are known. Therefore, only the erasure values need to be found. This can be done, as before, in the Forney algorithm step. In computing the syndromes of the received polynomial, it can be shown that any values of the erasures can be replaced, without any difference in the decoded word.

The decoding procedure is similar to the errors-only RS decoder, with the following exceptions. A modified syndrome polynomial, or modified Forney syndrome, is formed,

t{x) = nt1 + ^x)>

T(x) = S(x)r(x) + 1 mod x2td+1.

The BMA algorithm can be applied to find o(x) with the following modifications: 1. The discrepancy is now defined as

u

di = ^i+M+t ^ Mj^S'i+zi+iit 3=1

'i+?+1 i >

(4.10)

(4.11)

68

THE ART OF ERROR CORRECTING CODING

with do Tp+i.

2. The algorithm finishes when the following stopping condition is met:

( ^ (j+1 + id 1

After cr(x) is obtained, a modified errors-and-erasure evaluator, or errata evaluator, is computed as ui{x),

u>(x) = [1 + T(a;)] a(x) mod x2td+l. (4.12)

In addition, the following errata locator polynomial is computed,

4>{x) = t(x)<t(x). (4.13)

The resulting errata evaluation, or modified Forney algorithm, is given by

_ (qi)2-buj(a-j)

n ~ <}>'{a-F) (4'l4)

1 < t < u, for the error values, and

h = (4.15)

4>'(yie )

1 < ? < p, for the erasure values.

For errors-and-erasures decoding, the Euclidean algorithm can also be applied to the modified syndrome polynomial T(x), using 1 + T(x) instead of S(x) as in errors-only decoding. That is, the inital conditions are ro(a;) = x2td+1 and ri(a;) = 1 + T(a:). The algorithm stops when deg[r^(x)] < [(d 1 + p)/2J, with lo(x) = rj(x) and a{x) = bj(x).

Example 43 Let C be anRS (15,9,7) code overG'F(24) with zeros {a,a2, ,a6}, where

a is a primitive element satisfying p(a) = a4 + a3 + 1 = 0. As a reference for this example, a table of elements of GF(24) as powers of a primitive element a, with a4 + a3 + 1 = 0, is shown below.

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

Power Vector

0 0000

1 0001

a 0010

a2 0100

a3 1000

a4 1001

a5 1011

a6 1111

a7 0111

a8 1110

a9 0101

a10 1010

a11 1101

a12 0011

a13 0110

**32**> 33 34 35 36 37 38 .. 86 >> Next