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

(110101)

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

The systematic 15-bit codewords will have 10 data bits and 5 parity bits.

Sample (15,10) 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) = 000000000110101
(02) = 000000001101010

DATA = 00 : 000000000000000
DATA = 01 : 000000000110101
DATA = 02 : 000000001011111
DATA = 03 : 000000001101010
DATA = 04 : 000000010001011
DATA = 05 : 000000010111110
DATA = 06 : 000000011010100
DATA = 07 : 000000011100001
DATA = 08 : 000000100010110
DATA = 09 : 000000100100011
DATA = 10 : 000000101001001
DATA = 11 : 000000101111100
DATA = 12 : 000000110011101
DATA = 13 : 000000110101000
DATA = 14 : 000000111000010
DATA = 15 : 000000111110111
DATA = 16 : 000001000011001
DATA = 17 : 000001000101100
DATA = 18 : 000001001000110
DATA = 19 : 000001001110011
DATA = 20 : 000001010010010
DATA = 21 : 000001010100111
DATA = 22 : 000001011001101
DATA = 23 : 000001011111000
DATA = 24 : 000001100001111
DATA = 25 : 000001100111010
DATA = 26 : 000001101010000
DATA = 27 : 000001101100101
DATA = 28 : 000001110000100
DATA = 29 : 000001110110001
DATA = 30 : 000001111011011
DATA = 31 : 000001111101110
← 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) = 000000001011111
(03) = 000000001101010
(01) = 000000000110101

Distance Analysis

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

 0001020304050607080910111213141516171819202122232425262728293031
00--04060404060404040404060604040804040406040606060606040604060808
0104--040606040404040406040406080404040604060406060606060406040808
020604--0404040406040604040408060404060404060604060406060608080406
03040604--04040604060404040804040606040404060606040604060608080604
0404060404--040604060404080404040604060606040404060406080806060406
050604040404--0406040608040404060406040606040406040604080806060604
06040404060604--04040806040406040406060406040604040808040604060606
0704040604040604--080404060604040406060604060404040808060406040606
080404040606040408--0406040406040406060406040608080404040604060606
09040406040406080404--04060604040406060604060408080404060406040606
1004060404040806040604--040404040604060606080804060406040406060406
110604040408040406040604--0404060406040606080806040604040406060604
12060404080404040604060404--04060404060808060604060406060604040406
1304060804040406040604040404--040606040808060606040604060604040604
140408060404060404040404060604--0408080406040606060606040604060404
15080404060604040404040604040604--08080604060406060606060406040404
1604040406040606060606040604060808--040604040604040404040606040408
170404060406040606060606040604080804--0406060404040404060404060804
18040604040606040604060606080804060604--04040404060406040404080604
1906040404060606040604060608080604040604--040406040604040408040406
200406060604040406040608080606040604060404--0406040604040804040406
21060406060404060406040808060606040604040404--04060406080404040604
2206060406040604040808040604060606040404060604--040408060404060404
230606060406040404080806040604060604040604040604--0804040606040404
24060604060406080804040406040606060404040606040408--04060404060404
2506060604060408080404060406040606040406040406080404--040606040404
260406060608080406040604040606040604060404040806040604--0404040406
27060406060808060406040404060606040604040408040406040604--04040604
2804060808060604060406060604040406060404080404040604060404--040604
290604080806060604060406060404060404060804040406040604040404--0406
30080804060406060606060406040604040408060404060404040404060604--04
3108080604060406060606060406040404080404060604040404040604040604--

This sampling of 32 codewords is not necessarily indicative of the error control performance of all 210 = 1024 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 06:41:07 ADT
Last Updated: 2015-02-06 		Richard Tervo [ tervo@unb.ca ] Back to the course homepage...