Data Link Layer: Error Detection & Correction (CRC, Parity, Hamming)

TAKEAWAYS:

• Errors happen: Bit flips due to noise, interference, or collisions corrupt data; detection/correction ensures accuracy.
• Parity is simple: Single-bit checks (even/odd) detect odd errors but fail for even errors.
• CRC is powerful: Uses polynomial division to append redundant bits, catching burst errors with high probability.
• Hamming codes correct: Single-bit errors by encoding extra bits to pinpoint and fix flipped bits.
• Real-world use: eSewa (Khalti) uses CRC to validate transaction data; Ncell’s SMS relies on error correction for text delivery.
• Trade-offs: Detection (CRC) vs. correction (Hamming) balance complexity and reliability.

Why Errors Occur in Data Transmission

Data travels through physical media (copper cables, fiber optics, wireless channels) where noise, interference, or collisions can flip bits. For example:

• Thermal noise in cables corrupts signals.
• Multipath fading in Wi-Fi causes signal distortion.
• Bit collisions in shared channels (e.g., Ethernet) overwrite data.

Example: Sending 1010 might arrive as 1000 (1st bit flipped). Without correction, the receiver accepts incorrect data.

Error Detection Methods

1. Parity Bit (Simple but Limited)

• How it works: Adds 1 extra bit to make the total number of 1s even (even parity) or odd (odd parity).
• Detection: If the received parity doesn’t match, an error is detected.
• Limitations: Fails for even-numbered errors (e.g., 1010 → 0010 flips two bits; parity remains unchanged).

stateDiagram-v2
    [*] --> ParityCheck: Transmit with parity bit
    ParityCheck --> CheckParity: Receiver verifies parity
    CheckParity --> Correct: "No error (parity matches)"
    CheckParity --> ErrorDetected: "Error (parity mismatch)"
    ErrorDetected --> [*]

Example:

• Data: 1101 (3 1s → odd parity → append 1 → 11011).
• Received: 10011 (2 1s → even parity → error detected).

2. Checksum (Weak but Fast)

• How it works: Treats data as a sequence of 16-bit words, sums them, and sends the complement of the sum.
• Use case: UDP (User Datagram Protocol) uses checksums for lightweight error detection.
• Limitation: Detects only random errors, not burst errors.

Example:

• Data: 1010 1100 (sum = 0110 → complement = 1001).
• Received: 1010 1101 (sum = 0111 → complement mismatch → error).

3. Cyclic Redundancy Check (CRC) – The Gold Standard

CRC is used in Ethernet, Wi-Fi, PPP, and HDLC. It detects burst errors (multiple consecutive bit flips) with high probability.

How CRC Works

1. Generator Polynomial: A predefined binary divisor (e.g., x³ + 1 = 1011).
2. Append Redundancy: Treat data as a binary polynomial, divide by the generator, and append the remainder.
3. Receiver Check: Divide received data by the generator. If remainder ≠ 0 → error.

Example: Transmit 100101010 with generator x³ + 1 (1011).

1. Step 1: Append 3 zeros → 100101010000.
2. Step 2: Divide by 1011 (binary division):

   100101010000 ÷ 1011 = 110010101 with remainder 010 → CRC = 010.
   

3. Transmitted: 100101010010.
4. Receiver: Divides 100101010010 by 1011 → remainder 000 → no error.

Visual: CRC Division Process

Real-World Use:

• eSewa (Khalti): Uses CRC to validate transaction IDs and payment data before processing.
• Ncell SMS: CRC ensures text messages arrive intact despite mobile network noise.

Comparison Table: Error Detection Methods

Error Correction: Hamming Codes

While CRC detects errors, Hamming codes correct them by adding redundant bits to locate and fix flipped bits.

How Hamming Codes Work

1. Position Redundancy: Extra bits are placed at powers of 2 (e.g., bits 1, 2, 4, 8).
2. Parity Calculation: Each redundant bit covers a subset of data bits.
3. Error Location: The receiver computes syndrome bits. Their binary value points to the flipped bit.

Example: Encode 101101 (6 bits) with Hamming (7,4) code.

1. Add 3 parity bits (positions 1, 2, 4) → P1 P2 1 P3 1 1 0.
2. Calculate parity:
   • P1 covers bits 1,3,5,7 → 1 ⊕ 1 ⊕ 1 ⊕ 0 = 1.
   • P2 covers bits 2,3,6,7 → 0 ⊕ 1 ⊕ 1 ⊕ 0 = 0.
   • P3 covers bits 4,5,6,7 → 1 ⊕ 1 ⊕ 1 ⊕ 0 = 1.
3. Encoded: 1 0 1 1 1 1 0.
4. Transmit: 1011110.
5. Receiver: Computes syndrome 101 (binary 5) → flips bit 5 → corrects to 101101.

Visual: Hamming Code Structure

Real-World Use:

• CD/DVD Storage: Hamming codes correct scratches or dust-induced bit errors.
• Satellite Communication: NASA uses Hamming codes to fix errors in deep-space data.

Why CRC Dominates Over Hamming for Networks

Example in Networks:

• PPP (Point-to-Point Protocol): Uses CRC-16 to detect errors in dial-up/modem connections.
• Ethernet: CRC-32 ensures frames like 10101010 arrive as 10101010 despite collisions.

In the Real World

1. eSewa (Khalti) Transaction Validation

   • When you pay via Khalti, the app appends a CRC-16 checksum to the transaction ID. If the bank’s server detects a mismatch, it rejects the payment to prevent fraud.
   • Example: Sending TXN12345 with CRC 0xB40B ensures the bank knows the data wasn’t corrupted during transmission.

2. Ncell SMS Delivery

   • SMS uses a checksum (similar to CRC) to verify text messages. If your phone receives Hello as Hxllo, the checksum fails, and the message is redelivered.
   • Worked Example: Original SMS 01001000 01100101 (sum = 00001101 → checksum 11110010). If received as 01000000 01100101, the checksum fails → error.

3. Daraz Order Processing

   • When you place an order, Daraz’s backend uses CRC to validate the order ID before processing payment. If the ID is corrupted (e.g., due to a network glitch), the system flags it for retransmission.
   • Visual: Imagine a queue of orders as bits. CRC acts like a "spell-check" for the order number.

Exam Tip

1. CRC is the star: Always explain it with:

   • Generator polynomial (e.g., x³ + 1).
   • Division steps (show binary long division).
   • Remainder as the CRC.
   • Example: Given data 1101 and generator 1011, show the transmitted string and verify correctness.

2. Parity vs. CRC:

   • Parity detects odd errors (1 bit).
   • CRC detects burst errors (multiple bits).
   • Exam trick: If asked to "differentiate," use a table like above.

3. Hamming for correction:

   • Focus on syndrome calculation and bit flipping.
   • Example: Given a received Hamming code 1100101, compute syndrome to find the error.

4. Real-world mapping:

   • Link CRC to Ethernet/Wi-Fi.
   • Link Hamming to memory/CDs.
   • Tip: Mention eSewa/Khalti for CRC in payment systems.

5. Common pitfalls:

   • Forgetting to append zeros before CRC division.
   • Misplacing parity bits in Hamming codes.
   • Confusing detection (CRC) with correction (Hamming).