CRC - Cyclic Redundancy Check

You've mastered polynomial division and understand why generator polynomials are carefully chosen. Now comes the practical application: how do we actually compute a CRC value?

The sender takes a raw message, applies the CRC algorithm, and produces a protected codeword—the original data plus the appended CRC bits. This codeword has a special property: it is exactly divisible by the generator polynomial. The receiver can then verify this divisibility to detect any transmission errors.

This page walks through the complete CRC calculation procedure with multiple worked examples, explaining both the conceptual framework and practical implementation details.

Let's establish the formal procedure for CRC calculation. Given:

• M(x): The message polynomial (data to protect)
• G(x): The generator polynomial of degree r
• T(x): The transmitted codeword

The Goal:

Construct T(x) such that:

1. T(x) contains all of M(x) (the receiver needs the original data)
2. T(x) is exactly divisible by G(x) (enabling error detection)

The Solution:

Append r bits (the CRC value) to M(x) to form T(x). These bits are chosen such that T(x) mod G(x) = 0.

The Algorithm:

1. Multiply M(x) by x^r — This is equivalent to appending r zero bits to the message, creating space for the CRC

2. Divide by G(x) — Compute: x^r · M(x) mod G(x) to get remainder R(x)

3. Form the codeword — T(x) = x^r · M(x) + R(x)

Mathematical Justification:

Why does this work? Let's verify:

$$T(x) = x^r \cdot M(x) + R(x)$$

Divide by G(x): $$\frac{T(x)}{G(x)} = \frac{x^r \cdot M(x) + R(x)}{G(x)}$$

We know that $x^r \cdot M(x) = Q(x) \cdot G(x) + R(x)$ (from the division in step 2).

Therefore: $$\frac{T(x)}{G(x)} = \frac{Q(x) \cdot G(x) + R(x) + R(x)}{G(x)} = Q(x) + \frac{2 \cdot R(x)}{G(x)}$$

But in GF(2), 2 = 0 (since 1 + 1 = 0), so: $$\frac{T(x)}{G(x)} = Q(x) + 0 = Q(x)$$

The remainder is zero! T(x) is exactly divisible by G(x). ✓

Let's walk through a complete CRC calculation with a concrete example.

Given:

• Message M = 110101 (6 bits)
• Generator G = 1011 (polynomial x³ + x + 1, degree r = 3)

Step 1: Append r Zero Bits

Shift M left by r = 3 positions:

$$x^3 \cdot M(x) = 110101 \text{ followed by } 000 = 110101000$$

This represents M(x) · x³, making room for the 3-bit CRC.

Step 2: Divide by G(x)

