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

(1011)

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

The systematic 7-bit codewords will have 4 data bits and 3 parity bits.

# Generator Matrix (G) for (7, 4) Code

G is a (4 × 7) matrix

For 4-bit input data i the corresponding 7-bit codeword is given by C = iG.

The steps involved in using G(x) to create a generator matrix (G) for a systematic code are shown below.

STEP ONE  -  Creating a non-systematic generating matrix G

A suitable (4 × 7) generator matrix can be constructed by writing the generator polynomial 1011 shifted right one bit for each successive row. There are 4 rows corresponding to the choice of 4 input data bits. The 4 rows are labeled (0 to 3) for reference. While this is a valid generator polynomial, it does not generate a systematic code.

 0: 1 0 1 1 0 0 0 1: 0 1 0 1 1 0 0 2: 0 0 1 0 1 1 0 3: 0 0 0 1 0 1 1

Each row in this generator matrix is also a valid 7-bit codeword, being divisible by P(x).

STEP TWO  -  Creating a systematic generating matrix   G = [Ik|P]

A systematic generator matrix G is distinguished by having a (k × k) identity matrix, often on the lefthand side as G = [Ik|P] such that each codeword includes (k) data bits followed by (n-k) parity bits. Alternatively, the format G = [P|Ik] places the identity matrix on the righthand side.

To adjust the above generator matrix for a (7,4) systematic code, the leftmost columns will be manipulated to form a (4 × 4) identity matrix. To this end, begin with the top row and add to it selected rows until the first 4-bits describe the top row of an identity matrix. The new Row 0 is formed by the sum of rows (3,2,0) refering to the labels shown above. Go down the matrix for each row until the complete generator matrix is formed.

 1 0 0 0 1 0 1 = ROW(3+2+0) 0 1 0 0 1 1 1 = ROW(3+1) 0 0 1 0 1 1 0 = ROW(2) 0 0 0 1 0 1 1 = ROW(3)

Each row in the generator matrix is a valid 7-bit codeword. In a linear code, the sum of codewords is another valid codeword.

# Complete Set of (7,4) Codewords  (cyclic)

 When codewords are cyclic the circular shift of a valid codeword produces another valid codeword. For example, rotating the 7-bit codeword (01) left by one bit gives the codeword (02): (01) = 0001011(02) = 0010110

 DATA = 00 : 0 0 0 0 0 0 0 DATA = 01 : 0 0 0 1 0 1 1 DATA = 02 : 0 0 1 0 1 1 0 DATA = 03 : 0 0 1 1 1 0 1 DATA = 04 : 0 1 0 0 1 1 1 DATA = 05 : 0 1 0 1 1 0 0 DATA = 06 : 0 1 1 0 0 0 1 DATA = 07 : 0 1 1 1 0 1 0 DATA = 08 : 1 0 0 0 1 0 1 DATA = 09 : 1 0 0 1 1 1 0 DATA = 10 : 1 0 1 0 0 1 1 DATA = 11 : 1 0 1 1 0 0 0 DATA = 12 : 1 1 0 0 0 1 0 DATA = 13 : 1 1 0 1 0 0 1 DATA = 14 : 1 1 1 0 1 0 0 DATA = 15 : 1 1 1 1 1 1 1

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

# Distance Analysis

This complete set of 7-bit codewords has a minimum distance D=3, correcting up to t=1 error.

 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 00 -- 03 03 04 04 03 03 04 03 04 04 03 03 04 04 07 01 03 -- 04 03 03 04 04 03 04 03 03 04 04 03 07 04 02 03 04 -- 03 03 04 04 03 04 03 03 04 04 07 03 04 03 04 03 03 -- 04 03 03 04 03 04 04 03 07 04 04 03 04 04 03 03 04 -- 03 03 04 03 04 04 07 03 04 04 03 05 03 04 04 03 03 -- 04 03 04 03 07 04 04 03 03 04 06 03 04 04 03 03 04 -- 03 04 07 03 04 04 03 03 04 07 04 03 03 04 04 03 03 -- 07 04 04 03 03 04 04 03 08 03 04 04 03 03 04 04 07 -- 03 03 04 04 03 03 04 09 04 03 03 04 04 03 07 04 03 -- 04 03 03 04 04 03 10 04 03 03 04 04 07 03 04 03 04 -- 03 03 04 04 03 11 03 04 04 03 07 04 04 03 04 03 03 -- 04 03 03 04 12 03 04 04 07 03 04 04 03 04 03 03 04 -- 03 03 04 13 04 03 07 04 04 03 03 04 03 04 04 03 03 -- 04 03 14 04 07 03 04 04 03 03 04 03 04 04 03 03 04 -- 03 15 07 04 04 03 03 04 04 03 04 03 03 04 04 03 03 --

All 16 available codewords have been verifed in this table.

 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.

# Check Matrix (H) for (7, 4) code

H is a (3 × 7) matrix

The check matrix for a systematic code can be found directly from the generator matrix. The rightmost columns form a (3 × 3) identity matrix while the remaining columns can be identified in corresponding rows in the generator matrix.

 1 1 1 0 1 0 0 0 1 1 1 0 1 0 1 1 0 1 0 0 1

Each row in the check matrix is a valid 7-bit codeword only for a cyclic code.

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-09-18 19:26:18 ADT Last Updated: 2015-02-06 Richard Tervo [ tervo@unb.ca ]