Learn more about Communications Toolbox

Representing Elements of Galois Fields

On this page…
Section Overview Creating a Galois Array Example: Creating Galois Field Variables Example: Representing Elements of GF(8) How Integers Correspond to Galois Field Elements Example: Representing a Primitive Element Primitive Polynomials and Element Representations

Section Overview

This section describes how to create a Galois array, which is a MATLAB expression that represents the elements of a Galois field. This section also describes how MATLAB technical computing software interprets the numbers that you use in the representation, and includes several examples.

Back to Top

Creating a Galois Array

To begin working with data from a Galois field GF(2^m), you must set the context by associating the data with crucial information about the field. The gf function performs this association and creates a Galois array in MATLAB. This function accepts as inputs

• The Galois field data, x, which is a MATLAB array whose elements are integers between 0 and 2^m-1.

• (Optional) An integer, m, that indicates x is in the field GF(2^m). Valid values of m are between 1 and 16. The default is 1, which means that the field is GF(2).

• (Optional) A positive integer that indicates which primitive polynomial for GF(2^m) you are using in the representations in x. If you omit this input argument, gf uses a default primitive polynomial for GF(2^m). For information about this argument, see Specifying the Primitive Polynomial.

The output of the gf function is a variable that MATLAB recognizes as a Galois field array, rather than an array of integers. As a result, when you manipulate the variable, MATLAB works within the Galois field you have specified. For example, if you apply the log function to a Galois array, MATLAB computes the logarithm in the Galois field and not in the field of real or complex numbers.

When MATLAB Implicitly Creates a Galois Array

Some operations on Galois arrays require multiple arguments. If you specify one argument that is a Galois array and another that is an ordinary MATLAB array, MATLAB interprets both as Galois arrays in the same field. It implicitly invokes the gf function on the ordinary MATLAB array. This implicit invocation simplifies your syntax because you can omit some references to the gf function. For an example of the simplification, see Example: Addition and Subtraction.

Back to Top

Example: Creating Galois Field Variables

The code below creates a row vector whose entries are in the field GF(4), and then adds the row to itself.

x = 0:3; % A row vector containing integers
m = 2; % Work in the field GF(2^2), or, GF(4).
a = gf(x,m) % Create a Galois array in GF(2^m).

b = a + a % Add a to itself, creating b.

The output is

a = GF(2^2) array. Primitive polynomial = D^2+D+1 (7 decimal)
 
Array elements = 
 
     0     1     2     3


b = GF(2^2) array. Primitive polynomial = D^2+D+1 (7 decimal)
 
Array elements = 
 
     0     0     0     0

The output shows the values of the Galois arrays named a and b. Each output section indicates

• The field containing the variable, namely, GF(2^2) = GF(4).

• The primitive polynomial for the field. In this case, it is the toolbox's default primitive polynomial for GF(4).

• The array of Galois field values that the variable contains. In particular, the array elements in a are exactly the elements of the vector x, and the array elements in b are four instances of the zero element in GF(4).

The command that creates b shows how, having defined the variable a as a Galois array, you can add a to itself by using the ordinary + operator. MATLAB performs the vectorized addition operation in the field GF(4). The output shows that

• Compared to a, b is in the same field and uses the same primitive polynomial. It is not necessary to indicate the field when defining the sum, b, because MATLAB remembers that information from the definition of the addends, a.

• The array elements of b are zeros because the sum of any value with itself, in a Galois field of characteristic two, is zero. This result differs from the sum x + x, which represents an addition operation in the infinite field of integers.

Back to Top

Example: Representing Elements of GF(8)

To illustrate what the array elements in a Galois array mean, the table below lists the elements of the field GF(8) as integers and as polynomials in a primitive element, A. The table should help you interpret a Galois array like

gf8 = gf([0:7],3); % Galois vector in GF(2^3)

Integer Representation	Binary Representation	Element of GF(8)
0	000	0
1	001	1
2	010	A
3	011	A + 1
4	100	A2
5	101	A2 + 1
6	110	A2 + A
7	111	A2 + A + 1

Back to Top

How Integers Correspond to Galois Field Elements

Building on the GF(8) example above, this section explains the interpretation of array elements in a Galois array in greater generality. The field GF(2^m) has 2^m distinct elements, which this toolbox labels as 0, 1, 2,..., 2^m-1. These integer labels correspond to elements of the Galois field via a polynomial expression involving a primitive element of the field. More specifically, each integer between 0 and 2^m-1 has a binary representation in m bits. Using the bits in the binary representation as coefficients in a polynomial, where the least significant bit is the constant term, leads to a binary polynomial whose order is at most m-1. Evaluating the binary polynomial at a primitive element of GF(2^m) leads to an element of the field.

Conversely, any element of GF(2^m) can be expressed as a binary polynomial of order at most m-1, evaluated at a primitive element of the field. The m-tuple of coefficients of the polynomial corresponds to the binary representation of an integer between 0 and 2^m.

