Main Content

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

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

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

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

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