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) = x11+x10+x6+x5+x4+x2+1

(110001110101)

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

The systematic 23-bit codewords will have 12 data bits and 11 parity bits.


Sample (23,12) Codewords  (cyclic)

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

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

(01) = 00000000000110001110101
(02) = 00000000001100011101010

DATA = 00 : 00000000000000000000000
DATA = 01 : 00000000000110001110101
DATA = 02 : 00000000001010010011111
DATA = 03 : 00000000001100011101010
DATA = 04 : 00000000010010101001011
DATA = 05 : 00000000010100100111110
DATA = 06 : 00000000011000111010100
DATA = 07 : 00000000011110110100001
DATA = 08 : 00000000100011011100011
DATA = 09 : 00000000100101010010110
DATA = 10 : 00000000101001001111100
DATA = 11 : 00000000101111000001001
DATA = 12 : 00000000110001110101000
DATA = 13 : 00000000110111111011101
DATA = 14 : 00000000111011100110111
DATA = 15 : 00000000111101101000010
DATA = 16 : 00000001000000110110011
DATA = 17 : 00000001000110111000110
DATA = 18 : 00000001001010100101100
DATA = 19 : 00000001001100101011001
DATA = 20 : 00000001010010011111000
DATA = 21 : 00000001010100010001101
DATA = 22 : 00000001011000001100111
DATA = 23 : 00000001011110000010010
DATA = 24 : 00000001100011101010000
DATA = 25 : 00000001100101100100101
DATA = 26 : 00000001101001111001111
DATA = 27 : 00000001101111110111010
DATA = 28 : 00000001110001000011011
DATA = 29 : 00000001110111001101110
DATA = 30 : 00000001111011010000100
DATA = 31 : 00000001111101011110001
DATA = 32 : 00000010000001101100110
DATA = 33 : 00000010000111100010011
DATA = 34 : 00000010001011111111001
DATA = 35 : 00000010001101110001100
DATA = 36 : 00000010010011000101101
DATA = 37 : 00000010010101001011000
DATA = 38 : 00000010011001010110010
DATA = 39 : 00000010011111011000111
DATA = 40 : 00000010100010110000101
DATA = 41 : 00000010100100111110000
DATA = 42 : 00000010101000100011010
DATA = 43 : 00000010101110101101111
DATA = 44 : 00000010110000011001110
DATA = 45 : 00000010110110010111011
DATA = 46 : 00000010111010001010001
DATA = 47 : 00000010111100000100100
DATA = 48 : 00000011000001011010101
DATA = 49 : 00000011000111010100000
DATA = 50 : 00000011001011001001010
DATA = 51 : 00000011001101000111111
DATA = 52 : 00000011010011110011110
DATA = 53 : 00000011010101111101011
DATA = 54 : 00000011011001100000001
DATA = 55 : 00000011011111101110100
DATA = 56 : 00000011100010000110110
DATA = 57 : 00000011100100001000011
DATA = 58 : 00000011101000010101001
DATA = 59 : 00000011101110011011100
DATA = 60 : 00000011110000101111101
DATA = 61 : 00000011110110100001000
DATA = 62 : 00000011111010111100010
DATA = 63 : 00000011111100110010111
← less

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

(02) = 00000000001010010011111
(03) = 00000000001100011101010
(01) = 00000000000110001110101


Distance Analysis

This sample subset of 23-bit codewords has a minimum distance D=7, correcting up to t=3 errors.

 00010203040506070809101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263
