Finite Fields

National Instruments has partnered with Prentice Hall to bring you large portions of in-depth technical topics from several PTR RF and Communications books, including Digital Communications: Fundamentals and Applications, 2nd Edition. This series of content is designed for a broad range of audiences, from experts who want to review a specific topic to students who need easy-to-understand documentation for their projects.

For the complete list of RF topics, please visit the RF and Communications Resource Main Page.

8.1.4 Finite Fields

In order to understand the encoding and decoding principles of nonbinary codes,

such as a Reed–Solomon (R-S) codes, it is necessary to venture into the area of

finite fields known as Galois Fields (GF). For any prime number p there exists a

finite field denoted GF(p), containing p elements. It is possible to extend GF(p) to

a field of p^m elements, called an extension field of GF(p), and denoted by GF(p^m),

where m is a nonzero positive integer. Note that GF(p^m) contains as a subset the

elements of GF(p). Symbols from the extension field GF(2^m) are used in the

construction of Reed–Solomon (R–S) codes.

The binary field GF(2) is a subfield of the extension field GF(2^m), much the

same way as the real number field is a subfield of the complex number field. Besides

the numbers 0 and 1, there are additional unique elements in the extension

field that will be represented with a new symbol α. Each nonzero element in

 can be represented by a power of . An infinite set of elements, F, is

formed by starting with the elements   and generating additional elements

by progressively multiplying the last entry by α which yields

To obtain the finite set of elements of GF(2^m) from F, a condition must be imposed

on F so that it may contain only 2^m elements and is closed under multiplication.

The condition that closes the set of field elements under multiplication is

characterized by the irreducible polynomial

                                                            

or equivalently,

Using this polynomial constraint, any field element that has a power equal to

or greater than 2^m − 1 can be reduced to an element with a power less than 2^m − 1 as

follows:

Thus, Equation (8.10) can be used to form the finite sequence F* from the infinite

sequence F, as follows:

Therefore, it can be seen from Equation (8.12) that the elements of the finite

field GF(2)m are given by

8.1.4.1 Addition in the Extension Field GF(2m)

Each of the 2^m elements of the finite field GF(2^m) can be represented as a

distinct polynomial of degree m − 1 or less. The degree of a polynomial is the value

of its highest order exponent. We denote each of the nonzero elements of GF(2^m)

as a polynomial a_i(X), where at least one of the m coefficients of a_i(X) is nonzero.

For i = 0, 1, 2, . . . , 2^m − 2,

Consider the case of m = 3, where the finite field is denoted GF(2³). Figure

8.7 shows the mapping of the seven elements  and the zero element, in terms of

the basis elements {X⁰, X¹, X²} described by Equation (8.14). Since Equation (8.10)

indicates that , there are seven nonzero elements or a total of eight elements

in this field. Each row in the Figure 8.7 mapping comprises a sequence of binary

values representing the coefficients , and  in Equation (8.14). One of the

benefits of using extension field elements  in place of binary elements is the

compact notation that facilitates the mathematical representation of nonbinary

encoding and decoding processes. Addition of two elements of the finite field is

then defined as the modulo-2 sum of each of the polynomial coefficients of like

powers, i.e.,

8.1.4.2 A Primitive Polynomial is Used to Define the Finite Field

A class of polynomials called primitive polynomials, is of interest because

such functions define the finite fields of GF(2^m) which in turn are needed to define

R-S codes. The following condition is necessary and sufficient to guarantee that a

Figure 8.7 Mapping field elements in terms of basis elements for GF(8) with f(X) = 1 + X + X³.

polynomial is primitive. An irreducible polynomial, ƒ(X), of degree m is said to be

primitive, if the smallest positive integer n for which ƒ(X) divides Xⁿ + 1 is n = 2^m − 1.

Note that an irreducible polynomial is one that cannot be factored to yield lower

order polynomials, and that the statement A divides B means that A divided into B

yields a nonzero quotient and a zero remainder. Polynomials will usually be shown

low order-to-high order. Sometimes, it is convenient to follow the reverse format

(e.g., when performing polynomial division).

Example 8.1 Recognizing a Primitive Polynomial

Based on the foregoing definition of a primitive polynomial, determine whether the following

irreducible polynomials are primitive:

Solution

(a) We can verify whether or not this degree m = 4 polynomial is primitive by determining

if it divides Xⁿ + 1 = X(^{2m − 1}) + 1 = X¹⁵ + 1, but does not divide Xⁿ + 1, for

values of n in the range of 1 ≤ n < 15. It is easy to verify that 1 + X + X⁴ divides

X¹⁵ + 1 (see Section 6.8.1), and after repeated computations it can be verified that

1 + X + X⁴ will not divide Xⁿ + 1 for any n in the range of 1 ≤ n < 15. Therefore,

1 + X + X⁴ is a primitive polynomial.

(b) It is simple to verify that the polynomial 1 + X + X² + X³ + X⁴ divides X¹⁵ + 1. Testing

to see if it will divide Xⁿ + 1 for some n that is less than 15, yields the fact that it

