CRC Verification

The sender has computed the CRC and transmitted the protected codeword. The bits have traversed noisy cables, potentially suffering interference, attenuation, and corruption. Now it's the receiver's turn: did the data arrive intact, or has it been corrupted in transit?

CRC verification answers this question with elegant simplicity. The same polynomial division that created the CRC now validates it. If the data survived transmission unchanged, a mathematical property guarantees a specific result. If any bit flipped, that property is violated—and the error is detected.

This page explores CRC verification in depth: the two equivalent verification methods, why they work, how errors manifest as non-zero syndromes, and practical considerations for real-world implementations.

The receiver obtains a string of bits—let's call it T'(x). This is supposedly the transmitted codeword T(x), but transmission errors may have corrupted it:

$$T'(x) = T(x) + E(x)$$

where E(x) is the error polynomial (zeros everywhere except at corrupted bit positions).

The Receiver's Challenge:

The receiver knows:

• The generator polynomial G(x)
• The received data T'(x)
• The expected format (n-bit message + r-bit CRC)

The receiver does NOT know:

• Whether T'(x) = T(x) (no errors) or T'(x) ≠ T(x) (errors occurred)
• The original message M(x), until verified

The Goal:

Determine whether T'(x) is a valid codeword. If so, extract M(x). If not, signal an error.

The most intuitive verification approach mirrors the sender's process:

Algorithm:

1. Separate the codeword into message M'(x) (first n bits) and received CRC R'(x) (last r bits)

2. Recompute the CRC from M'(x) using the same algorithm the sender used, obtaining R_computed(x)

3. Compare: If R'(x) = R_computed(x), accept the message. Otherwise, reject.

Why This Works:

If no errors occurred, then:

• M'(x) = M(x) (original message)
• R'(x) = R(x) (original CRC)
• Computing CRC of M'(x) gives R(x) = R'(x) ✓

If errors occurred in the message:

• M'(x) ≠ M(x)
• Computing CRC of M'(x) gives some R_computed(x) ≠ R(x)
• Since errors in R'(x) are possible but rare, mismatch is detected ✓

If errors occurred only in the CRC:

• M'(x) = M(x)
• R'(x) ≠ R(x)
• Computing CRC of M'(x) gives R(x) ≠ R'(x) ✓

Worked Example:

Received: T' = 1101011 (7 bits: 4-bit message + 3-bit CRC) Generator: G = 1011

Step 1: Separate

• M' = 1101 (first 4 bits)
• R' = 011 (last 3 bits)

Step 2: Recompute CRC of M' = 1101 Append 3 zeros: 1101000 Divide by 1011:

1101000 ÷ 1011:
1101000
1011
────
0110000 → 110000
1011
────
011100 → 11100
1011
────
01010 → 1010
1011
────
0001 → 001

R_computed = 001

Step 3: Compare R' = 011 ≠ R_computed = 001

Result: Error detected! The received CRC doesn't match what the message should produce.

A more elegant approach leverages a key property: valid codewords are exactly divisible by G(x).

Algorithm:

1. Divide T'(x) by G(x) (the entire received codeword, including the CRC portion)

2. Check the remainder:

   • If remainder = 0: Accept (no error detected)
   • If remainder ≠ 0: Reject (error detected)

Why This Works:

Recall that the transmitted codeword was constructed as: $$T(x) = x^r \cdot M(x) + R(x)$$

where R(x) = (x^r · M(x)) mod G(x).

This means T(x) mod G(x) = 0 by construction.

If T'(x) = T(x) (no errors): $$T'(x) \mod G(x) = T(x) \mod G(x) = 0 \quad ✓$$

If T'(x) = T(x) + E(x) (errors occurred): $$T'(x) \mod G(x) = (T(x) + E(x)) \mod G(x) = 0 + E(x) \mod G(x) = E(x) \mod G(x)$$

This is non-zero unless G(x) divides E(x)—which is extremely rare for well-chosen G(x).

Worked Example:

Case A: No Errors

Received: T' = 1101001 (the correct codeword from earlier) Generator: G = 1011

Divide T' by G:

1101001 ÷ 1011:
1101001
1011
────
0110001 → 110001
1011
────
011101 → 11101
1011
────
01011 → 1011
1011
────
0000

