What is a Cyclic Redundancy Check?

Imagine sending an important document by mail. To make sure it arrives unchanged, you could write down a special "verification number" on the envelope, calculated from the document's content. The recipient performs the same calculation on the received document and checks if their number matches yours. If it does, the document is likely intact. If not, something went wrong.

The Cyclic Redundancy Check (CRC) is a powerful, digital version of this idea. It's an error-detecting code commonly used in digital networks and storage devices to detect accidental changes to raw data. It generates a short, fixed-length binary sequence, known as the CRC checksum or simply CRC, for a given block of data. This checksum is like a "digital fingerprint" that is appended to the data and sent along with it.

The Core Idea: Polynomials and Modulo-2 Arithmetic

The "magic" behind CRC's effectiveness lies in treating binary strings as if they were mathematical polynomials. For example, the binary string $1101$ can be interpreted as the polynomial:

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

All calculations are performed using a special kind of math called Modulo-2 Arithmetic. In this system, addition and subtraction work exactly like the logical XOR operation, which greatly simplifies the hardware required.

How CRC is Calculated (Sender's Side)

Let's walk through an example. Suppose we want to send the message 110101 and we have agreed on the generator polynomial 101.

1. Step 1: Append Zeros.

   First, we append a number of zeros to the end of our message. The number of zeros is one less than the length of the generator polynomial. Our generator `101` has a length of 3 bits, so we append $3-1=2$ zeros.
   Our padded message is now: 11010100.

2. Step 2: Binary Long Division (Modulo-2).

   Next, we divide the padded message by the generator polynomial using modulo-2 long division (where subtraction is XOR).

   

   The division yields a quotient (which we discard) and a remainder. For this calculation, the remainder is 11. This remainder is our CRC checksum.

3. Step 3: Create the Transmitted Frame.

   Finally, we replace the zeros we appended in Step 1 with the calculated CRC checksum.
   Original Message: '110101'
   Padded with Zeros: '11010100'
   XOR Remainder: '00000011'
   Final Frame to Transmit: 11010111

How Errors are Checked (Receiver's Side)

The receiver performs a simple verification process.

1. Receive the Frame: The receiver gets the complete frame, including the data and the CRC checksum: '11010111'.
2. Perform the Division: It divides the entire received frame by the exact same generator polynomial (`101`).
3. Check the Remainder:
   • If the remainder is zero, the receiver assumes the data has arrived without detectable errors and accepts the packet. The CRC is then stripped off, leaving the original data.
   • If the remainder is non-zero, it signals that an error has occurred during transmission. The receiver then discards the entire packet, knowing it is corrupt. It is typically up to a higher-level protocol (like TCP) to request a retransmission.

Interactive CRC Calculator

Why is CRC So Effective?

The power of CRC lies in the mathematical properties of polynomial division. A well-chosen generator polynomial makes it highly unlikely that transmission errors will transform the original message into another valid message that is still perfectly divisible by the generator. CRC is particularly good at detecting:

• All single-bit errors.
• All double-bit errors (as long as the generator polynomial has at least three '1's).
• Any odd number of errors.
• Burst errorsup to a length equal to the degree of the generator polynomial. This is its most significant advantage for real-world channels.

This robustness is why CRC is the de-facto standard for error detection in many technologies, including Ethernet frames (CRC-32), Wi-Fi, HDLC, and file formats like ZIP and PNG.