UNB ECE4253 Digital Communications
Department of Electrical and Computer Engineering - University of New Brunswick, Fredericton, NB, Canada

Polynomial Code Generator Tool

Given a generator polynomial G(x) of degree 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 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.

Polynomial G(x)

G(x) = x4+x+1

(10011)

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

The systematic 15-bit codewords will have 11 data bits and 4 parity bits.

Sample (15,11) Codewords  (cyclic)

When codewords are cyclic the circular shift of a valid codeword produces another valid codeword.

For example, rotating the 15-bit codeword (01) left by one bit gives the codeword (02):

(01) = 000000000010011
(02) = 000000000100110

DATA = 00 : 000000000000000
DATA = 01 : 000000000010011
DATA = 02 : 000000000100110
DATA = 03 : 000000000110101
DATA = 04 : 000000001001100
DATA = 05 : 000000001011111
DATA = 06 : 000000001101010
DATA = 07 : 000000001111001
DATA = 08 : 000000010001011
DATA = 09 : 000000010011000
DATA = 10 : 000000010101101
DATA = 11 : 000000010111110
DATA = 12 : 000000011000111
DATA = 13 : 000000011010100
DATA = 14 : 000000011100001
DATA = 15 : 000000011110010
DATA = 16 : 000000100000101
DATA = 17 : 000000100010110
DATA = 18 : 000000100100011
DATA = 19 : 000000100110000
DATA = 20 : 000000101001001
DATA = 21 : 000000101011010
DATA = 22 : 000000101101111
DATA = 23 : 000000101111100
DATA = 24 : 000000110001110
DATA = 25 : 000000110011101
DATA = 26 : 000000110101000
DATA = 27 : 000000110111011
DATA = 28 : 000000111000010
DATA = 29 : 000000111010001
DATA = 30 : 000000111100100
DATA = 31 : 000000111110111
← less | more →

When codewords are linear, any linear combination of codewords is another codeword. For example, the 15-bit codeword (01) is the sum (02)+(03)

(02) = 000000000100110
(03) = 000000000110101
(01) = 000000000010011

Distance Analysis

This sample subset of 15-bit codewords has a minimum distance D=3, correcting up to t=1 error.

 0001020304050607080910111213141516171819202122232425262728293031
00--03030403060405040305060504040503040403040507060506040704050508
0103--040306030504030406050405050404030304050406070605070405040805
020304--0304050306050604030405050404030304070604050407050605080405
03040303--05040603060503040504040503040403060705040704060508050504
0403060405--030304050404050403050604050706030404030405050805060407
050603050403--0403040505040304060505040607040303040504080506050704
06040503060304--03040505040506040307060405040303040508040504070506
0705040603040303--050404050605030406070504030404030805050407040605
080403050605040405--0303040306040505060407040505080304040304050706
09030406050405050403--04030603050406050704050408050403030405040607
1005060403040505040304--030405030604070506050804050403030407060405
110605030405040405040303--0504060307040605080505040304040306070504
12050404050403050603060405--03030404050508050604070405070603040403
1304050504030406050603050403--040305040805060507040504060704030304
140405050405060403040503060304--0305080405040705060706040504030304
15050404050605030405040603040303--08050504070406050607050403040403
1603040403040507060506040704050508--030304030604050403050605040405
170403030405040607060507040504080503--0403060305040304060504050504
18040303040706040504070506050804050304--03040503060506040304050504
1903040403060705040704060508050504040303--050406030605030405040405
200405070603040403040505080506040703060405--0303040504040504030506
21050406070403030405040805060507040603050403--04030405050403040605
2207060405040303040508040504070506040503060304--030405050405060403
230607050403040403080505040704060505040603040303--0504040506050304
24050604070405050803040403040507060403050605040405--03030403060405
2506050704050408050403030405040607030406050405050403--040306030504
260407050605080405040303040706040505060403040505040304--0304050306
27070406050805050403040403060705040605030405040405040303--05040603
2804050508050604070405070603040403050404050403050603060405--030304
290504080506050704050406070403030404050504030406050603050403--0403
30050804050407050607060405040303040405050405060403040503060304--03
3108050504070406050607050403040403050404050605030405040603040303--

This sampling of 32 codewords is not necessarily indicative of the error control performance of all 211 = 2048 possible codewords.

To determine the minimum distance between any two codewords in a linear block code, it is sufficient to check every codeword once against the all-zero 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 remaining codewords could be easily checked in this way.


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

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

Discussion Codewords Generator Format
G = [Ik|P]
G = [P|Ik]
MATLAB Matrices

Examples

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

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

  3. (15,11) Hamming Code (D=3) single bit error correction

  4. (15,10) Extended Hamming Code (D=4) single bit error correction

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

  6. (15,5) BCH Code (D=7) triple bit error correction (notes)

  7. (23,12,7) Binary Golay Code (D=7) triple bit error correction

  8. (35,27) Fire Code specialized 3-bit burst error correction

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

2024-05-16 03:20:29 ADT
Last Updated: 2015-02-06 		Richard Tervo [ tervo@unb.ca ] Back to the course homepage...