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 .. 26 27 28 29 30 31 < 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+i—it 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 Previous << 1 .. 26 27 28 29 30 31 < 32 > 33 34 35 36 37 38 .. 86 >> Next 