Error Detection & Correction: Parity, CRC & Hamming Code

---

1. Why Errors Occur in Transmission

Transmission errors are caused by:

• Thermal noise: Random electron motion in conductors
• Impulse noise: Short spikes from lightning, switching equipment
• Attenuation: Signal weakens over distance
• Crosstalk: Signal from adjacent wires "bleeds" into the channel
• Echo: Signal reflections at impedance mismatches

Errors can be:

• Single-bit errors: One bit flips (e.g., 0→1)
• Burst errors: Multiple consecutive bits corrupted (more common in practice; caused by impulse noise or fading)

---

2. Parity Check

The simplest error detection method.

Single-Bit Parity

• Even parity: Add one parity bit so total number of 1s in the block (data + parity) is even
• Odd parity: Total number of 1s is odd

Example — Even Parity:

• Data bits: 1011001 (four 1s — already even)
• Parity bit: 0 → Transmitted: 10110010
• Data bits: 1011101 (five 1s — odd)
• Parity bit: 1 → Transmitted: 10111011

Limitation: Cannot detect errors in an even number of bits — if 2 bits flip, the parity appears correct. Cannot correct any error.

2D Parity (Vertical Redundancy Check + Longitudinal Redundancy Check)

• Calculate parity for each row AND each column
• Can detect all single-bit errors and some burst errors
• Structured as a grid — parity bits added to rows and columns

---

3. Cyclic Redundancy Check (CRC)

CRC is the most widely used error detection scheme. It can detect:

• All single and double-bit errors
• All odd-number bit errors
• All burst errors up to the degree of the generator polynomial

CRC Algorithm

1. Choose a generator polynomial G(x) of degree r (e.g., CRC-8: x^8 + x^2 + x + 1)
2. Append r zero bits to the end of the message M
3. Perform binary modulo-2 division of the augmented message by G
4. The remainder (exactly r bits) is the Frame Check Sequence (FCS) / CRC
5. The sender transmits: M + FCS
6. The receiver divides received frame by G — if remainder = 0, no error detected

CRC Worked Example

Generator polynomial: G = 1101 (degree r = 3, meaning CRC is 3 bits) Message: M = 110010

Step 1: Append 3 zeros → 110010000

Step 2: Binary modulo-2 division (XOR-based long division):

110010000 ÷ 1101
110010000
XOR 1101
-----------
 00110...

Full division:

110010000
1101
─────
  110100
  1101
  ──────
    001000
    0000
    ──────
     01000 → Remainder = 100

(Detailed working: After completing the division, Remainder = 100)

Step 3: Transmitted frame = 110010 + 100 = 110010100

Verification at Receiver: 110010100 ÷ 1101 → Remainder = 000 ✓

Standard CRC Polynomials

Exam Tip: For CRC questions, always append r zero bits (r = degree of generator) to the message, then perform XOR-based modulo-2 division. The remainder IS the CRC. CRC-32 is used in Ethernet — commonly asked.

---

4. Checksum

Used in TCP/UDP/IP headers:

1. Divide data into fixed-size segments (e.g., 16-bit words)
2. Sum all segments using ones-complement arithmetic
3. Take the ones-complement of the sum → this is the checksum
4. At receiver: sum all segments including checksum → result should be all 1s

Advantage: Simple and fast to compute in software Disadvantage: Weaker than CRC — misses some multi-bit errors

---

5. Hamming Code — Error Correction

Hamming Code can detect up to 2-bit errors and correct any 1-bit error without retransmission.

Hamming Code Structure

• For a message of m data bits, the number of parity bits p must satisfy:
• 2^p ≥ m + p + 1
• Parity bits are placed at positions that are powers of 2: positions 1, 2, 4, 8, 16, …
• Each parity bit covers specific positions (those whose bit position index includes that power of 2 in binary representation)

Hamming Code Worked Example

Message to encode: 1011 (4 data bits, m = 4)

Step 1: Find p (number of parity bits)

• Try p = 3: 2^3 = 8 ≥ 4 + 3 + 1 = 8 ✓
• So we need 3 parity bits → total codeword = 7 bits

Step 2: Assign positions (P = parity bit, D = data bit)

Step 3: Calculate parity bits (even parity)

• P1 (covers positions 1, 3, 5, 7): bits = P1, 1, 1, 1 → three 1s → P1 = 1
• P2 (covers positions 2, 3, 6, 7): bits = P2, 1, 0, 1 → two 1s → P2 = 0
• P4 (covers positions 4, 5, 6, 7): bits = P4, 1, 0, 1 → two 1s → P4 = 0

Step 4: Final codeword (positions 7 down to 1): 1 0 1 0 1 0 1

Error Detection & Correction:

• At receiver, recalculate all parity bits
• Build error syndrome from parity check results
• Convert syndrome to decimal → that decimal number = position of the erroneous bit
• Flip that bit to correct the error

Hamming Distance

Standard Hamming code has d_min = 3 → can correct 1 error or detect 2 errors.

---

Study Deep: CRC vs Hamming

• CRC is detection-only: Much stronger error detection than Hamming, but cannot correct errors — detected errors must be retransmitted (ARQ).
• Hamming corrects single-bit errors: No retransmission needed — ideal for memory (ECC RAM corrects single-bit DRAM errors in real-time).
• Real-world combination: Hard drives use Reed-Solomon codes (generalisation of Hamming); Ethernet uses CRC-32 for detection; satellite links use forward error correction (FEC) because retransmission is impractical over multi-second round-trip delays.
• CRC-32 in Ethernet: Every 64–1518 byte Ethernet frame has a 4-byte CRC appended at the end. If the CRC check fails, the frame is silently discarded — retransmission is handled by higher layers (TCP).