Error Detection Codes

Introduction

Data in a computer isn't always safe. When bits travel across a network cable, get written to a disk, or sit in memory, they can get corrupted — a 1 might flip to a 0 due to electrical noise, cosmic rays (yes, really!), or hardware faults. Error detection codes add extra bits to data so that the receiver can detect (and sometimes correct) errors. This is a critical aspect of reliable computer systems.

Why Errors Occur

Sources of Errors

• Electrical noise: Interference on communication lines
• Cosmic rays: High-energy particles can flip bits in memory (soft errors)
• Hardware aging: Degradation of storage media over time
• Cross-talk: Signals interfering between adjacent wires
• Timing errors: Reading data at the wrong moment

Error Types

• Single-bit error: One bit is flipped (most common)
• Burst error: Multiple consecutive bits are corrupted (common in communication)
• Random errors: Multiple non-adjacent bits affected

Parity Bit (Simplest Error Detection)

Concept

Add one extra bit to make the total number of 1s either always even (even parity) or always odd (odd parity).

Even Parity

The parity bit is set so that the total number of 1s (including the parity bit) is even.

Odd Parity

The parity bit makes the total count of 1s odd.

Detection Capability

• Detects: All single-bit errors and any odd number of bit errors
• Cannot detect: Even number of bit errors (two bits flip → parity still matches)
• Cannot correct: Any errors (only detects, doesn't know which bit is wrong)

Where It's Used

• Memory systems (parity RAM)
• Serial communication (RS-232)
• ASCII transmission (8th bit as parity)

Two-Dimensional Parity

Concept

Arrange data in a matrix and compute parity for each row AND each column:

Advantages Over Simple Parity

• Can detect most 2-bit errors
• Can identify and correct single-bit errors (the intersection of the failing row and column reveals the bad bit)
• Detects burst errors better than simple parity

Hamming Code (Error Correction)

Concept

Richard Hamming developed a code that not only detects errors but pinpoints exactly which bit is wrong, allowing correction. The key idea: use multiple parity bits, each covering a different subset of data bits. The pattern of which parity checks fail reveals the error position.

How It Works (Hamming(7,4) — 4 data bits, 3 parity bits)

Position the 7 bits (p1, p2, d3, p4, d5, d6, d7) where parity bits occupy positions that are powers of 2:

Each parity bit covers positions whose binary representation has a 1 in the corresponding bit position:

• P1 (position 1 = ...001): covers positions 1,3,5,7 (binary xxx1)
• P2 (position 2 = ...010): covers positions 2,3,6,7 (binary xx1x)
• P4 (position 4 = ...100): covers positions 4,5,6,7 (binary x1xx)

Encoding Example

Data bits: d3=1, d5=0, d6=1, d7=0

Calculate parity bits (even parity):

• P1 covers positions 1,3,5,7: P1⊕1⊕0⊕0=0 → P1=1
• P2 covers positions 2,3,6,7: P2⊕1⊕1⊕0=0 → P2=0
• P4 covers positions 4,5,6,7: P4⊕0⊕1⊕0=0 → P4=1

Encoded: 1 0 1 1 0 1 0

Error Detection and Correction

Receiver checks all parity groups. If all check out → no error. If some fail, their position numbers form the syndrome, which is the binary address of the error bit.

Example: If P1 and P4 fail → syndrome = 101₂ = 5 → bit 5 is wrong → flip it!

Hamming Distance

The Hamming distance between two codes is the number of positions where they differ. For a code with minimum distance d:

• Can detect up to (d-1) errors
• Can correct up to ⌊(d-1)/2⌋ errors

Hamming(7,4) has minimum distance 3 → detects 2 errors, corrects 1.

CRC (Cyclic Redundancy Check)

Concept

CRC treats the data as a polynomial and divides it by a fixed generator polynomial. The remainder of this division is appended to the data as a check value. The receiver performs the same division — if the remainder is zero, no errors detected.

How CRC Works (Simplified)

1. Choose a generator polynomial G(x) of degree r (e.g., x³+x+1 → 1011)
2. Append r zeros to the data
3. Divide (XOR-based polynomial division) by the generator
4. The remainder (r bits) is the CRC — append it to the original data
5. Receiver divides the entire received message by G(x) — remainder should be 0

CRC Properties

• Detects all single-bit errors
• Detects all double-bit errors (with proper generator)
• Detects all burst errors shorter than r+1 bits
• Very efficient in hardware (shift register implementation)

Common CRC Standards

• CRC-8: 8-bit check, used in ATM, Bluetooth
• CRC-16: Used in USB, Modbus
• CRC-32: Used in Ethernet, ZIP files, PNG images

Checksum

Concept

Divide data into fixed-size words, add them all up, and transmit the sum. The receiver adds all words plus the checksum — should get a known result.

Internet Checksum (used in TCP/IP)

1. Divide data into 16-bit words
2. Add all words using one's complement addition
3. The complement of the sum is the checksum
4. Receiver adds all words + checksum → should get all 1s (0xFFFF)

Comparison of Methods

Applications in Computer Systems

• ECC RAM: Uses Hamming codes (or SEC-DED variants) to correct single-bit memory errors — critical in servers
• Hard drives: Use CRC and Reed-Solomon codes for data integrity
• Networking: Ethernet frames include CRC-32; TCP uses checksums
• Flash memory: Uses BCH or LDPC codes for error correction

Key Takeaways

1. Error detection adds redundant bits to data so corruption can be identified
2. Parity is simplest — detects odd numbers of errors but cannot correct
3. Hamming code can locate and correct single-bit errors using multiple overlapping parity groups
4. CRC uses polynomial division — excellent for detecting burst errors in communication
5. The choice of method balances detection capability, overhead, and hardware complexity
6. Modern systems layer multiple error detection/correction methods for reliability