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

ISBN 0471-49581-6

**Download**(direct link)

**:**

**23**> 24 25 26 27 28 29 .. 86 >> Next

Decoding with GF(2m) arithmetic allows replacement of complex combinatorial circuits with practical processor architectures that can solve Equation (3.8) as a set of linear equations. In the following, the necessary tools to solve equations involved in decoding of cyclic codes are introduced.

Important properties of GF(2m)

The field GF{2m) is isomorphic (with respect to “+”) to the linear space {0, l}m. In other words, for every element (3 ? GF(2m), there exists a unique m-dimensional binary vector vs G {0,l}m.

There is a primitive element a ? GF(2m), such that every nonzero element j3 in GF(2rn) can be expressed as (3 = a*, 0 < j < 2m — 2. This element a is the root of an irreducible polynomial, called a primitive polynomial, p(x) over {0,1}, i.e., p(a) = 0. A primitive element a of the field GF(2m) satisfies the equation a2™-1 = 1, and n = 2m - 1 is the smallest positive integer such that an = 1.

Example 27 Let p(a-) = x3 + x + 1, a primitive polynomial of GF(23). Let a be a primitive element such thatp(o) = a3 + a + l = 0 and a7 = 1. The table below shows three different ways to express, or representations of, elements in GF(23).

Power Polynomial Vector

— 0 000

1 1 001

a a 010

a2 a2 100

a3 1 + a 011

a4 a + a2 110

a5 1 + a + a2 111

a6 1 + a2 101

When adding elements in GF(2m), the vector representation is the most useful, because a simple exclusive-or operation is needed. However, when elements are to be multiplied, the power representation is the most efficient. Using the power representation, a multiplication becomes simply an addition modulo 2m — 1. The polynomial representation may be appropriate when making operations modulo a polynomial. An example of the need of this polynomial representation was seen in the discussion of shortened cyclic codes, where the value of a;"-1 mod g(x) was required.

4 The author likes [Her],

42

THE ART OF ERROR CORRECTING CODING

In the power representation, because o?m~x = 1 holds, note that a2” = aa2”-1 = a, a2 +1 = a2a2 -1 = a2, and so on. This is to say that the powers of a are to be computed modulo 2m — 1. Applying the same argument shows that a-1 = a-1-1"2"*-1 = a2"*“2. For Example 27 above, a~1 = a2 ~2 = a6. In general, the inverse /3“1 = ak of an element (3 = ae is found by determining the integer k, 0 < k < 2m — 1 such that ae+k = 1, which can be expressed as I + k = 0 mod (2m — 1). Therefore, ? = 2m — 1 — k. Also, in the polynomial representation, the equation p(a) = 0 is used in order to reduce the expressions. In Example 27, a3 = a3 + 0 = a3 + (a3 + a + 1) = a + 1.

Log and anti-log tables

A convenient way to perform both multiplications and additions in GF(2m) is to use two look-up tables, with different interpretations of the address. This allows one to change between polynomial (vector) representation and power representations of an element of GF(2m).

The anti-log table A(i) is useful when performing additions. The table gives the value of a binary vector, represented as an integer in natural representation, A{i), that corresponds to the element a1. The log table L(i) is used when performing multiplications. This table gives the value of a power of alpha, aL^ that corresponds to the binary vector represented by the integer i. The following equality holds:

aL(i) = A(i).

The best way to understand how to use the tables in the computation of arithmetic operations in GF(2m) is through an example.

Example 28 Consider GF(23) with p(a) = a3 + a + 1, and a1 = 1. The log and anti-log tables are the following:

Address i GF(2m)-to-vector Anti-log table, A(i) Vector-to-GF(2m) Log table, L(i)

0 1 -1

1 2 0

2 4 1

3 3 3

4 6 2

5 7 6

6 5 4

7 0 5

Consider the computation of an element 7 = a(a3 + a5)3 in vector form. Using the properties of GF(23), 7 can be computed as follows: a3 + a5 = 110 © 111 = 001 = a2. Thus, 7 = a(a2)3 = a1+6 = a7(= 1).

On the other hand, using the log and anti-log tables, the computation of 7 proceeds as follows: 7 = A(L(A(3) 0 A(5)) * 3 + 1) = A(L(3 © 7) * 3 + 1) = A(L(4) * 3 + 1) = A(2 * 3 + 1) = .4(7) = (4(0) = 1). In the last step, use was made of the fact that a7 = 1.

Anti-log and log tables are used in performing addition and multiplication over GF(2m). Computer programs are available on the ECC web site for simulating encoding and decoding algorithms of BCH and Reed-Solomon codes, with arithmetic in GF(2m). These algorithms are described in subsequent sections.

BINARY CYCLIC CODES AND BCH CODES

43

More properties of GF(2m)

The minimal polynomial 4>i{x) of an element a% is the smallest degree polynomial that has a1 as a root. The following properties regarding minimal polynomials can be shown. The minimal polynomial <f>i(x) has binary coefficients and is irreducible over GF(2) = {0.1}. Moreover, <j>i (x) has roots a1, a2\ • • •, a2 \ where /t divides m. These elements are known as the conjugate elements of a1 in GF(2m). The powers of the conjugate elements form a cyclotomic coset (see [MS], p. 104, and [GG], p. 391):

**23**> 24 25 26 27 28 29 .. 86 >> Next