also divides X⁵ + 1. Thus, although 1 + X + X² + X³ + X⁴ is irreducible, it is not

primitive.

8.1.4.3 The Extension Field GF(23)

Consider an example involving a primitive polynomial and the finite field that

it defines. Table 8.1 contains a listing of some primitive polynomials. We choose

the first one shown, f (X) = 1 + X + X³ which defines a finite field GF(2^m), where

the degree of the polynomial is m = 3. Thus, there are 2^m = 2³ = 8 elements in the

field defined by f (X). Solving for the roots of ƒ(X) means that the values of X that

correspond to f (X) = 0 must be found. The familiar binary elements 1 and 0 do not

satisfy (are not roots of) the polynomial f (X) = 1 + X + X³, since ƒ(1) = 1 and ƒ(0) =

1 (using modulo-2 arithmetic). Yet, a fundamental theorem of algebra states that a

polynomial of degree m must have precisely m roots. Therefore for this example,

f (X) = 0 must yield 3 roots. Clearly a dilemma arises, since the 3 roots do not lie in

the same finite field as the coefficients of f (X). Therefore, they must lie somewhere

else; the roots lie in the extension field GF(2³). Let   an element of the extension

field, be defined as a root of the polynomial f (X). Therefore, it is possible

to write

Since in the binary field +1 = −1, then 3 can be represented as

Thus,  is expressed as a weighted sum of  terms having lower orders. In fact, all

powers of can be so expressed. For example, consider

Now consider

From Equations (8.17) and (8.18b), we obtain

Now, using Equation (8.18c), we obtain

And using Equation (8.18d), we obtain

Note that  and therefore, the eight finite field elements of GF(2³) are

The mapping of field elements in terms of basis elements, described by Equation

(8.14) can be demonstrated with the linear feedback shift register (LFSR) circuit

shown in Figure 8.8. The circuit generates (with m = 3) the 2^m − 1 nonzero

elements of the field, and thus summarizes the findings of Equations (8.17) through

(8.19). Note that in Figure 8.8, the circuit feedback connections correspond to the

coefficients of the polynomial f(X) = 1 + X + X³, just like for binary cyclic codes.

(See Section 6.7.5.) By starting the circuit in any nonzero state, say 1 0 0, and performing

a right-shift at each clock time, it is possible to verify that each of the field

 

Figure 8.8 Extension field elements can be represented by the contents of a binary linear feedback shift register

(LFSR) formed from a primitive polynomial.

 

elements shown in Figure 8.7 (except the all-zeros element) will cyclicly appear in

the stages of the shift register. Two arithmetic operations, addition and multiplication,

can be defined for this GF(2³) finite field. Addition is shown in Table 8.2, and

multiplication is shown in Table 8.3 for the nonzero elements only. The rules of

addition follow from Equations (8.17) through (8.18e), and can be verified by

noticing in Figure 8.7 that the sum of any field elements can be obtained by adding

(modulo-2) the respective coefficients of their basis elements. The multiplication

rules in Table 8.3 follow the usual procedure in which the product of the field

elements is obtained by adding their exponents modulo-(2^m − 1), or for this case,

modulo-7.

8.1.4.4 A Simple Test to Determine if a Polynomial is Primitive

There is another way of defining a primitive polynomial that makes its verification

relatively easy. For an irreducible polynomial to be a primitive polynomial,

at least one of its roots must be a primitive element. A primitive element is one that

when raised to higher order exponents will yield all the nonzero elements in the

field. Since the field is a finite field, the number of such elements is finite.

Example 8.2 A Primitive Polynomial Must Have at Least one Primitive Element

Find the m = 3 roots of f(X) = 1 + X + X³, and verify that the polynomial is primitive

by checking that at least one of the roots is a primitive element. What are the roots?

Which ones are primitive?

Solution

 It is not difficult to verify that

starting with any one of these roots and generating higher order exponents yields all of

the 7 nonzero elements in the field. Hence, each of the roots is a primitive element.

Since our verification requires that at least one root be a primitive element, the polynomial

is primitive.

A relatively simple method to verify if a polynomial is primitive can be described

in a manner that is related to this example. For any given polynomial under

test, draw the LFSR, with the feedback connections corresponding to the polynomial

coefficients as shown by the example of Figure 8.8. Load into the circuit-registers any

nonzero setting, and perform a right shift with each clock pulse. If the circuit generates

each of the nonzero field elements within one period, then the polynomial that defines

this GF(2^m) field is a primitive polynomial.

Relevant NI products

Customers interested in this topic were also interested in the following NI products:

• RF and Communication Hardware and Software
  
• Other Modular Instruments (digital multimeters, digitizers, switching, etc...)
• LabVIEW Graphical Programming Environment

For the complete list of tutorials, return to the NI RF and Communications Fundamentals Main page.

Buy the Book

Purchase Digital Communications from Prentice Hall Professional through this link and receive the following:

• Between 15% and 30% Off
• Free Shipping and Handling

Reader Comments | Submit a comment »