Error Detection

Error Detection: Finding Mistakes in Digital Transmission

In any real-world communication system, errors are inevitable. Noise corrupts signals, interference garbles data, and components introduce distortion. Error detection is the art of adding just enough extra information to transmitted data so that the receiver can reliably determine whether errors have occurred. Without error detection, a digital system would silently deliver corrupted data — and you would never know your downloaded file was damaged or your bank transfer amount was wrong.

Why Errors Happen

Think of it this way: when you speak in a noisy restaurant, some of your words get lost. The listener can often tell that they missed something (detection) and may ask you to repeat it (retransmission). Digital communication faces the same fundamental challenge — the "noise" comes from:

Thermal noise: Random electron motion in every electronic component generates continuous background noise. This is the most fundamental and unavoidable noise source.

Interference: Other signals sharing nearby frequencies leak into the desired channel — like someone else's conversation in a crowded room.

Fading: In wireless systems, signal strength fluctuates as the environment changes (buildings, movement, weather).

Equipment imperfections: Non-ideal filters, amplifiers, and clocks introduce distortion that corrupts signal timing and amplitude.

Types of Errors

Single-bit errors: One isolated bit flips from 0→1 or 1→0. Caused by brief noise spikes. Common in parallel data buses.

Burst errors: Multiple consecutive bits are corrupted. Caused by signal fades, impulse noise (lightning, switching), or scratches on optical media. The burst length is defined as the distance from first to last error bit.

Random errors: Bits are independently corrupted with equal probability. Characteristic of AWGN channels. BER (Bit Error Rate) describes the probability of each bit being wrong.

Understanding the error model is critical for choosing the right detection scheme:

• Random errors → parity checks and checksums work well
• Burst errors → CRC and interleaved codes are needed

The Principle of Redundancy

All error detection works by adding redundant (extra) information that creates constraints the valid data must satisfy. If received data violates these constraints, an error has occurred.

Code rate: r = k/(k+m), where k = data bits, m = redundancy bits Overhead: m/(k+m) = fraction of transmitted bits that are redundancy

The trade-off: more redundancy → better detection → less throughput for useful data.

Parity Check: The Simplest Detector

Add one bit to make the total number of 1s even (even parity) or odd (odd parity):

Example (even parity):

• Data: 1011001 (four 1s — even) → Parity bit = 0 → Transmitted: 10110010
• Data: 1011011 (five 1s — odd) → Parity bit = 1 → Transmitted: 10110111

Detection capability: Detects ALL single-bit errors and ALL odd numbers of bit errors. Misses all even numbers of bit errors.

Overhead: Just 1 bit per data word — minimal.

Two-Dimensional Parity

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

Detection: Catches single-bit errors AND pinpoints their exact position (error correction). Also detects most double and triple errors. However, rectangular error patterns (4 bits at corners of a rectangle) go undetected.

Checksum-Based Detection

Add all data units and transmit the sum. The receiver recomputes and compares:

• Simple sum checksum: Fast, catches most errors
• One's complement checksum: Used in TCP/IP
• Fletcher checksum: Catches byte reordering

Detection strength depends on checksum size: n-bit checksum misses approximately one in 2ⁿ random error patterns.

Cyclic Redundancy Check (CRC)

The most powerful practical error detection technique. Uses polynomial division to generate a check value sensitive to bit positions:

• CRC-16: Detects all bursts ≤ 16 bits
• CRC-32: Detects all bursts ≤ 32 bits, all single and double errors

CRC dominates in Ethernet, USB, HDLC, storage media, and file formats.

Automatic Repeat Request (ARQ)

Error detection is most commonly paired with ARQ — a protocol that retransmits data when errors are detected:

Stop-and-Wait ARQ:

1. Send one frame, wait for acknowledgment
2. ACK received → send next frame
3. NACK (or timeout) → retransmit same frame

Go-Back-N ARQ:

1. Send up to N frames without waiting for ACKs
2. If error detected in frame k → retransmit frame k and ALL subsequent frames
3. Simple receiver but wastes bandwidth retransmitting correct frames

Selective Repeat ARQ:

1. Send up to N frames continuously
2. If error detected in frame k → retransmit only frame k
3. Receiver buffers out-of-order frames and resequences
4. Most bandwidth-efficient but complex receiver

Metrics for Error Detection Performance

Undetected error probability (Pud): Probability that an error pattern produces a valid code word. For random errors and n-bit check field: Pud ≈ 2⁻ⁿ.

Missed detection rate: Fraction of all possible error patterns that go undetected. Depends on the code structure and error model.

Throughput efficiency: Fraction of transmitted bits that carry useful data:

• Without errors: η = k/(k+m)
• With errors and ARQ: η = k/(k+m) × (1 - Pf) — where Pf is frame error probability

Choosing the Right Detection Method

Error Detection in Layered Protocols

Modern communication systems apply error detection at multiple layers:

1. Physical layer: Parity checks on individual characters
2. Data link layer: CRC on each frame (Ethernet CRC-32)
3. Network layer: IP header checksum
4. Transport layer: TCP/UDP checksum over entire segment
5. Application layer: File hash verification (MD5, SHA-256)

Each layer catches errors that slip through lower layers, providing defense-in-depth.

Key Takeaways

1. Error detection adds redundant information that creates constraints — violations of these constraints reveal errors.
2. Single parity detects all odd-numbered errors; CRC detects all burst errors up to its polynomial degree.
3. The trade-off is always overhead vs. detection strength — more redundancy means better detection but less useful throughput.
4. Error detection is typically paired with ARQ (retransmission) for reliable delivery, or with FEC for one-way channels.
5. Real systems use multiple layers of error detection (CRC at link layer, checksum at transport layer) for defense-in-depth.
6. The choice of detection method depends on the error model: random errors → checksums/parity; burst errors → CRC.