Loading learning content...
Every Ethernet frame you've ever sent—every packet traversing fiber optic cables, every USB transfer to your flash drive—has been protected by a mathematical technique so powerful that it can detect virtually any realistic transmission error: the Cyclic Redundancy Check (CRC).
At the heart of CRC lies an elegant mathematical operation: polynomial division over the binary field GF(2). While this may sound intimidatingly abstract, the concept is surprisingly intuitive once you understand how binary data can be viewed as polynomials and how division in this context differs from ordinary arithmetic.
This page lays the essential mathematical foundation. Without understanding polynomial representation and modulo-2 division, CRC appears as black-box magic. With this understanding, CRC becomes a beautifully logical and predictable tool in your networking arsenal.
By the end of this page, you will understand how to represent binary data as polynomials, master modulo-2 (XOR-based) arithmetic and its unique properties, perform polynomial long division in GF(2), recognize why this mathematical framework provides exceptionally powerful error detection, and build intuition for how CRC exploits polynomial structure to catch errors.
The first insight of CRC is that any binary string can be represented as a polynomial. This isn't just a clever trick—it unlocks powerful algebraic tools for manipulating and analyzing bit patterns.
The Polynomial Representation:
Consider a binary string of n bits: $b_{n-1}, b_{n-2}, ..., b_1, b_0$ where each $b_i \in {0, 1}$.
This string corresponds to the polynomial:
$$M(x) = b_{n-1}x^{n-1} + b_{n-2}x^{n-2} + ... + b_1x^1 + b_0x^0$$
Each bit becomes a coefficient, and its position (counting from the right, starting at 0) becomes the exponent of x.
| Binary String | Polynomial Representation | Degree |
|---|---|---|
| 1101 | x³ + x² + 1 | 3 |
| 1011 | x³ + x + 1 | 3 |
| 10011 | x⁴ + x + 1 | 4 |
| 11001 | x⁴ + x³ + 1 | 4 |
| 110110 | x⁵ + x⁴ + x² + x | 5 |
| 1000001 | x⁶ + 1 | 6 |
| 1111 | x³ + x² + x + 1 | 3 |
Key Observations:
Why Polynomials?
Polynomials provide structure that raw bit strings lack:
To convert a polynomial back to binary, write out all positions from the degree down to 0, putting 1 where a term exists and 0 where it doesn't. For example, x⁴ + x + 1 has terms at positions 4, 1, 0, so the binary is 10011 (degree 4, so 5 bits: positions 4,3,2,1,0 → 1,0,0,1,1).
CRC doesn't use ordinary arithmetic. Instead, it operates in a mathematical structure called GF(2)—the Galois Field with two elements. This isn't as exotic as it sounds: GF(2) is simply arithmetic where:
Why GF(2)?
GF(2) has a property that makes it perfect for binary computation: addition and subtraction are identical. In regular arithmetic, 1 + 1 = 2 and 1 - 1 = 0, requiring different operations. In GF(2):
$$1 + 1 = 0 \quad \text{(same as } 1 - 1 = 0\text{)}$$ $$1 \oplus 1 = 0 \quad \text{(XOR)}$$
This means we never need to track signs or carries—dramatically simplifying hardware implementation.
| Operation | 0 ⊕ 0 | 0 ⊕ 1 | 1 ⊕ 0 | 1 ⊕ 1 |
|---|---|---|---|---|
| Addition (XOR) | 0 | 1 | 1 | 0 |
| Subtraction (XOR) | 0 | 1 | 1 | 0 |
| × | 0 | 1 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
Critical Properties for CRC:
No Carries: When we add polynomials in GF(2), coefficients don't carry over. Each bit position is independent.
Self-Inverse: Every element is its own additive inverse: $a + a = 0$ for any $a$. This means $a - a = a + a = 0$.
XOR is Reversible: If $a \oplus b = c$, then $a = c \oplus b$ and $b = c \oplus a$. This property is crucial for CRC verification.
Polynomial Arithmetic in GF(2):
When we add polynomials, we XOR corresponding coefficients:
$$(x^3 + x + 1) + (x^3 + x^2 + 1) = x^2 + x$$
In binary: $1011 \oplus 1101 = 0110$
Notice: x³ terms cancel (1⊕1=0), x² term survives (0⊕1=1), x term survives (1⊕0=1), constant terms cancel (1⊕1=0).
XOR gates are among the simplest and fastest digital logic components. Because GF(2) arithmetic uses only XOR and AND, CRC can be computed at wire speed using shift registers and XOR gates—no complex arithmetic circuits needed. This is why CRC is ubiquitous in hardware: it's essentially 'free' compared to more sophisticated checksums.
The heart of CRC is polynomial division. Given a dividend polynomial M(x) and a divisor polynomial G(x), we compute:
$$M(x) = Q(x) \cdot G(x) + R(x)$$
Where:
The Algorithm:
Polynomial division in GF(2) follows the same long division process you learned in school, but with XOR instead of subtraction:
Detailed Example:
Let's divide M(x) = x⁶ + x⁵ + x⁴ + x + 1 (binary: 1110011) by G(x) = x³ + x + 1 (binary: 1011).
1100 ← Quotient (we don't use this for CRC)
──────
1011 │ 1110011
1011 ← XOR (since leading bit is 1)
────
1010 ← Result after first XOR
1011 ← XOR again (leading bit is 1)
────
0011 ← Result
0011 ← Bring down next bit: 00111
0000 ← Don't XOR (leading bit is 0)
────
0111 ← Bring down: 01110
0000 ← Don't XOR (leading bit is 0)
────
1110 ← Final: 11101
1011 ← XOR (leading bit is 1)
────
101 ← Remainder = x² + 1 (CRC value!)
The remainder is 101 (binary) = x² + 1 (polynomial). This 3-bit value (one less than divisor degree) is the CRC.
In GF(2) polynomial division: If the current leading bit is 1, XOR with the divisor. If it's 0, don't XOR (equivalently, XOR with 0). Then shift left and repeat. The remainder always has degree less than the divisor.
Step-by-Step Breakdown:
Let's trace through another example with explicit bit positions.
Divide 110101 by 1011:
| Step | Current Value | Action | Result |
|---|---|---|---|
| 1 | 110101 | Leading bit = 1, XOR with 1011 | 010101 → 10101 |
| 2 | 10101 | Leading bit = 1, XOR with 1011 | 00001 → 0001 |
| 3 | 0001 | Leading bit = 0, no XOR | 0001 |
| 4 | 001 | Leading bit = 0, no XOR | 001 |
Wait—we need to track this more carefully. Let me redo with proper alignment:
1011 │ 110101
1011
────
01110 (110101 XOR 101100 in aligned position)
1011
────
01011 (bring down, XOR)
1011
────
000 ← Remainder = 000
So 110101 ÷ 1011 leaves remainder 000, meaning 110101 is exactly divisible by 1011.
The power of CRC lies in a beautiful mathematical fact: if you carefully choose the generator polynomial G(x), then any 'reasonable' transmission error will change the remainder.
To understand why, we need to think about errors as polynomials.
Errors as Polynomials:
Suppose we transmit a codeword C(x) and the received word is C'(x). If errors occurred, we can write:
$$C'(x) = C(x) + E(x)$$
where E(x) is the error polynomial — a polynomial with 1s in exactly the positions where bit flips occurred.
Examples:
The Detection Principle:
When the receiver divides the received word by G(x), it computes:
$$\frac{C'(x)}{G(x)} = \frac{C(x) + E(x)}{G(x)} = \frac{C(x)}{G(x)} + \frac{E(x)}{G(x)}$$
If C(x) was constructed correctly (as we'll see in CRC calculation), then C(x) is exactly divisible by G(x), so:
$$\frac{C(x)}{G(x)} \text{ has remainder } 0$$
Therefore, the remainder of dividing C'(x) by G(x) equals the remainder of dividing E(x) by G(x).
The Key Insight:
An error goes undetected if and only if E(x) is divisible by G(x).
If E(x) mod G(x) ≠ 0, the error is detected. So we want to choose G(x) such that common error patterns are NOT divisible by G(x).
An error pattern E(x) is undetectable by CRC with generator G(x) if and only if G(x) divides E(x) evenly—that is, E(x) = Q(x) · G(x) for some polynomial Q(x). This means the error pattern must be a multiple of the generator. For well-chosen generators, such error patterns are extremely rare or require many bit errors.
Why Single-Bit Errors Are Always Caught:
A single-bit error at position i gives E(x) = xⁱ.
For this to be divisible by G(x), we need xⁱ = Q(x) · G(x).
But xⁱ has only one term, while G(x) has at least two (including a constant term for any practical CRC). The product Q(x) · G(x) must have at least as many terms as G(x), so it cannot equal xⁱ unless Q(x) = 0 (no error) or G(x) = xⁱ (which is never chosen as a generator).
Therefore, every single-bit error is detected by any CRC with a multi-term generator.
Why Burst Errors Are Caught:
A burst of length b starting at position i is represented by: $$E(x) = x^i(x^{b-1} + ... + 1)$$
The inner polynomial has degree b-1. If b-1 < degree of G(x), then G(x) cannot divide the inner polynomial (you can't divide a lower-degree polynomial by a higher-degree one and get a polynomial result). Therefore, G(x) cannot divide E(x), and the error is detected.
This is why CRC generator polynomials aren't arbitrary—they're carefully selected to maximize error detection. The "CRC-32" used in Ethernet was chosen after extensive mathematical analysis to catch the error patterns most likely in network transmission. We'll explore specific standard polynomials later in this module.
The name 'Cyclic Redundancy Check' comes from a remarkable property of the remainder operation in polynomial arithmetic: cyclic shifts of codewords produce predictable shifts in remainders.
The Cyclic Shift Operation:
A cyclic shift of a binary string moves all bits left (or right), with the bit that 'falls off' one end wrapping around to the other. For an n-bit string:
In polynomial terms, a left cyclic shift of M(x) is represented as: $$x \cdot M(x) \mod (x^n + 1)$$
The Key Property:
If C(x) ≡ 0 (mod G(x)) — that is, C(x) is a valid codeword — then any cyclic shift of C(x) is also divisible by G(x), producing another valid codeword.
This means the set of valid codewords is closed under cyclic shifts. This closure property is what enables efficient shift-register implementation of CRC.
Why This Matters for Implementation:
The cyclic property means CRC can be computed using a Linear Feedback Shift Register (LFSR):
This implementation requires:
No complex arithmetic, no memory beyond the register width. This is why CRC can be computed at multi-gigabit line rates in hardware.
The LFSR structure directly mirrors the polynomial. For G(x) = x³ + x + 1, you need a 3-bit register. XOR feedback occurs at positions corresponding to the polynomial terms: between bits 0 and 1 (the x term) and after bit 2 (wrapping with the x³ term). We'll see concrete circuit diagrams when we explore CRC calculation.
Before proceeding to CRC calculation, let's solidify understanding with comprehensive practice problems. Mastering polynomial arithmetic is essential for following CRC procedures.
Problem 1: Polynomial Addition
Compute (x⁵ + x³ + x² + 1) + (x⁵ + x⁴ + x² + x)
Solution: Align and XOR coefficients:
Result: x⁴ + x³ + x + 1 (binary: 011011)
Problem 2: Polynomial Multiplication
Compute (x² + 1) × (x + 1) in GF(2)
Solution: Multiply term by term:
Sum (XOR): x³ + x² + x + 1 (binary: 1111)
Verification: (101) × (11) in binary:
101
× 11
─────
101 (101 × 1)
101 (101 × 1, shifted left)
─────
1111 (XOR: 0101 ⊕ 1010 = 1111)
Problem 3: Full Division
Divide x⁵ + x⁴ + x² (binary: 110100) by x³ + x + 1 (binary: 1011)
Solution:
11 ← Quotient
─────
1011 │ 110100
1011 ← XOR at position 5
─────
011000 → 11000
1011 ← XOR at position 4
────
01110 → 1110
1011 ← XOR at position 3
────
0101 ← Remainder (degree < 3, stop)
Answer: Remainder = 101 = x² + 1
When doing polynomial division by hand, you can skip writing the quotient entirely—just track the XOR operations. The process is: (1) If leading bit is 1, XOR with divisor. (2) Drop the leading bit and continue. Repeat until remaining bits are fewer than divisor bits. Those remaining bits are your CRC.
Students new to GF(2) polynomial arithmetic often make predictable mistakes. Let's address these explicitly to prevent confusion.
A frequent conceptual error is thinking 'what is x?' The variable x has no specific value—it's a placeholder for positional structure. Polynomial 1011 means x³+x+1 regardless of what x is. We never evaluate; we only manipulate coefficients. This is abstract algebra, not high school polynomial evaluation.
The Subtraction = Addition Insight:
This is worth repeating until it's second nature:
In GF(2): a - b = a + b = a ⊕ b
This is why division works with XOR. When we 'subtract' the divisor from the dividend during long division, we're actually XORing. The lack of borrowing is precisely why the algorithm is so simple.
Verification technique: If you're unsure whether your XOR is correct, you can verify by XORing the result with either operand—you should get the other operand back:
This property is fundamental to both CRC verification and error correction.
We've established the mathematical foundation upon which CRC is built. Let's consolidate the key insights:
What's Next:
With polynomial division mastered, we're ready to explore the generator polynomial—the specific polynomial G(x) that defines a CRC algorithm. The next page examines how generator polynomials are chosen, what properties they must have, and why different standards (CRC-16, CRC-32, CRC-CCITT) use different generators for different applications.
You now understand the mathematical core of CRC: polynomial representation of binary data and division in GF(2). This foundation will make the rest of CRC—calculation procedures, verification, and standard polynomials—straightforward applications of what you've learned here. Next, we explore why generator polynomial selection is both an art and a science.