|
|
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(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. |
| 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 | |
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 |
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 a2 gives syndrome = (100) = 4. 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 (100) = 4, then log(4) = 2 and the error is at column a2.
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 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.[ 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 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
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.
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-04-23 09:50:58 ADT
Last Updated: 2016-02-06 |
Richard Tervo [ tervo@unb.ca ] | Back to the course homepage... |
