Polynomial Division - CRC - Cyclic Redundancy Check | OneNoughtOne

0/240

Computer NetworksCyclic Redundancy Check

CRC - Cyclic Redundancy Check

LevelIntermediate

Duration75 mins

TopicCyclic Redundancy Check

1 / 5

Polynomial Division

The Mathematics Behind Bulletproof Error Detection

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.

What You Will Learn

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.

Binary Data as Polynomials

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.

Examples: Binary Strings to Polynomials
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:

Degree of the polynomial = position of the leftmost 1 bit (highest power of x)
Leading term always has coefficient 1 (we don't write leading zeros)
Constant term (x⁰ = 1) corresponds to the rightmost bit
Terms with coefficient 0 are omitted (just like we omit 0s in polynomial notation)

Why Polynomials?

Polynomials provide structure that raw bit strings lack:

Algebraic operations (addition, multiplication, division) are well-defined
Divisibility concepts transfer directly—key to CRC
Cyclic properties of polynomial remainders enable efficient implementation
Error patterns correspond to polynomial factors, enabling systematic analysis

Reading Polynomials Back to Binary

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).

Practice: Convert These

•Binary 101101 → Polynomial: x⁵ + x³ + x² + 1 (positions 5, 3, 2, 0 have 1s)
•Polynomial x⁶ + x⁵ + x² + x + 1 → Binary: 1100111 (7 bits: positions 6,5,4,3,2,1,0 → 1,1,0,0,1,1,1)
•Binary 1000000001 → Polynomial: x⁹ + 1
•Polynomial x⁷ + x³ + x² + x → Binary: 10001110 (8 bits)

The Galois Field GF(2): Where CRC Lives

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:

The only allowed values are 0 and 1
Addition is the XOR operation
Multiplication is the AND operation

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.

GF(2) Arithmetic Tables
Operation	0 ⊕ 0	0 ⊕ 1	1 ⊕ 0	1 ⊕ 1
Addition (XOR)	0	1	1	0
Subtraction (XOR)	0	1	1	0

GF(2) Multiplication (AND)
×	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).

Why This Matters for Hardware

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.

GF(2) Polynomial Addition Examples

•(x⁴ + x² + x) + (x⁴ + x³ + x²) = x³ + x (binary: 10110 ⊕ 11100 = 01010)
•(x⁵ + x⁴ + x + 1) + (x⁵ + x² + 1) = x⁴ + x² + x (binary: 110011 ⊕ 100101 = 010110)
•(x³ + x² + x + 1) + (x³ + x² + x + 1) = 0 (any polynomial added to itself gives zero)

Polynomial Long Division in GF(2)

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:

M(x) is the message polynomial (data to protect)
G(x) is the generator polynomial (defines the CRC algorithm)
Q(x) is the quotient (we discard this)
R(x) is the remainder — this becomes the CRC value

The Algorithm:

Polynomial division in GF(2) follows the same long division process you learned in school, but with XOR instead of subtraction:

Align the divisor with the highest-order bit of the dividend
If that bit is 1, XOR the divisor into the dividend
Shift right one position
Repeat until you've processed all bits
The remaining bits (below the divisor's degree) are the remainder

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.

The Golden Rule of GF(2) Division

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.

Key Properties of GF(2) Polynomial Division

•Remainder degree is always less than divisor degree (n-bit divisor → (n-1)-bit remainder)
•XOR is subtraction — when you 'subtract' the divisor, you XOR it
•No borrowing — each bit position is independent of others
•Quotient is irrelevant for CRC — we only care about the remainder
•Zero remainder means the dividend is exactly divisible by the divisor

Why Polynomial Division Catches Errors

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:

Single bit error at position 5: E(x) = x⁵ (binary: 100000)
Two bit errors at positions 3 and 7: E(x) = x⁷ + x³ (binary: 10001000)
Burst error affecting positions 2-5: E(x) could be x⁵ + x⁴ + x² (binary: 110100)

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).

The Undetectable Error

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.

What a Good Generator G(x) Guarantees

•All single-bit errors — E(x) = xⁱ is never divisible by G(x) if G(x) has more than one term
•All double-bit errors — E(x) = xⁱ + xʲ is detected if G(x) has a factor (x + 1)
•All odd-bit-count errors — Detected if G(x) has (x + 1) as a factor
•All burst errors ≤ r bits — Detected if G(x) has degree r (100% guarantee)
•Most longer bursts — Probability of missing a burst of length r+1 is 2⁻⁽ʳ⁻¹⁾

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.

