Error Detection Codes

Error detection codes are built into every memory chip, CAN bus frame, and Ethernet packet your system sends. Without them, a single flipped bit in a RAM array or a noise pulse on a data line would corrupt data silently and permanently.

Core Concept

Error detection works by adding redundant bits to transmitted data so the receiver can check whether any bits flipped during transmission. The key metric is Hamming distance — the minimum number of bit positions that differ between any two valid codewords. A code with Hamming distance d can detect up to d-1 single-bit errors and correct up to floor((d-1)/2) errors.

Simple parity adds one bit so the total number of 1s is always even (even parity) or always odd (odd parity). The 74280 IC generates and checks 9-bit parity — one byte plus one parity bit. Its propagation delay is 23 ns at 5 V supply with a fan-out of 20 LS-TTL loads. Parity detects all odd-numbered bit errors but misses even-numbered errors.

CRC (Cyclic Redundancy Check) uses polynomial division to produce a multi-bit checksum. CRC-16 detects all burst errors of 16 bits or fewer. The 74F401 CRC generator IC implements CRC-16 and CCITT polynomials in hardware. CRC is standard in USB, Ethernet, and CAN bus frames for this reason.

Boolean Expression

Even parity bit P for data bits d1 through dn: P = d1 XOR d2 XOR ... XOR dn. The receiver recomputes this XOR; a non-zero result signals an error. For a single parity bit, the Hamming distance is 2 — it detects 1-bit errors but cannot locate which bit flipped. The syndrome in Hamming code extends this to a multi-bit XOR pattern that identifies the exact error position.

Given:
  Data word = 1101001 (7 bits)
  Using even parity

Formula / Rule:
  P = d1 XOR d2 XOR d3 XOR d4 XOR d5 XOR d6 XOR d7

Step by step:
  Count 1s in 1101001 = 4 (positions 1,2,4,7)
  P = 1 XOR 1 XOR 0 XOR 1 XOR 0 XOR 0 XOR 1 = 0
  Even count → even parity bit = 0

Transmit: 1101001 0

Error scenario: bit 3 flips → received 1111001 0
  Receiver XOR check: 1 XOR 1 XOR 1 XOR 1 XOR 0 XOR 0 XOR 1 XOR 0 = 1
  Result = 1 (non-zero) → error detected

Final Answer:
  Even parity bit = 0
  1-bit error in received word detected by parity check.

Exam Tip: GATE tests Hamming distance heavily. Remember: minimum Hamming distance d=2 means detect 1-bit errors only (parity). d=3 means detect 2-bit errors OR correct 1-bit errors (Hamming code). You cannot simultaneously detect 2 bits and correct 1 bit with d=3 — you must choose one mode. A second trap: parity cannot detect 2-bit errors because two flipped bits preserve the parity count.

Key Properties

• Hamming distance d: detects up to d-1 errors; corrects up to floor((d-1)/2) errors.
• Simple parity: Hamming distance 2; detects single-bit errors only.
• 74280 parity IC: 9-bit generator/checker, 23 ns propagation delay, 5 V supply.
• CRC-16: detects all burst errors ≤16 bits; implemented in 74F401.
• Parity misses all even-count errors (2, 4, 6… bit flips).
• 2D parity (longitudinal + transverse): Hamming distance 4, detects and corrects 1-bit errors.
• ECC RAM uses Hamming(72,64): adds 8 check bits to 64 data bits for single-bit correction.

Quick Revision

• Error detection: add redundant check bits; Hamming distance d governs capability.
• Parity bit = XOR of all data bits; detects odd-number bit flips only.
• d=2: detect 1-bit; d=3: detect 2-bit or correct 1-bit; d=4: detect 3-bit or correct 1-bit.
• CRC uses polynomial division; CRC-32 is standard in Ethernet and ZIP files.
• 74280: 9-bit parity generator/checker; 23 ns, 5 V TTL.
• ECC RAM (Hamming 72,64): single-bit correction, double-bit detection.
• Exam trap: a code with d=3 cannot both detect 2-bit errors and correct 1-bit errors simultaneously in the same received word — the decoder has to commit to one interpretation.