Learn more about Communications Toolbox

Arithmetic in Galois Fields

On this page…
Section Overview Example: Addition and Subtraction Example: Multiplication Example: Division Example: Exponentiation Example: Elementwise Logarithm

Section Overview

You can perform arithmetic operations on Galois arrays by using familiar MATLAB operators, listed in the table below. Whenever you operate on a pair of Galois 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.

Back to Top

Example: Addition and Subtraction

The code below adds two Galois 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 array from an ordinary MATLAB array. The Galois 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.

Back to Top

Example: Multiplication

The example below multiplies individual elements in a Galois 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

Back to Top

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

Back to Top

Example: Exponentiation

The examples below illustrate how to compute integer powers of a Galois array. To perform matrix exponentiation on a Galois array, you must use a square Galois 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

Back to Top

Example: Elementwise Logarithm

The code below computes the logarithm of the elements of a Galois 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.

Back to Top

Representing Elements of Galois Fields

Logical Operations in Galois Fields

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