CRC

Part 10 · Reliability and Recovery · Working (W)

On this page

A link protocol adds a check to every packet. The first version uses a simple checksum: add up the bytes. In testing, a noise burst flips a bit from 0 to 1 in one byte and from 1 to 0 in the next. The sum is unchanged, the checksum passes, and corrupted data is delivered. A CRC of the same size would have caught it, and every burst like it, every time.

What makes a CRC good at catching the errors links actually see?

The obvious answer, and why it breaks

The obvious check is a sum: cheap, simple, and it catches most single changes. But addition is forgiving in exactly the wrong way: errors that cancel (one bit up, another down; two bytes swapped) leave the sum unchanged, and a burst on a serial wire easily produces such patterns. A good link check should be very unlikely to be fooled by the error patterns the channel produces, especially bursts.

The idea: the remainder of a division

Treat the message bits as the coefficients of a polynomial and divide it by a fixed generator polynomial of degree r, using arithmetic where addition is XOR (no carries). The r-bit remainder is the CRC, sent with the message. The receiver divides again; any change to the message changes the remainder unless the error pattern is itself an exact multiple of the generator.

That last condition gives CRCs their guarantee. A burst of length r or less, as a polynomial, cannot be a multiple of a degree-r generator that has a constant term. So a CRC with an r-bit generator detects every burst of up to r bits, and longer, random error patterns slip through only about once in 2^r.

One clock per bit: the incoming bit XORed with the register's top bit decides whether the generator is added in as the register shifts.

Build it: CRC-8, serial and parallel

This is DCLink's CRC-8: generator x⁸ + x² + x + 1 (0x07), initial value 0. The serial version takes one bit per cycle; the parallel version unrolls eight bit steps into combinational logic and takes one byte per cycle. Both process the message "1234" and must agree with each other and with a one-step reference.

tb.sv

// DCLink's CRC-8 (polynomial x^8 + x^2 + x + 1, initial value 0x00) computed two
// ways over the same 4-byte message: serially, one bit per cycle with a shift
// register, and in parallel, one byte per cycle with a combinational next-state
// function. The checker compares the two with each other and with the same
// division done in one step in the testbench.
module tb;
  logic clk = 0;
  always #5 clk = ~clk;
  initial begin $dumpfile("wave.vcd"); $dumpvars(0, tb); end

  localparam logic [7:0] POLY = 8'h07;            // x^8 + x^2 + x + 1, x^8 implicit
  logic [7:0] msg [0:3];
  initial begin msg[0] = 8'h31; msg[1] = 8'h32; msg[2] = 8'h33; msg[3] = 8'h34; end  // "1234"

  // One bit into the CRC (MSB first)
  function automatic logic [7:0] crc_bit(input logic [7:0] c, input logic b);
    logic fb;
    fb = c[7] ^ b;
    return {c[6:0], 1'b0} ^ (fb ? POLY : 8'h00);
  endfunction
  // One byte into the CRC: eight bit steps unrolled into combinational logic
  function automatic logic [7:0] crc_byte(input logic [7:0] c, input logic [7:0] d);
    logic [7:0] r;
    r = c;
    for (int i = 7; i >= 0; i--) r = crc_bit(r, d[i]);
    return r;
  endfunction

  int cyc = 0;
  always @(posedge clk) cyc <= cyc + 1;
  // Serial: one bit per cycle, 32 cycles, starting in cycle 1
  logic [7:0] crc_s = 0;
  int bit_i = 0;
  always @(posedge clk) if (cyc >= 1 && bit_i < 32) begin
    crc_s <= crc_bit(crc_s, msg[bit_i / 8][7 - (bit_i % 8)]);
    bit_i <= bit_i + 1;
  end
  // Parallel: one byte per cycle, 4 cycles, starting in cycle 1
  logic [7:0] crc_p = 0;
  int byte_i = 0;
  always @(posedge clk) if (cyc >= 1 && byte_i < 4) begin
    crc_p <= crc_byte(crc_p, msg[byte_i]);
    byte_i <= byte_i + 1;
  end

  // Reference: the same division done in the testbench, all at once
  logic [7:0] ref_crc;
  initial begin
    ref_crc = 0;
    for (int k = 0; k < 4; k++) ref_crc = crc_byte(ref_crc, msg[k]);
  end
  initial begin
    #400;
    if (crc_s == crc_p && crc_p == ref_crc) $display("PASS: serial (32 cycles) and parallel (4 cycles) CRC-8 agree: 0x%02h", crc_p);
    else $display("FAIL: serial %02h parallel %02h reference %02h", crc_s, crc_p, ref_crc);
    $finish;
  end
endmodule

crc_byte is just crc_bit applied eight times; synthesis turns those eight steps into a small XOR network, which is how real links compute CRCs over 32 or more bits per cycle.

Watch it run

How to read it, slot by slot:

Slots 0 to 3: the parallel CRC takes one byte per cycle (byte_i 0 to 3); crc_p passes through 0x97, 0x72 and 0xC0 and reaches the final value, 0xC2, in slot 4.
Same slots, serial: crc_s takes one bit per cycle. The first two bits of "1" (0x31) are 0 and change nothing; the register becomes 0x07 when the first 1 arrives. It will need 32 cycles to reach 0xC2.

Check it: the reference and what it detects

