2026-05-08
Every Ethernet frame, every SATA sector, every CAN bus message carries a CRC (Cyclic Redundancy Check) appended to its tail. Software engineers see CRC32 as a hash function. Hardware engineers see it as a shift register with a few XOR taps — and that view explains why CRCs catch the errors they catch.
A CRC treats your message as a giant polynomial over GF(2) (coefficients are 0 or 1, addition is XOR). You divide it by a fixed generator polynomial and the remainder is the CRC. The math sounds intimidating, but the hardware is embarrassingly simple.
The LFSR-style implementation. For generator polynomial G(x), you build a shift register of degree N (the polynomial's order) with XOR gates inserted at each tap position corresponding to a non-zero coefficient. Data bits feed in serially; on each clock edge:
After clocking in all message bits (plus N zero bits), the register contains the CRC. That's it — no division unit, no lookup table, just N flip-flops and a handful of XOR gates.
Real example: CRC-16-CCITT. The generator is x¹⁶ + x¹² + x⁵ + 1 (0x1021). You need 16 flip-flops and exactly 3 XOR gates — taps after bits 0, 5, and 12. This guards every Bluetooth, XMODEM, and HDLC frame in existence. At 1 GHz, you process one bit per cycle = 1 Gbps with maybe 50 gates total.
Parallel CRC for real throughput. Serial CRC at 1 bit/cycle won't keep up with a 100 Gbps Ethernet MAC. The trick: unroll the recurrence. If the next state is a linear function of current state and one input bit, then the state after 64 bits is a linear function of the current state and 64 input bits. You compute the equivalent XOR network at design time and synthesize it as one combinational block. A 64-bit-wide CRC32 engine is roughly ~200 XOR gates in 3-4 levels of logic — fast enough for terabit links.
Rule of thumb for error detection: A CRC of degree N detects:
So CRC32 misses roughly 1 in 4 billion random bit-flips — which is why it's the workhorse of every link layer that matters.