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

  SENDER:
  Dataword D (k bits) ──> Append r Zeros ──> Divide by Generator G (r+1 bits)
                                                    |
                                            Modulo-2 Remainder R (r bits = CRC)
                                                    |
  Transmitted Frame = [ Dataword D (k bits) ] + [ CRC Remainder R (r bits) ]

  RECEIVER:
  Received Frame ──> Modulo-2 Division by Generator G ──> Remainder = 0?
                                                              |
                                            Yes: ACCEPT    No: REJECT / DISCARD

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

             1 1 1 0 1 1   <--- Quotient (Ignored)
Divisor:   +-------------
1 1 0 1    | 1 0 0 1 0 0 0 0 0   <--- Data + 3 Zeros
           ^ 1 1 0 1
           -----------
             0 1 0 0 0
             ^ 1 1 0 1
             ---------
               0 1 0 1 0
               ^ 1 1 0 1
               ---------
                 0 1 1 1 0
                 ^ 0 0 0 0
                 ---------
                   1 1 1 0
                   1 1 0 1
                   -------
                   0 0 1 1 0
                   ^   1 1 0 1
                   -----------
                       0 0 1   <--- Remainder R (3 bits) = CRC

---

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

             1 1 1 0 1 1
Divisor:   +-------------
1 1 0 1    | 1 0 0 1 0 0 0 0 1
             1 1 0 1
             -------
               1 0 0 0
               1 1 0 1
               -------
                 1 0 1 0
                 1 1 0 1
                 -------
                   1 1 1 0
                   0 0 0 0
                   -------
                   1 1 1 0
                   1 1 0 1
                   -------
                     0 1 1 1
                       1 1 0 1
                       -------
                         0 0 0  <--- Remainder = 0 ===> ACCEPT!

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

---

7. Key Exam Questions & Takeaways

1. How many redundant bits are appended to a dataword if the generator polynomial is $x^4 + x + 1$?
   • The degree of $G(x)$ is $r = 4$, so exactly 4 zeros are appended.
2. Why does modulo-2 division use XOR instead of ordinary subtraction?
   • In modulo-2 arithmetic over Galois Field $\text{GF}(2)$, addition and subtraction are identical and carryless, precisely mapping to the electronic logic of the XOR gate.
3. What error types are guaranteed to be detected by CRC-32?
   • All single-bit errors, all double-bit errors, all odd numbers of inverted bits, and all burst errors up to 32 bits in length.