ECE4253 Digital Communications  
Department of Electrical and Computer Engineering  University of New Brunswick, Fredericton, NB, Canada  
The mathematics of error control can be based on either a matrix or a polynomial approach. This page shows how any polynomial G(x) may be used to define an equivalent check matrix and generator matrix. Conversely, it is not always possible to find a polynomial G(x) corresponding to an arbitary generator matrix.
The generator polynomial G(x) can be up to degree p=36, and the input data size is limited to k=36 bits.
G(x) = x^{3}+x+1
(1011)
This polynomial G(x) is degree 3, giving a 3bit parity field. (See factors of G(x))
The systematic 7bit codewords will have 4 data bits and 3 parity bits.
For 4bit input data i the corresponding 7bit codeword is given by C = iG.
The steps involved in using G(x) to create a generator matrix (G) for a systematic code are shown below.
STEP ONE  Creating a nonsystematic generating matrix G
A suitable (4 × 7) generator matrix can be constructed by writing the generator polynomial 1011 shifted right one bit for each successive row. There are 4 rows corresponding to the choice of 4 input data bits. The 4 rows are labeled (0 to 3) for reference. While this is a valid generator polynomial, it does not generate a systematic code.
0:  1  0  1  1  0  0  0 
1:  0  1  0  1  1  0  0 
2:  0  0  1  0  1  1  0 
3:  0  0  0  1  0  1  1 
Each row in this generator matrix is also a valid 7bit codeword, being divisible by P(x).
STEP TWO  Creating a systematic generating matrix G = [I_{k}P]
A systematic generator matrix G is distinguished by having a (k × k) identity matrix, often on the lefthand side as G = [I_{k}P] such that each codeword includes (k) data bits followed by (nk) parity bits. Alternatively, the format G = [PI_{k}] places the identity matrix on the righthand side.
To adjust the above generator matrix for a (7,4) systematic code, the leftmost columns will be manipulated to form a (4 × 4) identity matrix. To this end, begin with the top row and add to it selected rows until the first 4bits describe the top row of an identity matrix. The new Row 0 is formed by the sum of rows (3,2,0) refering to the labels shown above. Go down the matrix for each row until the complete generator matrix is formed.
1  0  0  0  1  0  1  = ROW(3+2+0) 
0  1  0  0  1  1  1  = ROW(3+1) 
0  0  1  0  1  1  0  = ROW(2) 
0  0  0  1  0  1  1  = ROW(3) 
Each row in the generator matrix is a valid 7bit codeword. In a linear code, the sum of codewords is another valid codeword.
When codewords are cyclic the circular shift of a valid codeword produces another valid codeword.
For example, rotating the 7bit codeword (01) left by one bit gives the codeword (02): (02) = 0010110 
DATA = 00 :  0  0  0  0  0  0  0 
DATA = 01 :  0  0  0  1  0  1  1 
DATA = 02 :  0  0  1  0  1  1  0 
DATA = 03 :  0  0  1  1  1  0  1 
DATA = 04 :  0  1  0  0  1  1  1 
DATA = 05 :  0  1  0  1  1  0  0 
DATA = 06 :  0  1  1  0  0  0  1 
DATA = 07 :  0  1  1  1  0  1  0 
DATA = 08 :  1  0  0  0  1  0  1 
DATA = 09 :  1  0  0  1  1  1  0 
DATA = 10 :  1  0  1  0  0  1  1 
DATA = 11 :  1  0  1  1  0  0  0 
DATA = 12 :  1  1  0  0  0  1  0 
DATA = 13 :  1  1  0  1  0  0  1 
DATA = 14 :  1  1  1  0  1  0  0 
DATA = 15 :  1  1  1  1  1  1  1 
When codewords are linear, any linear combination of codewords is another codeword. For example, the 7bit codeword (01) is the sum (02)+(03) (03) = 0011101 (01) = 0001011 
This complete set of 7bit codewords has a minimum distance D=3, correcting up to t=1 error.
00  01  02  03  04  05  06  07  08  09  10  11  12  13  14  15  
00    03  03  04  04  03  03  04  03  04  04  03  03  04  04  07 
01  03    04  03  03  04  04  03  04  03  03  04  04  03  07  04 
02  03  04    03  03  04  04  03  04  03  03  04  04  07  03  04 
03  04  03  03    04  03  03  04  03  04  04  03  07  04  04  03 
04  04  03  03  04    03  03  04  03  04  04  07  03  04  04  03 
05  03  04  04  03  03    04  03  04  03  07  04  04  03  03  04 
06  03  04  04  03  03  04    03  04  07  03  04  04  03  03  04 
07  04  03  03  04  04  03  03    07  04  04  03  03  04  04  03 
08  03  04  04  03  03  04  04  07    03  03  04  04  03  03  04 
09  04  03  03  04  04  03  07  04  03    04  03  03  04  04  03 
10  04  03  03  04  04  07  03  04  03  04    03  03  04  04  03 
11  03  04  04  03  07  04  04  03  04  03  03    04  03  03  04 
12  03  04  04  07  03  04  04  03  04  03  03  04    03  03  04 
13  04  03  07  04  04  03  03  04  03  04  04  03  03    04  03 
14  04  07  03  04  04  03  03  04  03  04  04  03  03  04    03 
15  07  04  04  03  03  04  04  03  04  03  03  04  04  03  03   
To determine the minimum distance between any two codewords in a linear block code, it is sufficient to check every codeword once against the allzero codeword. In other words, the Hamming distance of a code may be determined from the distances in row 00 only. Moreover, the distance from a given codeword to zero is found by the sum of the 1's in the codeword. 
The check matrix for a systematic code can be found directly from the generator matrix. The rightmost columns form a (3 × 3) identity matrix while the remaining columns can be identified in corresponding rows in the generator matrix.
1  1  1  0  1  0  0 
0  1  1  1  0  1  0 
1  1  0  1  0  0  1 
Each row in the check matrix is a valid 7bit codeword only for a cyclic code.

(8,7) Simple Parity Bit (D=2) no error correction
(7,4) Hamming Code (D=3) single bit error correction
(15,11) Hamming Code (D=3) single bit error correction
(15,10) Extended Hamming Code (D=4) single bit error correction
(31,21) BCH Code (D=5) double bit error correction (notes)
(15,5) BCH Code (D=7) triple bit error correction (notes)
(23,12,7) Binary Golay Code (D=7) triple bit error correction
(35,27) Fire Code specialized 3bit burst error correction
16bit CRC (CCITT) commonly used for error detection (notes)
20240918 19:26:18 ADT
Last Updated: 20150206 
Richard Tervo [ tervo@unb.ca ]  Back to the course homepage... 