Polynomial Division

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.

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.

Key Observations:

1. Degree of the polynomial = position of the leftmost 1 bit (highest power of x)
2. Leading term always has coefficient 1 (we don't write leading zeros)
3. Constant term (x⁰ = 1) corresponds to the rightmost bit
4. 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

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.

Critical Properties for CRC:

1. No Carries: When we add polynomials in GF(2), coefficients don't carry over. Each bit position is independent.

2. Self-Inverse: Every element is its own additive inverse: $a + a = 0$ for any $a$. This means $a - a = a + a = 0$.

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

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:

1. Align the divisor with the highest-order bit of the dividend
2. If that bit is 1, XOR the divisor into the dividend
3. Shift right one position
4. Repeat until you've processed all bits
5. 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.

Step-by-Step Breakdown:

Let's trace through another example with explicit bit positions.

Divide 110101 by 1011:

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:

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

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

1. Initialize the register (typically to all 1s for proper CRC)
2. 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
3. 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.

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

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

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.