2.2 Error Detection: Parity, Checksum & Cyclic Redundancy Check (CRC)

Back to Computer Networks Notes

📚Module 02: Data Link Layer: Framing, Flow & Error ControlTopic 2.2⏱️11 min read

🎯High-Yield For:Semester Exams (All Universities) • Placement Technical Rounds • Engineering Foundations

💡 Core Intuition: The Check Digit Principle

🍳 The Everyday Analogy: The Barcode Check Digit & Bank Check Sums

Whenever you purchase an item at a supermarket, the cashier scans a barcode with an optical laser. The final digit on that barcode is not part of the manufacturer's item code—it is a mathematical check digit:

• If the laser lens is smudged or the cashier mistypes a digit on the keypad, the checkout scanner instantly beeps with an error.
• The scanner does not know what the correct number was; it simply knows that the mathematical relationship between the digits was violated.

Similarly, bank checks encode account routing numbers using checksum algorithms. If a single digit is transposed, the automated clearinghouse rejects the transaction immediately.

💻 Bridging to Computer Science

In computer networks, physical transmission media (copper wires, fiber strands, atmospheric radio frequencies) are continuously bombarded by electromagnetic interference, thermal noise, and signal attenuation. These physical phenomena flip transmitted $0$s into $1$s and $1$s into $0$s.

To protect data integrity, the sender calculates a mathematical signature from the payload and appends these redundant bits to the frame. The receiver recomputes the calculation upon arrival. If the signatures do not match, the frame is corrupted.

---

📑Table of Contents

• ⚡ Error Types in Physical Transmission
  • Why Burst Errors Dominate Modern Networks
• 🧱 The Redundancy Principle & Block Coding
• 📏 Hamming Distance & Error Detection Theorems
  • Minimum Hamming Distance (d_{\min})
  • 🛡️ Theorem 1: Condition for Error Detection
  • 🔧 Theorem 2: Condition for Error Correction
