Department of Electrical and Computer Engineering - University of New Brunswick, Fredericton, NB, Canada
| |
|
|
EE4253 Digital Communications
Department of Electrical and Computer Engineering - University of New Brunswick, Fredericton, NB, Canada |
| |
For an (n,k) block code, a generator matrix maps k-bit information words to n-bit codewords, while a check matrix serves to identify valid or errored n-bit codewords. These matrices both derive from a suitably chosen generator polynomial G(x). On this page, the properties of Galois fields GF(2m) based on primitive polynomials of degree m are used to create G(x) for simple (D=3) block codes.
The Galois field GF(23) specified by the primitive polynomial P(x) of degree 3 serves to define a generator polynomial G(x) for a new set of error control codewords for single-bit error correction (D=3). Valid codewords C(x) will be integer multiples of G(x), such that an errored codeword is expected to give a non-zero remainder when divided by G(x). Error correction is possible if that remainder is unique and can be used to identify the error.
A primitive polynomial P(x) of degree 3 can be used to define a Galois field called GF(23) or GF(8) being a set of eight 3-bit values. Every single bit error of the form E(x)=xN (for N < 8) leads to a distinctive remainder when divided by P(x).
Given (1011), describing the primitive P(x) = x3 + x + 1, then the remainders below correspond uniquely to each error E(x) = xN as shown:
Given (1011), describing P(x) = x3 + x + 1, then if a is a root, P(a) = 0 and From the table below, a is a root because P(a) = a3 + a + 1 = 011 + 010 + 001 = 0, therefore: a3 + a + 1 = 0 a3 = a + 1 This result simplies the table below showing successive terms in aN.
| 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 | |
Click on one of the 3-bit values above to confirm the division result using the GF(2) calculator tool.
For single bit error correction (D=3), the generating polynomial is given directly from these results and G(x) = P(x).
This (3 × 7) check matrix (H) identifies good 7-bit codewords (C) when the product HCT is zero. The columns in this matrix are the 3-bit values from above, reading down.
[ 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 remainder terms for each aN correspond to the seven columns in this matrix.The number of rows (3) equals the degree of P(x). The rightmost columns form a (3 × 3) identity matrix.
Given a 4-bit information word (i), this (4 x 7) generator matrix (G) defines a corresponding 7-bit codeword (C) as C = iG
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. Observe that every row in this matrix is itself a valid 7-bit codeword.[ 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
Given a 4-bit information word (i), this (4 x 7) generator matrix (G) defines a corresponding 7-bit codeword (C) as C = iG
Note that this matrix incorporates the generator polynomial bits 1011 in each row and is easily constructed. Using this matrix, the four input bits would be not be seen directly in each 7-bit codeword; rather, each codeword is the product of the information bits with the defining polynomial. Observe that every row in this matrix is itself a valid 7-bit codeword.[ 1 0 1 1 0 0 0 ] [ 0 1 0 1 1 0 0 ] [ 0 0 1 0 1 1 0 ] [ 0 0 0 1 0 1 1 ]
This matrix differs from the other form by a sequence of row operations. Any such manipulations simply change the specific mapping from input bits to valid codewords accomplished by the generator matrix. A different check matrix is also required.
The same codewords are found in the table below as generated directly by the product operation.
The defining polynomial for the error control code can be used directly to generate systematic codewords.
Consider G(x) = x3 + x + 1 of degree 3. The corresponding codewords would have 3 parity bits. Given a message M(x) of any length, the required parity bits can be found by appending 3 zeros to M(x) and dividing by P(x). The parity bits are the remainder of [M(x) x3] / G(x)].
For example, for the message (001), append 3 zeros to obtain (001000).
Division by G(x) leaves remainder (011). (Check the math)
The final codeword is (001011), an exact multiple of G(x). (Check the math)
0: 0 × 1011 = 0000000 1: 1 × 1011 = 0001011 2: 10 × 1011 = 0010110 3: 11 × 1011 = 0011101 4: 100 × 1011 = 0101100 5: 101 × 1011 = 0100111 6: 110 × 1011 = 0111010 7: 111 × 1011 = 0110001 8: 1000 × 1011 = 1011000 9: 1001 × 1011 = 1010011 10: 1010 × 1011 = 1001110 11: 1011 × 1011 = 1000101 12: 1100 × 1011 = 1110100 13: 1101 × 1011 = 1111111 14: 1110 × 1011 = 1100010 15: 1111 × 1011 = 1101001
In an error control application, valid codewords are carefully chosen to have zero remainder when divided by some generator polynomial G(x). Any non-zero remainder signals an error. This remainder is called the syndrome. A primitive polynomial P(x) has been used to define a generator polynomial G(x) which leads to a check matrix and generator matrix for codewords having minimum Hamming distance (D=3). The check matrix can be used to correct single bit errors by returning a unique non-zero syndrome for a given error. The check matrix can be used to detect two bit errors by returning a non-zero syndrome for the error.
| ||
|
Fri May 24 06:30:55 ADT 2013
Last Updated: 06 FEB 2010 |
Richard Tervo [ tervo@unb.ca ] | Back to the course homepage... |
| ||