Remainder = 000 ✓

Zero remainder → No error detected

---

Case B: One Bit Error

Original T = 1101001, but bit 4 flipped → T' = 1111001

Divide T' by G:

1111001 ÷ 1011:
1111001
1011
────
0100001 → 100001
1011
────
(align at pos 5, but 100001 < 1011 at high positions...)

Actually: 1111001
          1011
          ────
          01000|01 → 100001
           (leading 1 at position 5)
           1011   (shift to position 5-2)
           ────
           01100|1 → 110001
            1011
            ────
            01110|1 → 111001...

Let me compute more carefully:

1111001
Step 1: 1111 vs 1011 at pos [6:3] → 1111 XOR 1011 = 0100
Result: 0100001 → 100001

Step 2: 1000 vs 1011 at pos [5:2] → cannot (1000 < 1011 as 4-bit? No, 1000 > 1011 is false)
Actually 1000 starts with 1, so we can XOR:
1000 XOR 1011 = 0011
Result: 0011|01 → 11001 (bring down)

Step 3: Wait, let me track positions...

Let me use the shift register method instead for clarity:

Input: 1111001 (bits from left to right) Register (3-bit): 000 Poly: 1011 → feedback pattern 011

Process bit by bit:

• Bit 1: Reg=000, in=1, shift→001, MSB out=0, no XOR
• Bit 1: Reg=001, in=1, shift→011, MSB out=0, no XOR
• Bit 1: Reg=011, in=1, shift→111, MSB out=0, no XOR
• Bit 1: Reg=111, in=1, shift→111, MSB out=1, XOR with 011→100
• Bit 0: Reg=100, in=0, shift→000, MSB out=1, XOR with 011→011
• Bit 0: Reg=011, in=0, shift→110, MSB out=0, no XOR
• Bit 1: Reg=110, in=1, shift→101, MSB out=1, XOR with 011→110

Final: 110 ≠ 000

Non-zero remainder → Error detected!

When the remainder of T'(x) ÷ G(x) is non-zero, that remainder is called the syndrome. The syndrome contains valuable information about the error that occurred.

Definition:

$$\text{Syndrome } S(x) = T'(x) \mod G(x) = E(x) \mod G(x)$$

The syndrome is entirely determined by the error polynomial—it doesn't depend on the original message! This is because:

$$S(x) = (T(x) + E(x)) \mod G(x) = \underbrace{T(x) \mod G(x)}_{= 0} + E(x) \mod G(x) = E(x) \mod G(x)$$

Key Properties:

1. S(x) = 0 implies no detectable error (E(x) = 0 or E(x) is divisible by G(x))

2. S(x) ≠ 0 implies an error was detected

3. Same syndrome, same error class: Different error patterns with the same syndrome are indistinguishable by CRC

Observations from the Table:

1. Each single-bit error has a unique syndrome for positions 0-5 (up to 2^r - 1 positions for a degree-r CRC)

2. Bit 3 error and double error (bits 0,1) have the same syndrome (011) — The CRC detects that an error occurred but cannot distinguish these cases

3. No single-bit error has syndrome 000 — All single-bit errors are detected

Error Correction Potential:

In some applications (not standard CRC), the syndrome can be used to locate single-bit errors:

• Syndrome 001 → error at position 0
• Syndrome 010 → error at position 1
• etc.

However, this only works for single-bit errors within a limited message length. CRC is fundamentally designed for error detection, not correction.

CRC is not perfect. An error goes undetected when the error polynomial E(x) is exactly divisible by G(x):

$$E(x) = Q(x) \cdot G(x) \quad \text{for some polynomial } Q(x)$$

In this case, the syndrome S(x) = E(x) mod G(x) = 0, and the corrupted data is accepted as valid.

What Does an Undetected Error Look Like?

For G(x) = x³ + x + 1 = 1011, some divisible error patterns are:

• E(x) = G(x) itself = 1011 (errors at positions 3, 1, 0)
• E(x) = x · G(x) = 10110 (errors at positions 4, 2, 1)
• E(x) = G(x)² = 1011 × 1011 = ... (more complex pattern)

These are specific, structured error patterns—not random bit flips. The probability of random noise producing exactly such a pattern is vanishingly small.

Probability Analysis:

