Working with Galois Fields

This example shows how to work with Galois fields. This example also shows the effects of using with Hamming codes and Galois field theory for error-control coding.

A Galois field is an algebraic field with a finite number of members. A Galois field that has $2^{\mathit{m}}$ members is denoted by $\mathrm{GF}\left(2^{\mathit{m}}\right)$, where m is an integer in the range [1, 16].

Create Galois Field Arrays

Create Galois field arrays using the gf function. For example, create the element 3 in the Galois field $\mathrm{GF}\left(2^2\right)$.

A = gf(3,2)

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

Use Galois Field Arrays

You can now use A as if it is a built-in MATLAB® data type. For example, add two different elements in a Galois field.

A = gf(3,2);
B = gf(1,2);
C = A+B

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

Demonstrate Arithmetic in Galois Fields

The rules for arithmetic operations are different for Galois field elements compared to integers. For example, in $\mathrm{GF}\left(2^2\right)$, 3 + 1 = 2. This table shows some of the differences between Galois field arithmetic and integer arithmetic for integers 0 through 3.

+__0__1__2__3

0| 0 1 2 3

1| 1 2 3 4

2| 2 3 4 5

3| 3 4 5 6

Define such a table in MATLAB®.

A = ones(4,1)*(0:3);
B = (0:3)'*ones(1,4);
A+B

ans = 4×4

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

Similarly, create an addition table for the Galois field $\mathrm{GF}\left(2^2\right)$.

A = gf(ones(4,1)*(0:3),2);
B = gf((0:3)'*ones(1,4),2);
A+B

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

Use MATLAB Functions with Galois Arrays

For a list of MATLAB® functions that work with Galois arrays, see Galois Computations on the gf function reference page. For example, create two different Galois arrays, and then use the conv function to multiply the two polynomials.

A = gf([1 33],8);
B = gf([1 55],8);

C = conv(A,B)

 
C = GF(2^8) array. Primitive polynomial = D^8+D^4+D^3+D^2+1 (285 decimal)
 
Array elements = 
 
     1    22   153

You can use the roots function to find the roots of a polynomial. For example, find the roots of polynomial C. The results show that the roots match the original values in polynomials A and B.

roots(C)

 
ans = GF(2^8) array. Primitive polynomial = D^8+D^4+D^3+D^2+1 (285 decimal)
 
Array elements = 
 
   33
   55

Use Hamming Codes and Galois Theory

This section shows how to use a simple Hamming code and Galois field theory for error-control coding. An error-control code adds redundancy to information bits. For example, a (7,4) Hamming code maps 4 bits of information to 7-bit codewords by multiplying the 4 information bits by a 4-by-7 generation matrix in Galois field $\mathrm{GF}\left(2\right)$. Use the hammgen function to obtain this matrix.

[paritymat,genmat] = hammgen(3)

paritymat = 3×7

     1     0     0     1     0     1     1
     0     1     0     1     1     1     0
     0     0     1     0     1     1     1

genmat = 4×7

     1     1     0     1     0     0     0
     0     1     1     0     1     0     0
     1     1     1     0     0     1     0
     1     0     1     0     0     0     1

The output paritymat is the parity-check matrix, and the output genmat is the generator matrix. To encode the information bits [0 1 0 0], multiply the bits by the generator matrix genmat in Galois field $\mathrm{GF}\left(2\right)$.

A = gf([0 1 0 0],1)

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

code = A*genmat

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

For this example, suppose that somewhere along transmission, an error is introduced in this codeword. The Hamming code used in this example can correct up to 1 bit error. Insert an error in the transmission by changing the first bit from 0 to 1.

code(1) = 1

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

Use the parity-check matrix to determine where the error occurred, by multiplying the erroneous codeword by the parity-check matrix.

paritymat*code'

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

Find the error, by inspecting the parity-check matrix, paritymat. The column in paritymat that matches [1 0 0]' is the location of the error. In this example, the first column is [1 0 0]', so the first element of the vector code contains the error.

paritymat

paritymat = 3×7

     1     0     0     1     0     1     1
     0     1     0     1     1     1     0
     0     0     1     0     1     1     1