40.06.08 · combinatorics / design-coding-theory

Cyclic Codes: BCH, Reed-Solomon, Reed-Muller, and Assmus-Mattson

shipped3 tiersLean: none

Anchor (Master): van Lint 1999 *Introduction to Coding Theory* 3e (Springer GTM 86) Ch. 6-7, 9 (cyclic codes, BCH bound, Reed-Solomon MDS optimality, Reed-Muller and majority-logic decoding, Assmus-Mattson and the 5-designs); MacWilliams-Sloane 1977 *The Theory of Error-Correcting Codes* (North-Holland) Ch. 7-9, 13-15 (cyclic codes, BCH, Reed-Muller, generalized Reed-Solomon, the Assmus-Mattson theorem); Bose-Ray-Chaudhuri 1960 *Information and Control* 3; Hocquenghem 1959 *Chiffres* 2; Reed-Solomon 1960 *J. SIAM* 8; Reed 1954 *IRE Trans.* 4 and Muller 1954 *IRE Trans.* 3; Assmus-Mattson 1969 *J. Combin. Theory* 6

Intuition Beginner

A code is a chosen collection of allowed strings, spread far apart so that a few flipped symbols cannot carry one allowed string all the way to another. Most codes are just lists with no further pattern. A cyclic code adds one extra rule of remarkable power: if a string is allowed, then so is the string you get by sliding every symbol one step to the right and wrapping the last symbol around to the front. Rotate a codeword and you land on another codeword. This single symmetry, repeated, ties the whole code together and makes it cheap to build and to decode in real hardware.

The trick that unlocks the symmetry is to stop thinking of a string of length $n$ as a flat list and instead read it as the coefficients of a polynomial. The string $a_{0} a_{1} a_{2}$ becomes $a_{0} + a_{1} x + a_{2} x^{2}$ . Sliding the symbols one step and wrapping around turns out to be the same as multiplying that polynomial by $x$ and folding $x^{n}$ back to $1$ . So a cyclic code is a family of polynomials closed under multiplication by $x$ , and one special polynomial — the generator — divides every codeword and so describes the whole code at a glance.

Why care? Because choosing the generator's roots lets you order up a code to spec. Want to correct three errors? Plant a run of related roots and a clean count guarantees the codewords stay far apart. This is how the codes on a scratched compact disc, in a QR square, and on a probe past Pluto are made: Reed-Solomon and BCH codes, both cyclic, both built by choosing roots.

Visual Beginner

Picture a codeword as beads on a ring rather than on a straight wire. A cyclic shift just rotates the ring by one bead; the cyclic-code rule says every rotation of an allowed pattern is again allowed. So codewords come in whole rotation families, and the code is built from these spinning necklaces rather than from isolated strings.

length- $7$ string	as a polynomial	shift right by one (wrap around)
$1000000$	$1$	$0100000$ which is $x$
$0100000$	$x$	$0010000$ which is $x^{2}$
$0000001$	$x^{6}$	$1000000$ which is $1$ (the $x^{7}$ wraps to $1$ )

The table shows the engine: shifting a string is multiplying its polynomial by $x$ , and when a power reaches $x^{7}$ it folds back to $1$ . A cyclic code is exactly a set of polynomials you can multiply by $x$ and stay inside.

Worked example Beginner

Build a small cyclic code of length $7$ over the two-symbol alphabet ${0, 1}$ by hand. Start from the generator polynomial $g (x) = 1 + x + x^{3}$ , a divisor of $x^{7} - 1$ . Codewords are the multiples of $g$ that still have length $7$ , namely $g (x)$ times a message polynomial of degree at most $3$ .

Step 1. Read off the generator as a string. The polynomial $1 + x + x^{3}$ has coefficient $1$ at positions $0$ , $1$ , and $3$ , so $g$ is the string $1101000$ .

Step 2. Make a codeword by multiplying. Take the message $m (x) = 1 + x$ , the string $1100000$ . Multiply: $(1 + x) (1 + x + x^{3}) = 1 + x + x^{3} + x + x^{2} + x^{4} = 1 + x^{2} + x^{3} + x^{4}$ , since $x + x = 0$ in this alphabet. That is the string $1011100$ .

Step 3. Check the cyclic-shift rule. Slide $1011100$ right by one with wraparound to get $0101110$ . As a polynomial this is $x + x^{3} + x^{4} + x^{5}$ , which equals $x \cdot (1 + x^{2} + x^{3} + x^{4})$ folded — and it is again a multiple of $g$ , so it is another codeword.

Step 4. Count the codewords. The message has $4$ free coefficients, so there are $2^{4} = 16$ codewords. This is the $[7, 4]$ Hamming code in cyclic dress.

What this tells us: one short generator polynomial, by multiplication alone, produces an entire code that is automatically closed under rotation. Picking a different generator with cleverly chosen roots is how engineers dial in exactly how many errors the code will fix.

Check your understanding Beginner

Formal definition Intermediate+

Throughout, $F_{q}$ is the finite field with $q$ elements (its structure is developed in 21.02.01; here it is applied), $q$ a prime power, and $g cd (n, q) = 1$ so that $x^{n} - 1$ has $n$ distinct roots in a splitting field. Words of length $n$ are identified with polynomials of degree below $n$ via $a = (a_{0}, \dots, a_{n - 1}) \leftrightarrow a (x) = \sum_{i = 0}^{n - 1} a_{i} x^{i}$ , inside the quotient ring $R_{n} = F_{q} [x] / (x^{n} - 1)$ . The Hamming metric and the parameters $[n, k, d]_{q}$ are those of 40.06.06.

Definition (cyclic code). A linear code $C \subseteq F_{q}^{n}$ is cyclic if it is closed under the cyclic shift $(a_{0}, \dots, a_{n - 1}) \mapsto (a_{n - 1}, a_{0}, \dots, a_{n - 2})$ . Under the identification above, this shift is multiplication by $x$ in $R_{n}$ , so $C$ is cyclic exactly when $C$ is an ideal of $R_{n}$ .

