CRC – Mathematical Background

Introduction

Cyclic Redundancy Checks (CRCs) are based on polynomial arithmetic over the Galois Field GF(2). Although hardware implementations use shift registers and XOR gates, the underlying theory is purely algebraic. Understanding this mathematical foundation explains why different CRC variants exist, why reflection changes behavior, and how parallel CRC equations are derived.

Polynomials over GF(2)

A binary message is interpreted as a polynomial whose coefficients are 0 or 1.
For example, the bit string:

1101001

represents the polynomial:

Arithmetic in GF(2) uses:

• addition = XOR
• subtraction = XOR
• multiplication = AND + XOR
• no carries or borrows

This makes CRCs extremely efficient in hardware and mathematically elegant.

Generator Polynomial

A CRC is defined by a generator polynomial G(x).
For example, CRC‑32 Ethernet uses:

which corresponds to the hexadecimal representation:

0x04C11DB7

The generator polynomial determines:

• error‑detecting capability
• structure of the LFSR
• parallel XOR equations
• syndrome properties

Polynomial Division

CRC computation is equivalent to dividing the message polynomial M(x) by the generator polynomial G(x):

The remainder of this division is the CRC value.

In hardware, this division is implemented using:

• shift registers
• XOR feedback
• conditional taps

which form the LFSR representation of the polynomial.

Reflection (Bit Reversal)

Many CRCs use bit reflection:

• RefIn: input bytes are reversed bit‑wise
• RefOut: the final CRC is reversed bit‑wise

Reflection changes:

• the direction of the LFSR
• the order of taps
• the parallel XOR equations

Example:

• CRC‑32 Ethernet → reflected
• CRC‑32 MPEG‑2 → non‑reflected

Two CRCs with the same polynomial can behave differently solely due to reflection rules.

Initial Value and Final XOR

Two additional parameters influence CRC behavior:

• Init — initial value loaded into the CRC register
• XOR Out — value XORed with the CRC at the end

These parameters allow:

• detection of leading zeros
• compatibility with legacy protocols
• simplified verification

Example:

• CRC‑32 Ethernet: Init = 0xFFFFFFFF, XOR Out = 0xFFFFFFFF
• CRC‑32 MPEG‑2: Init = 0xFFFFFFFF, XOR Out = 0x00000000

LFSR Representation

The generator polynomial maps directly to an LFSR:

• each non‑zero term corresponds to a feedback tap
• the highest‑order term x^n defines the register width
• XOR gates implement modulo‑2 addition

This representation is the foundation for:

• serial CRC
• parallel CRC
• pipelined CRC

Unrolling the LFSR (Basis for Parallel CRC)

Parallel CRCs are derived by unrolling the LFSR for N steps.
Mathematically:

where:

• A is the state transition matrix
• B is the input influence vector

This formulation is the theoretical basis for the XOR matrices used in hardware.

Error‑Detection Properties

CRCs detect:

• all single‑bit errors
• all double‑bit errors
• all odd‑numbered bit errors (for many polynomials)
• all burst errors shorter than the polynomial degree
• most longer burst errors with extremely high probability

Example:
CRC‑32 Ethernet detects all burst errors up to 32 bits.

Why Many CRC Variants Exist

Different protocols choose different parameters to optimize:

• error‑detection capability
• hardware complexity
• compatibility with legacy systems
• bit ordering
• throughput

This is why CRC‑32 Ethernet, CRC‑32 Castagnoli, and CRC‑32 MPEG‑2 are all 32‑bit CRCs but behave differently.

Related Pages

• CRC — Overview, Families & Architecture
  Architectural principles derived from the mathematical model, including polynomial division, reflection rules, and parallel architectures.
• CRC — Reference Table
  A curated collection of CRC polynomials, initialization values, reflection settings, and expected results for standard test vectors.
• LFSR / PRBS — Mathematical Background
  Algebraic foundations of LFSRs and PRBS sequences, including primitive polynomials, maximal‑length sequences, and GF(2) recurrence relations.
• LFSR / PRBS — Overview, Families & Architecture
  Shared mathematical foundations with CRCs, including polynomial arithmetic and feedback structures.
• Data Path — Architecture & Fundamentals
  Integration of LFSR/PRBS generators and checkers into streaming datapaths, including placement, throughput considerations, and interaction with downstream blocks.
• Flow Control — Architecture & Fundamentals
  Mechanisms that regulate data movement and ensure correct alignment, seeding, and checking of LFSR/PRBS sequences within streaming pipelines.
• Pipelining — Architecture & Fundamentals
  Architectural techniques used to balance LFSR/PRBS computation latency, improve timing closure, and maintain full‑rate throughput.