Galois Fields

Galois Field Computations for Even Order, GF(2^m), Fields

A Galois field is an algebraic field that has a finite number of members. Galois fields having 2^m members are used in error-control coding and are denoted GF(2^m). This section describes how to work with fields that have 2^m members, where m is an integer between 1 and 16.

If you need to use Galois fields having an odd number of elements, see Galois Field Computations for Odd Order, GF(pm), Fields.

For more details about specific functions that process arrays of Galois field elements, see the gf reference page.

Note

Please note that the Galois field objects do not support the copy method.

MATLAB^® functions whose generalization to Galois fields is straightforward to describe do not have specific Communications Toolbox™ reference pages because the entries would be identical to those in the MATLAB documentation.

• Galois Field Terminology

• Representing Elements of Galois Fields

• Arithmetic in Galois Fields

• Logical Operations in Galois Fields

• Matrix Manipulation in Galois Fields

• Linear Algebra in Galois Fields

• Signal Processing Operations in Galois Fields

• Polynomials over Galois Fields

• Manipulating Galois Variables

• Speed and Nondefault Primitive Polynomials

• Selected Bibliography for Galois Fields

Galois Field Terminology

The discussion of Galois fields in this document uses a few terms that are not used consistently in the literature. The definitions adopted here appear in van Lint [5]:

• A primitive element of GF(2^m) is a cyclic generator of the group of nonzero elements of GF(2^m). This means that every nonzero element of the field can be expressed as the primitive element raised to some integer power.

• A primitive polynomial for GF(2^m) is the minimal polynomial of some primitive element of GF(2^m). It is the binary-coefficient polynomial of smallest nonzero degree having a certain primitive element as a root in GF(2^m). As a consequence, a primitive polynomial has degree m and is irreducible.

The definitions imply that a primitive element is a root of a corresponding primitive polynomial.

Representing Elements of Galois Fields

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

Creating a Galois field 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 field array in MATLAB. Inputs to the gf function include:

• The Galois field data, x, which is a MATLAB array whose elements are integers in the range [0, (2^m – 1)].

• (Optional) An integer, m, that indicates x is in the field GF(2^m). Valid values of m are in the range [1, 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 Primitive Polynomials and Element Representations.

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 field 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 field array

Some operations on Galois field arrays require multiple arguments. If you specify one argument that is a Galois field array and another that is an ordinary MATLAB array, MATLAB interprets both as Galois field 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.

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 field 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 field 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.

Example: Representing Elements of GF(8).  To illustrate what the array elements in a Galois field 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 field 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

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 field 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.

$$\begin{array}{c}X=b_{m-1}\cdot 2^{m-1}+\cdots +b_2\cdot 4+b_1\cdot 2+b_0\\ \leftrightarrow b_{m-1}\cdot A^{m-1}+\cdots +b_2\cdot A^2+b_1\cdot A+b_0\end{array}$$

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 field 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)

Primitive Polynomials and Element Representations.  This section builds on the discussion in Creating a Galois field array by describing how to specify your own primitive polynomial when you create a Galois field array. The topics are

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 field 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 field 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 field 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 field 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 field array satisfies a certain equation. By contrast, when the primitive polynomial has integer representation 11, the Galois field 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.

Arithmetic in Galois Fields

Section Overview.  You can perform arithmetic operations on Galois field arrays by using familiar MATLAB operators, listed in the table below. Whenever you operate on a pair of Galois field arrays, both arrays must be in the same Galois field.

Operation	Operator
Addition	+
Subtraction	-
Elementwise multiplication	.*
Matrix multiplication	*
Elementwise left division	./
Elementwise right division	.\
Matrix left division	/
Matrix right division	\
Elementwise exponentiation	.^
Elementwise logarithm	log()
Exponentiation of a square Galois matrix by a scalar integer	^

For multiplication and division of polynomials over a Galois field, see Addition and Subtraction of Polynomials.

Example: Addition and Subtraction.  The code below adds two Galois field arrays to create an addition table for GF(8). Addition uses the ordinary + operator. The code below also shows how to index into the array addtb to find the result of adding 1 to the elements of GF(8).

m = 3;
e = repmat([0:2^m-1],2^m,1);
f = gf(e,m); % Create a Galois array.
addtb = f + f' % Add f to its own matrix transpose.

addone = addtb(2,:); % Assign 2nd row to the Galois vector addone.

The output is below.

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

Array elements =

     0     1     2     3     4     5     6     7
     1     0     3     2     5     4     7     6
     2     3     0     1     6     7     4     5
     3     2     1     0     7     6     5     4
     4     5     6     7     0     1     2     3
     5     4     7     6     1     0     3     2
     6     7     4     5     2     3     0     1
     7     6     5     4     3     2     1     0

As an example of reading this addition table, the (7,4) entry in the addtb array shows that gf(6,3) plus gf(3,3) equals gf(5,3). Equivalently, the element A²+A plus the element A+1 equals the element A²+1. The equivalence arises from the binary representation of 6 as 110, 3 as 011, and 5 as 101.

The subtraction table, which you can obtain by replacing + by -, is the same as addtb. This is because subtraction and addition are identical operations in a field of characteristic two. In fact, the zeros along the main diagonal of addtb illustrate this fact for GF(8).

Simplifying the Syntax

The code below illustrates scalar expansion and the implicit creation of a Galois field array from an ordinary MATLAB array. The Galois field arrays h and h1 are identical, but the creation of h uses a simpler syntax.

g = gf(ones(2,3),4); % Create a Galois array explicitly.
h = g + 5; % Add gf(5,4) to each element of g.
h1 = g + gf(5*ones(2,3),4) % Same as h.

The output is below.

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

Array elements =

     4     4     4
     4     4     4

Notice that 1+5 is reported as 4 in the Galois field. This is true because the 5 represents the polynomial expression A²+1, and 1+(A²+1) in GF(16) is A². Furthermore, the integer that represents the polynomial expression A² is 4.

Example: Multiplication.  The example below multiplies individual elements in a Galois field array using the .* operator. It then performs matrix multiplication using the * operator. The elementwise multiplication produces an array whose size matches that of the inputs. By contrast, the matrix multiplication produces a Galois scalar because it is the matrix product of a row vector with a column vector.

m = 5;
row1 = gf([1:2:9],m); row2 = gf([2:2:10],m);
col = row2'; % Transpose to create a column array.
ep = row1 .* row2; % Elementwise product.
mp = row1 * col; % Matrix product.

Multiplication Table for GF(8)

As another example, the code below multiplies two Galois vectors using matrix multiplication. The result is a multiplication table for GF(8).