Definition (generator and check polynomials). Since $R_{n}$ is a principal ideal ring, every cyclic code $C$ is generated by a unique monic divisor $g (x) ∣ x^{n} - 1$ of least degree, the generator polynomial; then $C = ⟨ g (x)⟩$ , $dim C = n - de g g$ , and a generator matrix has rows the shifts $g (x), xg (x), \dots, x^{k - 1} g (x)$ with $k = n - de g g$ . The check polynomial is $h (x) = (x^{n} - 1) / g (x)$ ; a word $c (x)$ lies in $C$ iff $c (x) h (x) \equiv 0 (mod x^{n} - 1)$ , and $C^{⊥}$ is the cyclic code with generator the reciprocal of $h$ .

Definition (defining set). Fix a primitive $n$ -th root of unity $α$ in an extension $F_{q^{m}}$ (so $m$ is the multiplicative order of $q$ modulo $n$ ). The defining set of $C$ is $$ T = { i \in \mathbb{Z}_n : g(\alpha^i) = 0 }, $$ the exponents of the roots of $g$ among the powers of $α$ . Because $g$ has coefficients in $F_{q}$ , the set $T$ is a union of $q$ -cyclotomic cosets $C_{s} = {s, s q, s q^{2}, \dots} (mod n)$ , and $c (x) \in C$ iff $c (α^{i}) = 0$ for all $i \in T$ .

Definition (BCH and Reed-Solomon codes). The BCH code of length $n$ and designed distance $δ$ over $F_{q}$ is the cyclic code whose defining set contains a run of $δ - 1$ consecutive exponents $b, b + 1, \dots, b + δ - 2$ ; equivalently $g$ is the least-degree polynomial over $F_{q}$ vanishing at $α^{b}, \dots, α^{b + δ - 2}$ , namely the least common multiple of their minimal polynomials. It is narrow-sense when $b = 1$ and primitive when $n = q^{m} - 1$ . A Reed-Solomon code is the special case $n = q - 1$ , $α$ a primitive element of $F_{q}$ itself ( $m = 1$ ): then each minimal polynomial is linear, $g (x) = \prod_{i = 1}^{δ - 1} (x - α^{i})$ has degree $δ - 1$ , and the code is $[q - 1, q - δ, δ]_{q}$ .

Definition (Reed-Muller code). For $0 \leq r \leq m$ the Reed-Muller code $RM (r, m)$ is the binary code of length $2^{m}$ obtained by evaluating every Boolean polynomial in $m$ variables of degree at most $r$ at all $2^{m}$ points of $F_{2}^{m}$ : $$ \mathrm{RM}(r,m) = { (f(v))_{v \in \mathbb{F}_2^m} : f \in \mathbb{F}2[x_1,\dots,x_m],\ \deg f \le r }, $$ with dimension $\sum{i=0}^{r} \binom{m}{i} $an d minim u m d i s t an ce$ 2^{m-r}$.

Counterexamples to common slips Intermediate+

The generator is not any divisor — it is the monic divisor of least degree generating the ideal. Two different divisors of $x^{n} - 1$ generate different codes; the dimension is $n - de g g$ , so a larger $g$ means a smaller code.
The BCH bound uses a run of consecutive exponents, not just $δ - 1$ roots. Any $δ - 1$ roots scattered arbitrarily give no distance guarantee; the consecutive-run hypothesis is what powers the Vandermonde argument. Conversely the true minimum distance can exceed the designed distance $δ$ .
Reed-Solomon needs $n \leq q$ . Because the evaluation points are field elements (and the roots of the generator are powers of a primitive element of $F_{q}$ itself), $n = q - 1$ for the cyclic form and $n \leq q$ for the extended/evaluation form; you cannot have a length- $255$ Reed-Solomon code over $F_{2}$ — it lives over $F_{256}$ .
$RM (r, m)$ is graded by degree, not by a single monomial. The codewords come from all polynomials up to degree $r$ , so $RM (0, m)$ is the repetition code, $RM (m, m)$ is the whole space, and $RM (m - 1, m)$ is the even-weight (parity-check) code.

Key theorem with proof Intermediate+

The structural engine of designed-distance codes is the BCH bound: a run of consecutive zeros of the generator forces a lower bound on minimum distance, proved by a Vandermonde determinant. From it the Reed-Solomon MDS optimality follows at once.

Theorem (BCH bound). Let $C$ be a cyclic code of length $n$ over $F_{q}$ with defining set $T$ , and suppose $T$ contains $δ - 1$ consecutive exponents $b, b + 1, \dots, b + δ - 2$ . Then the minimum distance satisfies $d (C) \geq δ$ ^{[Bose-Ray-Chaudhuri 1960]}.

Proof. Let $α$ be the fixed primitive $n$ -th root of unity, so $α^{b}, α^{b + 1}, \dots, α^{b + δ - 2}$ are roots of every codeword polynomial. Let $c (x) = \sum_{j} c_{j} x^{j}$ be a nonzero codeword and write its support $supp (c) = {j_{1}, \dots, j_{w}}$ with $w = wt (c)$ ; the nonzero coefficients are $c_{j_{1}}, \dots, c_{j_{w}}$ . The condition $c (α^{b + ℓ}) = 0$ for $ℓ = 0, \dots, δ - 2$ reads $$ \sum_{s=1}^{w} c_{j_s}, (\alpha^{j_s})^{,b+\ell} = 0, \qquad \ell = 0, 1, \dots, \delta - 2. $$ Set $β_{s} = α^{j_{s}}$ and $d_{s} = c_{j_{s}} β_{s}^{b}$ ; the $β_{s}$ are distinct powers of $α$ , and each $d_{s} \neq = 0$ . The equations become $\sum_{s = 1}^{w} d_{s} β_{s}^{ℓ} = 0$ for $ℓ = 0, \dots, δ - 2$ . Suppose, for contradiction, that $w \leq δ - 1$ . Take the first $w$ of these equations ( $ℓ = 0, \dots, w - 1$ ); in matrix form they are $V d = 0$ , where $V = (β_{s}^{ℓ})_{ℓ, s}$ is a $w \times w$ Vandermonde matrix on the distinct nodes $β_{1}, \dots, β_{w}$ . Its determinant is $\prod_{s < t} (β_{t} - β_{s}) \neq = 0$ , so $V$ is invertible and $d = 0$ , contradicting $d_{s} \neq = 0$ . Hence $w \geq δ$ , and since $C$ is linear $d (C) = min_{c \neq = 0} wt (c) \geq δ$ . $□$

