Error Correction Codes: Reliable Communication Over Noisy Channels

simulation intermediate ~12 min
Loading simulation...

Formula

\text{Hamming}(7,4): \text{syndrome} = H \cdot r^T
R = \frac{k}{n} = \frac{4}{7} \approx 0.571
P_{\text{block error}} = 1 - (1-p)^n - n \cdot p \cdot (1-p)^{n-1}
d_{\min} = 3 \implies \text{corrects } \lfloor(3-1)/2\rfloor = 1 \text{ error}
Every digital communication system faces the same fundamental problem: noise corrupts data. Bits flip, signals fade, and interference intrudes. Error correction codes solve this by adding structured redundancy that enables the receiver to detect and fix errors without asking for retransmission. The simplest approach is repetition: send each bit three times and take a majority vote. This corrects single-bit errors per triple but wastes two-thirds of the channel capacity. Richard Hamming, frustrated by error-prone punch card readers at Bell Labs, invented a far more elegant solution in 1950. Hamming(7,4) encodes 4 data bits into 7 code bits by adding 3 parity bits at carefully chosen positions. Each parity bit covers a specific overlapping subset of the data bits. When a single bit error occurs during transmission, the receiver computes the syndrome — the result of checking all three parity equations. The syndrome is a 3-bit number that directly indicates the position of the error (0 means no error). The receiver simply flips that bit to recover the original data. This simulator lets you transmit hundreds of data blocks through a noisy channel and compare three strategies: no coding (raw transmission), repetition coding, and Hamming coding. Watch as errors (shown in red) corrupt the transmitted bits, parity bits (shown in cyan) enable detection, and the decoder corrects the damage. The deeper lesson is Shannon's channel coding theorem: for any noisy channel, there exists a coding scheme that achieves reliable communication at any rate below the channel capacity. Hamming codes are an early, practical step toward this theoretical promise. Modern codes like LDPC and turbo codes come remarkably close to Shannon's limit.

FAQ

What is a Hamming code?

A Hamming code is a linear error-correcting code invented by Richard Hamming in 1950. The most common variant, Hamming(7,4), encodes 4 data bits into 7 code bits by adding 3 parity bits at positions 1, 2, and 4. Each parity bit covers a specific subset of data bits. The syndrome — computed by checking all parity equations — identifies the position of a single-bit error, enabling correction without retransmission.

How does error correction relate to Shannon's channel coding theorem?

Shannon's channel coding theorem (1948) proves that for any channel with capacity C, reliable communication is possible at any rate below C by using sufficiently long codes. Hamming codes are short, simple codes that correct single errors. Modern codes like turbo codes and LDPC codes approach Shannon's limit much more closely by using longer block lengths and iterative decoding.

What is the difference between error detection and error correction?

Error detection identifies that an error occurred but not where. A simple parity bit can detect any single-bit error. Error correction both detects and locates the error, enabling the receiver to fix it. Hamming(7,4) can correct any single-bit error and detect (but not correct) any two-bit error. Correction requires more redundancy than detection.

Where are error correction codes used in practice?

Error correction codes are ubiquitous: ECC RAM uses Hamming codes to fix memory bit flips; QR codes use Reed-Solomon codes for damage tolerance; hard drives, SSDs, and optical discs use LDPC and Reed-Solomon codes; 5G cellular networks use polar codes and LDPC; deep-space communication uses convolutional and turbo codes to maintain contact across billions of kilometers.

Sources

Other simulations: Information Theory

simulation

Channel Capacity Explorer
simulation

Data Compression Simulator
simulation

Shannon Entropy Calculator
View source on GitHub