The reference model computes the same CRC bit by bit, confirms 0xC2 for "1234", then flips bursts in a 32-byte payload and counts how many go undetected.

example.py

"""Reference CRC-8 (polynomial x^8 + x^2 + x + 1, initial 0) and what it detects.

The CRC is the remainder of dividing the message, as a polynomial over bits, by
the generator polynomial. The model computes it bit by bit, checks the value the
lesson's RTL produces for "1234", and then tests error patterns: every burst of
up to 8 bits is detected; longer bursts slip through about 1 time in 256.
"""
import random

POLY = 0x07


def crc8(data, crc=0):
    for byte in data:
        for i in range(7, -1, -1):
            fb = ((crc >> 7) & 1) ^ ((byte >> i) & 1)
            crc = ((crc << 1) & 0xFF) ^ (POLY if fb else 0)
    return crc


msg = b"1234"
c = crc8(msg)
print(f'CRC-8 of "1234": 0x{c:02X}')
assert c == 0xC2


def flip_burst(data, start, length):
    """Flip a burst: first and last bits flipped, the bits between random."""
    bits = int.from_bytes(data, "big")
    n = len(data) * 8
    pattern = (1 << (length - 1)) | 1 if length > 1 else 1
    rng = random.Random(start * 31 + length)
    for k in range(1, length - 1):
        if rng.random() < 0.5:
            pattern |= 1 << k
    bits ^= pattern << (n - start - length)
    return bits.to_bytes(len(data), "big")


frame = bytes(range(32))                         # a 32-byte payload
good = crc8(frame)
for length in (1, 2, 5, 8):
    missed = sum(crc8(flip_burst(frame, s, length)) == good for s in range(0, 256 - length))
    print(f"bursts of {length:2d} bits: {missed} missed of {256 - length}")
    assert missed == 0
rng = random.Random(1)
trials, missed = 20000, 0
for _ in range(trials):
    length = rng.randint(9, 64)
    s = rng.randrange(0, 256 - length)
    missed += crc8(flip_burst(frame, s, length)) == good
print(f"random longer bursts (9-64 bits): {missed} missed of {trials} (about 1 in {trials // max(missed, 1)})")
assert 0 < missed < trials / 100
print("PASS: CRC-8 catches every burst up to 8 bits; longer bursts escape about 1 time in 256")

It prints:

Diagram

CRC-8 of "1234": 0xC2
bursts of  1 bits: 0 missed of 255
bursts of  2 bits: 0 missed of 254
bursts of  5 bits: 0 missed of 251
bursts of  8 bits: 0 missed of 248
random longer bursts (9-64 bits): 66 missed of 20000 (about 1 in 303)
PASS: CRC-8 catches every burst up to 8 bits; longer bursts escape about 1 time in 256

Every burst of up to 8 bits, at every position, is caught. Longer random bursts get through about once in 256 (here 66 of 20,000, about one in 303, close to 2⁻⁸ for a test of this size). That is why real links use 16- or 32-bit CRCs: a 32-bit CRC lets a random long error pattern through about once in four billion.

How real protocols chose

Protocol	CRC
Ethernet	CRC-32 frame check sequence at the end of every frame.
PCI Express	A 32-bit LCRC on every packet, checked at each link; an optional 32-bit ECRC end to end (lesson 10.14).
USB, CAN and many others	CRCs of 5 to 16 bits sized to their packet lengths.
DCLink (step 9)	CRC-8, polynomial x⁸ + x² + x + 1, initial value 0, over header and payload.

What breaks

The opening checksum (illustrative) missed a burst that flipped bits in opposite directions in neighbouring bytes. Replacing it with a CRC of the same width removed that blind spot entirely. A second, classic mistake is a mismatch in CRC conventions between two ends: bit order, initial value or final inversion. Both ends must agree on every one, which is why protocols specify them exactly.

Check yourself A 16-bit CRC: which bursts is it guaranteed to detect?

Every burst of 16 bits or fewer (for a generator with a constant term).

Check yourself Why does the parallel CRC take 4 cycles for 4 bytes while the serial one takes 32?

The parallel version unrolls eight one-bit steps into combinational logic, processing a whole byte per cycle.

Key takeaways

A CRC is the remainder of dividing the message by a generator polynomial, with XOR arithmetic.
An r-bit CRC catches every burst up to r bits; longer random errors escape about once in 2^r.
Build it as a shift register (serial) or an XOR network (parallel), and specify every convention exactly.

Navigate

The obvious answer, and why it breaks

The idea: the remainder of a division

Build it: CRC-8, serial and parallel

Watch it run

Check it: the reference and what it detects

How real protocols chose

What breaks

Key takeaways

Related topics

CRC

The obvious answer, and why it breaks

The idea: the remainder of a division

Build it: CRC-8, serial and parallel

Watch it run

Check it: the reference and what it detects

How real protocols chose

What breaks

Key takeaways

Related topics

The obvious answer, and why it breaks

The idea: the remainder of a division

Build it: CRC-8, serial and parallel

Watch it run

Check it: the reference and what it detects

How real protocols chose

What breaks

Key takeaways

Related topics

Up next

The obvious answer, and why it breaks

The idea: the remainder of a division

Build it: CRC-8, serial and parallel

Watch it run

Check it: the reference and what it detects

How real protocols chose

What breaks

Key takeaways

Related topics

Up next