Coding theory is the mathematical study of how to transmit information reliably over noisy channels and store it on imperfect media. By adding controlled redundancy to data β error-detecting or error-correcting bits β codes allow receivers to identify and repair corruptions without retransmission. The field spans foundational block-code algebra, iterative modern schemes, and practical deployment in everything from QR codes and storage RAID to 5G wireless and deep-space telemetry. A key mental model: the code rate R = k/n (information bits / total bits) and the minimum Hamming distance d_min together govern what a code can do β higher redundancy buys more error correction, and Shannon's channel capacity sets the ultimate limit no code can exceed.
What This Cheat Sheet Covers
This topic spans 17 focused tables and 126 indexed concepts. Below is a complete table-by-table outline of this topic, spanning foundational concepts through advanced details.
Table 1: Channel Models
Every error-correcting code is designed for a specific channel model. These three models β Binary Symmetric Channel, Binary Erasure Channel, and Additive White Gaussian Noise β cover the vast majority of practical scenarios and anchor the theoretical bounds used throughout coding theory.
| Model | Example | Description |
|---|---|---|
\Pr[Y \neq X] = p | β’ Each transmitted bit is independently flipped with crossover probability pβ’ capacity C = 1 - H_b(p) where H_b is binary entropy | |
\Pr[Y = \text{e}] = p_e | β’ Bit is received correctly or erased (marked unknown) with probability p_eβ’ capacity C = 1 - p_eβ’ easier to decode than BSC | |
Y = X + N,\ N \sim \mathcal{N}(0,\sigma^2) | β’ Continuous channel β’ received signal is transmitted value plus Gaussian noise β’ capacity C = \frac{1}{2}\log_2(1 + \text{SNR}) (ShannonβHartley). |