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) = x8+x6+x5+x3+x+1

(101101011)

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

The systematic 35-bit codewords will have 27 data bits and 8 parity bits.

Sample (35,27) Codewords  (cyclic)

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

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

(01) = 00000000000000000000000000101101011
(02) = 00000000000000000000000001011010110

DATA = 00 : 00000000000000000000000000000000000
DATA = 01 : 00000000000000000000000000101101011
DATA = 02 : 00000000000000000000000001011010110
DATA = 03 : 00000000000000000000000001110111101
DATA = 04 : 00000000000000000000000010011000111
DATA = 05 : 00000000000000000000000010110101100
DATA = 06 : 00000000000000000000000011000010001
DATA = 07 : 00000000000000000000000011101111010
DATA = 08 : 00000000000000000000000100011100101
DATA = 09 : 00000000000000000000000100110001110
DATA = 10 : 00000000000000000000000101000110011
DATA = 11 : 00000000000000000000000101101011000
DATA = 12 : 00000000000000000000000110000100010
DATA = 13 : 00000000000000000000000110101001001
DATA = 14 : 00000000000000000000000111011110100
DATA = 15 : 00000000000000000000000111110011111
DATA = 16 : 00000000000000000000001000010100001
DATA = 17 : 00000000000000000000001000111001010
DATA = 18 : 00000000000000000000001001001110111
DATA = 19 : 00000000000000000000001001100011100
DATA = 20 : 00000000000000000000001010001100110
DATA = 21 : 00000000000000000000001010100001101
DATA = 22 : 00000000000000000000001011010110000
DATA = 23 : 00000000000000000000001011111011011
DATA = 24 : 00000000000000000000001100001000100
DATA = 25 : 00000000000000000000001100100101111
DATA = 26 : 00000000000000000000001101010010010
DATA = 27 : 00000000000000000000001101111111001
DATA = 28 : 00000000000000000000001110010000011
DATA = 29 : 00000000000000000000001110111101000
DATA = 30 : 00000000000000000000001111001010101
DATA = 31 : 00000000000000000000001111100111110
← less | more →

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

(02) = 00000000000000000000000001011010110
(03) = 00000000000000000000000001110111101
(01) = 00000000000000000000000000101101011

Distance Analysis

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

 0001020304050607080910111213141516171819202122232425262728293031
00--06060806060408060606060406081004060806060606100408061006080810
0106--080606060804060606060604100806040608060610060804100608061008
020608--0604080606060606060810040608060406061006060610040808100608
03080606--08040606060606061008060406080604100606061006080410080806
0406060408--060608040608100606060606060610040608060608081004080610
050606080406--0806060410080606060606061006060406080806100808041006
06040806060608--06081004060606060606100606080604060810060806100408
0708040606080606--100806040606060610060606060806041008080610060804
080606060604060810--0606080606040804080610060808100406080606060610
09060606060604100806--08060606080408041006080610080604060806061006
1006060606081004060608--060408060606100408081006080806040606100606
110606060610080604080606--0804060610060804100808060608060410060606
12040608100606060606060408--06060806080810040806100606061004060806
1306041008060606060606080406--080608061008080410060606100606040608
140810040606060606040806060608--0608100608061004080610060608060406
15100806040606060608040606080606--10080806100608041006060606080604
1604060806060606100408061006080810--060608060604080606060604060810
170604060806061006080410060806100806--0806060608040606060606041008
18080604060610060606100408081006080608--06040806060606060608100406
1906080604100606061006080410080806080606--080406060606060610080604
200606061004060806060808100408061006060408--0606080406081006060606
21060610060604060808061008080410060606080406--08060604100806060606
2206100606080604060810060806100408040806060608--060810040606060606
231006060606080604100808061006080408040606080606--1008060406060606
24040806100608081004060806060606100606060604060810--06060806060408
2508041006080610080604060806061006060606060604100806--080606060804
260610040808100608080604060610060606060606081004060608--0604080606
27100608041008080606080604100606060606060610080604080606--08040606
2806080810040806100606061004060806040608100606060606060408--060608
290806100808041006060610060604060806041008060606060606080406--0806
30081006080610040806100606080604060810040606060606040806060608--06
3110080806100608041006060606080604100806040606060608040606080606--

This sampling of 32 codewords is not necessarily indicative of the error control performance of all 227 = 134217728 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. A much larger sampling of 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 08:51:19 ADT
Last Updated: 2015-02-06 		Richard Tervo [ tervo@unb.ca ] Back to the course homepage...