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) = x16+x12+x5+1

(10001000000100001)

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

The systematic 52-bit codewords will have 36 data bits and 16 parity bits.

Sample (52,36) Codewords  (not cyclic)

DATA = 00 : 0000000000000000000000000000000000000000000000000000
DATA = 01 : 0000000000000000000000000000000000010001000000100001
DATA = 02 : 0000000000000000000000000000000000100010000001000010
DATA = 03 : 0000000000000000000000000000000000110011000001100011
DATA = 04 : 0000000000000000000000000000000001000100000010000100
DATA = 05 : 0000000000000000000000000000000001010101000010100101
DATA = 06 : 0000000000000000000000000000000001100110000011000110
DATA = 07 : 0000000000000000000000000000000001110111000011100111
DATA = 08 : 0000000000000000000000000000000010001000000100001000
DATA = 09 : 0000000000000000000000000000000010011001000100101001
DATA = 10 : 0000000000000000000000000000000010101010000101001010
DATA = 11 : 0000000000000000000000000000000010111011000101101011
DATA = 12 : 0000000000000000000000000000000011001100000110001100
DATA = 13 : 0000000000000000000000000000000011011101000110101101
DATA = 14 : 0000000000000000000000000000000011101110000111001110
DATA = 15 : 0000000000000000000000000000000011111111000111101111
more →

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

(02) = 0000000000000000000000000000000000100010000001000010
(03) = 0000000000000000000000000000000000110011000001100011
(01) = 0000000000000000000000000000000000010001000000100001

Distance Analysis

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

 00010203040506070809101112131415
00--040408040808120408081208121216
0104--0804080412080804120812081612
020408--04081204080812040812160812
03080404--120808041208080416121208
0404080812--0404080812121604080812
050804120804--08041208161208041208
06081204080408--041216081208120408
0712080804080404--1612120812080804
080408081208121216--04040804080812
09080412081208161204--080408041208
1008120408121608120408--0408120408
111208080416121208080404--12080804
12081212160408081204080812--040408
1312081612080412080804120804--0804
141216081208120408081204080408--04
15161212081208080412080804080404--

This sampling of 16 codewords is not necessarily indicative of the error control performance of all 236 = 68719476736 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-04-29 16:25:34 ADT
Last Updated: 2015-02-06 		Richard Tervo [ tervo@unb.ca ] Back to the course homepage...