UNB ECE4253 Digital Communications
Department of Electrical and Computer Engineering - University of New Brunswick, Fredericton, NB, Canada

Code Generation with Galois Fields

On this page, the properties of Galois fields GF(2m) based on primitive polynomials of degree m are used to create a generating matrix for cyclic block codes.


A Galois field GF(23) = GF(8) specified by the primitive polynomial P(x)=(1011) of degree 3 serves to define a generator matrix G(x) to create a set of (7,4) codewords for single-bit error correction (D=3). Other observations about the elements in this GF(8) are also made.


An Integer Finite Field of the form {an}

The finite set of integers {0, 1, 2, 3, ... ,P-1} modulus P is a field only for prime P. In particular, the elements of the set must include all integers less than P simply to satisfy closure under addition.

The finite set of integers S={0, a1, a2, a3, ... ,an} modulus P is a field only for certain values of a that are called the roots of P. Only the roots of P will ensure that all the integers less than P are included in the set S.

For example, if a=8 and P=11, then 10 non-zero elements {80, 81, 82,..., 89} modulus 11 can be generated using MATLAB as:

>> S = mod(8.^(0:9),11)
 S=  
     1     8     9     6     4    10     3     2     5     7      

Therefore, 8 is a root of 11 and this sequence of elements (describing a cyclic group) repeats periodically for larger values of n. This result is essentially a maximum length sequence for the integer P.

These concepts may now be carried into the development of a Galois Field GF(23) having 8 elements.


A GF(23) Field of the form {an}

A Galois field GF(23) = GF(8) specified by the primitive polynomial P(x) of degree 3 is a set of eight 3-bit elements including 0.

For a primitive polynomial P(x), the set {0, a0,a1,a2,...,an} modulus P(x) is a field, provided that a is a root of P(x).

For the polynomial P(x) = x3 + x + 1 = (1011), the value a is a root if P(a) = 0.

Successive non-zero terms in an modulus P(x) are derived in the table below.


If P(a)=0 (because a is a root) then a3 + a + 1 = 0, and a3 = a + 1.
This result can be applied to simplify terms in a3 as they appear below.


a0 = a0 = 1 = 1 = 1 = 001 = 1
a1 = a0 × a = (1) × a = a = a = 010 = 2
a2 = a1 × a = (a) × a = a2 = a2 = 100 = 4
a3 = a2 × a = (a2) × a = a3 = a+1 = 011 = 3
a4 = a3 × a = (a+1) × a = a2+a = a2+a = 110 = 6
a5 = a4 × a = (a2+a) × a = a3+a2 = a2+a+1 = 111 = 7
a6 = a5 × a = (a2+a+1) × a = a3+a2+a = a2+1 = 101 = 5

a7 = a6 × a = (a2+1) × a = a3+a = 1 = 001 = 1

Each of these terms in an can be found directly as the remainder after the division xn / P(x).
Click on one of the 3-bit values above to confirm the division result using the GF(2) calculator tool.

Using the table values it may now be confirmed that a is a root of P(x), since:

P(a) = a3 + a + 1 = (011) + (010) + (001) = 0


Check Matrix for (7,4) Code

A systematic (3 × 7) check matrix (H) can be constructed directly from the terms {an}. Each column from left-to-right is a 3-bit value from a6 to a0.

[ 5 7 6 3 4 2 1 ]
a6 . . . . . a0 1 1 1 0 1 0 0 0 1 1 1 0 1 0 1 1 0 1 0 0 1

The number of columns (7) corresponds to the 7-bit codeword size. The number of rows (3) equals the degree of P(x). The rightmost columns form a (3 × 3) identity matrix.

When a single bit error occurs, the resulting 3-bit syndrome is found vertically in the corresponding column of the check matrix. For example, an error in bit position a1 gives syndrome = (010) = 2. In practice, it is necessary to identify a bad bit given only the syndrome. To that end, the check matrix column may be identified by finding the index n such that an = syndrome. This result is called the discrete logarithm because if an=syndrome, then n =log(syndrome). Specifically, given the syndrome (010) = 2, then log(2) = 1 and the error is at column a1.


Generator Matrix for (7,4) Code

This (4 x 7) generator matrix (G) is readily obtained from the above Check matrix.

[ 1 0 0 0 1 0 1 ] = 5 [ 0 1 0 0 1 1 1 ] = 7 [ 0 0 1 0 1 1 0 ] = 6 [ 0 0 0 1 0 1 1 ] = 3
Note that this matrix incorporates a (4 x 4) identity matrix and three columns corresponding to the ordered 3-bit terms as shown highlighted. The identiy matrix ensures that the output codewords form a systematic block code since the four input bits will be seen directly in each 7-bit codeword, followed by the three check bits.
Comparison with a Linear Feedback Shift Register

In a linear feedback shift register (LFSR) having three flip flops, there are 23 = 8 possible circuit states including the all-zero state. The behavior of the circuit is determined by a polynomial P(x) that defines the feedback taps in the shift register. As the circuit is clocked, successive states of the flip flops describe a maximum length sequence only if P(x) is a primitive polynomial. The maximum length sequence has 23-1 = 7 states, not including the all-zero state.

Consider a LFSR designed with the same polynomial P(x)=(1011) as used for the above GF(8), then the 3-bit circuit states follow the identical sequence of 3-bit states as found in the derivation of this GF(8) shown from a7 to a0:

1 5 7 6 3 4 2 1

(See the Galois LFSR Circuit)

The circuit configuation produces a maximum length sequence from a primitive P(x). In comparison, the powers of {an} for a=2 describe the successive powers of 2 that result as a shift register is clocked.



Conclusion

A Galois field GF(8) has been used to define a (d=3) single error correcting code based on a primitive polynomial P(x).

The GF(8) is defined as the set {0, a1, a2, a3, ... ,an} where a is a root of P(x).

Non-zero elements of the field GF(8) expressed as consecutive terms in {an} serve to define a check matrix and the corresponding generator matrix for (7,4) systematic codewords.

The same terms {an} provide the information necessary to accomplish single-bit error correction by relating each an directly to a specific single bit error.

The same terms {an} emerge from a linear feedback shift register with three flip flops and feedback connections determined by P(x).

The same terms {an} are found as the remainder after the division xn  /   P(x).


2024-07-14 18:06:33 ADT
Last Updated: 2016-02-06
Richard Tervo [ tervo@unb.ca ] Back to the course homepage...