m = 3;
els = gf([0:2^m-1]',m);
multb = els * els' % Multiply els by its own matrix transpose.

The output is below.

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

Array elements =

     0     0     0     0     0     0     0     0
     0     1     2     3     4     5     6     7
     0     2     4     6     3     1     7     5
     0     3     6     5     7     4     1     2
     0     4     3     7     6     2     5     1
     0     5     1     4     2     7     3     6
     0     6     7     1     5     3     2     4
     0     7     5     2     1     6     4     3

Example: Division.  The examples below illustrate the four division operators in a Galois field by computing multiplicative inverses of individual elements and of an array. You can also compute inverses using inv or using exponentiation by -1.

Elementwise Division

This example divides 1 by each of the individual elements in a Galois field array using the ./ and .\ operators. These two operators differ only in their sequence of input arguments. Each quotient vector lists the multiplicative inverses of the nonzero elements of the field. In this example, MATLAB expands the scalar 1 to the size of nz before computing; alternatively, you can use as arguments two arrays of the same size.

m = 5;
nz = gf([1:2^m-1],m); % Nonzero elements of the field
inv1 = 1 ./ nz; % Divide 1 by each element.
inv2 = nz .\ 1; % Obtain same result using .\ operator.

Matrix Division

This example divides the identity array by the square Galois field array mat using the / and \ operators. Each quotient matrix is the multiplicative inverse of mat. Notice how the transpose operator (') appears in the equivalent operation using \. For square matrices, the sequence of transpose operations is unnecessary, but for nonsquare matrices, it is necessary.

m = 5;
mat = gf([1 2 3; 4 5 6; 7 8 9],m);
minv1 = eye(3) / mat; % Compute matrix inverse.
minv2 = (mat' \ eye(3)')'; % Obtain same result using \ operator.

Example: Exponentiation.  The examples below illustrate how to compute integer powers of a Galois field array. To perform matrix exponentiation on a Galois field array, you must use a square Galois field array as the base and an ordinary (not Galois) integer scalar as the exponent.

Elementwise Exponentiation

This example computes powers of a primitive element, A, of a Galois field. It then uses these separately computed powers to evaluate the default primitive polynomial at A. The answer of zero shows that A is a root of the primitive polynomial. The .^ operator exponentiates each array element independently.

m = 3;
av = gf(2*ones(1,m+1),m); % Row containing primitive element
expa = av .^ [0:m]; % Raise element to different powers.
evp = expa(4)+expa(2)+expa(1) % Evaluate D^3 + D + 1.

The output is below.

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

Array elements =

     0

Matrix Exponentiation

This example computes the inverse of a square matrix by raising the matrix to the power -1. It also raises the square matrix to the powers 2 and -2.

m = 5;
mat = gf([1 2 3; 4 5 6; 7 8 9],m);
minvs = mat ^ (-1); % Matrix inverse
matsq = mat^2; % Same as mat * mat
matinvssq = mat^(-2); % Same as minvs * minvs

Example: Elementwise Logarithm.  The code below computes the logarithm of the elements of a Galois field array. The output indicates how to express each nonzero element of GF(8) as a power of the primitive element. The logarithm of the zero element of the field is undefined.

gf8_nonzero = gf([1:7],3); % Vector of nonzero elements of GF(8)
expformat = log(gf8_nonzero) % Logarithm of each element

The output is

expformat =

     0     1     3     2     6     4     5

As an example of how to interpret the output, consider the last entry in each vector in this example. You can infer that the element gf(7,3) in GF(8) can be expressed as either

• A⁵, using the last element of expformat

• A²+A+1, using the binary representation of 7 as 111. See Example: Representing Elements of GF(8) for more details.

Logical Operations in Galois Fields

Section Overview.  You can apply logical tests to Galois field arrays and obtain a logical array. Some important types of tests are testing for the equality of two Galois field arrays and testing for nonzero values in a Galois field array.

Testing for Equality.  To compare corresponding elements of two Galois field arrays that have the same size, use the operators == and ~=. The result is a logical array, each element of which indicates the truth or falsity of the corresponding elementwise comparison. If you use the same operators to compare a scalar with a Galois field array, MATLAB technical computing software compares the scalar with each element of the array, producing a logical array of the same size.

m = 5; r1 = gf([1:3],m); r2 = 1 ./ r1;
lg1 = (r1 .* r2 == [1 1 1]) % Does each element equal one?
lg2 = (r1 .* r2 == 1) % Same as above, using scalar expansion
lg3 = (r1 ~= r2) % Does each element differ from its inverse?

The output is below.

lg1 =

     1     1     1


lg2 =

     1     1     1


lg3 =

     0     1     1

Comparison of isequal and ==

To compare entire arrays and obtain a logical scalar result rather than a logical array, use the built-in isequal function. However, isequal uses strict rules for its comparison, and returns a value of 0 (false) if you compare

• A Galois field array with an ordinary MATLAB array, even if the values of the underlying array elements match

• A scalar with a nonscalar array, even if all elements in the array match the scalar

The example below illustrates this difference between == and isequal.

m = 5; r1 = gf([1:3],m); r2 = 1 ./ r1;
lg4 = isequal(r1 .* r2, [1 1 1]); % False
lg5 = isequal(r1 .* r2, gf(1,m)); % False
lg6 = isequal(r1 .* r2, gf([1 1 1],m)); % True

Testing for Nonzero Values.  To test for nonzero values in a Galois vector, or in the columns of a Galois field array that has more than one row, use the any or all function. These two functions behave just like the ordinary MATLAB functions any and all, except that they consider only the underlying array elements while ignoring information about which Galois field the elements are in. Examples are below.

m = 3; randels = gf(randi([0 2^m-1],6,1),m);
if all(randels) % If all elements are invertible
    invels = randels .\ 1; % Compute inverses of elements.
else
    disp('At least one element was not invertible.');
end
alph = gf(2,4);
poly = 1 + alph + alph^3;
if any(poly) % If poly contains a nonzero value
    disp('alph is not a root of 1 + D + D^3.');
end
code = [0:4 4 0; 3:7 4 5]
if all(code,2) % Is each row entirely nonzero?
    disp('Both codewords are entirely nonzero.');
else
    disp('At least one codeword contains a zero.');
end

Matrix Manipulation in Galois Fields

Basic Manipulations of Galois Field Arrays.  Basic array operations on Galois field arrays are in the table below. The functionality of these operations is analogous to the MATLAB operations having the same syntax.

Operation	Syntax
Index into array, possibly using colon operator instead of a vector of explicit indices	a(vector) or a(vector,vector1), where vector and/or vector1 can be ":" instead of a vector
Transpose array	a'
Concatenate matrices	[a,b] or [a;b]
Create array having specified diagonal elements	diag(vector) or diag(vector,k)
Extract diagonal elements	diag(a) or diag(a,k)
Extract lower triangular part	tril(a) or tril(a,k)
Extract upper triangular part	triu(a) or triu(a,k)
Change shape of array	reshape(a,k1,k2)

The code below uses some of these syntaxes.

m = 4; a = gf([0:15],m);
a(1:2) = [13 13]; % Replace some elements of the vector a.
b = reshape(a,2,8); % Create 2-by-8 matrix.
c = [b([1 1 2],1:3); a(4:6)]; % Create 4-by-3 matrix.
d = [c, a(1:4)']; % Create 4-by-4 matrix.
dvec = diag(d); % Extract main diagonal of d.
dmat = diag(a(5:9)); % Create 5-by-5 diagonal matrix
dtril = tril(d); % Extract upper and lower triangular
dtriu = triu(d); % parts of d.

Basic Information About Galois Field Arrays.  You can determine the length of a Galois vector or the size of any Galois field array using the length and size functions. The functionality for Galois field arrays is analogous to that of the MATLAB operations on ordinary arrays, except that the output arguments from size and length are always integers, not Galois field arrays. The code below illustrates the use of these functions.

m = 4; e = gf([0:5],m); f = reshape(e,2,3);
lne = length(e); % Vector length of e
szf = size(f); % Size of f, returned as a two-element row
[nr,nc] = size(f); % Size of f, returned as two scalars
nc2 = size(f,2); % Another way to compute number of columns

Positions of Nonzero Elements

Another type of information you might want to determine from a Galois field array are the positions of nonzero elements. For an ordinary MATLAB array, you might use the find function. However, for a Galois field array, you should use find in conjunction with the ~= operator, as illustrated.

x = [0 1 2 1 0 2]; m = 2; g = gf(x,m);
nzx = find(x); % Find nonzero values in the ordinary array x.
nzg = find(g~=0); % Find nonzero values in the Galois array g.

Linear Algebra in Galois Fields

Inverting Matrices and Computing Determinants.  To invert a square Galois field array, use the inv function. Related is the det function, which computes the determinant of a Galois field array. Both inv and det behave like their ordinary MATLAB counterparts, except that they perform computations in the Galois field instead of in the field of complex numbers.

Note

A Galois field array is singular if and only if its determinant is exactly zero. It is not necessary to consider roundoff errors, as in the case of real and complex arrays.

The code below illustrates matrix inversion and determinant computation.

m = 4;
randommatrix = gf(randi([0 2^m-1],4,4),m);
gfid = gf(eye(4),m);
if det(randommatrix) ~= 0
    invmatrix = inv(randommatrix);
    check1 = invmatrix * randommatrix;
    check2 = randommatrix * invmatrix;
    if (isequal(check1,gfid) & isequal(check2,gfid))
        disp('inv found the correct matrix inverse.');
    end
else
    disp('The matrix is not invertible.');
end

The output from this example is either of these two messages, depending on whether the randomly generated matrix is nonsingular or singular.

inv found the correct matrix inverse.
The matrix is not invertible.

Computing Ranks.  To compute the rank of a Galois field array, use the rank function. It behaves like the ordinary MATLAB rank function when given exactly one input argument. The example below illustrates how to find the rank of square and nonsquare Galois field arrays.

m = 3;
asquare = gf([4 7 6; 4 6 5; 0 6 1],m);
r1 = rank(asquare);
anonsquare = gf([4 7 6 3; 4 6 5 1; 0 6 1 1],m);
r2 = rank(anonsquare);
[r1 r2]

The output is

ans =

     2     3

The values of r1 and r2 indicate that asquare has less than full rank but that anonsquare has full rank.

Factoring Square Matrices.  To express a square Galois field array (or a permutation of it) as the product of a lower triangular Galois field array and an upper triangular Galois field array, use the lu function. This function accepts one input argument and produces exactly two or three output arguments. It behaves like the ordinary MATLAB lu function when given the same syntax. The example below illustrates how to factor using lu.

tofactor = gf([6 5 7 6; 5 6 2 5; 0 1 7 7; 1 0 5 1],3);
[L,U]=lu(tofactor); % lu with two output arguments
c1 = isequal(L*U, tofactor) % True
tofactor2 = gf([1 2 3 4;1 2 3 0;2 5 2 1; 0 5 0 0],3);
[L2,U2,P] = lu(tofactor2); % lu with three output arguments
c2 = isequal(L2*U2, P*tofactor2) % True

Solving Linear Equations.  To find a particular solution of a linear equation in a Galois field, use the \ or / operator on Galois field arrays. The table below indicates the equation that each operator addresses, assuming that A and B are previously defined Galois field arrays.

Operator	Linear Equation	Syntax	Equivalent Syntax Using \
Backslash (\)	A * x = B	x = A \ B	Not applicable
Slash (/)	x * A = B	x = B / A	x = (A'\B')'

The results of the syntax in the table depend on characteristics of the Galois field array A:

• If A is square and nonsingular, the output x is the unique solution to the linear equation.

• If A is square and singular, the syntax in the table produces an error.

• If A is not square, MATLAB attempts to find a particular solution. If A'*A or A*A' is a singular array, or if A is a matrix, where the rows outnumber the columns, that represents an overdetermined system, the attempt might fail.

Note

An error message does not necessarily indicate that the linear equation has no solution. You might be able to find a solution by rephrasing the problem. For example, gf([1 2; 0 0],3) \ gf([1; 0],3) produces an error but the mathematically equivalent gf([1 2],3) \ gf([1],3) does not. The first syntax fails because gf([1 2; 0 0],3) is a singular square matrix.

Example: Solving Linear Equations

The examples below illustrate how to find particular solutions of linear equations over a Galois field.

m = 4;
A = gf(magic(3),m); % Square nonsingular matrix
Awide=[A, 2*A(:,3)]; % 3-by-4 matrix with redundancy on the right
Atall = Awide'; % 4-by-3 matrix with redundancy at the bottom
B = gf([0:2]',m);
C = [B; 2*B(3)];
D = [B; B(3)+1];
thesolution = A \ B; % Solution of A * x = B
thesolution2 = B' / A; % Solution of x * A = B'
ck1 = all(A * thesolution == B) % Check validity of solutions.
ck2 = all(thesolution2 * A == B')
% Awide * x = B has infinitely many solutions. Find one.
onesolution = Awide \ B;
ck3 = all(Awide * onesolution == B) % Check validity of solution.
% Atall * x = C has a solution.
asolution = Atall \ C;
ck4 = all(Atall * asolution == C) % Check validity of solution.
% Atall * x = D has no solution.
notasolution = Atall \ D;
ck5 = all(Atall * notasolution == D) % It is not a valid solution.

The output from this example indicates that the validity checks are all true (1), except for ck5, which is false (0).

Signal Processing Operations in Galois Fields

Section Overview.  You can perform some signal-processing operations on Galois field arrays, such as filtering, convolution, and the discrete Fourier transform.

This section describes how to perform these operations.

Other information about the corresponding operations for ordinary real vectors is in the Signal Processing Toolbox™ documentation.

Filtering.  To filter a Galois vector, use the filter function. It behaves like the ordinary MATLAB filter function when given exactly three input arguments.

The code and diagram below give the impulse response of a particular filter over GF(2).

m = 1; % Work in GF(2).
b = gf([1 0 0 1 0 1 0 1],m); % Numerator
a = gf([1 0 1 1],m); % Denominator
x = gf([1,zeros(1,19)],m);
y = filter(b,a,x); % Filter x.
figure; stem(y.x); % Create stem plot.
axis([0 20 -.1 1.1])

Convolution.  Communications Toolbox software offers two equivalent ways to convolve a pair of Galois vectors:

• Use the conv function, as described in Multiplication and Division of Polynomials. This works because convolving two vectors is equivalent to multiplying the two polynomials whose coefficients are the entries of the vectors.

• Use the convmtx function to compute the convolution matrix of one of the vectors, and then multiply that matrix by the other vector. This works because convolving two vectors is equivalent to filtering one of the vectors by the other. The equivalence permits the representation of a digital filter as a convolution matrix, which you can then multiply by any Galois vector of appropriate length.

Tip

If you need to convolve large Galois vectors, multiplying by the convolution matrix might be faster than using conv.

Example

Computes the convolution matrix for a vector b in GF(4). Represent the numerator coefficients for a digital filter, and then illustrate the two equivalent ways to convolve b with x over the Galois field.

m = 2; b = gf([1 2 3]',m);
n = 3; x = gf(randi([0 2^m-1],n,1),m);
C = convmtx(b,n); % Compute convolution matrix.
v1 = conv(b,x); % Use conv to convolve b with x
v2 = C*x; % Use C to convolve b with x.

Discrete Fourier Transform.  The discrete Fourier transform is an important tool in digital signal processing. This toolbox offers these tools to help you process discrete Fourier transforms:

• fft, which transforms a Galois vector

• ifft, which inverts the discrete Fourier transform on a Galois vector

• dftmtx, which returns a Galois field array that you can use to perform or invert the discrete Fourier transform on a Galois vector

In all cases, the vector being transformed must be a Galois vector of length 2^m-1 in the field GF(2^m). The following example illustrates the use of these functions. You can check, using the isequal function, that y equals y1, z equals z1, and z equals x.

m = 4;
x = gf(randi([0 2^m-1],2^m-1,1),m); % A vector to transform
alph = gf(2,m);
dm = dftmtx(alph);
idm = dftmtx(1/alph);
y = dm*x; % Transform x using the result of dftmtx.
y1 = fft(x); % Transform x using fft.
z = idm*y; % Recover x using the result of dftmtx(1/alph).
z1 = ifft(y1); % Recover x using ifft.

Tip

If you have many vectors that you want to transform (in the same field), it might be faster to use dftmtx once and matrix multiplication many times, instead of using fft many times.

Polynomials over Galois Fields

Section Overview.  You can use Galois vectors to represent polynomials in an indeterminate quantity x, with coefficients in a Galois field. Form the representation by listing the coefficients of the polynomial in a vector in order of descending powers of x. For example, the vector

gf([2 1 0 3],4)

represents the polynomial Ax³ + 1x² + 0x + (A+1), where

• A is a primitive element in the field GF(2⁴).

• x is the indeterminate quantity in the polynomial.

You can then use such a Galois vector to perform arithmetic with, evaluate, and find roots of polynomials. You can also find minimal polynomials of elements of a Galois field.

Addition and Subtraction of Polynomials.  To add and subtract polynomials, use + and - on equal-length Galois vectors that represent the polynomials. If one polynomial has lower degree than the other, you must pad the shorter vector with zeros at the beginning so the two vectors have the same length. The example below shows how to add a degree-one and a degree-two polynomial.

lin = gf([4 2],3); % A^2 x + A, which is linear in x
linpadded = gf([0 4 2],3); % The same polynomial, zero-padded
quadr = gf([1 4 2],3); % x^2 + A^2 x + A, which is quadratic in x
% Can't do lin + quadr because they have different vector lengths.
sumpoly = [0, lin] + quadr; % Sum of the two polynomials
sumpoly2 = linpadded + quadr; % The same sum

Multiplication and Division of Polynomials.  To multiply and divide polynomials, use conv and deconv on Galois vectors that represent the polynomials. Multiplication and division of polynomials is equivalent to convolution and deconvolution of vectors. The deconv function returns the quotient of the two polynomials as well as the remainder polynomial. Examples are below.

m = 4;
apoly = gf([4 5 3],m); % A^2 x^2 + (A^2 + 1) x + (A + 1)
bpoly = gf([1 1],m); % x + 1
xpoly = gf([1 0],m); % x
% Product is A^2 x^3 + x^2 + (A^2 + A) x + (A + 1).
cpoly = conv(apoly,bpoly);
[a2,remd] = deconv(cpoly,bpoly); % a2==apoly. remd is zero.
[otherpol,remd2] = deconv(cpoly,xpoly); % remd is nonzero.

The multiplication and division operators in Arithmetic in Galois Fields multiply elements or matrices, not polynomials.

Evaluating Polynomials.  To evaluate a polynomial at an element of a Galois field, use polyval. It behaves like the ordinary MATLAB polyval function when given exactly two input arguments. The example below evaluates a polynomial at several elements in a field and checks the results using .^ and .* in the field.

m = 4;
apoly = gf([4 5 3],m); % A^2 x^2 + (A^2 + 1) x + (A + 1)
x0 = gf([0 1 2],m); % Points at which to evaluate the polynomial
y = polyval(apoly,x0)

a = gf(2,m); % Primitive element of the field, corresponding to A.
y2 = a.^2.*x0.^2 + (a.^2+1).*x0 + (a+1) % Check the result.

The output is below.

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

Array elements =

     3     2    10


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

Array elements =

     3     2    10

The first element of y evaluates the polynomial at 0 and, therefore, returns the polynomial's constant term of 3.

Roots of Polynomials.  To find the roots of a polynomial in a Galois field, use the roots function on a Galois vector that represents the polynomial. This function finds roots that are in the same field that the Galois vector is in. The number of times an entry appears in the output vector from roots is exactly its multiplicity as a root of the polynomial.

Note

If the Galois vector is in GF(2^m), the polynomial it represents might have additional roots in some extension field GF((2^m)^k). However, roots does not find those additional roots or indicate their existence.

The examples below find roots of cubic polynomials in GF(8).

p = 3; m = 2;
field = gftuple([-1:p^m-2]',m,p); % List of all elements of GF(9)
% Use default primitive polynomial here.
polynomial = [1 0 1 1]; % 1 + x^2 + x^3
rts =gfroots(polynomial,m,p) % Find roots in exponential format
% Check that each one is actually a root.
for ii = 1:3
   root = rts(ii);
   rootsquared = gfmul(root,root,field);
   rootcubed = gfmul(root,rootsquared,field);
   answer(ii)= gfadd(gfadd(0,rootsquared,field),rootcubed,field);
   % Recall that 1 is really alpha to the zero power.
   % If answer = -Inf, then the variable root represents
   % a root of the polynomial.
end
answer

Roots of Binary Polynomials.  In the special case of a polynomial having binary coefficients, it is also easy to find roots that exist in an extension field. This is because the elements 0 and 1 have the same unambiguous representation in all fields of characteristic two. To find roots of a binary polynomial in an extension field, apply the roots function to a Galois vector in the extension field whose array elements are the binary coefficients of the polynomial.

The example below seeks the roots of a binary polynomial in various fields.

gf2poly = gf([1 1 1],1); % x^2 + x + 1 in GF(2)
noroots = roots(gf2poly); % No roots in the ground field, GF(2)
gf4poly = gf([1 1 1],2); % x^2 + x + 1 in GF(4)
roots4 = roots(gf4poly); % The roots are A and A+1, in GF(4).
gf16poly = gf([1 1 1],4); % x^2 + x + 1 in GF(16)
roots16 = roots(gf16poly); % Roots in GF(16)
checkanswer4 = polyval(gf4poly,roots4); % Zero vector
checkanswer16 = polyval(gf16poly,roots16); % Zero vector

The roots of the polynomial do not exist in GF(2), so noroots is an empty array. However, the roots of the polynomial exist in GF(4) as well as in GF(16), so roots4 and roots16 are nonempty.

Notice that roots4 and roots16 are not equal to each other. They differ in these ways:

• roots4 is a GF(4) array, while roots16 is a GF(16) array. MATLAB keeps track of the underlying field of a Galois field array.

• The array elements in roots4 and roots16 differ because they use representations with respect to different primitive polynomials. For example, 2 (which represents a primitive element) is an element of the vector roots4 because the default primitive polynomial for GF(4) is the same polynomial that gf4poly represents. On the other hand, 2 is not an element of roots16 because the primitive element of GF(16) is not a root of the polynomial that gf16poly represents.

Minimal Polynomials.  The minimal polynomial of an element of GF(2^m) is the smallest degree nonzero binary-coefficient polynomial having that element as a root in GF(2^m). To find the minimal polynomial of an element or a column vector of elements, use the minpol function.

The code below finds that the minimal polynomial of gf(6,4) is D² + D + 1 and then checks that gf(6,4) is indeed among the roots of that polynomial in the field GF(16).

m = 4;
e = gf(6,4);
em = minpol(e) % Find minimal polynomial of e. em is in GF(2).

emr = roots(gf([0 0 1 1 1],m)) % Roots of D^2+D+1 in GF(2^m)

The output is

em = GF(2) array.

Array elements =

     0     0     1     1     1


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

Array elements =

     6
     7

To find out which elements of a Galois field share the same minimal polynomial, use the cosets function.

Manipulating Galois Variables

Section Overview.  This section describes techniques for manipulating Galois variables or for transferring information between Galois field arrays and ordinary MATLAB arrays.

Note

These techniques are particularly relevant if you write MATLAB file functions that process Galois field arrays. For an example of this type of usage, enter edit gf/conv in the Command Window and examine the first several lines of code in the editor window.

Determining Whether a Variable Is a Galois Field Array.  To find out whether a variable is a Galois field array rather than an ordinary MATLAB array, use the isa function. An illustration is below.

mlvar = eye(3);
gfvar = gf(mlvar,3);
no = isa(mlvar,'gf'); % False because mlvar is not a Galois array
yes = isa(gfvar,'gf'); % True because gfvar is a Galois array

Extracting Information from a Galois Field Array.  To extract the array elements, field order, or primitive polynomial from a variable that is a Galois field array, append a suffix to the name of the variable. The table below lists the exact suffixes, which are independent of the name of the variable.

Information	Suffix	Output Value
Array elements	.x	MATLAB array of type uint16 that contains the data values from the Galois field array.
Field order	.m	Integer of type double that indicates that the Galois field array is in GF(2^m).
Primitive polynomial	.prim_poly	Integer of type uint32 that represents the primitive polynomial. The representation is similar to the description in How Integers Correspond to Galois Field Elements.

Note

If the output value is an integer data type and you want to convert it to double for later manipulation, use the double function.

Use Field Extension Suffixes Appended to Galois Field Array Variables

Extract information from Galois field arrays by using field extension suffixes.

Array elements (.x)

Convert a Galois field array to doubles.

a = gf([1,0])

 
a = GF(2) array. 
 
Array elements = 
 
   1   0

b = double(a.x) % a.x is in uint16

b = 1×2

     1     0

Field Order (.m)

Check that e solves its own minimal polynomial. Create empr as a Galois field array in a field order extension field (.m) by using a vector of binary coefficients of a polynomial (emp.x).

e = gf(6,4);                % An element of GF(16)
emp = minpol(e);            % Minimal polynomial is in GF(2)
empr = roots(gf(emp.x,e.m)) % Find roots of emp in GF(16)

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

Primitive polynomial (.prim_poly)

Check that the primitive element gf(2,m) is really a root of the primitive polynomial for the field by confirming the output vector includes 2. Retrieve the primitive polynomial for the field and convert it to a binary vector representation having the appropriate number of bits.

primpoly_int = double(e.prim_poly);
mval = e.m;
primpoly_vect = gf(int2bit(primpoly_int,mval+1)',mval);
containstwo = roots(primpoly_vect)

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

Speed and Nondefault Primitive Polynomials

Primitive Polynomials and Element Representations describes how to represent elements of a Galois field with respect to a primitive polynomial of your choice. This section describes how you can increase the speed of computations involving a Galois field array that uses a primitive polynomial other than the default primitive polynomial. The technique is recommended if you perform many such computations.

The mechanism for increasing the speed is a data file, userGftable.mat, that some computational functions use to avoid performing certain computations repeatedly. To take advantage of this mechanism for your combination of field order (m) and primitive polynomial (prim_poly):

1. Navigate in the MATLAB application to a folder to which you have write permission. You can use either the cd function or the Current Folder feature to navigate.

2. Define m and prim_poly as workspace variables. For example:

   m = 3; prim_poly = 13; % Examples of valid values
   

3. Invoke the gftable function:

   gftable(m,prim_poly); % If you previously defined m and prim_poly
   

The function revises or creates userGftable.mat in your current working folder to include data relating to your combination of field order and primitive polynomial. After you initially invest the time to invoke gftable, subsequent computations using those values of m and prim_poly should be faster.

Note

If you change your current working directory after invoking gftable, you must place userGftable.mat on your MATLAB path to ensure that MATLAB can see it. Do this by using the addpath command to prefix the directory containing userGftable.mat to your MATLAB path. If you have multiple copies of userGftable.mat on your path, use which('userGftable.mat','-all') to find out where they are and which one MATLAB is using.

To see how much gftable improves the speed of your computations, you can surround your computations with the tic and toc functions. See the gftable reference page for an example.

Selected Bibliography for Galois Fields

[1] Blahut, Richard E., Theory and Practice of Error Control Codes, Reading, MA, Addison-Wesley, 1983, p. 105.

[2] Blahut, Richard E. Algebraic Codes for Data Transmission. Cambridge University Press, 2003.

[3] Lang, Serge, Algebra, Third Edition, Reading, MA, Addison-Wesley, 1993.

[4] Lin, Shu, and Daniel J. Costello, Jr., Error Control Coding: Fundamentals and Applications, Englewood Cliffs, NJ, Prentice-Hall, 1983.

[5] van Lint, J. H., Introduction to Coding Theory, New York, Springer-Verlag, 1982.

[6] Wicker, Stephen B. Error Control Systems for Digital Communication and Storage. Upper Saddle River, NJ: Prentice Hall, 1995.

Galois Field Computations for Odd Order, GF(p^m), Fields

A Galois field is an algebraic field having p^m elements, where p is prime and m is a positive integer. This section describes how to work with Galois fields in which p is odd. To work with Galois fields having an even number of elements, see Galois Field Computations.

• Galois Field Terminology

• Representing Elements of Galois Fields

• Default Primitive Polynomials

• Converting and Simplifying Element Formats

• Arithmetic in Galois Fields

• Polynomials over Prime Fields

• Other Galois Field Functions

• Selected Bibliography for Galois Fields

Galois Field Terminology

Throughout this section, p is an odd prime number and m is a positive integer.

Also, this document uses a few terms that are not used consistently in the literature. The definitions adopted here appear in van Lint [5].

• A primitive element of GF(p^m) is a cyclic generator of the group of nonzero elements of GF(p^m). This means that every nonzero element of the field can be expressed as the primitive element raised to some integer power. Primitive elements are called A throughout this section.

• A primitive polynomial for GF(p^m) is the minimal polynomial of some primitive element of GF(p^m). As a consequence, it has degree m and is irreducible.

Representing Elements of Galois Fields

Section Overview.  This section discusses how to represent Galois field elements using this toolbox's exponential format and polynomial format. It also describes a way to list all elements of the Galois field, because some functions use such a list as an input argument. Finally, it discusses the nonuniqueness of representations of Galois field elements.

The elements of GF(p) can be represented using the integers from 0 to p-1.

When m is at least 2, GF(p^m) is called an extension field. Integers alone cannot represent the elements of GF(p^m) in a straightforward way. MATLAB technical computing software uses two main conventions for representing elements of GF(p^m): the exponential format and the polynomial format.

Note

Both the exponential format and the polynomial format are relative to your choice of a particular primitive element A of GF(p^m).

Exponential Format.  This format uses the property that every nonzero element of GF(p^m) can be expressed as A^c for some integer c between 0 and p^m-2. Higher exponents are not needed, because the theory of Galois fields implies that every nonzero element of GF(p^m) satisfies the equation x^q-1 = 1 where q = p^m.

The use of the exponential format is shown in the table below.

Element of GF(pm)	MATLAB Representation of the Element
0	-Inf
A0 = 1	0
A1	1
...	...
Aq-2 where q = pm	q-2

Although -Inf is the standard exponential representation of the zero element, all negative integers are equivalent to -Inf when used as input arguments in exponential format. This equivalence can be useful; for example, see the concise line of code at the end of the section Default Primitive Polynomials.

Note

The equivalence of all negative integers and -Inf as exponential formats means that, for example, -1 does not represent A^-1, the multiplicative inverse of A. Instead, -1 represents the zero element of the field.

Polynomial Format.  The polynomial format uses the property that every element of GF(p^m) can be expressed as a polynomial in A with exponents between 0 and m-1, and coefficients in GF(p). In the polynomial format, the element

A(1) + A(2) A + A(3) A² + ... + A(m) A^m-1

is represented in MATLAB by the vector

[A(1) A(2) A(3) ... A(m)]

Note

The Galois field functions in this toolbox represent a polynomial as a vector that lists the coefficients in order of ascending powers of the variable. This is the opposite of the order that other MATLAB functions use.

List of All Elements of a Galois Field.  Some Galois field functions in this toolbox require an argument that lists all elements of an extension field GF(p^m). This is again relative to a particular primitive element A of GF(p^m). The proper format for the list of elements is that of a matrix having p^m rows, one for each element of the field. The matrix has m columns, one for each coefficient of a power of A in the polynomial format shown in Polynomial Format above. The first row contains only zeros because it corresponds to the zero element in GF(p^m). If k is between 2 and p^m, then the kth row specifies the polynomial format of the element A^k-2.

The minimal polynomial of A aids in the computation of this matrix, because it tells how to express A^m in terms of lower powers of A. For example, the table below lists the elements of GF(3²), where A is a root of the primitive polynomial 2 + 2x + x². This polynomial allows repeated use of the substitution

A² = -2 - 2A = 1 + A

when performing the computations in the middle column of the table.

Elements of GF(9) 

Exponential Format	Polynomial Format	Row of MATLAB Matrix of Elements
A-Inf	0	0 0
A0	1	1 0
A1	A	0 1
A2	1+A	1 1
A3	A + A2 = A + 1 + A = 1 + 2A	1 2
A4	A + 2A2 = A + 2 + 2A = 2	2 0
A5	2A	0 2
A6	2A2 = 2 + 2A	2 2
A7	2A + 2A2 = 2A + 2 + 2A = 2 + A	2 1

Example

An automatic way to generate the matrix whose rows are in the third column of the table above is to use the code below.

p = 3; m = 2;
% Use the primitive polynomial 2 + 2x + x^2 for GF(9).
prim_poly = [2 2 1];
field = gftuple([-1:p^m-2]',prim_poly,p);

The gftuple function is discussed in more detail in Converting and Simplifying Element Formats.

Nonuniqueness of Representations.  A given field has more than one primitive element. If two primitive elements have different minimal polynomials, then the corresponding matrices of elements will have their rows in a different order. If the two primitive elements share the same minimal polynomial, then the matrix of elements of the field is the same.

Note

You can use whatever primitive element you want, as long as you understand how the inputs and outputs of Galois field functions depend on the choice of some primitive polynomial. It is usually best to use the same primitive polynomial throughout a given script or function.

Other ways in which representations of elements are not unique arise from the equations that Galois field elements satisfy. For example, an exponential format of 8 in GF(9) is really the same as an exponential format of 0, because A⁸ = 1 = A⁰ in GF(9). As another example, the substitution mentioned just before the table Elements of GF(9)  shows that the polynomial format [0 0 1] is really the same as the polynomial format [1 1].

Default Primitive Polynomials

This toolbox provides a default primitive polynomial for each extension field. You can retrieve this polynomial using the gfprimdf function. The command

prim_poly = gfprimdf(m,p); % If m and p are already defined

produces the standard row-vector representation of the default minimal polynomial for GF(p^m).

For example, the command below shows that the default primitive polynomial for GF(9) is 2 + x + x², not the polynomial used in List of All Elements of a Galois Field.

poly1=gfprimdf(2,3);

poly1 =

     2     1     1

To generate a list of elements of GF(p^m) using the default primitive polynomial, use the command

field = gftuple([-1:p^m-2]',m,p);

Converting and Simplifying Element Formats

Converting to Simplest Polynomial Format.  The gftuple function produces the simplest polynomial representation of an element of GF(p^m), given either an exponential representation or a polynomial representation of that element. This can be useful for generating the list of elements of GF(p^m) that other functions require.

Using gftuple requires three arguments: one representing an element of GF(p^m), one indicating the primitive polynomial that MATLAB technical computing software should use when computing the output, and the prime p. The table below indicates how gftuple behaves when given the first two arguments in various formats.

Behavior of gftuple Depending on Format of First Two Inputs

How to Specify Element	How to Indicate Primitive Polynomial	What gftuple Produces
Exponential format; c = any integer	Integer m > 1	Polynomial format of Ac, where A is a root of the default primitive polynomial for GF(pm)
Example: tp = gftuple(6,2,3); % c = 6 here
Exponential format; c = any integer	Vector of coefficients of primitive polynomial	Polynomial format of Ac, where A is a root of the given primitive polynomial
Example: polynomial = gfprimdf(2,3); tp = gftuple(6,polynomial,3); % c = 6 here
Polynomial format of any degree	Integer m > 1	Polynomial format of degree < m, using default primitive polynomial for GF(pm) to simplify
Example: tp = gftuple([0 0 0 0 0 0 1],2,3);
Polynomial format of any degree	Vector of coefficients of primitive polynomial	Polynomial format of degree < m, using the given primitive polynomial for GF(pm) to simplify
Example: polynomial = gfprimdf(2,3); tp = gftuple([0 0 0 0 0 0 1],polynomial,3);

The four examples that appear in the table above all produce the same vector tp = [2, 1], but their different inputs to gftuple correspond to the lines of the table. Each example expresses the fact that A⁶ = 2+A, where A is a root of the (default) primitive polynomial 2 + x+ x² for GF(3²).

Example

This example shows how gfconv and gftuple combine to multiply two polynomial-format elements of GF(3⁴). Initially, gfconv multiplies the two polynomials, treating the primitive element as if it were a variable. This produces a high-order polynomial, which gftuple simplifies using the polynomial equation that the primitive element satisfies. The final result is the simplest polynomial format of the product.

p = 3; m = 4;
a = [1 2 0 1]; b = [2 2 1 2];
notsimple = gfconv(a,b,p) % a times b, using high powers of alpha
simple = gftuple(notsimple,m,p) %Highest exponent of alpha is m-1

The output is below.

notsimple =

     2     0     2     0     0     1     2


simple =

     2     1     0     1

Example: Generating a List of Galois Field Elements.  This example applies the conversion functionality to the task of generating a matrix that lists all elements of a Galois field. A matrix that lists all field elements is an input argument in functions such as gfadd and gfmul. The variables field1 and field2 below have the format that such functions expect.

p = 5; % Or any prime number
m = 4; % Or any positive integer
field1 = gftuple([-1:p^m-2]',m,p);

prim_poly = gfprimdf(m,p); % Or any primitive polynomial
% for GF(p^m)
field2 = gftuple([-1:p^m-2]',prim_poly,p);

Converting to Simplest Exponential Format.  The same function gftuple also produces the simplest exponential representation of an element of GF(p^m), given either an exponential representation or a polynomial representation of that element. To retrieve this output, use the syntax

[polyformat, expformat] = gftuple(...)

The input format and the output polyformat are as in the table Behavior of gftuple Depending on Format of First Two Inputs. In addition, the variable expformat contains the simplest exponential format of the element represented in polyformat. It is simplest in the sense that the exponent is either -Inf or a number between 0 and p^m-2.

Example

To recover the exponential format of the element 2 + A that the previous section considered, use the commands below. In this case, polyformat contains redundant information, while expformat contains the desired result.

[polyformat, expformat] = gftuple([2 1],2,3)

polyformat =

     2     1

expformat =

     6

This output appears at first to contradict the information in the table Elements of GF(9) , but in fact it does not. The table uses a different primitive element; two plus that primitive element has the polynomial and exponential formats shown below.

prim_poly = [2 2 1];
[polyformat2, expformat2] = gftuple([2 1],prim_poly,3)

The output below reflects the information in the bottom line of the table.

polyformat2 =

     2     1


expformat2 =

     7

Arithmetic in Galois Fields

Section Overview.  You can add, subtract, multiply, and divide elements of Galois fields using the functions gfadd, gfsub, gfmul, and gfdiv, respectively. Each of these functions has a mode for prime fields and a mode for extension fields.

Arithmetic in Prime Fields.  Arithmetic in GF(p) is the same as arithmetic modulo p. The functions gfadd, gfmul, gfsub, and gfdiv accept two arguments that represent elements of GF(p) as integers between 0 and p-1. The third argument specifies p.

Example: Addition Table for GF(5)

The code below constructs an addition table for GF(5). If a and b are between 0 and 4, then the element gfp_add(a+1,b+1) represents the sum a+b in GF(5). For example, gfp_add(3,5) = 1 because 2+4 is 1 modulo 5.

p = 5;
row = 0:p-1;
table = ones(p,1)*row;
gfp_add = gfadd(table,table',p)

The output for this example follows.

gfp_add =

     0     1     2     3     4
     1     2     3     4     0
     2     3     4     0     1
     3     4     0     1     2
     4     0     1     2     3

Other values of p produce tables for different prime fields GF(p). Replacing gfadd by gfmul, gfsub, or gfdiv produces a table for the corresponding arithmetic operation in GF(p).

Arithmetic in Extension Fields.  The same arithmetic functions can add elements of GF(p^m) when m > 1, but the format of the arguments is more complicated than in the case above. In general, arithmetic in extension fields is more complicated than arithmetic in prime fields; see the works listed in Selected Bibliography for Galois Fields for details about how the arithmetic operations work.

When working in extension fields, the functions gfadd, gfmul, gfsub, and gfdiv use the first two arguments to represent elements of GF(p^m) in exponential format. The third argument, which is required, lists all elements of GF(p^m) as described in List of All Elements of a Galois Field. The result is in exponential format.

Example: Addition Table for GF(9)

The code below constructs an addition table for GF(3²), using exponential formats relative to a root of the default primitive polynomial for GF(9). If a and b are between -1 and 7, then the element gfpm_add(a+2,b+2) represents the sum of A^a and A^b in GF(9). For example, gfpm_add(4,6) = 5 because

A² + A⁴ = A⁵

Using the fourth and sixth rows of the matrix field, you can verify that

A² + A⁴ = (1 + 2A) + (2 + 0A) = 3 + 2A = 0 + 2A = A⁵ modulo 3.

p = 3; m = 2; % Work in GF(3^2).
field = gftuple([-1:p^m-2]',m,p); % Construct list of elements.
row = -1:p^m-2;
table = ones(p^m,1)*row;
gfpm_add = gfadd(table,table',field)

The output is below.

gfpm_add =

  -Inf     0     1     2     3     4     5     6     7
     0     4     7     3     5  -Inf     2     1     6
     1     7     5     0     4     6  -Inf     3     2
     2     3     0     6     1     5     7  -Inf     4
     3     5     4     1     7     2     6     0  -Inf
     4  -Inf     6     5     2     0     3     7     1
     5     2  -Inf     7     6     3     1     4     0
     6     1     3  -Inf     0     7     4     2     5
     7     6     2     4  -Inf     1     0     5     3

Note

If you used a different primitive polynomial, then the tables would look different. This makes sense because the ordering of the rows and columns of the tables was based on that particular choice of primitive polynomial and not on any natural ordering of the elements of GF(9).

Other values of p and m produce tables for different extension fields GF(p^m). Replacing gfadd by gfmul, gfsub, or gfdiv produces a table for the corresponding arithmetic operation in GF(p^m).

Polynomials over Prime Fields

Section Overview.  A polynomial over GF(p) is a polynomial whose coefficients are elements of GF(p). Communications Toolbox software provides functions for

• Changing polynomials in cosmetic ways

• Performing polynomial arithmetic

• Characterizing polynomials as primitive or irreducible

• Finding roots of polynomials in a Galois field

  Note

  The Galois field functions in this toolbox represent a polynomial over GF(p) for odd values of p as a vector that lists the coefficients in order of ascending powers of the variable. This is the opposite of the order that other MATLAB functions use.

Cosmetic Changes of Polynomials.  To display the traditionally formatted polynomial that corresponds to a row vector containing coefficients, use gfpretty. To truncate a polynomial by removing all zero-coefficient terms that have exponents higher than the degree of the polynomial, use gftrunc. For example,

polynom = gftrunc([1 20 394 10 0 0 29 3 0 0])
gfpretty(polynom)

The output is below.

polynom =

     1    20   394    10     0     0    29     3


                                   2       3       6      7
                   1 + 20 X + 394 X  + 10 X  + 29 X  + 3 X

Note

If you do not use a fixed-width font, then the spacing in the display might not look correct.

Polynomial Arithmetic.  The functions gfadd and gfsub add and subtract, respectively, polynomials over GF(p). The gfconv function multiplies polynomials over GF(p). The gfdeconv function divides polynomials in GF(p), producing a quotient polynomial and a remainder polynomial. For example, the commands below show that 2 + x + x² times 1 + x over the field GF(3) is 2 + 2x² + x³.

a = gfconv([2 1 1],[1 1],3)
[quot, remd] = gfdeconv(a,[2 1 1],3)

The output is below.

a =

     2     0     2     1


quot =

     1     1

remd =

     0

The previously discussed functions gfadd and gfsub add and subtract, respectively, polynomials. Because it uses a vector of coefficients to represent a polynomial, MATLAB does not distinguish between adding two polynomials and adding two row vectors elementwise.

Characterization of Polynomials.  Given a polynomial over GF(p), the gfprimck function determines whether it is irreducible and/or primitive. By definition, if it is primitive then it is irreducible; however, the reverse is not necessarily true. The gfprimdf and gfprimfd functions return primitive polynomials.

Given an element of GF(p^m), the gfminpol function computes its minimal polynomial over GF(p).

Example

For example, the code below reflects the irreducibility of all minimal polynomials. However, the minimal polynomial of a nonprimitive element is not a primitive polynomial.

p = 3; m = 4;
% Use default primitive polynomial here.

prim_poly = gfminpol(1,m,p);
ckprim = gfprimck(prim_poly,p);
% ckprim = 1, since prim_poly represents a primitive polynomial.

notprimpoly = gfminpol(5,m,p);
cknotprim = gfprimck(notprimpoly,p);
% cknotprim = 0 (irreducible but not primitive)
% since alpha^5 is not a primitive element when p = 3.

ckreducible = gfprimck([0 1 1],p);
% ckreducible = -1 since the polynomial is reducible.

Roots of Polynomials.  Given a polynomial over GF(p), the gfroots function finds the roots of the polynomial in a suitable extension field GF(p^m). There are two ways to tell MATLAB the degree m of the extension field GF(p^m), as shown in the following table.

Formats for Second Argument of gfroots 

Second Argument	Represents
A positive integer	m as in GF(pm). MATLAB uses the default primitive polynomial in its computations.
A row vector	A primitive polynomial for GF(pm). Here m is the degree of this primitive polynomial.

Example: Roots of a Polynomial in GF(9)

The code below finds roots of the polynomial 1 + x² + x³ in GF(9) and then checks that they are indeed roots. The exponential format of elements of GF(9) is used throughout.

p = 3; m = 2;
field = gftuple([-1:p^m-2]',m,p); % List of all elements of GF(9)
% Use default primitive polynomial here.
polynomial = [1 0 1 1]; % 1 + x^2 + x^3
rts =gfroots(polynomial,m,p) % Find roots in exponential format
% Check that each one is actually a root.
for ii = 1:3
   root = rts(ii);
   rootsquared = gfmul(root,root,field);
   rootcubed = gfmul(root,rootsquared,field);
   answer(ii)= gfadd(gfadd(0,rootsquared,field),rootcubed,field);
   % Recall that 1 is really alpha to the zero power.
   % If answer = -Inf, then the variable root represents
   % a root of the polynomial.
end
answer

The output shows that A⁰ (which equals 1), A⁵, and A⁷ are roots.

roots =

     0
     5
     7


answer =

  -Inf  -Inf  -Inf

See the reference page for gfroots to see how gfroots can also provide you with the polynomial formats of the roots and the list of all elements of the field.

Other Galois Field Functions

See the online reference pages for information about these other Galois field functions in Communications Toolbox software:

• gfcosets, which produces cyclotomic cosets

• gffilter, which filters data using GF(p) polynomials

• gfprimfd, which finds primitive polynomials

• gfrank, which computes the rank of a matrix over GF(p)

• gfrepcov, which converts one binary polynomial representation to another

Selected Bibliography for Galois Fields

[1] Blahut, Richard E., Theory and Practice of Error Control Codes, Reading, MA, Addison-Wesley, 1983, p. 105.

[2] Lang, Serge, Algebra, Third Edition, Reading, MA, Addison-Wesley, 1993.

[3] Lin, Shu, and Daniel J. Costello, Jr., Error Control Coding: Fundamentals and Applications, Englewood Cliffs, NJ, Prentice-Hall, 1983.

[4] van Lint, J. H., Introduction to Coding Theory, New York, Springer-Verlag, 1982.