Coding Theory

Bits, parity, and error-correcting codes from repetition to Hamming.

Binary & XOR — Bits, , and Hamming distance — the alphabet of coding theory.
Repetition Code — Repeat each bit n times, decode by majority — the rate vs. distance tradeoff at its starkest.
Singleton Bound — d ≤ n - k + 1 — the fundamental limit on rate vs. distance.
Parity Check Matrix — C = c : Hc = 0 — the dual representation of a linear code.
Hat Puzzle — Sequential: n - 1 guaranteed. Simultaneous (Hamming): n/(n+1).
Hamming Code — Hamming(7,4): rate 4/7, single-error correction, syndrome = error position.

Further Topics

Hamming Distance & Minimum Distance — Counting disagreeing positions, and the distance that bounds correction.
Linear Codes & Generator Matrix — Generator matrix G, encoding uG, and the [n, k, d] parameters.
Syndrome Decoding — Decode by the syndrome: cosets, coset leaders, and the parity-check matrix.
Dual Codes — Orthogonal complement of a code, and the generator/parity-check duality.
Hamming / Sphere-Packing Bound — Pack disjoint balls to cap code size; equality means perfect.
Perfect Codes — The sphere-packing bound and the codes that meet it: Hamming and Golay.
Cyclic Codes — Generator polynomials, ideals modulo x^n-1, and polynomial encoding.
Reed–Solomon Codes — Encode a message as a polynomial, sample it, and recover from errors.
Gilbert–Varshamov Bound — A sphere-covering guarantee that good codes exist.