Signal Processing

Cyclic Redundancy Check (CRC)

Q: How many bit errors can a CRC-32 guarantee to detect?

A CRC guarantees detection of all error patterns up to a Hamming distance one less than the minimum distance of the code for a given frame length. The IEEE 802.3 CRC-32 polynomial (0x04C11DB7) has a minimum Hamming distance of 4 for frames up to 11,455 bits, meaning it detects all 1-bit, 2-bit, and 3-bit errors, all odd numbers of errors (because the polynomial includes the factor x+1), and every burst error up to 32 bits long. Beyond the HD=4 frame length the guarantee drops to HD=3. For longer frames the fraction of undetected random errors approaches 2 raised to the minus 32, about 1 in 4.3 billion, regardless of frame size.

Q: Why does the CRC generator polynomial include the factor (x + 1)?

Including the factor x+1 makes the CRC detect every error pattern that contains an odd number of flipped bits. The product of a polynomial multiplied by an error pattern with odd weight always has a nonzero remainder when the divisor contains x+1, because x+1 evaluated at x=1 forces the parity check. This is why standard polynomials such as CRC-16-CCITT (0x1021 implies 0x11021 with the implicit high bit) and CRC-32 are chosen to be the product of (x+1) and a primitive polynomial of degree n-1. The primitive factor maximizes the burst-error and double-error detection length, while the x+1 factor guarantees odd-error and single-bit-error detection.

Q: How is a CRC computed in hardware at line rate?

In hardware a CRC is computed with a linear feedback shift register (LFSR) whose tap positions correspond to the nonzero terms of the generator polynomial. Each incoming bit is XORed with the register feedback and shifted; after the whole frame plus n appended zero bits has been clocked through, the register holds the remainder. For high-speed RF and optical links running at 10 to 100 Gbit/s, designers parallelize the LFSR to process 8, 32, 64, or 512 bits per clock by precomputing the equivalent state-transition matrix, trading logic gates for throughput. A table-driven software equivalent uses a 256-entry lookup table to process one byte per iteration.

/ˈsɪklɪk rɪˈdʌndənsi tʃɛk/ · spelled out C-R-C

Treating a block of transmitted bits as the coefficients of a binary polynomial, a cyclic redundancy check divides that message by a fixed generator polynomial and appends the remainder as a check value, letting the receiver recompute the division and flag any nonzero remainder as a corrupted frame. Implemented as a linear feedback shift register, the CRC is the dominant error-detection mechanism in digital RF and wired links: it catches every burst error shorter than the check field, all single and double bit flips within the design length, and any odd number of errors. Standard variants such as CRC-32 in Ethernet frames and CRC-16 in HDLC and Bluetooth payloads reduce the residual undetected-error probability to roughly 2^-n, which complements the corrective action of a bit-error-rate budget rather than fixing the errors itself.

Category: Signal Processing

Common widths: 8, 16, 24, 32 bits

Residual error rate: ≈ 2^-n

How Polynomial Division Detects Errors

The mathematics behind a cyclic redundancy check live in the field of polynomials over GF(2), where addition and subtraction are both the exclusive-OR operation and there are no carries. A message of k bits is interpreted as a degree k-1 polynomial M(x). To form an n-bit CRC, the transmitter multiplies M(x) by xⁿ (a left shift of n zero bits) and divides by the chosen generator polynomial G(x) of degree n. The remainder R(x), always of degree less than n, becomes the frame check sequence that is appended to the message. The transmitted codeword T(x) = M(x)·xⁿ + R(x) is then exactly divisible by G(x) with zero remainder.

At the receiver the entire incoming codeword, check bits included, is divided by the same G(x). If no bits were disturbed, the remainder is zero and the frame is accepted. Any disturbance can be written as an additive error polynomial E(x), so the received word is T(x) + E(x). Because T(x) is divisible by G(x), the receiver remainder depends only on E(x) mod G(x). An error escapes detection only when E(x) is itself a multiple of G(x), which is why the generator is chosen so that the lowest-degree such multiple is long. This is a pure detection scheme; correcting the flagged frame requires retransmission through an ARQ protocol or a separate coding layer.