Corollary (Reed-Solomon codes are MDS). The Reed-Solomon code with $n = q - 1$ and generator $g (x) = \prod_{i = 1}^{δ - 1} (x - α^{i})$ is an $[q - 1, q - δ, δ]_{q}$ code meeting the Singleton bound ^{[Reed-Solomon 1960]}. Here $de g g = δ - 1$ , so $k = n - (δ - 1) = q - δ$ , and the defining set is the consecutive run ${1, \dots, δ - 1}$ , giving $d \geq δ$ by the BCH bound. The Singleton bound of 40.06.06 gives $d \leq n - k + 1 = (q - 1) - (q - δ) + 1 = δ$ . The two inequalities force $d = δ = n - k + 1$ , so the code is maximum distance separable.

Bridge. The BCH bound builds toward every designed-distance construction by converting "plant $δ - 1$ consecutive roots" into the certificate $d \geq δ$ , and it appears again in the master tier as the spectral skeleton of Reed-Solomon decoding, where the same Vandermonde structure becomes the key equation of Berlekamp-Massey. The foundational reason a consecutive run works — and scattered roots do not — is that consecutiveness is exactly the hypothesis making the coefficient matrix a Vandermonde on distinct nodes, so non-vanishing of $\prod_{s < t} (β_{t} - β_{s})$ is the whole proof. This is dual to the Singleton bound of 40.06.06: Singleton caps $d$ from above by the rank of a parity-check matrix, the BCH bound props $d$ up from below by the rank of a Vandermonde, and putting these together pins Reed-Solomon to the MDS boundary where the two meet. The central insight, that a code's distance is read off the zeros of its generator rather than its coefficients, generalises into the design-theoretic Assmus-Mattson theorem, where the placement of dual zeros below the redundancy forces the fixed-weight codewords into $t$ -designs.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

Over $F_{2}$ , the $2$ -cyclotomic cosets modulo $7$ are ${0}$ , ${1, 2, 4}$ , and ${3, 6, 5}$ . The minimal polynomial of a primitive $7$ th root $α$ is $m_{1} (x) = 1 + x + x^{3}$ (defining set ${1, 2, 4}$ ). Show that the narrow-sense BCH code of length $7$ with designed distance $δ = 3$ is the $[7, 4, 3]_{2}$ Hamming code, and identify its generator.

Hint

A designed distance $δ = 3$ needs the consecutive run ${1, 2}$ in the defining set. Which cyclotomic coset contains both $1$ and $2$ ? The generator is the lcm of the minimal polynomials of those roots.

Answer

To force $δ = 3$ the defining set must contain the consecutive exponents ${1, 2}$ . Both $1$ and $2$ lie in the single cyclotomic coset ${1, 2, 4}$ , whose minimal polynomial is $m_{1} (x) = 1 + x + x^{3}$ . Hence $g (x) = m_{1} (x) = 1 + x + x^{3}$ , of degree $3$ , so $k = 7 - 3 = 4$ and the BCH bound gives $d \geq 3$ . The defining set ${1, 2, 4}$ has size $3 = n - k$ , the redundancy, so this is the full parity. The resulting $[7, 4]$ cyclic code with $d = 3$ is the Hamming code (the true distance equals the designed distance here). Rubric: full credit for noting ${1, 2}$ forces the coset ${1, 2, 4}$ , the generator $1 + x + x^{3}$ , the parameters $[7, 4, 3]$ , and the Hamming identification.

Exercise 4 (medium, symbolic).

Prove the $(u, u + v)$ construction for Reed-Muller codes: $RM (r, m) = {(u, u + v) : u \in RM (r, m - 1), v \in RM (r - 1, m - 1)}$ , and use it to derive the dimension recursion $dim RM (r, m) = dim RM (r, m - 1) + dim RM (r - 1, m - 1)$ .

Hint

Split the variables as $x_{1}, \dots, x_{m - 1}$ and $x_{m}$ . Write any degree- $\leq r$ polynomial as $f (x_{1}, \dots, x_{m - 1}) + x_{m} h (x_{1}, \dots, x_{m - 1})$ and read off the degrees of $f$ and $h$ . Evaluate on the two halves $x_{m} = 0$ and $x_{m} = 1$ .

Answer

