Cyclic Redundancy Check (CRC)

---

1. Fundamentals of Cyclic Codes & CRC

Cyclic Redundancy Check (CRC) is a powerful, mathematically rigorous error-detecting code based on binary polynomial division. It is the dominant error-detection algorithm used in modern networking standards, including IEEE 802.3 Ethernet, Wi-Fi, HDLC, and ATM.

Why "Cyclic"?

In cyclic codes, if a codeword is cyclically shifted (rotated), the resulting binary string is also a valid codeword in the codebook.

---

2. Polynomial Representation of Bit Streams

In CRC, binary bit sequences are represented as polynomials in indeterminate $x$ with binary coefficients ($0$ or $1$):

• Highest power of $x$ present in the polynomial defines the Degree of the Polynomial ($r$).
• A polynomial of degree $r$ contains $(r + 1)$ binary coefficients.

---

3. Mathematical Mechanism of CRC

The Modulo-2 Division Rules:

• Addition and Subtraction in Modulo-2 are identical and equivalent to the XOR operation ($0 \oplus 0 = 0,\ 0 \oplus 1 = 1,\ 1 \oplus 0 = 1,\ 1 \oplus 1 = 0$).
• There are no carries in addition and no borrows in subtraction.
• If the leftmost bit of the current dividend is 1, the divisor aligns and XORs.
• If the leftmost bit is 0, the divisor does not divide (or XORs with all 0s).

---

4. Complete Step-by-Step Solved Numerical

Problem Statement:

A sender wants to transmit the dataword $D = 100100$.
The Generator Polynomial is $G(x) = x^3 + x^2 + 1$.

1. Find the transmitted CRC codeword.
2. Verify that the receiver detects no error if the frame arrives uncorrupted.

---

Step 1: Determine the Divisor and Appended Zeros

• Generator Polynomial: $G(x) = x^3 + x^2 + 0\cdot x^1 + 1 \implies \mathbf{1101}$ (4 bits).
• Degree of $G(x)$: $r = 3$.
• Append $r = 3$ zeros to the dataword:

---

Step 2: Modulo-2 Division at Sender

---

Step 3: Construct the Transmitted Codeword

Replace the 3 appended zeros with the 3-bit remainder:

---

Step 4: Verification at Receiver

The receiver divides the received codeword $100100001$ by the generator $1101$:

Since the remainder is $000$, the frame is accepted as uncorrupted.

---

5. Standard Generator Polynomials in Networking

Name	Polynomial Expression	Degree ($r$)	Primary Industry Standard
CRC-8	$x^8 + x^2 + x + 1$	8	ATM Header Error Control (HEC)
CRC-16 (ANSI)	$x^{16} + x^{15} + x^2 + 1$	16	USB, Modbus, ANSI
CRC-CCITT	$x^{16} + x^{12} + x^5 + 1$	16	HDLC, X.25, Bluetooth
CRC-32	$x^{32} + x^{26} + x^{23} + x^{22} + x^{16} + x^{12} + x^{11} + x^{10} + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1$	32	IEEE 802.3 Ethernet, Wi-Fi, ZIP, PNG

---

6. Error-Catching Capabilities of CRC

A well-designed generator polynomial $G(x)$ guarantees:

1. Single-bit errors: Detected if $G(x)$ has at least two non-zero terms (contains $x^0$).
2. Double-bit errors: Detected if $G(x)$ does not divide $x^t + 1$ for any $t < \text{frame length}$.
3. Odd number of errors: Detected if $G(x)$ contains $(x + 1)$ as a mathematical factor.
4. Burst errors of length $\leq r$: $100\%$ detected (where $r$ is the polynomial degree).
5. Burst errors of length $r + 1$: Detected with probability $1 - \left(\frac{1}{2}\right)^{r-1}$ ($99.9999998\%$ for CRC-32).

---