Division over GF(2)

The Generator Polynomial

The generator is the polynomial divisor. Its degree sets the number of zeros appended before division.

highlighted = computed this step

Why the generator controls division

The generator is the divisor in CRC long division. Its degree tells how many CRC bits will be appended.

generator=1011\text{generator}=1011

Generator polynomial

The generator bits 1011 map to 1 times x^3 plus 0 times x^2 plus 1 times x plus 1, so the x^2 term drops out and the degree is 3.

1011=1⋅x3+0⋅x2+1⋅x+1=x3+x+11011=1\cdot x^3+0\cdot x^2+1\cdot x+1=x^3+x+1
Generator bitsThe generator bits are decoded as one exact bit field.Generator8 bits / 1 byte0xb0byte 010110000generator1011pad0000

Append degree zeros

Before dividing, append 3 zeros to the message. The dividend becomes 11010011101100000.

11010011101100 ∥ 000=1101001110110000011010011101100\,\Vert\,000=11010011101100000

Summary

The generator fixes both the divisor and the CRC width. Polynomial arithmetic over the exact bits; timing/throughput is not modeled here.

degree=3\text{degree}=3
Generator bitsThe generator bits are decoded as one exact bit field.Generator8 bits / 1 byte0xb0byte 010110000generator1011pad0000