Index the $2^{m}$ points of $F_{2}^{m}$ by $(w, x_{m})$ with $w \in F_{2}^{m - 1}$ , listing the $x_{m} = 0$ half first. A Boolean polynomial of degree $\leq r$ is uniquely $f (x^{'}) + x_{m} h (x^{'})$ with $x^{'} = (x_{1}, \dots, x_{m - 1})$ , where $de g f \leq r$ and $de g h \leq r - 1$ (the factor $x_{m}$ already contributes degree $1$ ). Evaluating: on the half $x_{m} = 0$ the codeword is $ev (f) =: u \in RM (r, m - 1)$ ; on the half $x_{m} = 1$ it is $ev (f) + ev (h) = u + v$ with $v = ev (h) \in RM (r - 1, m - 1)$ . Thus every codeword has the form $(u, u + v)$ , and conversely each such pair arises from a unique $(f, h)$ , giving the stated equality. Since $u$ and $v$ range independently over the two codes, $dim RM (r, m) = dim RM (r, m - 1) + dim RM (r - 1, m - 1)$ , which unrolls to $\sum_{i = 0}^{r} (i m)$ by Pascal's identity. Rubric: full credit for the unique split $f + x_{m} h$ with correct degree bounds, the two-half evaluation giving $(u, u + v)$ , and the independent-range dimension count.

Exercise 7 (hard, symbolic).

Prove that $RM (r, m)$ has minimum distance exactly $2^{m - r}$ . Show the lower bound by induction on $m$ via the $(u, u + v)$ construction, and exhibit a weight- $2^{m - r}$ codeword.

Hint

For the weight bound use $wt (u, u + v) \geq min (2 wt (u), wt (v))$ when $v \neq = 0$ , plus the inductive distances $2^{(m - 1) - r}$ and $2^{(m - 1) - (r - 1)}$ . For the achieving word evaluate the monomial $x_{1} x_{2} \dots x_{r}$ .

Answer

Induct on $m$ . Base $m = r$ : $RM (m, m)$ is the whole space, distance $1 = 2^{0}$ ; and $RM (0, m)$ is the repetition code, distance $2^{m}$ . Inductive step: a nonzero codeword of $RM (r, m)$ is $(u, u + v)$ with $u \in RM (r, m - 1)$ , $v \in RM (r - 1, m - 1)$ . If $v = 0$ then the word is $(u, u)$ with $u \neq = 0$ , of weight $2 wt (u) \geq 2 \cdot 2^{(m - 1) - r} = 2^{m - r}$ . If $v \neq = 0$ , then since $wt (u + v) \geq wt (v) - wt (u)$ and $wt (u) + wt (u + v) \geq wt (v)$ , $$ \mathrm{wt}(u, u+v) = \mathrm{wt}(u) + \mathrm{wt}(u+v) \ge \mathrm{wt}(v) \ge 2^{(m-1)-(r-1)} = 2^{m-r}. $$ Either way the weight is at least $2^{m - r}$ , so $d \geq 2^{m - r}$ . For equality, the monomial $f = x_{1} x_{2} \dots x_{r}$ vanishes unless $x_{1} = \dots = x_{r} = 1$ , leaving the $x_{r + 1}, \dots, x_{m}$ free: exactly $2^{m - r}$ points evaluate to $1$ . So $ev (x_{1} \dots x_{r})$ has weight $2^{m - r}$ , and $d = 2^{m - r}$ . Rubric: full credit for both cases of the weight bound, the inductive distances, and the achieving monomial.

Exercise 8 (hard, symbolic).

Show that a primitive narrow-sense binary BCH code of length $n = 2^{m} - 1$ with designed distance $δ = 2 t + 1$ has dimension $k \geq n - m t$ , and explain why the bound can be loose.

Hint

The generator is the lcm of the minimal polynomials of $α, α^{2}, \dots, α^{2 t}$ . Even powers repeat earlier cosets, so only $α, α^{3}, \dots, α^{2 t - 1}$ contribute new minimal polynomials, each of degree $\leq m$ .

Answer

The defining set must contain ${1, 2, \dots, 2 t}$ . Over $F_{2}$ , each even exponent $2 j$ lies in the same cyclotomic coset as $j$ (since squaring is the Frobenius and $2 j \equiv 2 \cdot j$ ), so the distinct cosets needed are those of the $t$ odd exponents $1, 3, 5, \dots, 2 t - 1$ . Each minimal polynomial $m_{i} (x)$ has degree equal to the coset size, at most $m$ . Hence $de g g = de g lcm (m_{1}, m_{3}, \dots, m_{2 t - 1}) \leq m t$ , giving $k = n - de g g \geq n - m t$ . The bound is loose because (i) some cosets are smaller than $m$ (when the order of $2$ modulo the relevant divisor is less than $m$ ), shrinking $de g g$ ; and (ii) distinct odd exponents can share a coset, so fewer than $t$ minimal polynomials may actually occur. The true dimension is read off the exact cyclotomic-coset partition, and the true minimum distance often exceeds $δ$ . Rubric: full credit for the even-exponent coset collapse, the $t$ odd contributors of degree $\leq m$ , the bound $k \geq n - m t$ , and at least one reason for looseness.

Advanced results Master

The cyclic framework unifies the named families and culminates in a design-theoretic statement. The results below trace the BCH-as-subfield-subcode-of-Reed-Solomon picture, the affine-geometric face of Reed-Muller, majority-logic decoding, and the Assmus-Mattson theorem that turns weight classes into $t$ -designs.

Theorem 1 (BCH is a subfield subcode of Reed-Solomon). Let $RS_{q^{m}}$ be the Reed-Solomon code over $F_{q^{m}}$ with the same length $n ∣ q^{m} - 1$ and the same consecutive defining set ${b, \dots, b + δ - 2}$ . The BCH code over $F_{q}$ with that designed distance is exactly the subfield subcode $$ \mathrm{BCH}q = \mathrm{RS}{q^m} \cap \mathbb{F}_q^n, $$ the codewords of the Reed-Solomon code all of whose coordinates already lie in $F_{q}$ ^{[MacWilliams-Sloane Ch. 9]}. The minimum distance of $BCH_{q}$ is at least that of $RS_{q^{m}}$ , namely $\geq δ$ , recovering the BCH bound; the dimension drops because the subfield constraint is $m$ linear conditions per Reed-Solomon check, encoded by the cyclotomic cosets. This is the conceptual home of the BCH bound: a BCH code inherits its distance from an ambient MDS code and pays for the smaller alphabet in dimension.

Theorem 2 (Reed-Muller as affine geometry and as a punctured-cyclic code). The codewords of $RM (r, m)$ of minimum weight $2^{m - r}$ are exactly the indicator vectors of the $(m - r)$ -dimensional affine subspaces of $F_{2}^{m}$ , the flats of the affine geometry $AG (m, 2)$ ^{[MacWilliams-Sloane Ch. 13]}. Punctured at one coordinate, $RM (r, m)$ minus the all-zero point becomes a cyclic code of length $2^{m} - 1$ whose defining set is described by the $2$ -adic weights of exponents (the Kasami-Lin-Peterson characterisation): $α^{j}$ is a zero iff the binary digit sum of $j$ is less than $m - r$ . So Reed-Muller codes are cyclic up to puncturing, and the affine-geometry codes of points-versus-flats incidence realise them combinatorially.

Theorem 3 (Reed's majority-logic decoding). $RM (r, m)$ decodes by majority logic in $r + 1$ rounds ^{[Reed 1954]}. Each degree- $r$ monomial coefficient is recovered by a set of $2^{m - r}$ disjoint parity-check sums (one per coset of the complementary subspace), each an unbiased estimate of that coefficient; a majority vote over the $2^{m - r}$ sums corrects up to $2^{m - r - 1} - 1$ errors, half the minimum distance. Subtracting the recovered top-degree part reduces to $RM (r - 1, m)$ , and the rounds cascade down to the constant term. The decoder is fully parallel and was used on the Mariner deep-space probes (the $[32, 6, 16]$ code $RM (1, 5)$ ).

Theorem 4 (generalized Reed-Solomon and the evaluation form). Fix distinct $a_{1}, \dots, a_{n} \in F_{q}$ and nonzero multipliers $v_{1}, \dots, v_{n}$ . The generalized Reed-Solomon code is $GRS_{k} = {(v_{1} f (a_{1}), \dots, v_{n} f (a_{n})) : de g f < k}$ , an $[n, k, n - k + 1]_{q}$ MDS code for any $n \leq q$ ^{[Reed-Solomon 1960]}. Its dual is again a GRS code (with multipliers from the Lagrange/derivative weights of the $a_{i}$ ), so the GRS family is closed under duality, and the narrow-sense cyclic Reed-Solomon code is the case $a_{i} = α^{i}$ , $v_{i} = 1$ . The evaluation form makes the erasure-recovery property of 40.06.06 manifest: any $k$ coordinates determine $f$ by Lagrange interpolation.

Theorem 5 (Assmus-Mattson theorem). Let $C$ be an $[n, k, d]_{q}$ code with dual $C^{⊥}$ of minimum distance $d^{⊥}$ . Fix $t < d$ , and let $s$ be the number of nonzero weights of $C^{⊥}$ in the range ${1, 2, \dots, n - t}$ . If $s \leq d - t$ , then for every weight $w$ with $d \leq w \leq n$ , the supports of the weight- $w$ codewords of $C$ form a $t$ -design (a $t$ - $(n, w, λ_{w})$ design for a suitable $λ_{w}$ ), and the same holds for $C^{⊥}$ in the analogous range ^{[Assmus-Mattson 1969]}. Applied to the extended binary Golay code $G_{24}$ , whose dual is itself and whose weights are $0, 8, 12, 16, 24$ : taking $t = 5$ , the dual weights in ${1, \dots, 19}$ are $8, 12, 16$ , so $s = 3 = d - t = 8 - 5$ , and the weight- $8$ codewords (the $759$ octads) form a $5$ - $(24, 8, 1)$ design — the Steiner system $S (5, 8, 24)$ of 40.06.04. The ternary $G_{12}$ yields $S (5, 6, 12)$ the same way.

Synthesis. Putting these together, the algebra of zeros, the geometry of flats, and the combinatorics of designs are three readings of one object pinned by the generator polynomial. The foundational reason Reed-Solomon sits exactly on the MDS boundary is that its zeros form a maximal consecutive run, so the BCH lower bound and the Singleton upper bound of 40.06.06 meet — this is exactly the rank-meets-Vandermonde coincidence of the Key theorem, and every BCH code is the shadow of such an MDS code over a larger field, inheriting distance and paying in dimension. This is dual, in the precise MacWilliams sense of 40.06.06, to the weight-enumerator picture: the Assmus-Mattson hypothesis is a statement about how few nonzero dual weights fall below the redundancy, and the central insight is that this scarcity forces the Pless power moments to be independent of which $t$ -subset one fixes, which is precisely the defining balance of a $t$ -design. The bridge from codes to designs runs both ways — the Golay codes produce the Steiner systems $S (5, 8, 24)$ and $S (5, 6, 12)$ of 40.06.04, and those designs reconstruct the codes — so the perfect-code arithmetic of 40.06.07, the design-graph dictionary of 40.06.09, and the Hadamard codes of 40.06.05 are corners of a single design-code-graph triangle, and Reed-Muller's first-order code $RM (1, m)$ is exactly the Hadamard code that sits on the triangle's coding vertex.

Full proof set Master

Proposition 1 (structure of cyclic codes). The ideals of $R_{n} = F_{q} [x] / (x^{n} - 1)$ are exactly the principal ideals $⟨ g (x)⟩$ with $g$ a monic divisor of $x^{n} - 1$ ; the corresponding code has dimension $n - de g g$ , and $dim C + dim C^{⊥} = n$ with $C^{⊥}$ cyclic.

Proof. $R_{n}$ is a quotient of the principal ideal domain $F_{q} [x]$ , hence every ideal is the image of an ideal $⟨ f ⟩ \supseteq ⟨ x^{n} - 1 ⟩$ of $F_{q} [x]$ , i.e. $⟨ g ⟩$ with $g ∣ x^{n} - 1$ monic of least degree in the ideal. The set ${g, xg, \dots, x^{k - 1} g}$ with $k = n - de g g$ is $F_{q}$ -linearly independent (distinct leading degrees below $n$ ) and spans the ideal modulo $x^{n} - 1$ , so $dim C = k$ . For the dual, with $h = (x^{n} - 1) / g$ the map $c \mapsto c \cdot h mod (x^{n} - 1)$ has kernel $C$ and image of dimension $de g g$ , and a coordinate computation identifies $C^{⊥}$ with $⟨ \tilde{h} ⟩$ , where $\tilde{h} (x) = x^{d e g h} h (1/ x)$ is the reciprocal of $h$ ; thus $C^{⊥}$ is cyclic of dimension $de g g = n - k$ , and $dim C + dim C^{⊥} = n$ as in the rank-nullity statement of 40.06.06. $□$

Proposition 2 (BCH bound via Vandermonde). A cyclic code whose defining set contains $δ - 1$ consecutive exponents has $d \geq δ$ .

Proof. As in the Key theorem, a nonzero codeword $c$ of weight $w$ with support ${j_{1}, \dots, j_{w}}$ satisfies $\sum_{s = 1}^{w} c_{j_{s}} (α^{j_{s}})^{b + ℓ} = 0$ for $ℓ = 0, \dots, δ - 2$ , where $α^{b}, \dots, α^{b + δ - 2}$ are the consecutive zeros. Writing $β_{s} = α^{j_{s}}$ (distinct) and $d_{s} = c_{j_{s}} β_{s}^{b}$ (nonzero), the first $w$ equations form a $w \times w$ Vandermonde system $V d = 0$ with $det V = \prod_{s < t} (β_{t} - β_{s}) \neq = 0$ . If $w \leq δ - 1$ the system has enough equations to force $d = 0$ , contradicting $d_{s} \neq = 0$ ; hence $w \geq δ$ . $□$

Proposition 3 (Reed-Solomon MDS and dual). The Reed-Solomon code $[n, k, n - k + 1]_{q}$ ( $n \leq q$ ) is MDS, and its dual is a generalized Reed-Solomon code, hence also MDS.

Proof. In the evaluation form $C = {(f (a_{1}), \dots, f (a_{n})) : de g f < k}$ a nonzero $f$ of degree $< k$ has at most $k - 1$ roots among the distinct $a_{i}$ , so at least $n - (k - 1) = n - k + 1$ coordinates are nonzero; thus $d \geq n - k + 1$ , and Singleton of 40.06.06 gives $d \leq n - k + 1$ , so $d = n - k + 1$ and $C$ is MDS. For the dual, the bilinear form pairs $C$ with the evaluations of degree- $< n - k$ polynomials against the Lagrange-derivative weights $u_{i} = \prod_{j \neq = i} (a_{i} - a_{j})^{- 1}$ : one checks $\sum_{i} u_{i} f (a_{i}) g (a_{i}) = 0$ whenever $de g f < k$ and $de g g < n - k$ , because $\sum_{i} u_{i} a_{i}^{ℓ} = 0$ for $0 \leq ℓ \leq n - 2$ (a Lagrange-interpolation identity for the coefficient of the top power). Hence $C^{⊥} = {(u_{i} g (a_{i}))_{i} : de g g < n - k}$ , a GRS code with multipliers $u_{i}$ , MDS of distance $k + 1$ . $□$

Proposition 4 (Reed-Muller dimension, distance, and duality). $dim RM (r, m) = \sum_{i = 0}^{r} (i m)$ , $d = 2^{m - r}$ , and $RM (r, m)^{⊥} = RM (m - r - 1, m)$ .

Proof. The evaluation map sends the $\sum_{i \leq r} (i m)$ squarefree monomials of degree $\leq r$ to linearly independent vectors (a Boolean function on $F_{2}^{m}$ has a unique multilinear representative, since $x^{2} = x$ ), giving the dimension. The distance is $2^{m - r}$ by the $(u, u + v)$ induction of Exercise 7. For duality, take $f$ of degree $\leq r$ and $g$ of degree $\leq m - r - 1$ ; the product $f g$ has degree $\leq m - 1$ , so the sum of $f g$ over all of $F_{2}^{m}$ vanishes (a Boolean polynomial of degree $< m$ has even weight, as the top monomial $x_{1} \dots x_{m}$ is the only odd-weight one). Hence $⟨ ev (f), ev (g)⟩ = \sum_{v} f (v) g (v) = 0$ , so $RM (m - r - 1, m) \subseteq RM (r, m)^{⊥}$ . The dimensions match: $\sum_{i \leq m - r - 1} (i m) = 2^{m} - \sum_{i \leq r} (i m)$ by the symmetry $(i m) = (m - i m)$ , equal to $2^{m} - dim RM (r, m)$ . Equality of dimensions forces $RM (r, m)^{⊥} = RM (m - r - 1, m)$ . $□$

Proposition 5 (Assmus-Mattson theorem). With $C$ , $t < d$ , and $s = ∣ {nonzero weights of C^{⊥} in [1, n - t]} ∣ \leq d - t$ , the weight- $w$ supports of $C$ form $t$ -designs for all $d \leq w \leq n$ .

Proof. Fix a $t$ -subset $T$ of coordinates and let $A_{w} (T)$ count weight- $w$ codewords whose support contains $T$ . The Pless power-moment identities express, for each $ν \leq t$ , the symmetric sums $\sum_{w} (w - ν n - ν) A_{w}$ in terms of the dual weight distribution $A_{j}^{⊥}$ for $j \leq ν \leq t$ . The shortened code $C_{T}$ (codewords zero on $T$ ) and the punctured dual relate the local counts $A_{w} (T)$ to the global dual spectrum through the MacWilliams transform of 40.06.06. The hypothesis $s \leq d - t$ means the dual has at most $d - t$ nonzero weights below $n - t + 1$ ; this is exactly the number of free parameters in the linear system whose unknowns are the $A_{w} (T)$ and whose equations are the power moments for $ν = 0, \dots, t$ . The system then has a unique solution independent of $T$ — the count $A_{w} (T)$ depends only on $∣ T ∣ = t$ , not on which $t$ -set $T$ is chosen. A weight- $w$ class in which every $t$ -subset lies in the same number $λ_{w} = A_{w} (T)$ of supports is, by definition, a $t$ - $(n, w, λ_{w})$ design. The dual statement follows by symmetry of the hypothesis. $□$

Connections Master

The co-produced unit 40.06.07 on perfect and Golay codes constructs both Golay codes as cyclic (quadratic-residue) codes — the binary $G_{23}$ from a degree- $11$ factor of $x^{23} - 1$ over $F_{2}$ , the ternary $G_{11}$ from a factor of $x^{11} - 1$ over $F_{3}$ — exactly the generator-polynomial mechanism of this unit. The Assmus-Mattson theorem proved here is what turns the Golay weight enumerators computed there into the $5$ -designs; the two units share the same codes seen from the cyclic-structure and the perfect-packing sides.
The Steiner systems of 40.06.04 are the output of the Assmus-Mattson theorem applied to the Golay codes: the $759$ octads form $S (5, 8, 24)$ and the $132$ hexads form $S (5, 6, 12)$ . The foundational reason a code can carry a $5$ -design is the dual-weight scarcity hypothesis — few nonzero dual weights below the redundancy — and this is exactly the condition that forces the fixed-weight supports into the balanced incidence structure that 40.06.04 studies axiomatically.
The arithmetic of the alphabet is the finite-field theory of 21.02.01: the defining set of a cyclic code is a union of $q$ -cyclotomic cosets because the generator has coefficients in $F_{q}$ while its roots live in $F_{q^{m}}$ , and Reed-Solomon codes evaluate polynomials at the primitive element of $F_{q}$ itself, so the length is bounded by $q - 1$ . This is dual to the additive-character structure used in 40.06.06 for the MacWilliams identity, on which the Assmus-Mattson proof rests.
The first-order Reed-Muller code $RM (1, m)$ is the Hadamard / biorthogonal code of 40.06.05: its $2^{m + 1}$ codewords are the rows of a $2^{m} \times 2^{m}$ Hadamard matrix and their complements, with all nonzero weights $2^{m - 1}$ , so the Paley-Hadamard constructions there and the affine-geometry codes here describe the same equidistant object. Together with the strongly regular graphs of 40.06.09, this closes the design-code-graph triangle that organises the whole chapter.

Historical & philosophical context Master

Cyclic codes crystallized in the late 1950s once Eugene Prange recast codes as ideals in $F_{q} [x] / (x^{n} - 1)$ , making the generator polynomial the central object. The multiple-error-correcting family was found independently by Alexis Hocquenghem in 1959 ^{[MacWilliams-Sloane Ch. 9]} and by Raj Chandra Bose and Dwijendra Kumar Ray-Chaudhuri in 1960 ^{[Bose-Ray-Chaudhuri 1960]}; their initials name the BCH codes, and the BCH bound — a consecutive run of zeros forces a distance — is the construction's engine.

Irving Reed and Gustave Solomon published their polynomial codes in 1960 ^{[Reed-Solomon 1960]}, a four-page paper in the Journal of the SIAM defining codes by evaluating low-degree polynomials over a finite field. The maximum-distance-separable optimality made them the workhorse of digital storage and transmission: compact discs, DVDs, QR codes, RAID arrays, and the Voyager probes all carry Reed-Solomon codes. The earlier Reed-Muller codes came from David Muller's 1954 Boolean-function construction ^{[Muller 1954]} and Irving Reed's companion 1954 majority-logic decoder ^{[Reed 1954]}; the $[32, 6, 16]$ first-order code flew on Mariner 9 to return the first close images of Mars.

The design-theoretic capstone is the Assmus-Mattson theorem of Edward Assmus and Harold Mattson in 1969 ^{[Assmus-Mattson 1969]}, which gave a purely coding-theoretic sufficient condition for the fixed-weight codewords to form $t$ -designs, recovering the Mathieu $5$ -designs from the Golay codes without group theory. The theorem tied error-correcting codes to the design theory of 40.06.04 and to the sporadic simple groups, and remains a primary source of $t$ -designs with large $t$ .

Bibliography Master

@article{hocquenghem1959,
  author  = {Hocquenghem, Alexis},
  title   = {Codes correcteurs d'erreurs},
  journal = {Chiffres},
  volume  = {2},
  year    = {1959},
  pages   = {147--156}
}

@article{boseraychaudhuri1960,
  author  = {Bose, Raj C. and Ray-Chaudhuri, Dwijendra K.},
  title   = {On a class of error correcting binary group codes},
  journal = {Information and Control},
  volume  = {3},
  number  = {1},
  year    = {1960},
  pages   = {68--79}
}

@article{reedsolomon1960,
  author  = {Reed, Irving S. and Solomon, Gustave},
  title   = {Polynomial codes over certain finite fields},
  journal = {Journal of the Society for Industrial and Applied Mathematics},
  volume  = {8},
  number  = {2},
  year    = {1960},
  pages   = {300--304}
}

@article{reed1954,
  author  = {Reed, Irving S.},
  title   = {A class of multiple-error-correcting codes and the decoding scheme},
  journal = {IRE Transactions on Information Theory},
  volume  = {4},
  number  = {4},
  year    = {1954},
  pages   = {38--49}
}

@article{muller1954,
  author  = {Muller, David E.},
  title   = {Application of Boolean algebra to switching circuit design and to error detection},
  journal = {IRE Transactions on Electronic Computers},
  volume  = {3},
  number  = {3},
  year    = {1954},
  pages   = {6--12}
}

@article{assmusmattson1969,
  author  = {Assmus, Edward F. and Mattson, Harold F.},
  title   = {New 5-designs},
  journal = {Journal of Combinatorial Theory},
  volume  = {6},
  number  = {2},
  year    = {1969},
  pages   = {122--151}
}

@book{vanlint1999coding,
  author    = {van Lint, Jacobus H.},
  title     = {Introduction to Coding Theory},
  series    = {Graduate Texts in Mathematics},
  volume    = {86},
  edition   = {3rd},
  publisher = {Springer},
  year      = {1999}
}

@book{macwilliamssloane1977,
  author    = {MacWilliams, F. Jessie and Sloane, Neil J. A.},
  title     = {The Theory of Error-Correcting Codes},
  publisher = {North-Holland},
  year      = {1977}
}

@book{vanlintwilson2001,
  author    = {van Lint, Jacobus H. and Wilson, Richard M.},
  title     = {A Course in Combinatorics},
  edition   = {2nd},
  publisher = {Cambridge University Press},
  year      = {2001}
}

@article{prange1957,
  author  = {Prange, Eugene},
  title   = {Cyclic error-correcting codes in two symbols},
  journal = {Air Force Cambridge Research Center Technical Report AFCRC-TN-57-103},
  year    = {1957}
}

Prerequisites

40.06.07
40.06.04

Tier anchors

beginner: van Lint-Wilson 2001 *A Course in Combinatorics* 2e (Cambridge) Ch. 18-20 (codes with a cyclic shift symmetry, polynomials as codewords, the generator polynomial picture); Hill 1986 *A First Course in Coding Theory* (Oxford) Ch. 12-13 (cyclic codes by hand, BCH and Reed-Solomon as practical error-correctors on CDs and in deep space)
intermediate: van Lint 1999 *Introduction to Coding Theory* 3e (Springer GTM 86) Ch. 6-7 (cyclic codes as ideals in F_q[x]/(x^n-1), generator and check polynomials, defining sets and the BCH bound, BCH and Reed-Solomon codes, Reed-Muller codes); van Lint-Wilson 2001 *A Course in Combinatorics* 2e (Cambridge) Ch. 18-20 (cyclic codes, Reed-Muller, the Assmus-Mattson theorem)
master: van Lint 1999 *Introduction to Coding Theory* 3e (Springer GTM 86) Ch. 6-7, 9 (cyclic codes, BCH bound, Reed-Solomon MDS optimality, Reed-Muller and majority-logic decoding, Assmus-Mattson and the 5-designs); MacWilliams-Sloane 1977 *The Theory of Error-Correcting Codes* (North-Holland) Ch. 7-9, 13-15 (cyclic codes, BCH, Reed-Muller, generalized Reed-Solomon, the Assmus-Mattson theorem); Bose-Ray-Chaudhuri 1960 *Information and Control* 3; Hocquenghem 1959 *Chiffres* 2; Reed-Solomon 1960 *J. SIAM* 8; Reed 1954 *IRE Trans.* 4 and Muller 1954 *IRE Trans.* 3; Assmus-Mattson 1969 *J. Combin. Theory* 6

References

van Lint, J. H. — Introduction to Coding Theory · Springer Graduate Texts in Mathematics 86, 3rd edition (1999). Chapter 6 develops cyclic codes as ideals in the quotient ring F_q[x]/(x^n-1), the generator polynomial g(x) as the monic divisor of x^n-1 of least degree, the check polynomial h(x) = (x^n-1)/g(x), the zeros of g(x) as the defining set of the code, the BCH bound on minimum distance from a run of consecutive zeros, and BCH and Reed-Solomon codes. Chapter 7 treats Reed-Muller codes, their recursive (u, u+v) construction, the duality RM(r,m)^perp = RM(m-r-1, m), and majority-logic decoding. Chapter 9 develops the Assmus-Mattson theorem and the designs held by the fixed-weight codewords of a code, recovering the 5-designs of the Golay codes.
MacWilliams, F. J. & Sloane, N. J. A. — The Theory of Error-Correcting Codes · North-Holland (1977). Chapter 7 treats cyclic codes as ideals, idempotents, and the Mattson-Solomon polynomial; Chapter 8 develops Reed-Muller codes as Boolean polynomials of bounded degree, the (u, u+v) construction, the affine-geometry description, and Reed's majority-logic decoding; Chapter 9 covers BCH codes, the BCH bound, cyclotomic cosets and the true minimum distance; Chapters 10-11 develop Reed-Solomon and generalized Reed-Solomon codes and their MDS optimality; Chapter 13 develops the BCH bound and BCH-as-subfield-subcode-of-RS; Chapter 16 (the Golay-code 5-designs) and the Assmus-Mattson theorem that fixed-weight codewords of a code with few nonzero dual weights below the redundancy form t-designs.
Bose, R. C. & Ray-Chaudhuri, D. K. — On a class of error correcting binary group codes · Information and Control 3 (1960), 68-79. The construction of multiple-error-correcting cyclic codes by prescribing a run of consecutive powers of a primitive element as zeros of the generator polynomial; the BCH bound that such a run of length delta-1 forces minimum distance at least delta.
Reed, I. S. & Solomon, G. — Polynomial codes over certain finite fields · Journal of the Society for Industrial and Applied Mathematics 8 (1960), 300-304. Reed-Solomon codes as the images of low-degree polynomials evaluated at the nonzero (or all) elements of a finite field; the parameters [n, k, n-k+1]_q with n <= q, meeting the Singleton bound, hence MDS.
Reed, I. S. — A class of multiple-error-correcting codes and the decoding scheme · IRE Transactions on Information Theory 4 (1954), 38-49. The Reed-Muller codes RM(r,m) as evaluations of Boolean polynomials of degree at most r in m variables, and the majority-logic (Reed) decoding algorithm that recovers each message coefficient by a vote over disjoint parity sums.
Muller, D. E. — Application of Boolean algebra to switching circuit design and to error detection · IRE Transactions on Electronic Computers 3 (1954), 6-12. The original definition of the codes by truncating Boolean functions to degree r, and the connection to switching-circuit complexity.
Assmus, E. F. & Mattson, H. F. — New 5-designs · Journal of Combinatorial Theory 6 (1969), 122-151. The Assmus-Mattson theorem: if an [n,k,d] code C and its dual C^perp have at most d-t nonzero weights in the range [1, n-t] (a condition on the number of nonzero weights below the redundancy), then for each weight w the supports of the weight-w codewords form a t-design; applied to the Golay codes it recovers the 5-(24,8,1) and 5-(12,6,1) Steiner systems.

Estimated time

beginner: 18m
intermediate: 48m
master: 90m