The Power of Polynomial Choice

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 Cyclic Property: Why It's Called 'Cyclic' Redundancy Check

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:

Left cyclic shift: $b_{n-1}b_{n-2}...b_1b_0 \rightarrow b_{n-2}b_{n-3}...b_0b_{n-1}$

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):

Initialize the register (typically to all 1s for proper CRC)
For each input bit:
- Shift the register left by one position
- If the bit shifted out is 1, XOR the register with the generator polynomial
After all bits are processed, the register contains the CRC

This implementation requires:

A shift register (simple D flip-flops)
A few XOR gates (positioned according to the generator polynomial)
One clock cycle per bit

No complex arithmetic, no memory beyond the register width. This is why CRC can be computed at multi-gigabit line rates in hardware.

LFSR Implementation Preview

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.

Benefits of the Cyclic Property

•Hardware Efficiency — Shift registers are the simplest sequential circuits, enabling line-rate CRC computation
•Parallel Computation — The linear nature allows processing multiple bits per clock cycle (e.g., 8 bits at a time in byte-oriented implementations)
•Incremental Computation — CRC can be updated as data arrives; no need to buffer entire frame
•Error Localization — Syndrome patterns (non-zero remainders) can help identify error positions in some applications
•Mathematical Analyzability — Cyclic codes have rich algebraic structure enabling formal proofs of error detection capability

Polynomial Arithmetic Practice

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:

x⁵: 1 ⊕ 1 = 0
x⁴: 0 ⊕ 1 = 1
x³: 1 ⊕ 0 = 1
x²: 1 ⊕ 1 = 0
x¹: 0 ⊕ 1 = 1
x⁰: 1 ⊕ 0 = 1

Result: x⁴ + x³ + x + 1 (binary: 011011)

Problem 2: Polynomial Multiplication

Compute (x² + 1) × (x + 1) in GF(2)

Solution: Multiply term by term:

x² × x = x³
x² × 1 = x²
1 × x = x
1 × 1 = 1

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

Division Shortcut

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.

Self-Check Problems

•Addition: (x⁴ + x³ + 1) + (x⁴ + x² + x + 1) = ? Answer: x³ + x² + x
•Multiplication: (x² + x) × (x + 1) = ? Answer: x³ + x (note: x² + x² = 0)
•Division: 1101011 ÷ 1101 = ? Answer: Remainder = 110
•Division: 10110 ÷ 101 = ? Answer: Remainder = 00 (exactly divisible!)

Common Pitfalls and Misconceptions

Students new to GF(2) polynomial arithmetic often make predictable mistakes. Let's address these explicitly to prevent confusion.

Common Mistakes

•Using regular subtraction — Trying to borrow or carry during XOR operations
•Forgetting leading zeros — Thinking 0110 ≠ 110 as polynomials (they're equal)
•Wrong remainder size — Expecting remainder to have same degree as divisor
•Evaluating at x=2 — Treating polynomials as numerical expressions rather than formal objects
•Adding coefficients > 1 — Writing 1+1=2 instead of 1⊕1=0

Correct Understanding

•XOR only — Addition and subtraction are both XOR; no carrying ever
•Only significant bits matter — 0110 = 110 = x² + x as polynomials
•Remainder has degree < divisor — 4-bit divisor → at most 3-bit remainder
•x is symbolic — Never substitute numbers for x; stay in polynomial form
•Only 0 and 1 exist — Coefficients are in {0,1}; 1⊕1=0, always

The Value of x Doesn't Matter

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:

If a ⊕ b = c, then c ⊕ a = b and c ⊕ b = a

This property is fundamental to both CRC verification and error correction.

Summary: The Mathematical Foundation of CRC

We've established the mathematical foundation upon which CRC is built. Let's consolidate the key insights:

Key Takeaways

•Binary strings map to polynomials — Each bit becomes a coefficient; position becomes the exponent. This representation enables powerful algebraic analysis.
•GF(2) arithmetic uses XOR — Addition, subtraction, and their polynomial equivalents all reduce to XOR. No carries, no borrowing, no negative numbers.
•Polynomial division produces a remainder — The remainder has degree less than the divisor, and this remainder becomes the CRC value.
•Error detection is divisibility checking — An error is undetected only if the error polynomial is divisible by the generator. Well-chosen generators make this astronomically unlikely.
•The cyclic property enables efficient implementation — Shift registers with XOR feedback compute CRC at wire speed with minimal hardware.
•Mathematical analysis guides polynomial selection — Generators are chosen based on proven detection capabilities for specific error types.

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.

Page Complete

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.