Perform polynomial division: 110101000 ÷ 1011

         110010   ← Quotient (we don't need this)
        ───────
  1011 │ 110101000
         1011     ← XOR (leading 1)
         ────
         01010    ← Result: 10101
          1011    ← XOR (leading 1)
          ────
          00111   ← Result: 1110
           1011   ← XOR (leading 1)
           ────
           01010  ← Result: 10100
            1011  ← XOR (leading 1)
            ────
            0010  ← Result: 0100
             000  ← Don't XOR (leading 0)
             ───
             100  ← Remainder = 100

Step 3: Form the Codeword

T(x) = 110101000 ⊕ 000000100 = 110101100

Or equivalently: Original message (110101) + CRC (100) = 110101100

The transmitted codeword is: 110101100

Verification:

Let's verify that 110101100 is exactly divisible by 1011:

  1011 │ 110101100
         1011
         ────
         10101    
          1011    
          ────
          01111   → 11110
           1011   
           ────
           01000  → 10000
            1011  
            ────
            0110  → 1100
             1011 
             ────
             0111 → 111
              000 
              ───
              111
               Do I have an error? Let me redo...

Actually, let me recalculate step 2 more carefully.

Step 2 (Recalculated Carefully):

Divide 110101000 by 1011:

Position:   876543210
Dividend:   110101000
Divisor:    1011

Step 1: Align at position 8
  110101000
  1011       (positions 8-5)
  ─────
  0110|01000  → 11001000  (after removing leading 0)

Step 2: Align at position 7
  11001000
  1011      (positions 7-4)
  ─────
  01111000  → 1111000

Step 3: Align at position 6
  1111000
  1011     (positions 6-3)
  ─────
  0100000  → 100000

Step 4: Align at position 5
  100000
  1011    (positions 5-2)
  ─────
  0011|00 → 1100

Step 5: Align at position 3
  1100
  1011   (positions 3-0)
  ─────
  0111   → 111

Remainder = 111 (3 bits, as expected for degree-3 divisor)

Corrected: CRC = 111

Codeword T = 110101111

Let's do a fresh, complete example with careful tracking.

Given:

• Message M = 1101 (4 bits) = x³ + x² + 1
• Generator G = 1011 (4 bits) = x³ + x + 1, degree r = 3

Sender Side:

Step 1: Append r = 3 zeros to M:

M' = 1101 000 = 1101000 (7 bits)

Step 2: Divide M' by G:

   1101000     (7 bits)
÷  1011        (divisor)
───────────

Align divisor with leading bit of dividend:
1101000
1011     (XOR at positions 6-3)
────
0110000  → 110000

110000
1011     (XOR at positions 5-2)
────
011100  → 11100

11100
1011     (XOR at positions 4-1)
────
01010  → 1010

1010
1011     (XOR at positions 3-0)
────
0001     → 001

Remainder R = 001

Step 3: Form codeword T = M' + R:

T = 1101000 + 0000001 = 1101000 XOR 0000001 = 1101001

Equivalently: 1101 | 001

Transmitted Codeword: 1101001

Receiver Side Verification:

Receive T = 1101001. Divide by G = 1011:

1101001
1011     (XOR)
────
0110001  → 110001

110001
1011     (XOR)
────
011101  → 11101

11101
1011     (XOR)
────
01011  → 1011

1011
1011     (XOR)
────
0000

Remainder = 000 ✓

Zero remainder confirms no errors detected!

Let's work through a longer example using a degree-4 polynomial (similar in complexity to real CRCs, but manageable by hand).

Given:

• Message M = 10110011 (8 bits)
• Generator G = 10011 (5 bits) = x⁴ + x + 1, degree r = 4

Step 1: Append 4 zeros:

M' = 10110011 0000 = 101100110000 (12 bits)

Step 2: Divide M' by G:

101100110000
10011         (align at pos 11)
─────
001110110000  → 1110110000

1110110000
10011         (align at pos 9)
─────
0111010000  → 111010000

111010000
10011         (align at pos 8)
─────
011100000  → 11100000

11100000
10011         (align at pos 7)
─────
01111000  → 1111000

1111000
10011         (align at pos 6)
─────
0110100  → 110100

110100
10011         (align at pos 5)
─────
010010  → 10010

10010
10011         (align at pos 4)
─────
00001  → 0001

Remainder R = 0001 (4 bits)

Step 3: Form codeword:

T = 101100110000 + 0001 = 101100110001

Transmitted: 10110011|0001 (8-bit message + 4-bit CRC)

Verification:

101100110001
10011
─────
001110110001  → 1110110001

1110110001
10011
─────
0111010001  → 111010001

111010001
10011
─────
011100001  → 11100001

11100001
10011
─────
01111001  → 1111001

1111001
10011
─────
0110101  → 110101

110101
10011
─────
010001  → 10001

10001
10011
─────
00010  → 0010

0010 < 10011 (too small to divide)

Final Remainder = 0010 ≠ 0000

Hmm, let me recheck step 2...

Recalculation of Step 2:

Divisor: 10011 (5 bits)
Dividend: 101100110000 (12 bits)

Round 1: bits [11:7] = 10110, XOR with 10011
  10110 ⊕ 10011 = 00101 → 01011 (bring next bit)
  Result so far: 01011 → working with: 10110 (after shift)
  
Actually, let me use a cleaner method:

Bit-by-bit with register:

Initial: Process "101100110000"

I'll use the standard shift-and-XOR approach:

Register (4 bits): 0000
Poly (without MSB): 0011

Process bit sequence from left:

Bit 1: Input=1, Reg=0000, MSB=0, Shift→0001, No XOR (MSB was 0)
Bit 1: Input=0, Reg=0001, MSB=0, Shift→0010, No XOR
Bit 1: Input=1, Reg=0010, MSB=0, Shift→0101, No XOR  
Bit 1: Input=1, Reg=0101, MSB=0, Shift→1011, No XOR
Bit 0: Input=0, Reg=1011, MSB=1, Shift→0110, XOR 0011→0101
Bit 0: Input=0, Reg=0101, MSB=0, Shift→1010, No XOR
Bit 1: Input=1, Reg=1010, MSB=1, Shift→0101, XOR 0011→0110
Bit 1: Input=1, Reg=0110, MSB=0, Shift→1101, No XOR
Bit 0: Input=0, Reg=1101, MSB=1, Shift→1010, XOR 0011→1001
Bit 0: Input=0, Reg=1001, MSB=1, Shift→0010, XOR 0011→0001
Bit 0: Input=0, Reg=0001, MSB=0, Shift→0010, No XOR
Bit 0: Input=0, Reg=0010, MSB=0, Shift→0100, No XOR

Final Register (CRC) = 0100

CRC = 0100

Codeword T = 10110011 0100 = 101100110100

CRC's elegance shines in hardware. A Linear Feedback Shift Register (LFSR) computes CRC one bit at a time using only:

• r flip-flops (one per CRC bit, where r = polynomial degree)
• XOR gates (one per polynomial term, minus the leading and constant)
• A feedback path from the output to specific positions

The LFSR Structure:

For generator G(x) = x^r + g_{r-1}x^{r-1} + ... + g₁x + 1:

                        Feedback ←────────────────┐
                                                   │
    ┌─────┐   ┌─────┐   ┌─────┐       ┌─────┐    │
───►│ XOR ├──►│  D  ├──►│  D  ├─ ... ─│  D  ├────┘
    └─────┘   └──┬──┘   └──┬──┘       └──┬──┘    
       │         │g₁       │g₂         │g_{r-1}
       │     ┌───┴───┐ ┌───┴───┐   ┌───┴───┐
       │     │  XOR  │ │  XOR  │   │  XOR  │
       │     └───────┘ └───────┘   └───────┘
       └─────────────────────────────────────►
              (only connects where gᵢ = 1)

The XOR gates are placed between flip-flops at positions where the polynomial has a coefficient of 1.

Example: G(x) = x³ + x + 1 (1011)

Polynomial terms: x³, x¹, x⁰ (constant)

XOR feedback at position 1 (for the x term):

                    ┌──────────────────┐
                    │    Feedback      │
                    ▼                  │
Data ──►┌─────┐  ┌─────┐  ┌─────┐  ┌─────┐──►
   In   │ XOR ├─►│ D₀  ├─►│ XOR ├─►│ D₁  ├─►│ D₂  │─►Out
        └─────┘  └─────┘  └──┬──┘  └─────┘  └─────┘
                             │                 ▲
                             └─────────────────┘
                           (XOR for x term)

Operation:

1. Initialize register to 0 (or all 1s, depending on standard)
2. For each message bit:
   • Shift register left by one
   • New D₀ = (input XOR feedback)
   • D₁ = D₀ XOR feedback (because of x term)
   • D₂ = D₁
3. After all message bits, feed in r zeros (or use special technique)
4. Register contains the CRC

While hardware uses shift registers, software implementations optimize differently. The main techniques are:

1. Bit-by-Bit (Direct Implementation)

Process one bit at a time, mirroring the hardware approach:

uint32_t crc_bitwise(uint8_t *data, size_t len, uint32_t poly) {
    uint32_t crc = 0xFFFFFFFF;  // Common initialization
    
    for (size_t i = 0; i < len; i++) {
        crc ^= (uint32_t)data[i] << 24;  // Align byte to MSB
        
        for (int bit = 0; bit < 8; bit++) {
            if (crc & 0x80000000)         // Check MSB
                crc = (crc << 1) ^ poly;   // Shift and XOR
            else
                crc <<= 1;                 // Just shift
        }
    }
    return crc ^ 0xFFFFFFFF;  // Final XOR (common)
}

This is slow: 8 branches per byte, hard to pipeline.

2. Table-Driven (Byte-at-a-Time)

Precompute a 256-entry table where entry i gives the CRC contribution of byte value i:

uint32_t crc_table[256];  // Precomputed

void init_crc_table(uint32_t poly) {
    for (int i = 0; i < 256; i++) {
        uint32_t crc = i << 24;
        for (int bit = 0; bit < 8; bit++) {
            crc = (crc << 1) ^ ((crc & 0x80000000) ? poly : 0);
        }
        crc_table[i] = crc;
    }
}

uint32_t crc_table_driven(uint8_t *data, size_t len) {
    uint32_t crc = 0xFFFFFFFF;
    
    for (size_t i = 0; i < len; i++) {
        uint8_t index = (crc >> 24) ^ data[i];
        crc = (crc << 8) ^ crc_table[index];
    }
    return crc ^ 0xFFFFFFFF;
}

This processes 8 bits per iteration with a single table lookup—8x faster than bit-by-bit.

3. Slicing-by-N (Multiple Tables)

Process N bytes at once using N tables. 'Slicing-by-8' processes 8 bytes per iteration:

• 8 tables of 256 entries each (8 KB total)
• Each iteration: XOR current CRC with 8 bytes, combine 8 table lookups
• Up to 8x faster than single-table on modern CPUs with cache

4. Hardware Intrinsics (CRC32C)

Modern x86_64 CPUs have PCLMULQDQ (carry-less multiplication) and CRC32 instructions:

// Intel CRC32C intrinsic (for iSCSI/SCTP polynomial)
uint32_t crc = _mm_crc32_u64(crc, *((uint64_t*)data));

This computes 8 bytes of CRC in a single cycle—fastest possible.

Real CRC implementations include several variations from the 'pure' algorithm. Understanding these is essential for interoperability.

1. Initial Value (Seed)

Instead of starting with register = 0, many standards initialize to all 1s (0xFFFFFFFF for CRC-32).

Why? An all-zeros message with all-zeros CRC is technically valid. Initializing to 1s ensures that leading zeros in the message affect the CRC.

2. Final XOR (Complement)

After processing, XOR the result with a constant (often all 1s).

Why? Combined with 0xFFFFFFFF initialization, this ensures that appending zeros to a message doesn't leave the CRC unchanged. It also provides some defense against implementation bugs.

3. Bit and Byte Reflection

Some standards reflect (reverse) bits within each byte, or reflect the entire final CRC.

Why? Historical reasons—some early hardware processed LSB first (UART-style). 'Reflected' CRCs become standard for compatibility.

RefIn (Input Reflection): Process each byte LSB-first instead of MSB-first.

RefOut (Output Reflection): Reverse all bits of the final CRC before output.

Example: For CRC-32 (Ethernet), you:

1. Initialize to 0xFFFFFFFF
2. Reflect each input byte (process LSB first)
3. Compute CRC
4. Reflect the 32-bit result
5. XOR with 0xFFFFFFFF

These details are critical for interoperability. Using the wrong reflection or init value produces a different (and incompatible) CRC.

We've covered the complete CRC calculation procedure, from conceptual framework to practical implementation. Let's consolidate:

What's Next:

With CRC calculation mastered, we turn to the receiver's perspective: CRC verification. How does the receiver confirm that received data is error-free? As we'll see, there are two equivalent approaches—recomputing and comparing the CRC, or dividing the entire codeword and checking for zero remainder.