dot
UNB EE4253 Digital Communications
Department of Electrical and Computer Engineering - University of New Brunswick, Fredericton, NB, Canada
dot
Generator Polynomial Tool

Given a generator polynomial G(x) of order p and a binary input data size k, this online tool creates and displays a generator matrix G, a check matrix H, and a demonstration of the resulting systematic codewords for this (n,k) code, where n=p+k. The nature of G(x) and the value of k will determine the utility of the codewords in a error control scheme.

The generator polynomial G(x) can be up to order p=36, and the input data size is limited to k=36 bits.


Polynomial G(x):

G(x) = x3+x+1

1011

This polynomial G(x) is of order 3, giving a 3-bit parity field. (See factors of G(x))

The systematic 7-bit codewords will have 4 data bits followed by 3 parity bits.


Generator Matrix (G) for (7, 4) code
G is a (4 × 7) matrix

For 4-bit input data i the corresponding 7-bit codeword is given by C = iG.

The steps involved in using G(x) to create a generator matrix for a systematic code are shown below.

STEP ONE

A generator matrix can be constructed as shown here 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 rows here are labeled for reference. While this is a valid generator polynomial, it does not generate a systematic code.

0: 1011000
1: 0101100
2: 0010110
3: 0001011

STEP TWO

To adjust the generator matrix for a 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 4-bits describe the top row of an identity matrix. The new Row 0 is formed by the sum of rows (0,2,3) refering to the labels shown above. Go down the matrix for each row until the complete generator matrix is formed.

1000101 = ROW(0+2+3)
0100111 = ROW(1+3)
0010110 = ROW(2)
0001011 = ROW(3)

Each row in the generator matrix is also a valid 7-bit codeword.


Complete Set of (7, 4) Codewords
DATA = 00 : 0000000
DATA = 01 : 0001011
DATA = 02 : 0010110
DATA = 03 : 0011101
DATA = 04 : 0100111
DATA = 05 : 0101100
DATA = 06 : 0110001
DATA = 07 : 0111010
DATA = 08 : 1000101
DATA = 09 : 1001110
DATA = 10 : 1010011
DATA = 11 : 1011000
DATA = 12 : 1100010
DATA = 13 : 1101001
DATA = 14 : 1110100
DATA = 15 : 1111111


Distance Analysis

This complete set of 7-bit codewords has a minimum distance D=3, correcting up to t=1 error.

 00010203040506070809101112131415
00--030304040303040304040303040407
0103--0403030404030403030404030704
020304--03030404030403030404070304
03040303--040303040304040307040403
0404030304--0303040304040703040403
050304040303--04030403070404030304
06030404030304--030407030404030304
0704030304040303--0704040303040403
080304040303040407--03030404030304
09040303040403070403--040303040403
1004030304040703040304--0303040403
110304040307040403040303--04030304
12030404070304040304030304--030304
1304030704040303040304040303--0403
140407030404030304030404030304--03
15070404030304040304030304040303--

All 16 available codewords have been verifed in this table.


Check Matrix (H) for (7, 4) code
H is a (3 × 7) matrix

The check matrix for a systematic code can be found directly from the generator matrix. In this example, the rightmost columns form a (3 × 3) identity matrix while the remaining columns can be identified in corresponding rows in the generator matrix.

1110100
0111010
1101001


Each row in the check matrix is also a valid 7-bit codeword.


Specify a new polynomial or a different number of data bits.

Model M20J GENERATOR POLYNOMIAL TOOL
Data Bits k =   G(x):

Discussion  |  Generator Matrix  |  Codewords  |  Check Matrix


Examples

1. (8,7) Simple Parity Bit (D=2) no error correction

2. (4,7) Hamming Code (D=3) single bit error correction

3. (31,25) BCH Code (D=5) double bit error correction (notes)

4. 16-bit CRC (CCITT) commonly used for error detection (notes)

dot
Sun Feb 12 04:18:19 AST 2012
Last Updated: 18 FEB 2010 		Richard Tervo [ tervo@unb.ca ] Back to the course homepage...
dot