UNB ECE4253 Digital Communications
Department of Electrical and Computer Engineering - University of New Brunswick, Fredericton, NB, Canada

Manipulation of Binary Messages as Polynomials in GF(2m)

Fields of the form GF(2) can be extended to higher order Galois Fields of the form GF(2m) for positive integer m. Such fields are called extension fields.

Introduction to the Galois Field GF(2m)

1. Multi-bit binary values are defined on a set {0,1,2...2m-1} which constititutes a finite field or Galois field labeled GF(2m). In the following examples, let m=3 such that the finite field GF(23) has eight 3-bit elements described as polynomials in GF(2). For such fields the addition operation is defined as being (bitwise) modulo 2. For example, 
      000 + 000 = 000    011 + 010 = 001    111 + 111 = 000
As with GF(2), this is equivalent to the exclusive-OR operation. The set satisfies the definition of an additive group: the properties of closure, identity, inverse, and associative can be confirmed for addition in this set. The operation is also commutative. For this field the multiplication operation is defined modulo 2 and modulo a GF(2) primitive prime P(x) of degree m. Let P(x) = (1011), then: 
      000 * 000 = 000    011 * 010 = 110    111 * 111 = 10101 = 011 mod P(x)
While this is like GF(2) multiplication, the introduction of a primitive polynomial modulus P(x) of degree 3 is important to ensure that this set of eight elements is closed under multiplication. In the example above, the simple product 111 * 111 gives 10101 which must be taken modulus P(x) to give a 3-bit result. The set satisfies the definition of a multiplicative group: the properties of closure, identity, inverse, and associative can be confirmed for multiplication in this set (excluding the zero which has no inverse). The operation is also commutative.

In summary the set {0,1,2...2m-1} is both an additive group and a multiplicative group and the operation of multiplication is distributive over addition (e.g. a * [b+c] = a*b + b*c ) both operations are commutative and the set defines a field named GF(2m).

The choice of a different P(x) as a modulus leads to different multiplication answers that still belong to the same field. In a practical sense, the results are not fundamentally different and two finite fields with the same number of elements (order) are called isomorphic.

2. Multi-bit binary values can be represented as polynomials with coefficients from GF(2m).

For example, with m=3, the 9-bit binary value 100110011 can be broken into 3-bit parts as 100 110 011 and written as

4 x2 + 6 x1 + 3 x0

and simplified as:

4 x2 + 6 x + 3

or as polynomial terms in brackets:

(4 6 3)

The degree of a polynomial is the power of the highest non-zero coefficient. The above example shows a polynomial of "degree 2".

3. Polynomials can be manipulated using the usual arithmetic rules, in particular, the polynomial powers add under multiplication, as expected.

Example 1: (4 6 3) x (1 0) = (4 6 3 0) can be written as:

( 4 x2 + 6 x + 3) (x) = ( 4 x3 + 6 x2 + 3x )

4. Polynomials always use modulo 2 addition as described above.

Example 2: (1 2) x (1 2) can be computed as: 

    
              1 2
            x 1 2
            -----
              2 4
          + 1 2 0
            -----
            1 0 4       Note modulo 2 addition
and as a polynomial:
(x + 2)(x + 2) = x2 + 2x + 2x + 4 = x2 + 4
Note that 2x + 2x = 0 when simplifying this result.

This example illustrates the more general property that (a + b)2 = a2 + b2 which shows that squaring is a linear operation in GF(2N).

5. The rules for subtraction follow from addition and are also equivalent to the bitwise exclusive-OR operation, as: 

      000 - 000 = 000    011 - 010 = 001    111 - 111 = 000

6. With these rules in mind, hand calculation is made easier with addition and multiplication tables for these operations. The choice of P(x) affects only the multiplication table.

* See addition and multiplication tables.

In particular, the multiplicative inverse of a value can be found from the multiplication table by identifying the entry in a given row or column that gives the result 1.

Longer calculations will benefit from the use a calculator. The P(x) must be specified in each case.

* Online GF(2^m) Calculator Tool

7. The non-zero elements of GF(2m} defined on P(x) are found in the terms {an} provided that the element a is a root of P(x), meaning that P(a) = 0.

For example, using the above P(x) = x3 + x + 1 having m=3, then a=2 is a root because P(2) = 2^3 + 2 + 1 = 3 + 2 + 1 = 0. In this case, the term 2^3 = 2x2x2 = 3 may be found from the multiplication table and the 3-bit additions proceed as 011 + 010 + 001 = 000.

Subsequently, successive powers of 2n describe all the non-zero field elements {1,2,4,3,6,7,5} for n= 0 to 6. For example, 25 = 7.

It follows that logarithms in GF(23) are defined such that, for example, if a5 = 7 then log(7) = 5. In general, the computation of such logarithms is not straightforward and the use of a lookup table is one possible approach.

GF(2m) Fields in MATLAB

The above field GF(23) is defined by a power 3 and a polynomial P(x) = x3 + x + 1 = (1011) = 11 decimal. 
>> a = gf(2,3,11);       % Let a=2 in GF(2^3) with P(x)   
>> y = a.^(0:6)          % find successive powers of 2^n   

y = GF(2^3) array. Primitive polynomial = D^3+D+1 (11 decimal)
 
Array elements = 

     1     2     4     3     6     7     5 

>> log(y)                % find the discrete logarithm of these values   

ans =

     0     1     2     3     4     5     6

Wed Apr 24 20:59:52 ADT 2024
Last Updated: 07 FEB 2016 		Richard Tervo [ tervo@unb.ca ] Back to the course homepage...