Working with Galois Fields

This example illustrates how to work with Galois fields.

Galois fields are used in error-control coding, where a Galois field is an algebraic field with a finite number of members. A Galois field that has 2m members is denoted by GF(2m), where m is an integer between 1 and 16 in this example.

Creating Galois Field Arrays

You create Galois field arrays using the GF function. To create the element 3 in the Galois field 22, you can use the following command:

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

Using Galois Field Arrays

You can now use A as if it were a built-in MATLAB® data type. For example, here is how you can add two elements in a Galois field together:

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

Arithmetic in Galois Fields

Note that 3 + 1 = 2 in this Galois field. The rules for arithmetic operations are different for Galois field elements compared to integers. To see some of the differences between Galois field arithmetic and integer arithmetic, first look at an addition table 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

You can define such a table in MATLAB with the following commands:

A = ones(4,1)*[0 1 2 3];
B = [0 1 2 3]'*ones(1,4);
Table = A+B
Table =

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

Similarly, create an addition table for the field GF(2^2) with the following commands:

A = gf(ones(4,1)*[0 1 2 3],2);
B = gf([0 1 2 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

Using MATLAB® Functions with Galois Arrays

Many other MATLAB functions will work with Galois arrays. To see this, first create a couple of arrays.

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

Now you can multiply two polynomials.

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 also find roots of a polynomial. (Note that they match the original values in 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

Hamming Code Example

The most important application of Galois field theory is in error-control coding. The rest of this example uses a simple error-control code, a Hamming code. An error-control code works by adding redundancy to information bits. For example, a (7,4) Hamming code maps 4 bits of information to 7-bit codewords. It does this by multiplying the 4-bit codeword by a 4 x 7 matrix. You can obtain this matrix with the HAMMGEN function:

[H,G] = hammgen(3)
H =

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


G =

     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

H is the parity-check matrix and G is the generator matrix. To encode the information bits [0 1 0 0], multiply the information bits [0 1 0 0] by the generator matrix G:

A = gf([0 1 0 0],1)
Code = A*G
 
A = GF(2) array. 
 
Array elements = 
 
           0           1           0           0

 
Code = GF(2) array. 
 
Array elements = 
 
  Columns 1 through 6

           0           1           1           0           1           0

  Column 7

           0

Suppose somewhere along transmission, an error is introduced into this codeword. (Note that a Hamming code can correct only 1 error.)

Code(1) = 1   % Place a 1 where there should be a 0.
 
Code = GF(2) array. 
 
Array elements = 
 
  Columns 1 through 6

           1           1           1           0           1           0

  Column 7

           0

You can use the parity-check matrix H to determine where the error occurred, by multiplying the codeword by H:

H*Code'
 
ans = GF(2) array. 
 
Array elements = 
 
           1
           0
           0

To find the error, look at the parity-check matrix H. The column in H that matches [1 0 0 ]' is the location of the error. Looking at H, you can see that the first column is [1 0 0]'. This means that the first element of the vector Code contains the error.

H
H =

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

Was this topic helpful?