CRC - Cyclic Redundancy Check

Not all CRC algorithms are created equal. The seemingly simple polynomial you choose as your 'generator' determines everything about your error detection capability: which errors are guaranteed to be caught, which might slip through, and how efficiently the algorithm runs.

The generator polynomial G(x) is to CRC what a key is to cryptography—it defines the algorithm's behavior entirely. Unlike cryptographic keys that should be secret, CRC generators are public standards, but they are chosen with equal mathematical care.

Why does CRC-32 use x³² + x²⁶ + x²³ + x²² + x¹⁶ + x¹² + x¹¹ + x¹⁰ + x⁸ + x⁷ + x⁵ + x⁴ + x² + x + 1? This isn't arbitrary—it's the result of extensive mathematical analysis and exhaustive computer search. This page reveals the science behind generator polynomial selection.

The generator polynomial G(x) is the fixed divisor polynomial used in all CRC operations. It has two critical roles:

1. At the sender: G(x) is used to compute the CRC remainder from the message
2. At the receiver: G(x) is used to verify that the received data + CRC has no errors

Formal Definition:

A generator polynomial of degree r has the form:

$$G(x) = x^r + g_{r-1}x^{r-1} + ... + g_1x + g_0$$

where each coefficient $g_i \in {0, 1}$ (we're in GF(2)).

Critical Constraints:

1. The leading coefficient must be 1 — This is automatic since we write the highest-degree term
2. The constant term g₀ must be 1 — This ensures single-bit errors are always detected
3. The polynomial should be 'primitive' or have (x+1) as a factor — For maximum error detection

The degree of the generator polynomial directly determines the length of the CRC checksum—and consequently, its error detection power.

The Fundamental Relationship:

If G(x) has degree r, then the CRC is r bits long.

This follows from polynomial division: when dividing by a polynomial of degree r, the remainder has degree at most r-1, requiring r bits to represent.

Why Higher Degree = Better Detection:

Consider what 'undetectable error' means: E(x) must be divisible by G(x). For a degree-r generator:

1. There are 2^r possible remainders (r-bit values)
2. Only one remainder (zero) indicates 'no error'
3. Random errors have probability 2^(-r) of producing zero remainder

So CRC-8 has ~1 in 256 chance of missing a random error, while CRC-32 has ~1 in 4 billion chance.

Tradeoff: Protection vs. Overhead:

Higher-degree CRCs provide better protection but add more overhead:

• CRC-8: 8 bits overhead (1 byte) — suitable for short messages
• CRC-16: 16 bits overhead (2 bytes) — good balance for medium links
• CRC-32: 32 bits overhead (4 bytes) — standard for Ethernet, ZIP, PNG
• CRC-64: 64 bits overhead (8 bytes) — used in high-reliability storage

The Overhead Percentage:

For a 1500-byte Ethernet frame:

• CRC-32 adds 4 bytes → 4/1500 = 0.27% overhead
• For short 64-byte frames → 4/64 = 6.25% overhead

For typical network traffic, 32-bit CRC overhead is negligible compared to the protection gained.

One of the most important design decisions for generator polynomials is whether to include (x + 1) as a factor. This seemingly simple factor provides a powerful guarantee.

The Parity Connection:

In GF(2), (x + 1) evaluated 'at x = 1' gives 1 + 1 = 0. But we don't evaluate polynomials—instead, we observe that:

A polynomial P(x) is divisible by (x + 1) if and only if P(x) has an even number of terms.

This is because adding an odd number of 1s in GF(2) gives 1, not 0. For (x+1) to divide P(x), the 'sum of coefficients' must be 0 in GF(2), meaning even parity.

What This Means for Errors:

If G(x) has (x + 1) as a factor, then for any valid codeword C(x), C(x) is also divisible by (x+1), meaning C(x) has an even number of 1s.

An odd number of bit flips would produce an odd number of 1s, which is NOT divisible by (x+1), so the error is detected.

Example: CRC-16-CCITT

G(x) = x¹⁶ + x¹² + x⁵ + 1 = (x + 1)(x¹⁵ + x¹⁴ + x¹³ + x¹² + x⁴ + x³ + x² + x + 1)

Because (x+1) divides G(x), CRC-16-CCITT detects:

• All single-bit errors (1 bit flipped = odd)
• All triple-bit errors (3 bits flipped = odd)
• All errors with odd number of corrupted bits

The Double-Bit Error Detection:

A two-bit error is E(x) = xⁱ + xʲ where i ≠ j. For this to be divisible by G(x), it must be divisible by (x+1), meaning i + j must be even... but wait, we need to think more carefully.

Actually, xⁱ + xʲ has exactly 2 terms, which is even, so it IS divisible by (x+1). Does this mean double-bit errors are undetected?

No! The generator usually has additional factors. For example, if G(x) = (x+1) · P(x) where P(x) is an irreducible polynomial, then xⁱ + xʲ = xʲ(xⁱ⁻ʲ + 1) must also be divisible by P(x). This additional constraint catches double-bit errors.

Beyond the (x+1) factor, the other component of an optimal CRC generator is typically a primitive polynomial. These special polynomials maximize error detection capability.

What Makes a Polynomial Primitive?

A polynomial P(x) of degree n is primitive if:

1. P(x) is irreducible — cannot be factored into lower-degree polynomials in GF(2)
2. x is a primitive element of the extension field GF(2ⁿ) defined by P(x)

In practical terms: P(x) divides x^(2ⁿ-1) + 1 but does not divide x^k + 1 for any smaller k.

The Period of a Polynomial:

The period of P(x) is the smallest positive integer p such that P(x) divides x^p + 1.

For a primitive polynomial of degree n: period = 2ⁿ - 1 (the maximum possible).

This is critical because it determines the length of data that can be protected effectively.

Why Primitive Polynomials Excel at Error Detection:

1. Maximal period — They don't divide x^k + 1 for any small k, so errors like xⁱ + x⁰ = xⁱ + 1 are detected for all i < 2ⁿ - 1

2. All single-bit errors detected — x^i is never divisible by a primitive polynomial (since the polynomial has a constant term)

3. All double-bit errors in message up to length 2ⁿ-1 detected — If the primitive polynomial has degree n, it detects all double-bit errors where the bits are fewer than 2ⁿ-1 positions apart

4. Burst detection optimality — Maximum protection for burst errors up to the polynomial degree

The most powerful CRC generators combine the (x+1) factor with a primitive polynomial:

$$G(x) = (x + 1) \cdot P(x)$$

where P(x) is a primitive polynomial of degree r-1.

This combination provides:

1. From (x+1): Detection of all odd-bit-count errors
2. From P(x): Detection of all double-bit errors up to message length 2^(r-1) - 1
3. Combined: Detection of all bursts up to length r

Example: CRC-16-CCITT

G(x) = x¹⁶ + x¹² + x⁵ + 1

This can be shown to equal (x + 1) times a primitive polynomial of degree 15. Properties:

• Detects all single-bit errors
• Detects all double-bit errors if message < 32,767 bits (about 4KB)
• Detects all odd-bit-count errors
• Detects all bursts ≤ 16 bits (100% guaranteed)
• Detects most bursts > 16 bits (probability 1 - 2⁻¹⁵ ≈ 99.997%)

Exhaustive Search for Optimal Polynomials:

For high-reliability applications, researchers conduct exhaustive computer searches to find the 'best' polynomial for a given degree. The criteria include:

1. Minimum Hamming distance — What's the minimum number of bit changes that produce a valid codeword? Higher is better.

2. Undetected error probability — For the expected error distribution, what fraction go undetected?

3. Implementation efficiency — Fewer terms means fewer XOR gates in hardware

The CRC-32 polynomial used in Ethernet was chosen in the 1970s through early computer analysis by Wesley Peterson and others. It represents a local optimum for 32-bit CRCs over typical network conditions.

Why Use Standard Polynomials?

It might seem attractive to 'roll your own' CRC polynomial for a custom application. After all, any polynomial with the right properties should work, right? Here's why you should almost always use a standard:

1. Extensive Vetting: Standard polynomials have been analyzed by mathematicians, tested by implementers, and validated by years of production use

2. Known Weaknesses: Any discovered weaknesses in standard polynomials are publicly documented, allowing informed decisions

3. Hardware Support: FPGAs, NICs, and CPUs have hardware acceleration for standard CRCs (especially CRC-32)

4. Interoperability: Using standard CRCs allows your data to be verified by standard tools

5. Library Availability: Every platform has optimized implementations of standard CRCs

Historical Note: The Quest for 'Perfect' CRCs

In the 1990s and 2000s, researchers used increasingly powerful computers to search for optimal polynomials. Notably, Philip Koopman and colleagues exhaustively analyzed billions of polynomials to identify the truly optimal choices for various degrees and message lengths.

Their research showed that some 'standard' polynomials are actually suboptimal—CRC-32C (used in iSCSI, SCTP) provides better detection than the original CRC-32 for many error patterns. However, backward compatibility often trumps optimality, so older standards persist.

The lesson: standards represent engineering compromises, not absolute perfection. They're good enough for their intended use cases, even if theoretically better options exist.

Generator polynomials appear in documentation and code in several forms. Understanding these representations is essential for implementing or analyzing CRC algorithms.

1. Mathematical Notation:

$$G(x) = x^{16} + x^{12} + x^5 + 1$$

This is the clearest representation but verbose for large polynomials.

2. Full Binary:

Write all bits from x^n down to x^0:

x¹⁶ + x¹² + x⁵ + 1 → 10001000000100001 (17 bits for degree 16)

3. Hexadecimal (Standard Form):

Convert binary to hex:

10001000000100001 → 0x11021

4. Truncated Representation:

Omit the leading 1 (since it's always present for the highest-degree term):

x¹⁶ + x¹² + x⁵ + 1 → 0x1021 (only 16 bits)

This is common in code because the CRC register is exactly n bits for a degree-n polynomial.

We've explored the critical role of generator polynomials in CRC error detection. Let's consolidate the key insights:

What's Next:

With the theory of generator polynomials established, we're ready to apply it. The next page covers the CRC calculation procedure—the step-by-step process for computing the CRC value given a message and generator polynomial. We'll see how the sender constructs the transmitted codeword and how this connects to what we've learned about polynomial division.