Below is a symbolic illustration of the correspondence of an integer X, representable in binary form, with a Galois field element. Each b_k is either zero or one, while A is a primitive element.

Back to Top

Example: Representing a Primitive Element

The code below defines a variable alph that represents a primitive element of the field GF(2⁴).

m = 4; % Or choose any positive integer value of m.
alph = gf(2,m) % Primitive element in GF(2^m)

The output is

alph = GF(2^4) array. Primitive polynomial = D^4+D+1 (19 decimal)
 
Array elements = 
 
     2

The Galois array alph represents a primitive element because of the correspondence among

• The integer 2, specified in the gf syntax

• The binary representation of 2, which is 10 (or 0010 using four bits)

• The polynomial A + 0, where A is a primitive element in this field (or 0A³ + 0A² + A + 0 using the four lowest powers of A)

Back to Top

Primitive Polynomials and Element Representations

This section builds on the discussion in Creating a Galois Array by describing how to specify your own primitive polynomial when you create a Galois array. The topics are

• Specifying the Primitive Polynomial

• Finding Primitive Polynomials

• Effect of Nondefault Primitive Polynomials on Numerical Results

If you perform many computations using a nondefault primitive polynomial, see Speed and Nondefault Primitive Polynomials.

Specifying the Primitive Polynomial

The discussion in How Integers Correspond to Galois Field Elements refers to a primitive element, which is a root of a primitive polynomial of the field. When you use the gf function to create a Galois array, the function interprets the integers in the array with respect to a specific default primitive polynomial for that field, unless you explicitly provide a different primitive polynomial. A list of the default primitive polynomials is on the reference page for the gf function.

To specify your own primitive polynomial when creating a Galois array, use a syntax like

c = gf(5,4,25) % 25 indicates the primitive polynomial for GF(16).

instead of

c1= gf(5,4); % Use default primitive polynomial for GF(16).

The extra input argument, 25 in this case, specifies the primitive polynomial for the field GF(2^m) in a way similar to the representation described in How Integers Correspond to Galois Field Elements. In this case, the integer 25 corresponds to a binary representation of 11001, which in turn corresponds to the polynomial D⁴ + D³ + 1.

Note   When you specify the primitive polynomial, the input argument must have a binary representation using exactly m+1 bits, not including unnecessary leading zeros. In other words, a primitive polynomial for GF(2^m) always has order m.

When you use an input argument to specify the primitive polynomial, the output reflects your choice by showing the integer value as well as the polynomial representation.

d = gf([1 2 3],4,25)

d = GF(2^4) array. Primitive polynomial = D^4+D^3+1 (25 decimal)
 
Array elements = 
 
     1     2     3

Note   After you have defined a Galois array, you cannot change the primitive polynomial with respect to which MATLAB interprets the array elements.

Finding Primitive Polynomials

You can use the primpoly function to find primitive polynomials for GF(2^m) and the isprimitive function to determine whether a polynomial is primitive for GF(2^m). The code below illustrates.

m = 4;
defaultprimpoly = primpoly(m) % Default primitive poly for GF(16)
allprimpolys = primpoly(m,'all') % All primitive polys for GF(16)
i1 = isprimitive(25) % Can 25 be the prim_poly input in gf(...)?
i2 = isprimitive(21) % Can 21 be the prim_poly input in gf(...)?

The output is below.

Primitive polynomial(s) = 
 
D^4+D^1+1

defaultprimpoly =

    19

Primitive polynomial(s) = 
 
D^4+D^1+1
D^4+D^3+1

allprimpolys =

    19
    25

i1 =

     1

i2 =

     0

Effect of Nondefault Primitive Polynomials on Numerical Results

Most fields offer multiple choices for the primitive polynomial that helps define the representation of members of the field. When you use the gf function, changing the primitive polynomial changes the interpretation of the array elements and, in turn, changes the results of some subsequent operations on the Galois array. For example, exponentiation of a primitive element makes it easy to see how the primitive polynomial affects the representations of field elements.

a11 = gf(2,3); % Use default primitive polynomial of 11.
a13 = gf(2,3,13); % Use D^3+D^2+1 as the primitive polynomial.
z = a13.^3 + a13.^2 + 1 % 0 because a13 satisfies the equation
nz = a11.^3 + a11.^2 + 1 % Nonzero. a11 does not satisfy equation.

The output below shows that when the primitive polynomial has integer representation 13, the Galois array satisfies a certain equation. By contrast, when the primitive polynomial has integer representation 11, the Galois array fails to satisfy the equation.

z = GF(2^3) array. Primitive polynomial = D^3+D^2+1 (13 decimal)
 
Array elements = 
 
     0


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

The output when you try this example might also include a warning about lookup tables. This is normal if you did not use the gftable function to optimize computations involving a nondefault primitive polynomial of 13.

Back to Top

Galois Field Terminology

Arithmetic in Galois Fields

© 1984-2009- The MathWorks, Inc.    -   Site Help   -   Patents   -   Trademarks   -   Privacy Policy   -   Preventing Piracy   -   RSS