Cyclic Redundancy Check

Cyclic Redundancy Check (CRC)

A Cyclic Redundancy Check (CRC) is an error-detecting code commonly used in digital networks and storage devices to detect accidental changes to raw data. Blocks of data entering these systems get a short check value attached, based on the remainder of a polynomial division of their contents. On retrieval, the calculation is repeated and, in the event the check values do not match, corrective action can be taken against data corruption.

Mathematical Definition

CRC calculation relies on polynomial arithmetic over the finite field GF(2), where addition and subtraction are equivalent to the logical XOR operation, and there is no carry. A message is treated as a polynomial where each bit represents a coefficient. This message polynomial is then multiplied by x^r (equivalent to appending r zero bits, where r is the degree of the generator polynomial). The resulting polynomial is divided by a predefined generator polynomial using modulo-2 arithmetic.

The remainder of this division is the CRC checksum. The sender replaces the appended zero bits with this remainder to form the transmitted codeword. The receiver performs the same polynomial division on the received codeword. If the transmission was error-free, the remainder will be zero. If a non-zero remainder is obtained, an error has been detected.

M(x): Message polynomial

G(x): Generator polynomial of degree r

T(x) = M(x) · x^r XOR R(x)

Where R(x) is the remainder of (M(x) · x^r) / G(x)

Key Concepts

A worked transmission

Let's perform a CRC encoding step-by-step. Suppose our data bits are 1101 and the generator bits are 1011 (which corresponds to the polynomial x³ + x + 1). The degree of the generator is r = 3. We append 3 zeros to the data, resulting in 1101000.

Now we divide 1101000 by 1011 using XOR subtraction. The expected remainder is 001. Here are the steps:

1101 XOR 1011 = 0110. Bring down 0: 1100.
1100 XOR 1011 = 0111. Bring down 0: 1110.
1110 XOR 1011 = 0101. Bring down 0: 1010.
1010 XOR 1011 = 0001. The remainder is 001.
Remainder: 001.
Codeword: 1101001.

Interactive Experiment

You can verify this exact calculation using the Cyclic Redundancy Check module.

Set Data bits to 1101 and Generator bits to 1011.
Click Step multiple times to walk through the long division XOR operations.
Click Finish to immediately compute the final remainder (001) and codeword (1101001).
Change the Flip position to 1, then click Finish again to replay and simulate a one-bit transmission error. You will observe received remainder 111, correctly displaying Detected error status.

Model Limitations

This educational module implements an unreflected, zero-initialized CRC. It intentionally omits common real-world CRC features such as:

Pre-inversion and Post-inversion: Standard CRCs (like CRC-32) often initialize the register with all ones (instead of zeros) and XOR the final remainder with all ones to detect added/dropped leading zeros.
Bit Reflection: Real-world implementations often reflect (reverse) the data bits and/or the remainder to match hardware shift register order.
No Correction Guarantee: Unlike Hamming codes, CRC is designed for detection, not correction. While a non-zero remainder guarantees one or more errors occurred, this module does not attempt to correct multi-bit errors or guarantee detection of every possible multi-bit error if the error polynomial happens to be a multiple of the generator.

References

Here is a reference that explores the mathematics of cyclic redundancy checks and polynomial long division over GF(2):

Perform Cyclic Redundancy Check - MathWorks

Cyclic Redundancy Check