CRC — Overview, Families & Architecture
Overview
Cyclic Redundancy Checks (CRCs) are polynomial-based error‑detection codes used in communication systems, networking, storage, and embedded applications. They detect burst errors, bit flips, and protocol‑level corruption with extremely low hardware cost.
CRCs operate over GF(2) and are implemented using linear feedback shift registers (LFSRs), XOR networks, and parallel datapath expansions.
1. Fundamentals of CRC Computation
CRC computation is equivalent to dividing the input bitstream by a generator polynomial over GF(2). All operations use XOR (addition/subtraction) and AND (multiplication), with no carries or borrows.
A CRC is fully defined by:
- generator polynomial
- initial value
- final XOR value
- input reflection (RefIn)
- output reflection (RefOut)
- bit ordering (LSB‑first or MSB‑first)
Two CRCs with the same width may behave differently if any of these parameters differ.
2. CRC Families
CRCs are grouped by width and protocol usage.
CRC‑8
Used in sensors, 1‑Wire, ATM, low‑bandwidth protocols.
CRC‑16
Used in telecom, USB, HDLC, industrial protocols.
CRC‑32
Used in Ethernet, storage, compression, multimedia.
CRC‑64
Used in high‑reliability storage and archival systems.
3. Common CRC Variants (Representative Table)
| Name | Width | Polynomial (hex) | Init | XOR Out | RefIn | RefOut | Typical Use |
|---|---|---|---|---|---|---|---|
| CRC‑8 ATM | 8 | 0x07 | 0x00 | 0x00 | No | No | ATM, telecom |
| CRC‑8 Maxim | 8 | 0x31 | 0x00 | 0x00 | Yes | Yes | 1‑Wire devices |
| CRC‑16 IBM | 16 | 0x8005 | 0x0000 | 0x0000 | Yes | Yes | Legacy protocols |
| CRC‑16 CCITT | 16 | 0x1021 | 0xFFFF | 0x0000 | No | No | Telecom, HDLC |
| CRC‑16 USB | 16 | 0x8005 | 0xFFFF | 0xFFFF | Yes | Yes | USB packets |
| CRC‑32 Ethernet | 32 | 0x04C11DB7 | 0xFFFFFFFF | 0xFFFFFFFF | Yes | Yes | Ethernet MAC |
| CRC‑32 Castagnoli | 32 | 0x1EDC6F41 | 0xFFFFFFFF | 0xFFFFFFFF | Yes | Yes | Storage, iSCSI |
| CRC‑32 MPEG‑2 | 32 | 0x04C11DB7 | 0xFFFFFFFF | 0x00000000 | No | No | MPEG‑2 TS |
| CRC‑64 ECMA | 64 | 0x42F0E1EBA9EA3693 | 0x0000000000000000 | 0x0000000000000000 | No | No | Storage, archives |
CRCs with the same width may differ in reflection rules, initial value, final XOR, or bit ordering.
4. Architectural Model
Polynomial Division
The CRC remainder is computed by dividing the input stream by the generator polynomial. The remainder is the CRC.
Shift‑Register Structure
Most CRCs use an LFSR‑like structure:
- register holds intermediate remainder
- XOR gates implement feedback taps
- each input bit updates the register
Reflection Rules
Protocols may require:
- RefIn: reverse input bits
- RefOut: reverse output bits
- Final XOR: apply a constant mask
These must match the protocol exactly.
5. Architectural Variants
Serial CRC
- 1 bit per cycle
- minimal hardware
- deterministic latency
- ideal for low‑throughput systems
Parallel CRC
- N bits per cycle (4/8/16/32/64)
- XOR matrix derived from polynomial
- used in MACs, PHYs, storage controllers
Pipelined CRC
- pipeline stages inserted into XOR network
- required for multi‑GHz datapaths
- common in ASIC and high‑performance FPGA designs
Table‑Based CRC (software)
Used in CPUs, not in RTL hardware.
6. Parallel CRC Computation
Parallel CRCs are derived by unrolling the serial LFSR for N steps.
Each next‑state CRC bit is expressed as XOR of:
- previous CRC bits
- input bits
The XOR matrix depends on:
- polynomial
- reflection rules
- input width
Example: CRC‑32 Ethernet
- polynomial: 0x04C11DB7
- reflected input/output
- init = 0xFFFFFFFF
- final XOR = 0xFFFFFFFF
Common widths:
- 4‑bit (100 Mbps MACs)
- 8‑bit (1 Gbps MACs)
- 32‑bit (10G MACs)
Each width requires a different XOR matrix.
7. How to Generate Parallel CRC Equations
Three methods:
- Matrix method (general and rigorous)
- Symbolic unrolling
- Automated generation (Python/MATLAB)
Matrix method:
- represent CRC LFSR as matrix A
- represent input influence as matrix B
- compute A^N and \sum A^kB
- extract XOR equations
Works for any polynomial, width, reflection rule, or input size.
8. Practical Implementation Notes
- XOR depth grows with input width
- pipelining may be required
- reflected vs non‑reflected CRCs produce different equations
- initial value and final XOR must be applied correctly
- verification requires golden models and standard test vectors (“123456789”)
- CRC must be updated only on valid bytes in MACs
9. Applications
CRCs are used in:
- Ethernet (CRC‑32)
- USB (CRC‑5, CRC‑16)
- PCIe (CRC‑32)
- SATA (CRC‑32)
- storage controllers
- avionics and automotive protocols
- compression and multimedia formats
They provide strong error detection with minimal hardware.