00--070807070807080807080707121108070807080807080707081112081108110708110808070811070807120811080708070811111207120807081111081112
0107--0708080708070708070812070811080708070708070808071211110811080807081107081108080712071108070807081108121112070708110808111211
020807--07070807080807080711080712070807080807080711120708081108111108070808110807071207080807081108110807071211120811080711121108
03070807--080708070708070808111207080708070708070812110807110811080811080711080708120708070708110811080708120712111108070812110811
0407080708--0708070712110808070807080708070708070808110811070811120807081107081108081108070708071211120712080708111108111208070811
050807080707--07081207081107080708070807080807080711081108080712110708110808070811110807080807120712111207070811080811121107081108
06070807080807--071108071208070807080708070708070808110811111207080811080711080708080708110712070807121112081108071112110808110807
0708070807070807--0811120707080708070807080807080711081108121108071108070808110807070811081207080712071211110807081211081111080708
080807080707121108--07080707080708070811120811081107080708080708070708071208110807070811080807081108070811110811120807081111120712
09070807081207081107--070808070807080712111108110808070807070807080807120711080708080708110708110807081108081112110708110812111207
1008070807110807120807--0707080708111207080811081107080708080708070712070808070811110807080811080708110807111211080811080707121112
110708070808111207070807--08070807121108071108110808070807070807081207080707081108081108071108070811080708121108111108070812071211
12071211080807080707080708--070807081108110708111208070807070807080811080707080712080708110708110811081112080708111112071208070811
1312070811070807080807080707--0708110811080807121107080708080708071108070808071207070811080807081108111211070811081211120707081108
141108071208070807070807080807--07081108111112070808070807070807080807081107120708081108071108070811121108081108070712111208110807
15081112070708070808070807070807--110811081211080707080708080708070708110812070807110807080811080712110811110807081207121111080708
1607080708080708070708111208110811--0708070708070808070807071211080807081111120712080708111108111207081108080708110708071208110807
170807080707080708080712111108110807--07080807080707080708120708110708110812111207070811080811121108070811070811080807120711080708
18070807080807080711120708081108110807--070708070808070807110807120811080707121112081108071112110811080708081108070712070808070811
1908070807070807081211080711081108070807--0807080707080708081112071108070812071211110807081211081108110807110807081207080707081108
200807080707080708081108110708111207080708--07080707121108080708071112071208070811110811120807081108070811070811080811080707080712
21070807080807080711081108080712110807080707--070812070811070807081211120707081108081112110708110807081108080708111108070808071207
2208070807070807080811081111120708070807080807--0711080712080708070712111208110807111211080811080708110807110807080807081107120708
230708070808070807110811081211080708070807070807--08111207070807081207121111080708121108111108070811080708081108070708110812070807
24070811120811081107080708080708070807080707121108--070807070807080807081111081112080708111112071207080712081108070708110808070811
2508071211110811080807080707080708070807081207081107--0708080708070708110808111211070811081211120708071207110807080807081107081108
261112070808110811070807080807080708070807110807120807--07070807080811080711121108081108070712111207120708080708111108070808110807
27121108071108110808070807070807080708070808111207070807--080708071108070812110811110807081207121112070807070811080811080711080708
2808110811070811120807080707080708071211080807080707080708--0708071108111208070811111207120807081108110807070807120807081107081108
291108110808071211070807080807080712070811070807080807080707--07080811121107081108121112070708110811080708080712070708110808070811
30081108111112070808070807070807081108071208070807070807080807--071112110808110807071211120811080708070811071207080811080711080708
3111081108121108070708070808070807081112070708070808070807070807--1211081111080708120712111108070807081108120708071108070808110807
320708110808070811070807120811080708070811111207120807081111081112--07080707080708080708070712110807080708080708070708111208110811
33080708110708110808071207110807080708110812111207070811080811121107--070808070807070807081207081108070807070807080807121111081108
3411080708081108070712070808070811081108070712111208110807111211080807--0707080708080708071108071207080708080708071112070808110811
350811080711080708120708070708110811080708120712111108070812110811070807--08070807070807080811120708070807070807081211080711081108
36080708110708110808110807070807121112071208070811110811120807081107080708--070807071211080807080708070807070807080811081107081112
3707081108080708111108070808071207121112070708110808111211070811080807080707--0708120708110708070807080708080708071108110808071211
380811080711080708080708110712070807121112081108071112110808110807070807080807--07110807120807080708070807070807080811081111120708
39110807080811080707081108120708071207121111080708121108111108070808070807070807--081112070708070807080708080708071108110812110807
4007080712081108070708110808070811080708111108111208070811111207120807080707121108--0708070708070807081112081108110708070808070807
410807120711080708080708110708110807081108081112110708110812111207070807081207081107--07080807080708071211110811080807080707080708
42071207080807081111080708081108070811080711121108081108070712111208070807110807120807--070708070811120708081108110708070808070807
4312070807070811080811080711080708110807081211081111080708120712110708070808111207070807--0807080712110807110811080807080707080708
440811080707080712080708110708110811081112080708111112071208070811071211080807080707080708--07080708110811070811120807080707080708
45110807080807120707081108080708110811121107081108121112070708110812070811070807080807080707--070811081108080712110708070808070807
4608070811071207080811080711080708111211080811080707121112081108071108071208070807070807080807--0708110811111207080807080707080708
470708110812070807110807080811080712110811110807081207121111080708081112070708070808070807070807--11081108121108070708070808070807
48080708111112071208070811110811120708110808070811070807120811080707080708080708070708111208110811--070807070807080807080707121108
4907081108121112070708110808111211080708110708110808071207110807080807080707080708080712111108110807--0708080708070708070812070811
500811080707121112081108071112110811080708081108070712070808070811070807080807080711120708081108110807--07070807080807080711080712
51110807081207121111080708121108110811080711080708120708070708110808070807070807081211080711081108070807--080708070708070808111207
5211120712080708111108111208070811080708110708110808110807070807120807080707080708081108110708111207080708--0708070712110808070807
531211120707081108081112110708110807081108080708111108070808071207070807080807080711081108080712110807080707--07081207081107080708
54071211120811080711121108081108070811080711080708080708110712070808070807070807080811081111120708070807080807--071108071208070807
5512071211110807081211081111080708110807080811080707081108120708070708070808070807110811081211080708070807070807--0811120707080708
560807081111081112080708111112071207080712081108070708110808070811070811120811081107080708080708070807080707121108--07080707080708
57070811080811121107081108121112070807120711080708080708110708110808071211110811080807080707080708070807081207081107--070808070807
5808110807111211080811080707121112071207080807081111080708081108071112070808110811070807080807080708070807110807120807--0707080708
591108070812110811110807081207121112070807070811080811080711080708121108071108110808070807070807080708070808111207070807--08070807
60110811120807081111120712080708110811080707080712080708110708110808110811070811120807080707080708071211080807080707080708--070807
6108111211070811081211120707081108110807080807120707081108080708111108110808071211070807080807080712070811070807080807080707--0708
621112110808110807071211120811080708070811071207080811080711080708081108111112070808070807070807081108071208070807070807080807--07
63121108111108070812071211110807080708110812070807110807080811080711081108121108070708070808070807081112070708070808070807070807--

This sampling of 64 codewords is not necessarily indicative of the error control performance of all 212 = 4096 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-10-31 20:43:04 ADT
Last Updated: 2015-02-06
Richard Tervo [ tervo@unb.ca ] Back to the course homepage...