Cyclic Redundancy Check (CRC)

Cyclic redundancy check

When sending an important document by mail, the sender could write a verification number on the envelope, calculated from the document's content. The recipient performs the same calculation on the received document and compares the result with the sender's value. Equality means that the check detected no change. A mismatch indicates a change in the data during storage or transmission.

The Cyclic Redundancy Check (CRC) implements this check as an error-detecting code. It is used in digital networks and storage devices to detect accidental changes in data. For a given block, it calculates a short, fixed-length binary sequence called the CRC checksum, or simply CRC, then appends it to the data before transmission or storage. In practice, CRC can refer to both the code and the calculated value. The receiver calculates the value again and compares the two results.

Polynomials and modulo-2 arithmetic

CRC represents a binary string as a polynomial over $GF(2)$. For example, the string $1101$ corresponds to the polynomial:

$1\cdot x^3 + 1\cdot x^2 + 0\cdot x^1 + 1\cdot x^0 = x^3 + x^2 + 1$

CRC division and the related operations use modulo-2 arithmetic. In this system, addition and subtraction have the same value table as XOR, so the algorithm does not use the carries of integer arithmetic.

CRC calculation at the sender

Consider a message 110101 and the agreed generator polynomial 101.

1. Step 1: append zeros.

   Append as many zeros to the message as the degree of the generator polynomial, which is one less than its number of bits. The generator $(101)$ has 3 bits and degree 2, so append $3-1=2$ zeros.
   The padded message is: 11010100.

2. Step 2: modulo-2 binary division.

   Divide the padded message by the generator polynomial using polynomial long division over modulo-2 arithmetic. XOR replaces subtraction at each stage.

   The division yields a quotient, which we discard, and a remainder. In this calculation, the remainder is 11, which becomes the CRC checksum.

3. Step 3: create the transmitted frame.

   Replace the zeros appended in the first step with the calculated CRC.
   Original message: $(110101)$
   Message with zeros: $(11010100)$
   XOR remainder: $(00000011)$
   Final frame to transmit: 11010111

Frame verification at the receiver

The receiver divides the received frame again by the same generator polynomial.

1. Receive the frame: The receiver gets the complete frame containing the data and CRC checksum: $(11010111)$.
2. Perform the division: It divides the entire received frame by the same generator polynomial $(101)$.
3. Check the remainder:
   • If the remainder is zero, the check detected no error. The receiver accepts the packet, and the CRC is removed, leaving the original data.
   • If the remainder is non-zero, the frame contains a detected error. The receiver discards the entire packet. A higher-level protocol, such as TCP, can request retransmission.

CRC error-detection properties

Detection of a given error pattern depends on the generator polynomial and the protected block length. The following properties follow from the structure of $G(x)$ and from the range of bit separations that can occur in the block:

• All single-bit errors if $G(x)$ has at least two non-zero terms.
• All double-bit errors within a specified block length if $G(x)$ has a non-zero constant term and does not divide $x^k+1$ for any possible separation $k$ between changed bits.
• All errors with an odd number of changed bits if the generator polynomial contains the factor $x+1$.
• Burst errors whose length does not exceed the degree of the generator polynomial when its constant term is non-zero.

CRC detects changes in data, while correction requires a separate mechanism. CRC is used in Ethernet frames, Wi-Fi networks, HDLC, and file formats such as ZIP and PNG.