Practical RF systems pick the polynomial to match the expected channel impairment. Fading and impulsive interference tend to produce clustered burst errors rather than independent bit flips, and a degree-n CRC catches every burst up to n bits regardless of position. Longer bursts are missed only with probability about 2^-n, so a 32-bit field driven by the IEEE 802.3 generator leaves under 1 in 4 billion frames undetected even on a noisy link.

The Governing Polynomial Equations

Codeword construction (transmit):
T(x) = M(x)·xⁿ + R(x), R(x) = [M(x)·xⁿ] mod G(x)

Receiver check (all arithmetic in GF(2)):
[T(x) + E(x)] mod G(x) = E(x) mod G(x) → accept if ≡ 0

Undetected error probability (random errors):
P_ud ≈ 2^-n × (1 − (1 − p)^L)

Where M(x) = message polynomial, G(x) = degree-n generator, R(x) = remainder (FCS), E(x) = error polynomial, n = CRC width in bits, p = channel bit-error probability, L = frame length. Example: CRC-32 with G(x) = x³²+x²⁶+x²³+…+x+1 gives P_ud ≈ 2.3 × 10^-10.

Common CRC Standards Compared

CRC variant	Width (bits)	Generator (hex)	Hamming distance	Typical use
CRC-8 (ATM HEC)	8	0x07	4 to ~120 bits	ATM cell headers, sensor buses
CRC-16-CCITT	16	0x1021	4 to ~32 kbit	HDLC, Bluetooth, X.25
CRC-24 (OpenPGP)	24	0x864CFB	4 for long frames	OpenPGP, FlexRay
CRC-32 (IEEE 802.3)	32	0x04C11DB7	4 up to 11,455 bits	Ethernet, ZIP, MPEG-2 TS
CRC-32C (Castagnoli)	32	0x1EDC6F41	6 for short frames	iSCSI, SCTP, NVMe

Common Questions

Frequently Asked Questions

How many bit errors can a CRC-32 guarantee to detect?

The IEEE 802.3 CRC-32 (0x04C11DB7) holds a minimum Hamming distance of 4 for frames up to 11,455 bits, so it detects all 1-, 2-, and 3-bit errors, every odd number of errors (the polynomial carries the x+1 factor), and any burst up to 32 bits long. Beyond that length the guarantee falls to HD=3, while the undetected fraction for random errors stays near 2^-32, about 1 in 4.3 billion.

Why does the CRC generator polynomial include the factor (x + 1)?

The x+1 factor forces the CRC to catch every error pattern with an odd number of flipped bits, because such patterns can never be a multiple of a divisor containing x+1. Standard generators are built as the product of (x+1) and a primitive polynomial of degree n−1: the primitive part maximizes burst and double-error detection length, and the x+1 part guarantees odd-error and single-bit detection.

How is a CRC computed in hardware at line rate?

A linear feedback shift register with taps at the nonzero polynomial terms XORs each input bit with the feedback and shifts; after the frame plus n zero bits clock through, the register holds the remainder. For 10 to 100 Gbit/s RF and optical links the LFSR is parallelized to handle 8, 32, 64, or 512 bits per clock by precomputing the state-transition matrix, trading gates for throughput. Software uses a 256-entry table to process one byte per step.

Does a CRC correct errors or only detect them?

A plain CRC only detects errors; it produces a pass or fail verdict and cannot locate or repair a flipped bit. Recovery is left to a higher layer, either an ARQ scheme that requests retransmission of the failed frame or a separate forward-error-correction code such as LDPC or a convolutional code that adds redundancy for correction. Some modern receivers feed the CRC result back to choose between retransmission and FEC in a hybrid-ARQ loop.

Related Terms

← CR 4/8 CRC-Aided SC List →