What Is Cyclic Redundancy Check (CRC) and How It Works

A Cyclic Redundancy Check (CRC) is a widely used error-detecting code designed to detect accidental changes to raw digital data in storage devices and communication networks. At its core, a CRC treats binary data strings as algebraic polynomials and performs division using modulo-2 arithmetic. By dividing the data polynomial by a predefined generator polynomial, the mathematical remainder produced serves as the checksum; upon reception, repeating this division confirms whether data corrupted during transmission.

What Is a Cyclic Redundancy Check?

A Cyclic Redundancy Check is a non-cryptographic hash function used to verify data integrity. When data is transmitted over a network or written to a disk, interference, noise, or hardware faults can flip bits from 0 to 1 or vice versa.

To catch these errors: 1. The sender calculates a short, fixed-length binary sequence (the CRC value) based on the payload data. 2. The sender appends this CRC value to the data before transmission. 3. The receiver recalculates the check on the incoming data using the same mathematical parameters. 4. If the calculated result matches the transmitted checksum, the data is assumed to be uncorrupted.

Representing Binary Data as Polynomials

In CRC computation, binary sequences are represented as polynomials where each bit corresponds to a coefficient of a specific power of \(x\), with values constrained to \(0\) or \(1\).

For example, a 5-bit binary sequence 10110 translates to: \[1 \cdot x^4 + 0 \cdot x^3 + 1 \cdot x^2 + 1 \cdot x^1 + 0 \cdot x^0 = x^4 + x^2 + x\]

The highest power with a non-zero coefficient defines the degree of the polynomial.

The Rules of Binary Arithmetic (Modulo-2)

CRC polynomial division operates in the Galois Field \(GF(2)\), commonly known as modulo-2 arithmetic. This simplifies traditional arithmetic in two key ways:

• Addition and Subtraction are Identical: Both operations behave like the bitwise XOR (Exclusive OR) operation.
  • \(0 \oplus 0 = 0\)
  • \(0 \oplus 1 = 1\)
  • \(1 \oplus 0 = 1\)
  • \(1 \oplus 1 = 0\)
• No Carries or Borrows: When adding or subtracting, values never carry over to the next higher power, and borrowing never occurs.

How Polynomial Division Generates the CRC

The algorithm relies on an agreed-upon divisor known as the generator polynomial (or divisor polynomial). The generator is fixed and standardized for specific protocols (such as CRC-16 or CRC-32).

The process works through the following sequence:

1. Zero-Padding: If the generator polynomial has a degree of \(n\), append \(n\) zero bits to the end of the original message data.
2. Modulo-2 Division: Divide the padded message polynomial by the generator polynomial using binary long division:
   • Align the generator polynomial with the leftmost 1 of the current remainder/data.
   • Apply the XOR operation between the aligned bits.
   • Shift right to the next 1 bit and repeat until all bits have been processed.
3. Extracting the Remainder: The final remainder will always have a length of \(n\) bits or fewer. This remainder is the CRC checksum.
4. Constructing the Frame: Replace the \(n\) zero bits added in step 1 with the CRC remainder. This newly formed sequence is the transmitted message.

Verifying Integrity at the Receiver

When the receiver receives the data frame (original message + CRC), it performs the exact same modulo-2 polynomial division using the identical generator polynomial.

• If the remainder is zero: The mathematical properties ensure that subtracting the remainder from the padded message produces an exact multiple of the generator polynomial. A remainder of zero indicates no detectable transmission errors.
• If the remainder is non-zero: One or more bits changed during transit, signaling that the data has been corrupted and must be retransmitted or discarded.

Why CRC Is Effective

Polynomial division gives CRC strong error-detection capabilities. Depending on the choice of the generator polynomial, CRCs are mathematically guaranteed to detect: * All single-bit errors. * All double-bit errors separated by a distance less than the polynomial’s length. * Any odd number of bit errors (if the generator contains the factor \((x + 1)\)). * Burst errors (clusters of corrupted bits) up to the degree of the generator polynomial.