AN2407 查看數據表（PDF） - Freescale Semiconductor

零件编号

产品描述 (功能)

生产厂家

AN2407

Reed Solomon Encoder/Decoder on the StarCore™ SC140/SC1400 Cores, With Extended Examples

Freescale Semiconductor 

Theory

2.1.1 Binary Field, GF(2)

The simplest Galois field is GF(2). Its elements are the set {0,1} under modulo-2 algebra. Addition and subtraction

in this algebra are both equivalent to the logical XOR operation. The addition and multiplication tables of GF(2)

are shown in Figure 2.

Addition

+

0

1

0

0

1

1

1

0

Multiplication

x

0

1

0

0

0

1

0

1

Figure 2. Addition (XOR) and Multiplication Tables of GF(2)

There is a one-to-one correspondence between any binary number and a polynomial in that every binary number

can be represented as a polynomial over GF(2), and vice versa. A polynomial of degree D over GF(2) has the

following general form:

f(x) = f0 + f1x + f2x2 + f3x3… + fDxD

where the coefficients f0,..., fD are taken from GF(2). A binary number of (N+1) bits can be represented as an

abstract polynomial of degree N by taking the coefficients equal to the bits and the exponents of x equal to the bit

locations.

For example, the binary number 100011101 is equivalent to the following polynomial:

100011101 ↔ 1 + x2 + x3 + x4 + x8

The bit at the zero position (the coefficient of x0) is equal to 1, the bit at the first position (the coefficient of x) is

equal to 0, the bit at the second position (the coefficient of x2) is equal to 1, and so on. Operations on polynomials,

such as addition, subtraction, multiplication and division, are performed in an analogous way to the real number

field. The sole difference is that the operations on the coefficients are performed under modulo-2 algebra. For

example, the multiplication of two polynomials is as follows:

(1 + x2 + x3 + x4) ⋅ (x3 + x5) = x3 + x5 + x5 + x6 + x7 + x7 + x8 + x9= x3 + x6 + x8 + x9

This result differs from the result obtained over the real number field (the middle expression) due to the XOR

operation (the + operation). The terms that appear an even number of times cancel out, so the coefficients of x5 and

x7 are not present in the end result.

2.1.2 Extended Galois Fields GF(2m)

A polynomial p(x) over GF(2) is defined as irreducible if it cannot be factored into non-zero polynomials over

GF(2) of smaller degrees. It is further defined as primitive if n = (xn + 1) divided by p(x) and the smallest positive

integer n equals 2m –1, where m is the polynomial degree. An element of GF(2m) is defined as the root of a

primitive polynomial p(x) of degree m. An element α is defined as primitive if

αimod(2m–1 )

Reed Solomon Encoder/Decoder on the StarCore™ SC140/SC1400 Cores, With Extended Examples, Rev. 1

4

Freescale Semiconductor

Share Link: