in black and white
Main menu
Home About us Share a book
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
Download (direct link): artoferrorcorrecting2002.pdf
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,
W2*{i) = H-
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)
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
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
a(x) = JJ(1 + ajex) = 1 + (j\X + a2x2 + ? ? ? + avxv,
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
V s2v /
\s„ Su+i
sv \
Gv — l
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).
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