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 .. 19 20 21 22 23 24 < 25 > 26 27 28 29 30 31 .. 86 >> Next 3.4 Polynomial codes
The important class of cyclic polynomial codes includes cyclic RM codes, BCH and Reed-Solomon codes, and finite-geometry codes [KLP, PW, LC]. Polynomial codes are also specified by setting conditions on their zeros:
Let a be a primitive element of GF{2ms). Let s be a positive integer, and b a divisor of 2s Ś 1. Then ah is a root of the generator polynomial g(x) of a p-th order polynomial code if and only ifb divides h and
min W2æ{h2l) Ś jb. with 0 < j < [^1 - p,
o<t<s ' L b J
where for an integer i, i = H-'V (i) is defined as the 2 s-ary weight of integer i,
mŚ1
W2*{i) = H-
i=0
46
THE ART OF ERROR CORRECTING CODING
According to this definition, both BCH and Reed-Solomon codes are polynomial codes with b = m = 1. Reed-Muller codes are subcodes of polynomial codes with s = 1. Finite-geometry codes ([LC], Chapter 8) occur as dual codes of polynomial codes [PW]. Below, following [LC], the specifications of the zeros of finite-geometry codes are presented.
Euclidean geometry (EG) codes
Let a be a primitive element ofGF(2ms ). Let hbe a nonnegative integer less that 2ms Ś 1. Thenah is a root of the generator polynomial g(x) of a (p. s)-order EG code of length 2ms Ś 1 if and only if
0< max W2s(h{e)) < (m - u - 1)(2S - 1).
0<t<s ō 7
where = 2eh modulo 2ms Ś 1.
For s = 1, EG codes become cyclic RM^ codes, and therefore EG codes are regarded as generalized RM codes.
Projective geometry (PG) codes
Let a be a primitive element of GF(2(m+1)s). Let h be a nonnegative integer less that 2(m+i)s _ p phen ah is a root of the generator polynomial g(x') of a {p. s)-order PG code of length n = (2 ms Ś 1)/(2S Ś 1) if and only ifh is divisible by 2s Ś 1 and
0< max W2s(/iw) < j(2s-l).
0<?<s ~
where = 2lh modulo 2ms Ś 1, and 0 < j < m Ś u.
3.5 Decoding of binary BCH codes
The main idea in decoding binary BCH codes is to use the elements /3 ł GF(2m) to number the positions of a codeword (or, equivalently, the order of the coefficients of the associated polynomial). This numbering illustrated in Figure 20 for a vector f = (r0 ri Ģ Ģ Ģ rn_i) with corresponding f{x).
values rä r, r ,
0 1 n-1
positions la a"'1
Figure 20 Codeword position numbering using elements of GF(2m).
Using GF(2TO) arithmetic, the positions of the errors can be found, by solving a set of equations. These equations can be obtained from the error polynomial e(x) and the zeros of the code, af for b < j < b + 2t,,i Ś 1, as shown in the following.
Let f(x) Ś v(x) + e(x) represent the polynomial associated with a received codeword, where the error polynomial is defined as
e(a;) = ejlxjl + ej2xh H b e^x^, (3.14)
BINARY CYCLIC CODES AND BCH CODES
47
and v < td is the number of errors. The sets {e^,, ej2, ? ? ?, e,jv}, and \aJ1, a?1, Ģ Ģ Ģ, a?1} are known as the error values and error positions, respectively, where ej ? {0,1} for binary BCH codes5 and a ? GF(2m).
The syndromes are the evaluation of r(x) at each of the zeros of the code:
-h Cjti OL
bjä
S\ = r(ab) = eJ-1akj'1 +
S2 = r(af>+1) = + Ģ Ģ ? + ejva^b+1^Æ'
S2td = r(ab+2id 1) = ej1a^b+2td 1)J'1 + ? ? ? + ejva
and are equivalent to s = HrT, with H given by (3.13).
Let the error locator polynomial be defined as
(b+2td-l)jv
a(x) = JJ(1 + ajex) = 1 + (j\X + a2x2 + ? ? ? + avxv,
(3.15)
e=i
with roots equal to the inverses of the error locations. Then the following relation between the coefficients of <t(x) and the syndromes holds (see, e.g., [Pet], [LC] p. 154, [PW] p. 284):
/Sä+i\ /Si
Sä+2
V s2v /
s2
\sä Su+i
sv \
S,
+1
\
Gv Ś l
(3.16)
S2V-I / \ <Ti /
Solving the key equation given by (3.16) constitutes the most computationally intensive operation in decoding BCH codes. Common methods to solve the key equation are:
1. Berlekamp-Massey algorithm (BMA)
The BMA was invented by Berlekamp [Berl] and Massey [Mas2], This is a computationally efficient method to solve the key equation, in terms of the number of operations in GF(2m). The BMA is a popular choice to simulate or implement BCH and RS decoders in software.
2. Euclidean algorithm (EA)
This method to solve the key equation, in polynomial form, was introduced in [SKHN] and further studied in [Man]. Due to its regular structure, the EA is widely used in hardware implementations of BCH and RS decoders.
3. Direct solution
Proposed first by Peterson [Pet], this method directly finds the coefficients of cr(a;), by solving (3.16) as a set of linear equations. The term PGZ (Peterson-Gorenstein-Zierler) decoder is often used in the literature. This is because in [GZ] PetersonÆs method is applied in decoding nonbinary BCH codes, or RS codes. Naturally, as the complexity of inverting a matrix grows with the cube of the error-correcting capability, the direct solution method works only for small values of td- Solutions to
(3.16) up to td < 6 are given in [ML], sec. 5.3.
5 It will be seen later that for Reed-Solomon codes ej ? GF(2m).
48 THE ART OF ERROR CORRECTING CODING
3.5.1 General decoding algorithm for BCH codes Previous << 1 .. 19 20 21 22 23 24 < 25 > 26 27 28 29 30 31 .. 86 >> Next 