ECE4253 Digital Communications  
Department of Electrical and Computer Engineering  University of New Brunswick, Fredericton, NB, Canada  
On this page, the properties of Galois fields GF(2^{m}) based on primitive polynomials of degree m are used to create a generating matrix for cyclic block codes.
A Galois field GF(2^{3}) = 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 singlebit error correction (D=3). Other observations about the elements in this GF(8) are also made.
An Integer Finite Field of the form {a^{n}}
The finite set of integers {0, 1, 2, 3, ... ,P1} 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, a^{1}, a^{2}, a^{3}, ... ,a^{n}} 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 nonzero elements {8^{0}, 8^{1}, 8^{2},..., 8^{9}} 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(2^{3}) having 8 elements.
A GF(2^{3}) Field of the form {a^{n}}
A Galois field GF(2^{3}) = GF(8) specified by the primitive polynomial P(x) of degree 3 is a set of eight 3bit elements including 0.
For a primitive polynomial P(x), the set {0, a^{0},a^{1},a^{2},...,a^{n}} modulus P(x) is a field, provided that a is a root of P(x).
For the polynomial P(x) = x^{3} + x + 1 = (1011), the value a is a root if P(a) = 0.
Successive nonzero terms in a^{n} modulus P(x) are derived in the table below.
If P(a)=0 (because a is a root) then a^{3} + a + 1 = 0, and a^{3} = a + 1. 
a^{0}  = a^{0}  = 1  = 1  = 1  = 001  = 1  
a^{1}  = a^{0} × a  = (1) × a  = a  = a  = 010  = 2  
a^{2}  = a^{1} × a  = (a) × a  = a^{2}  = a^{2}  = 100  = 4  
a^{3}  = a^{2} × a  = (a^{2}) × a  = a^{3}  = a+1  = 011  = 3  
a^{4}  = a^{3} × a  = (a+1) × a  = a^{2}+a  = a^{2}+a  = 110  = 6  
a^{5}  = a^{4} × a  = (a^{2}+a) × a  = a^{3}+a^{2}  = a^{2}+a+1  = 111  = 7  
a^{6}  = a^{5} × a  = (a^{2}+a+1) × a  = a^{3}+a^{2}+a  = a^{2}+1  = 101  = 5  
a^{7}  = a^{6} × a  = (a^{2}+1) × a  = a^{3}+a  = 1  = 001  = 1 
Using the table values it may now be confirmed that a is a root of P(x), since: P(a) = a^{3} + a + 1 = (011) + (010) + (001) = 0 
A systematic (3 × 7) check matrix (H) can be constructed directly from the terms {a^{n}}. Each column from lefttoright is a 3bit value from a^{6} to a^{0}.
[ 5 7 6 3 4 2 1 ]
a^{6} . . . . . a^{0} 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 7bit 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 3bit syndrome is found vertically in the corresponding column of the check matrix. For example, an error in bit position a^{1} 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 a^{n} = syndrome. This result is called the discrete logarithm because if a^{n}=syndrome, then n =log(syndrome). Specifically, given the syndrome (010) = 2, then log(2) = 1 and the error is at column a^{1}.
This (4 x 7) generator matrix (G) is readily obtained from the above Check matrix.
Note that this matrix incorporates a (4 x 4) identity matrix and three columns corresponding to the ordered 3bit 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 7bit codeword, followed by the three check bits.[ 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
In a linear feedback shift register (LFSR) having three flip flops, there are 2^{3} = 8 possible circuit states including the allzero 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 2^{3}1 = 7 states, not including the allzero state.
Consider a LFSR designed with the same polynomial P(x)=(1011) as used for the above GF(8), then the 3bit circuit states follow the identical sequence of 3bit states as found in the derivation of this GF(8) shown from a^{7} to a^{0}:
1 5 7 6 3 4 2 1
The circuit configuation produces a maximum length sequence from a primitive P(x). In comparison, the powers of {a^{n}} for a=2 describe the successive powers of 2 that result as a shift register is clocked.
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, a^{1}, a^{2}, a^{3}, ... ,a^{n}} where a is a root of P(x).
Nonzero elements of the field GF(8) expressed as consecutive terms in {a^{n}} serve to define a check matrix and the corresponding generator matrix for (7,4) systematic codewords.
The same terms {a^{n}} provide the information necessary to accomplish singlebit error correction by relating each a^{n} directly to a specific single bit error.
The same terms {a^{n}} emerge from a linear feedback shift register with three flip flops and feedback connections determined by P(x).
The same terms {a^{n}} are found as the remainder after the division x^{n} / P(x).

20240714 18:06:33 ADT
Last Updated: 20160206 
Richard Tervo [ tervo@unb.ca ]  Back to the course homepage... 