CRC (Cyclic Redundancy Check)

CRC: The Gold Standard of Error Detection

Cyclic Redundancy Check is the most powerful and widely-deployed error detection technique in digital communication and storage. Every Ethernet frame, every USB transfer, every file on your hard drive, and every ZIP archive is protected by CRC. Its mathematical elegance — based on polynomial arithmetic over binary fields — gives it remarkable error detection properties that simple checksums cannot match.

Why CRC Over Simple Checksums?

Think of it this way: a simple checksum adds up all the data bytes. If byte 5 increases by 3 and byte 10 decreases by 3, the checksum stays the same — the error goes undetected. CRC treats the entire data block as a single huge binary number and divides it by a carefully chosen polynomial. This division is sensitive to the position of every bit, not just the sum, making it vastly superior at detecting real-world error patterns.

CRC detects:

• ALL single-bit errors (any one flipped bit)
• ALL double-bit errors (any two flipped bits, if polynomial chosen correctly)
• ALL odd numbers of bit errors (if polynomial has factor x+1)
• ALL burst errors up to the CRC length (e.g., any 32 consecutive corrupted bits for CRC-32)
• 99.99998% of all burst errors longer than 32 bits (for CRC-32)

The Mathematical Framework

CRC treats data as polynomials with binary coefficients:

Data bits: 1 0 1 1 0 1 → Polynomial: x⁵ + x³ + x² + x⁰ = x⁵ + x³ + x² + 1

The CRC computation:

1. Represent the data as polynomial M(x)
2. Multiply M(x) by x^r (shift left by r bits, where r is CRC degree)
3. Divide x^r × M(x) by generator polynomial G(x)
4. The remainder R(x) is the CRC value
5. Transmit: original data followed by CRC bits

Verification: The receiver divides the entire received sequence (data + CRC) by G(x). If the remainder is zero, no errors are detected. Any non-zero remainder indicates an error.

Step-by-Step Example

Let us compute CRC-3 with G(x) = x³ + x + 1 (binary: 1011) for data 1010:

Step 1: Data = 1010, append 3 zeros → 1010000 Step 2: Divide 1010000 by 1011 using XOR division:

Step 3: Transmitted frame = 1010 011 (data + CRC)

Verification: Divide 1010011 by 1011:

Standard Generator Polynomials

Different applications use different generator polynomials optimized for their error environments:

The CRC-32 polynomial (0x04C11DB7) is the most ubiquitous — protecting Ethernet frames that carry virtually all internet traffic.

Properties of Good Generator Polynomials

A generator polynomial G(x) of degree r should have:

1. At least x+1 as a factor — ensures ALL odd-number errors are detected
2. Not divide x^k + 1 for any k < 2^r - 1 — maximizes burst error detection
3. High minimum distance — maximizes the minimum number of bit changes needed to create an undetectable error

These properties are found through exhaustive computer search — which is why standard polynomials are published and shared.

Hardware Implementation: LFSR

CRC computation is extremely efficient in hardware using a Linear Feedback Shift Register (LFSR):

Architecture:

• r flip-flops (one per CRC bit)
• XOR gates at positions corresponding to G(x) coefficients
• Feedback from the MSB to selected positions

Operation:

1. Initialize register to all zeros (or all ones for CRC-32)
2. Shift in data bits one at a time
3. After all data bits processed, register contains the CRC

This computes CRC at wire speed — one bit per clock cycle — with minimal gate count. Ethernet PHY chips compute CRC-32 at 10 Gbps and beyond using parallel LFSR architectures.

Software Implementation

For software, table-driven CRC computation processes one byte at a time:

The 256-entry lookup table pre-computes all possible single-byte CRC contributions. This processes data at one byte per iteration — 8× faster than bit-by-bit computation.

CRC vs. Checksum vs. Hash: When to Use What

Use CRC when:

• Burst errors are the primary concern (serial links, storage media)
• Hardware implementation speed is needed
• You want guaranteed detection of specific error patterns
• Communication protocols (Ethernet, USB, HDLC)

Use checksum when:

• Speed is paramount and error detection can be weaker
• Errors are random (not burst)
• Incremental update is needed (IP headers)

Use cryptographic hash when:

• Deliberate tampering must be detected
• Very high assurance is needed
• Digital signatures or certificates are involved

Error Detection vs. Error Correction

Standard CRC detects errors but cannot correct them. However:

• CRC combined with ARQ (Automatic Repeat Request): Detected errors trigger retransmission
• For error correction, use codes like Hamming, Reed-Solomon, or LDPC

Some specialized CRC applications can correct single-bit errors: the syndrome (non-zero remainder) uniquely identifies the error position for single-bit errors.

Practical Example: Ethernet CRC-32

Every Ethernet frame ends with a 4-byte Frame Check Sequence (FCS) containing CRC-32:

• Frame: [Destination MAC | Source MAC | Type | Payload | FCS]
• CRC computed over: Destination through end of Payload
• If receiver's CRC ≠ received FCS → frame silently discarded
• Error rate: At 1 Gbps with BER = 10⁻¹⁰, approximately 1 undetected error per 10²⁰ bits — essentially never

Key Takeaways

1. CRC uses polynomial division to generate a check value that detects all single-bit, double-bit, odd-bit errors, and all burst errors up to the CRC length.
2. Generator polynomial choice is critical — standard polynomials (CRC-32, CRC-16/CCITT) are mathematically optimized for maximum detection capability.
3. Hardware implementation uses LFSRs to compute CRC at line rate with minimal circuitry.
4. CRC-32 protects virtually all digital data in transit (Ethernet) and at rest (file systems, archives).
5. CRC detects but does not correct errors — correction requires either retransmission (ARQ) or dedicated error-correcting codes.
6. For an r-bit CRC, the probability of undetected random errors is approximately 2⁻ʳ — vanishingly small for CRC-32 (one in 4 billion).