The flagship matrix performs the CRC division from the exact message and generator bits. Every row is recomputed by XORing or skipping at the current leading bit.

highlighted = computed this step

Why the matrix is the proof

The CRC remainder is not typed separately from the division. The matrix shows each XOR placement and the running state down to the final bits.

dividend=11010011101100000\text{dividend}=11010011101100000

Divide by the generator

The dividend 11010011101100000 is divided by generator 1011. The engine recomputes the rows from those bits.

11010011101100000÷101111010011101100000\div1011
CRC long divisionGF(2) division rows are recomputed from the exact bits.CRC long divisiondivide by 1011dividend1101001110110000011010011101100000xor 0101101100011101100000xor 1101100111011101100000xor 2101100010111101100000xor 3101100000001101100000skip 400000001101100000skip 500000001101100000skip 600000001101100000xor 7101100000000110100000xor 8101100000000011000000xor 9101100000000001110000xor 10101100000000000101000xor 11101100000000000000100skip 1200000000000000100skip 1300000000000000100remainder100100

XOR or skip

When the leading bit is 1, XOR the generator at that position; when it is 0, skip. This example has 9 XOR steps.

xor steps=9\text{xor steps}=9
CRC long divisionGF(2) division rows are recomputed from the exact bits.CRC long divisiondivide by 1011dividend1101001110110000011010011101100000xor 0101101100011101100000xor 1101100111011101100000xor 2101100010111101100000xor 3101100000001101100000skip 400000001101100000skip 500000001101100000skip 600000001101100000xor 7101100000000110100000xor 8101100000000011000000xor 9101100000000001110000xor 10101100000000000101000xor 11101100000000000000100skip 1200000000000000100skip 1300000000000000100remainder100100

The final bits

After the last aligned step, the remainder is 100.

remainder=100\text{remainder}=100
CRC long divisionGF(2) division rows are recomputed from the exact bits.CRC long divisiondivide by 1011dividend1101001110110000011010011101100000xor 0101101100011101100000xor 1101100111011101100000xor 2101100010111101100000xor 3101100000001101100000skip 400000001101100000skip 500000001101100000skip 600000001101100000xor 7101100000000110100000xor 8101100000000011000000xor 9101100000000001110000xor 10101100000000000101000xor 11101100000000000000100skip 1200000000000000100skip 1300000000000000100remainder100100

Summary

CRC division is ordinary-looking long division, except subtraction is XOR and the final remainder is the CRC. Polynomial arithmetic over the exact bits; timing/throughput is not modeled here.

CRC=100\text{CRC}=100
CRC long divisionGF(2) division rows are recomputed from the exact bits.CRC long divisiondivide by 1011dividend1101001110110000011010011101100000xor 0101101100011101100000xor 1101100111011101100000xor 2101100010111101100000xor 3101100000001101100000skip 400000001101100000skip 500000001101100000skip 600000001101100000xor 7101100000000110100000xor 8101100000000011000000xor 9101100000000001110000xor 10101100000000000101000xor 11101100000000000000100skip 1200000000000000100skip 1300000000000000100remainder100100