For an r-bit CRC with random errors:

• Single-bit error: Probability of being undetected = 0 (guaranteed detection if g₀ = 1)

• Double-bit error: Probability of being undetected ≈ 0 (detected if message length < 2^r - 1)

• Burst of length ≤ r: Probability of being undetected = 0 (guaranteed)

• Burst of length r + 1: Probability of being undetected = 2^(-(r-1))

  • For CRC-32: 2^(-31) ≈ 4.7 × 10^(-10)

• Random pattern > r bits: Probability of being undetected ≈ 2^(-r)

  • For CRC-32: 2^(-32) ≈ 2.3 × 10^(-10)

In Practice:

With CRC-32, roughly 1 in 4 billion random error patterns goes undetected. Combined with:

• BER of 10^(-9) on modern links
• Frame size of 12,000 bits
• Frame error rate ≈ 1.2 × 10^(-5)

The probability of encountering an undetected corrupted frame is approximately:

$$10^{-5} \times 2.3 \times 10^{-10} \approx 2 \times 10^{-15}$$

At 10 Gbps, this is roughly one undetected corrupted frame per century of continuous transmission.

Real systems must handle both CRC pass and CRC fail cases gracefully. Let's examine the practical considerations.

On CRC Pass (Syndrome = 0):

1. Extract the message: Strip the last r bits (the CRC) from the codeword
2. Pass to upper layer: Deliver the message to the next protocol layer
3. Optionally acknowledge: In protocols like HDLC, send an ACK to the sender

On CRC Fail (Syndrome ≠ 0):

The appropriate action depends on the protocol and layer:

Option A: Silent Discard (Most Common at Link Layer)

• Drop the corrupted frame immediately
• Don't notify anybody—upper layers will timeout and retry
• Example: Ethernet, WiFi

Option B: Request Retransmission (Data Link ARQ)

• Send a NAK or allow timeout to trigger retransmission
• Used in protocols like HDLC, PPP, Bluetooth L2CAP

Option C: Forward Error Correction

• If FEC is available, attempt to correct the error
• If correction fails, then discard
• Used in DVB, 5G NR

Statistics and Monitoring:

Well-designed systems track CRC failures for diagnostics:

• Error counters: NICs maintain per-port CRC error counts
• Alarm thresholds: High error rates trigger alerts
• Trend analysis: Increasing errors may indicate cable degradation or interference

Example: Ethernet Interface Statistics

$ ifconfig eth0
eth0: flags=4163<UP,BROADCAST,RUNNING,MULTICAST>
      RX errors 0  dropped 0  overruns 0  frame 0
      TX errors 0  dropped 0 overruns 0  carrier 0

The 'errors' counter includes CRC failures. In healthy networks, this should stay at or near zero.

Efficient CRC verification is crucial for high-speed links. Several optimizations apply:

1. Incremental Verification

Rather than buffering the entire frame and then verifying, compute the CRC as data arrives. The shift-register approach naturally supports this:

• As each byte arrives, feed it into the CRC engine
• When all bytes have been processed, check if the register is zero (or a known 'magic' residue)

2. The Magic Residue

For many CRC standards, if you process the entire codeword (including the CRC bytes) through the CRC engine, you get a constant non-zero value—the magic residue or check value:

• CRC-32 (Ethernet): Residue = 0xC704DD7B
• CRC-16-CCITT: Residue = 0x0F47

This occurs because of the final XOR (complement) in the standard. Checking for this constant is equivalent to checking for zero remainder in the 'pure' algorithm.

3. Hardware CRC Engines

Network interface cards (NICs) perform CRC in hardware:

• On receive: As bits arrive from the wire, pass them through LFSR
• At frame end: Check register against magic residue
• If mismatch: Set an error flag in the receive descriptor
• Timing: Zero additional latency—verification completes as the last bit arrives

4. Parallel CRC

For very high-speed links (100 Gbps+), serial bit processing is too slow. Solutions include:

• Table-based parallelism: Process N bits per cycle using 2^N lookup table
• Matrix methods: Express CRC as linear transformation; parallelize matrix multiplication
• PCLMULQDQ instruction: Hardware carry-less multiplication enables efficient CRC on x86

These techniques achieve CRC verification at line rate even for terabit networks.