• ⚖️ Detection Techniques: Parity, Checksum & CRC
• 🔢 1. Single Parity Check (1D Parity)
• 🔲 2. Two-Dimensional Parity Check (2D Parity)
• 🌐 3. The Internet Checksum (1's Complement Arithmetic)
  • Sender Algorithm
  • Receiver Algorithm
• ⚙️ 4. Cyclic Redundancy Check (CRC)
  • The Mathematical Framework: Polynomial Arithmetic in GF(2)
  • The Step-by-Step CRC Algorithm
• 🔄 Interactive Flagship Pipeline: CRC Generation & Syndrome Verification
• 🛡️ Error Detection Theorems of Generator Polynomial G(x)
  • Industry Standard Polynomials
• 🏭 Real-World Production Context
  • How Ethernet NICs Compute CRC-32 at 100 Gbps Speeds
• 📐 Numerical Applications & Worked Examples
  • Example 1: Full CRC Polynomial Division & Codeword Generation
  • Example 2: Frame Length Determination with High-Degree Polynomials
  • Example 3: Error Detection & Correction Guarantees from Minimum Hamming Distance
• 🎯 Exam & Interview Pitfall Check

---

⚡ Error Types in Physical Transmission

When electromagnetic noise strikes a physical transmission medium, it perturbs the electrical voltage, optical pulse, or radio wave.

Why Burst Errors Dominate Modern Networks

The physical duration of an electromagnetic noise pulse (such as an electrical motor spark or lightning impulse lasting $1\text{ ms}$) is vastly longer than the duration of an individual bit on a high-speed transmission link:

• On a $1\text{ Gbps}$ Ethernet link, a single bit lasts only $1\text{ ns}$ ($10^{-9}\text{ s}$).
• A tiny noise spike of $1\text{ microsecond}$ ($10^{-6}\text{ s}$) wipes out $1000$ consecutive bits!
• Consequently, modern data link layer error detection mechanisms must be optimized specifically to trap burst errors.

---

🧱 The Redundancy Principle & Block Coding

To detect or correct errors, we cannot simply rely on raw information bits. We must introduce Redundancy: extra bits appended solely to verify transmission fidelity.

In Block Coding, we partition our message into $k$-bit chunks called Datawords. We then transform each $k$-bit dataword into an $n$-bit Codeword by appending $r = n - k$ redundant bits: $\text{Dataword: } k \text{ bits} \quad \xrightarrow{\quad \text{Generator} \quad} \quad \text{Codeword: } n \text{ bits} \quad (n > k, \, r = n - k)$

Architecture Flow

Block Coding Codeword Mapping Pipeline

Mapping k-bit datawords into a sparse subset of 2^n valid codewords

📄Dataword Space

2^k Datawords (k bits)

Original application payload chunks of length k.

→

Generator r = n - k

🛡️Valid Codewords

2^k Valid Patterns

Encoded n-bit words separated by minimum distance d_min.

→

Channel Transit

🚨Invalid Codewords

2^n - 2^k Error Space

Corrupted words falling here trigger instant error alarms.

• Valid vs. Invalid Codewords: Out of the $2^n$ possible patterns of length $n$, only $2^k$ represent valid codewords. The remaining $2^n - 2^k$ combinations are strictly invalid.
• Detection Mechanism: If channel noise corrupts a valid codeword into an invalid codeword, the receiver detects the error immediately. If noise happens to corrupt a valid codeword into another valid codeword, the error slips through undetected.

---

📏 Hamming Distance & Error Detection Theorems

The Hamming Distance $d(x, y)$ between two binary words of equal length is the number of bit positions in which the corresponding bits differ: $d(x, y) = \text{Count of } 1\text{s in } (x \oplus y)$

• Example: For $x = 10110$ and $y = 10001$: $x \oplus y = 10110 \oplus 10001 = 00111 \implies d(x, y) = 3$

Minimum Hamming Distance ($d_{\min}$)

The Minimum Hamming Distance $d_{\min}$ of a block code is the smallest Hamming distance between any pair of valid codewords in the code: $d_{\min} = \min \{ d(c_i, c_j) \mid c_i, c_j \in C, \, c_i \neq c_j \}$

🛡️ Theorem 1: Condition for Error Detection

To guarantee the detection of up to $s$ bit errors across any transmitted codeword, the minimum Hamming distance of the code must satisfy: $\mathbf{d_{\min} \ge s + 1}$

• Intuition: If the transmitter sends valid codeword $c_1$ and $s$ bits are flipped, the corrupted pattern is at distance $s$ from $c_1$. If every other valid codeword $c_2$ is at least distance $s + 1$ away, the corrupted pattern can never match any other valid codeword, guaranteeing detection!

🔧 Theorem 2: Condition for Error Correction

To guarantee the forward correction of up to $t$ bit errors without retransmission, the minimum Hamming distance must satisfy: $\mathbf{d_{\min} \ge 2t + 1}$

• Intuition: If at most $t$ bits flip, the received pattern remains strictly closer to the original valid codeword $c_1$ (distance $\le t$) than to any other valid codeword $c_2$ (distance $\ge t + 1$). The receiver selects the nearest valid codeword via majority decoding.

---

⚖️ Detection Techniques: Parity, Checksum & CRC

---

🔢 1. Single Parity Check (1D Parity)

In a simple parity-check code:

• For a $k$-bit dataword, $1$ redundant parity bit is appended ($n = k + 1$).
• Even Parity: Parity bit is chosen such that the total number of $1$s in the codeword is even.
• Odd Parity: Parity bit is chosen such that the total number of $1$s in the codeword is odd.

$\text{Dataword: } 1011001 \quad (\text{four } 1\text{s})$ $\text{Even Parity Codeword: } 1011001\mathbf{0} \quad (\text{total } 1\text{s remains } 4 \implies \text{Even})$ $\text{Odd Parity Codeword: } 1011001\mathbf{1} \quad (\text{total } 1\text{s becomes } 5 \implies \text{Odd})$

• Mathematical Limitation: $d_{\min} = 2$.
  • Since $d_{\min} \ge s + 1 \implies 2 \ge s + 1 \implies s = 1$.
  • It can reliably detect only 1 single-bit error (or any odd number of errors).
  • If noise flips two bits simultaneously (e.g., $1 \to 0$ and $0 \to 1$), the total count of $1$s remains even, completely blinding the receiver!

---

🔲 2. Two-Dimensional Parity Check (2D Parity)

To overcome the limitations of simple parity, data is organized into a two-dimensional grid of $m$ rows and $k$ columns:

1. An even parity bit is computed for each row (horizontal parity).
2. An even parity bit is computed for each column (vertical parity).
3. The intersection of an erroneous row and erroneous column pinpoints the exact bit that flipped, enabling single-bit error correction!

Data Matrix	Bit 1	Bit 2	Bit 3	Bit 4	Bit 5	Bit 6	Row Parity
Row 1	1	1	0	0	1	1	0
Row 2	1	0	1	0	1	0	1
Row 3	0	1	1	1	0	0	1
Row 4	0	1	0	1	1	1	0
Column Parity	0	1	0	0	1	0	0 (Corner)

• Capabilities:
  • Detects all $1$-bit, $2$-bit, and $3$-bit errors.
  • Detects most burst errors within the block.
  • Corrects any single-bit error by locating $(Row_i, Col_j)$.
  • Failure Case: Fails if an even number of bits flip in both the same row and the same column (a 4-bit rectangular error pattern).

---

🌐 3. The Internet Checksum (1's Complement Arithmetic)

Employed by the Internet Protocol suite (IPv4, TCP, UDP), the Checksum uses one's complement addition:

Sender Algorithm

1. The message is divided into $16$-bit words.
2. All $16$-bit words are summed using 1's complement addition:
   • Any carry bit generated beyond the 16th bit is wrapped around and added back to the lowest bit (End-Around Carry).
3. The final sum is inverted bitwise (one's complemented) to produce the Checksum.
4. The Checksum is appended to the packet.

Receiver Algorithm

1. The receiver sums all incoming $16$-bit words plus the received Checksum using 1's complement addition.
2. If the transmission is error-free, the resulting sum must be all 1s (0xFFFF) (or equivalently, its one's complement must be all 0s (0x0000)).
3. Any other result indicates corruption $\to$ the packet is discarded.

---

⚙️ 4. Cyclic Redundancy Check (CRC)

The Cyclic Redundancy Check (CRC) is the undisputed cornerstone of modern Data Link Layer error detection (Ethernet IEEE 802.3, Wi-Fi 802.11, HDLC, USB, and SATA).

The Mathematical Framework: Polynomial Arithmetic in $GF(2)$

A binary string is expressed as an algebraic polynomial with coefficients in the Galois Field of order 2 ($GF(2)$), where coefficients are strictly $0$ or $1$: $\text{Bitstring: } 10011 \iff 1\cdot x^4 + 0\cdot x^3 + 0\cdot x^2 + 1\cdot x^1 + 1\cdot x^0 = \mathbf{x^4 + x + 1}$

• Modulo-2 Arithmetic Rules:
  • Binary addition and subtraction are identical and equivalent to bitwise XOR ($\oplus$).
  • Zero Carries and Zero Borrows: $0 \oplus 0 = 0, \quad 0 \oplus 1 = 1, \quad 1 \oplus 0 = 1, \quad 1 \oplus 1 = 0$

Architecture Flow

CRC Mathematical Transformation Stages

Augmenting payload with zeros, dividing by G(x), and replacing with remainder

📄Stage 1

Dataword D(x)

k-bit binary dataword representation.

→

Shift by r bits

➕Stage 2

Augmented D(x) · 2^r

Appends r zeros clearing space for CRC remainder.

→

Modulo-2 XOR by G(x)

⚙️Stage 3

Remainder R(x)

r-bit remainder resulting from polynomial division.

→

Append to Data

📦Stage 4

Transmitted Codeword T(x)

Self-checking codeword divisible by G(x) with 0 remainder.

The Step-by-Step CRC Algorithm

1. Determine Divisor Length: Let the generator polynomial $G(x)$ have degree $r$. The binary divisor has $r + 1$ bits.
2. Append $r$ Zeros: Append $r$ zeros to the right of the $k$-bit dataword $D$ (equivalent to multiplying $D(x)$ by $x^r$).
3. Modulo-2 Division: Perform binary XOR long division of the augmented dataword by the divisor $G(x)$.
4. Extract Remainder: The division yields a remainder $R(x)$ of length $r$ bits.
5. Form Codeword: Replace the $r$ appended zeros with the remainder bits $R(x)$. Transmit the $n$-bit codeword $T(x) = D(x) \cdot 2^r \oplus R(x)$.
6. Receiver Verification: The receiver divides the received codeword $T'(x)$ by $G(x)$.
   • If Remainder = 0: The frame is accepted as valid (zero syndrome).
   • If Remainder $\neq$ 0: An error occurred; frame is dropped!

---

🔄 Interactive Flagship Pipeline: CRC Generation & Syndrome Verification

The pipeline below details the end-to-end mathematical lifecycle of CRC: appending $r$ zeros, running modulo-2 XOR division, transmitting the framed codeword, and running the receiver syndrome checker.

Architecture Flow

Step 1 of 5

Cyclic Redundancy Check (CRC): End-to-End Modulo-2 Division Pipeline

Interactive state sequence tracing dataword augmentation, XOR polynomial division, channel transmission, and syndrome checking

1Step 1: Shift & Pad Zeros

2Step 2: Feed into XOR Divider

3Step 3: Inject Remainder R(x)

4Step 4: Transmit Across Medium

5Step 5: Compute Syndrome & Decide

📄User Data

Dataword D(x)

Payload Bits (k bits)

➕Append r Zeros

Zero Augmenter

D(x) · 2^r

⚙️XOR Division

Modulo-2 XOR Engine

Hardware LFSR / ALU

📦Payload + CRC

Transmitted Codeword T(x)

D(x) · 2^r ⊕ R(x)

⚡Noise Channel

Physical Link & Noise

Channel Error Vector E(x)

🎯Zero-Syndrome Test

Receiver Syndrome Checker

T'(x) mod G(x)

💡Click or hover any card or transition arrow above to inspect deep-dive operational mechanics

---

🛡️ Error Detection Theorems of Generator Polynomial $G(x)$

The error-detecting power of CRC is determined entirely by the mathematical properties of the chosen generator polynomial $G(x)$:

Error Category	Condition on Generator Polynomial $G(x)$	Detection Guarantee
All Single-Bit Errors	$G(x)$ has $\ge 2$ terms and the $x^0$ term is non-zero ($x^0 = 1$)	$100\%$ Guaranteed
All Double-Bit Errors	$G(x)$ does not divide $x^k + 1$ for any $k \le$ max frame length	$100\%$ Guaranteed
All Odd Numbers of Errors	$G(x)$ contains $(x + 1)$ as a factor	$100\%$ Guaranteed
Burst Errors of Length $L \le r$	Generator degree is $r$	$100\%$ Guaranteed
Burst Errors of Length $L = r + 1$	Generator degree is $r$	$1 - (1/2)^{r-1}$ ($\approx 99.99\%$ for CRC-16)
Burst Errors of Length $L > r + 1$	Generator degree is $r$	$1 - (1/2)^r$ ($\approx 99.99999997\%$ for CRC-32)

Industry Standard Polynomials

• CRC-8: $x^8 + x^2 + x + 1$ (ATM headers)
• CRC-16: $x^{16} + x^{15} + x^2 + 1$ (Modbus, USB)
• CRC-CCITT: $x^{16} + x^{12} + x^5 + 1$ (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$ (Ethernet 802.3, Wi-Fi 802.11, ZIP, PNG)

---

🏭 Real-World Production Context

How Ethernet NICs Compute CRC-32 at 100 Gbps Speeds

In production network interface cards (NICs) and core routers, computing CRC-32 by sequentially looping through bits in software would choke CPU performance:

• Hardware implementations deploy Linear Feedback Shift Registers (LFSR) directly in silicon.
• Modern 100GbE NICs utilize parallelized Galois matrix multipliers capable of ingesting 64 bytes per clock cycle.
• The Frame Check Sequence (FCS) trailer appended to every Ethernet frame is validated on-the-fly as bits stream through the physical transceiver, dropping damaged frames before they consume a single cycle of host CPU memory bandwidth.

---

📐 Numerical Applications & Worked Examples

Example 1: Full CRC Polynomial Division & Codeword Generation

Problem Statement:
The message 11001001 is to be transmitted using the CRC generator polynomial $G(x) = x^3 + 1$. Calculate:

1. The CRC redundancy bits (remainder).
2. The complete transmitted codeword.

Step-by-Step Solution:

1. Convert Generator Polynomial to Binary: $G(x) = x^3 + 1 = 1\cdot x^3 + 0\cdot x^2 + 0\cdot x^1 + 1\cdot x^0 \implies \mathbf{1001}$
   • Degree of polynomial $r = 3$. The binary divisor has $r + 1 = 4$ bits.
2. Augment the Dataword with $r = 3$ Zeros: $\text{Dataword } D = 11001001 \implies \text{Augmented Dividend: } \mathbf{11001001000}$
3. Execute Modulo-2 XOR Long Division:
   • Step 1: Leading 4 bits 1100 $\oplus$ 1001 = 0101. Bring down 1 $\to$ 1011.
   • Step 2: 1011 $\oplus$ 1001 = 0010. Bring down 0 $\to$ 0100. Bring down 0 $\to$ 1001.
   • Step 3: 1001 $\oplus$ 1001 = 0000. Bring down 0 $\to$ 0000. Bring down 0 $\to$ 0000.
   • Step 4: After bringing down all augmented zeros, the resulting 3-bit remainder is: $\mathbf{R = 011}$
4. Construct the Transmitted Codeword: $T = \text{Dataword} \parallel \text{Remainder} = 11001001 \parallel 011 = \mathbf{11001001011}$
5. Final Result:
   • The CRC check bits are 011.
   • The transmitted codeword is 11001001011.

---

Example 2: Frame Length Determination with High-Degree Polynomials

Problem Statement:
A transmitter sends a 10-bit payload message $M = 1010001101$. The system protects frames using the CRC generator polynomial $G(x) = x^5 + x^4 + x^2 + 1$. Determine the total number of bits in the transmitted codeword frame.

Step-by-Step Solution:

1. Identify Given Parameters:
   • Message length $k = 10\text{ bits}$.
   • Generator polynomial: $G(x) = x^5 + x^4 + x^2 + 1$.
2. Determine Generator Degree ($r$):
   • The highest exponent in $G(x)$ is $5 \implies r = 5$.
   • A generator of degree $r$ produces a remainder of exactly $r$ bits.
3. Calculate Codeword Length ($n$): $n = k + r = 10 + 5 = \mathbf{15\text{ bits}}$
4. Final Result: The transmitted message frame spans exactly $15\text{ bits}$.

---

Example 3: Error Detection & Correction Guarantees from Minimum Hamming Distance

Problem Statement:
A block coding scheme is designed with a minimum Hamming distance $d_{\min} = 4$. Determine:

1. The maximum number of bit errors the code is guaranteed to detect.
2. The maximum number of bit errors the code is guaranteed to correct.

Step-by-Step Solution:

1. Error Detection Guarantee ($s$): $d_{\min} \ge s + 1 \implies 4 \ge s + 1 \implies s \le 3$
   • The code is mathematically guaranteed to detect up to $3$ bit errors.
2. Error Correction Guarantee ($t$): $d_{\min} \ge 2t + 1 \implies 4 \ge 2t + 1 \implies 2t \le 3 \implies t \le 1.5$
   • Since $t$ must be an integer, $t = \mathbf{1}$.
   • The code is guaranteed to forward-correct up to $1$ bit error.

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: "Why can a simple parity bit detect only odd numbers of errors but never even numbers?"
Key Focus Points:

• In even parity, the parity bit guarantees an even total count of 1s.
• A single bit flip changes the parity from even to odd (detected).
• A second bit flip changes the parity back from odd to even! Thus, any even number of bit inversions restores the expected parity status, rendering the receiver blind to the corruption.

Question 2: "What is the significance of the $x^0$ term being non-zero in a CRC generator polynomial?"
Key Focus Points:

• The term $x^0$ corresponds to the constant $1$.
• If $x^0 = 0$, $G(x)$ has $x$ as a common factor ($G(x) = x \cdot Q(x)$).
• A generator with a factor of $x$ cannot detect a single-bit error that shifts the bitstream or occurs in the least significant bit, violating the fundamental theorem for $100\%$ single-bit error detection!

Question 3: "How does CRC achieve line-rate hardware speeds in network switches?"
Key Focus Points:

• Modulo-2 division requires no multiplication, carries, or borrows.
• In hardware, CRC is implemented using a Linear Feedback Shift Register (LFSR) consisting of $r$ flip-flops and XOR gates corresponding to the generator polynomial coefficients. Bits are clocked through at 1 bit per clock cycle with zero ALU latency!

Common Interview Traps

Trap 1: "Can CRC perform error correction?"
Answer: Mathematically yes, but practically no in standard protocols. While cyclic codes can technically correct errors using algebraic syndrome decoding (e.g., BCH and Reed-Solomon codes), standard Data Link Layer protocols (Ethernet, Wi-Fi) use CRC strictly for error detection. When an error is detected, the frame is simply discarded, and the link layer relies on Automatic Repeat Request (ARQ) retransmissions.

Trap 2: "Is the Internet Checksum stronger than CRC?"
Answer: Absolutely NOT. The Internet Checksum is based on simple 1's complement addition. It is vulnerable to compensating errors—for instance, if one bit changes from $0$ to $1$ in word $A$ and another changes from $1$ to $0$ in word $B$, the sum remains unchanged! CRC uses non-linear polynomial modulo-2 arithmetic and is orders of magnitude stronger at detecting burst errors. The Internet Checksum was chosen solely for its software speed on 1980s CPUs.

---

🗺️View Complete Computer Networks Roadmap & Syllabus

← Previous Topic2.1 Data Link Layer Responsibilities & Framing TechniquesNext Topic →2.3 Flow Control: Stop-and-Wait ARQ & Efficiency Derivation