| Communications Toolbox | |
Arithmetic in Galois Fields
You can perform arithmetic operations on Galois arrays by using the same MATLAB operators that work on ordinary integer arrays. The table below lists the available arithmetic operations as well as the operators that perform them. Whenever you operate on a pair of Galois arrays, both arrays must be in the same Galois field.
| Note For multiplication and division of polynomials over a Galois field, see Addition and Subtraction of Polynomials. |
Examples of these operations are in the sections that follow:
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. 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 addone = addtb(2,:); % Assign 2nd row to the Galois vector addone.
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 A2+A plus the element A+1 equals the element A2+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 -, would be 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. 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 A2+1, and 1+(A2+1) in GF(16) is A2. Furthermore, the integer that represents the polynomial expression A2 is 4.
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. 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 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.
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. Notice that 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. 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 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 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
expformat
| | Primitive Polynomials and Element Representations | Logical Operations in Galois Fields | |