Part 9: Error Detection and Correction: Parity, Checksums, CRC-32 & Hamming

1. Types of Errors: Single-Bit vs. Burst Errors

2. Cyclic Redundancy Check (CRC-32)

The most powerful hardware-implemented error-detection code used in Ethernet (802.3), Wi-Fi, and storage SATA buses is the Cyclic Redundancy Check (CRC).

CRC treats binary bit sequences as algebraic polynomials with binary coefficients. Using Modulo-2 binary division (which uses XOR addition without carry), the transmitter appends an \(n\)-bit remainder (FCS) calculated by dividing the data payload by a predetermined divisor polynomial \(G(x)\). The receiver performs the identical division: if the remainder is exactly zero, the frame is intact; otherwise, it is silently dropped.

3. Hamming Codes: Forward Error Correction (FEC)

While CRC detects errors (prompting a request for retransmission via ARQ), satellite and deep-space links incur round-trip delays that make retransmission impractical. These links require Forward Error Correction (FEC), pioneered by Richard Hamming.

According to Hamming distance theory:

• To detect \(s\) errors, the minimum Hamming distance must satisfy: \(d_{min} \ge s + 1\).
• To correct \(t\) errors, the minimum Hamming distance must satisfy: \(d_{min} \ge 2t + 1\).

By interleaving parity check bits at positions of powers of 2 (1, 2, 4, 8, ...), the Hamming code computes an error syndrome whose binary numeric value directly identifies the exact bit position that flipped, allowing the receiver to invert it back without retransmission!