Coding Theory: Hamming Codes & Error Correction
How redundancy turns noisy channels into reliable ones.
A linear $[n, k, d]_q$ code is a $k$-dimensional subspace of $\mathbb F_q^n$ with minimum Hamming distance $d$ (smallest weight of any nonzero codeword). Can correct up to $\lfloor (d-1)/2 \rfloor$ errors per codeword.
Hamming bound: $|C| \cdot \sum_{i=0}^t \binom{n}{i}(q-1)^i \leq q^n$ for any $t$-error-correcting code. Codes achieving equality are perfect.
Hamming $[7,4,3]$ code: encodes 4 data bits into 7 with three parity checks, corrects any single-bit error. Generator matrix
$$G = \begin{pmatrix} 1&0&0&0&1&1&0 \\ 0&1&0&0&1&0&1 \\ 0&0&1&0&0&1&1 \\ 0&0&0&1&1&1&1 \end{pmatrix}.$$Parity-check matrix $H$ such that $HG^T = 0$; the syndrome $H r$ of a received word $r$ identifies the error position.
Beyond Hamming: Reed–Solomon codes correct burst errors (used in CDs, DVDs, QR codes); LDPC and turbo codes approach the Shannon limit and power modern Wi-Fi, 4G/5G, satellite communications.