Linear Codes, Bounds on Code Size, and the MacWilliams Identities

Corresponds to Lecture topic 1–3 of the coding theory syllabus. Opens with the Hamming code as the first nontrivial example of a linear code — a subspace of $\mathbb F_q^n$ whose minimum Hamming distance between codewords determines how many errors it can detect/correct — and the associated vocabulary (generator matrix, parity-check matrix, dual code). Covers the three standard bounds on how large a code can be for a given length and minimum distance: the sphere-packing (Hamming) bound (an upper bound, from disjoint error-correcting balls around codewords), the Plotkin bound (a different upper bound, strong when the relative minimum distance is large), and the Gilbert-Varshamov bound (a existence/lower bound via a greedy/volume argument, long the best known general-purpose guarantee). The MacWilliams identities are the chapter’s technical centerpiece: a transform (closely related to the discrete Fourier transform over $\mathbb F_2^n$) relating a linear code’s weight enumerator polynomial to its dual code’s — letting you compute one from the other without ever enumerating codewords directly.

Outline (TODO — flesh out each)

• Hamming codes
• Linear codes — minimum Hamming distance, generator/parity-check matrices
• Dual codes
• The sphere-packing (Hamming) bound
• The Plotkin bound
• The Gilbert-Varshamov bound
• The MacWilliams identities
• Extended coverage of the MacWilliams identities