Chapter 41: Coding Theory and Combinatorial Designs

How many corrupted symbols can a geometric code correct?

A code separates messages inside a discrete geometric space so that small perturbations cannot confuse them. The relevant geometry is Hamming distance, not Euclidean distance: for words $x,y$ of length $n$ over an alphabet of size $q$, define $d_H(x,y)=|\{i:x_i\ne y_i\}|$. A code $C$ is a subset of that space, with size $M=|C|$ and minimum distance $d=\min_{x\ne y\in C}d_H(x,y)$ when there are at least two codewords.

If $2t\lt d$, every received word within distance $t$ of a transmitted codeword has that codeword as its unique nearby candidate. Indeed, two such candidates would be within $2t$ of each other by the triangle inequality. Thus a minimum-distance-$d$ code guarantees correction of $\lfloor(d-1)/2\rfloor$ arbitrary symbol errors. Erasures are different: their positions are known, and up to $d-1$ can be uniquely recovered. With $e$ errors and $s$ erasures, the sufficient condition is $2e+s\lt d$.

The chapter's foundation is a binary code specified by the parity-check matrix

$$ H=\begin{pmatrix} 1&0&1&0&1&0&1\\ 0&1&1&0&0&1&1\\ 0&0&0&1&1&1&1 \end{pmatrix},\qquad C=\{c\in\mathbb F_2^7:Hc^T=0\}. $$

All arithmetic is modulo two. Column $j$ is the nonzero binary vector representing the integer $j$, with its least significant bit in the top row. Columns $1,2,4$ are independent, so $H$ has rank three and $C$ has dimension four and size sixteen. This is a linear $[7,4,3]_2$ Hamming code; the bracket notation records length, dimension, minimum distance, and field size.

To prove the distance, a weight-one codeword would require a zero column, and a weight-two word would require equal columns. Neither exists. Columns $1,2,3$ sum to zero, so $1110000$ is a weight-three codeword. For a linear code, minimum distance equals the smallest nonzero weight, hence $d=3$.

For received word $r=c+e_j$, the syndrome is $Hr^T=He_j^T=h_j$. It identifies the corrupted position uniquely. A zero syndrome means the received word is a codeword, but without an error-budget assumption it does not prove that no corruption occurred. Under at most one error, it means no error; under more errors, a syndrome decoder can miscorrect.

The Hamming ball of radius $t$ has $V_q(n,t)=\sum_{i=0}^t\binom ni(q-1)^i$ words. Disjoint correction balls give $MV_q(n,t)\le q^n$. Here $t=1$, each ball has eight words, and $16\cdot8=128=2^7$. The code corrects one error and its balls partition the entire space. These definitions, the rank/distance proof, and syndrome rule supply the final investigation independently of all optional numbered extensions. The linear algebra and abstract algebra background is used explicitly through finite-field equations.

41.1 Hamming distance and error-correcting codes

Optional extension; not required to complete the chapter foundation.

The weight $\operatorname{wt}(x)$ is the number of nonzero coordinates. Over a field, $d_H(x,y)=\operatorname{wt}(x-y)$, but distance itself needs only an alphabet. A possibly nonlinear code is described by parameters $(n,M,d)_q$. For a linear code with $M=q^k$, write $[n,k,d]_q$. Rate is $R=\log_q(M)/n$, and relative distance is $\delta=d/n$.

The basic separation proof gives unique decoding within radius $t$ whenever $2t\lt d$. It also proves detection of up to $d-1$ errors: such a nonzero error cannot turn one codeword into a different codeword. Detection does not necessarily locate the error. A received word farther away can be consistent with several different transmission scenarios.

Solved example. The binary repetition code $\{000,111\}$ has $(n,M,d)=(3,2,3)$, rate $1/3$, and corrects one error by majority vote. The word $010$ is one step from $000$ and two from $111$. The word $110$ is instead one step from $111$; if it arose from two errors in transmitted $000$, majority decoding would return the wrong message. Two-error detection is still possible by checking whether the received word is a codeword, while two-error correction is not guaranteed.

For erasures, suppose two codewords agree on all unerased positions. Their distance is at most the number of erasures. If that number is below $d$, they must coincide. With both unknown errors and known erasures, two candidates consistent with the error bound differ on at most $2e+s$ positions, giving the mixed condition stated in the foundation.

Exercise. What guarantees does a code of minimum distance five provide? Hint: distinguish errors from erasures. Solution: it corrects two arbitrary errors, detects up to four errors, and corrects four erasures. It also uniquely corrects one error together with two erasures because $2\cdot1+2=4\lt5$. These are worst-case guarantees for the stated channel model.

41.2 Linear codes over finite fields

Optional extension; not required to complete the chapter foundation.

A linear code is a vector subspace of $\mathbb F_q^n$, where $q$ is a prime power. A generator matrix $G$ has independent rows spanning the code; messages are row vectors encoded as $uG$. A parity-check matrix $H$ has independent rows spanning the orthogonal constraints, so $GH^T=0$ and $C=\ker H$. Rank–nullity gives $\dim C=n-\operatorname{rank}H$. For a prime-power field, arithmetic is field arithmetic, not integer arithmetic modulo a composite $q$.

Linearity reduces distance computation to nonzero codewords: subtracting any pair remains in $C$, and every nonzero codeword is a difference from zero. Thus checking $q^k-1$ weights suffices instead of all pairs, although this can still be exponential in $k$.

The dual code is $C^{\perp}=\{v:v\cdot c=0\text{ for all }c\in C\}$ and has dimension $n-k$. Here it is the row span of $H$, a $[7,3,4]_2$ simplex code: every nonzero row combination has four ones because a nonzero linear functional on $\mathbb F_2^3$ equals one on four of its eight inputs, with zero input contributing zero.

Exercise. Prove that two distinct codewords in $C$ are at distance at least three using parity-check columns alone. Hint: apply $H$ to their difference. Solution: a difference of weight one would make one column zero; a difference of weight two would make two columns equal in characteristic two. Both are impossible. The difference is nonzero, so its weight is at least three.

41.3 Hamming and Singleton bounds

Optional extension; not required to complete the chapter foundation.

For any $q$-ary code with $M$ words and minimum distance $d$, let $t=\lfloor(d-1)/2\rfloor$. Its radius-$t$ Hamming balls are disjoint, proving

$$ M\sum_{i=0}^t\binom ni(q-1)^i\le q^n. $$

The count chooses $i$ corrupted coordinates and one of $q-1$ replacements at each. This is a packing bound; it does not construct a code achieving equality.

The Singleton bound instead deletes any $d-1$ coordinates. The remaining words must be distinct, since equality after deletion would imply original distance at most $d-1$. Thus

$$ M\le q^{n-d+1},\qquad k\le n-d+1\text{ for a linear code}. $$

A code attaining Singleton is maximum-distance separable, or MDS. Its property concerns this bound, rather than perfect Hamming-ball packing.

Solved example and diagram. For the repetition code of length three, the radius-one balls about $000$ and $111$ contain four words each and partition all eight binary words. Deleting coordinates two and three leaves the two distinct symbols zero and one, attaining Singleton as well. The diagram lists every ball member and every retained projection explicitly. Center-to-member connectors record Hamming distance one; they are not Euclidean-radius claims.

For the $[7,4,3]_2$ Hamming code, packing gives $16(1+7)=128$, equality. Singleton gives $16\le2^5=32$, strict inequality. It is perfect but not MDS. Conversely, many MDS codes leave space outside their disjoint correction balls. Equality in one bound must not be transferred to another.

Exercise. Can a binary length-seven code with sixteen words have minimum distance five? Hint: use radius two. Solution: its balls would have volume $1+7+21=29$, requiring $16\cdot29\le128$, which is false. Thus the proposed parameters are impossible. The Hamming bound alone already rules them out.

41.4 Gilbert–Varshamov bounds

Optional extension; not required to complete the chapter foundation.

A packing upper bound limits all codes; a Gilbert–Varshamov bound guarantees existence. Greedily choose words while maintaining distance at least $d$, stopping when no additional word can be chosen. Maximality means every ambient word lies within distance $d-1$ of a selected word. These covering balls can overlap, so

$$ q^n\le M V_q(n,d-1),\qquad M\ge\frac{q^n}{\sum_{i=0}^{d-1}\binom ni(q-1)^i}. $$

The algorithm may require enormous enumeration. The existence statement does not supply an efficient encoding or decoding procedure, and its covering radius $d-1$ differs from the correction radius $\lfloor(d-1)/2\rfloor$.

A useful linear sufficient condition is

$$ q^{n-k}\gt\sum_{i=0}^{d-2}\binom{n-1}{i}(q-1)^i. $$

For $2\le d\le n$ and $1\le k\le n$, this guarantees a linear code of dimension at least $k$ and distance at least $d$. Build $n$ columns in $\mathbb F_q^{n-k}$, each avoiding linear combinations of at most $d-2$ previous columns. Such combinations number at most the right-hand side, including zero, so a new column exists. Any dependence among at most $d-1$ columns would express its latest column as a forbidden combination. The resulting kernel has the desired distance and dimension. If its dimension exceeds $k$, choose a $k$-dimensional subcode, preserving the distance lower bound.

Solved example. For binary $n=7,d=3$, the general greedy bound is $M\ge128/29$, so it guarantees at least five codewords. The linear sufficient condition with $k=4$ reads $8\gt1+6=7$. It guarantees at least dimension four, and the distinct nonzero-column construction realizes the Hamming code. The two existence statements are not equally strong at every finite instance.

For fixed relative distance below $1-1/q$, the ball-volume exponent is governed by the $q$-ary entropy $H_q(\delta)=\delta\log_q(q-1)-\delta\log_q\delta-(1-\delta)\log_q(1-\delta)$. Standard binomial estimates give achievable asymptotic rate at least $1-H_q(\delta)$, with rounding and vanishing terms understood. This is an existence lower bound, not an equality characterizing the optimal rate–distance tradeoff.

Exercise. Apply the general bound to binary length four and desired distance three. Hint: the covering volume is eleven. Solution: $M\ge16/11$, so an integer code of size at least two exists. The repetition code $\{0000,1111\}$ witnesses this, with actual distance four, which is at least three.

41.5 Perfect codes and Hamming codes

Optional extension; not required to complete the chapter foundation.

A code is perfect for radius $t$ when its radius-$t$ balls partition the whole ambient space. This implies correction of $t$ errors and equality in the packing bound, provided its minimum distance is at least $2t+1$. Perfection is a global partition property, rather than a statement that decoding succeeds under unlimited noise.

For a prime power $q$ and integer $r\ge2$, take one nonzero representative from each one-dimensional subspace of $\mathbb F_q^r$ as a parity-check column. There are $n=(q^r-1)/(q-1)$ columns. They span the field space, so the code has dimension $n-r$. No two are proportional, eliminating weights one and two. Three columns in a two-dimensional plane give a nontrivial dependence, showing distance three.

Every nonzero syndrome has a unique representation $a h_j$ with $a\in\mathbb F_q\setminus\{0\}$. Thus it identifies both the position and magnitude of one error. The radius-one volume is $1+n(q-1)=q^r$, and $q^{n-r}q^r=q^n$, proving perfection.

Solved example. In the binary $r=3$ case, every nonzero vector is its own one-dimensional representative, producing the seven foundation columns. An error at position six has syndrome $(0,1,1)^T$, which represents integer six in the chosen row convention. A codeword plus that error is decoded by flipping six. In a nonbinary Hamming code, correcting the coordinate additionally requires the syndrome's nonzero scalar multiple, not just a projective position.

The seven weight-three supports are

$$ 123,\ 145,\ 167,\ 246,\ 257,\ 347,\ 356. $$

They form the Fano-plane $2$-$(7,3,1)$ design. For any pair of distinct nonzero columns $h_i,h_j$, their sum is a third nonzero column, uniquely determining a triple with zero sum. Thus each pair of positions occurs in exactly one listed support. The same parity geometry proves distance and creates a design.

Exercise. Which Fano block contains positions two and five? Hint: add their binary column labels. Solution: $2\mathbin{\oplus}5=7$, so the block is $257$. Each pair belongs to one block, not to every codeword support containing either member.

41.6 BCH and Reed–Solomon codes

Optional extension; not required to complete the chapter foundation.

Polynomial evaluation gives an explicit MDS family. Choose $n\le q$ distinct elements $a_1,\ldots,a_n$ of $\mathbb F_q$ and evaluate all polynomials of degree less than $k$, where $1\le k\le n$. This Reed–Solomon code has dimension $k$: a polynomial of degree below $k$ with $n$ zeros must vanish. Two distinct message polynomials agree at at most $k-1$ evaluation points, giving distance at least $n-k+1$. A polynomial with exactly $k-1$ chosen evaluation roots attains that weight, so the parameters are $[n,k,n-k+1]_q$.

Solved Reed–Solomon example. Over $\mathbb F_5$, evaluate degree-at-most-two polynomials at $0,1,2,3,4$. The code is $[5,3,3]_5$. For $f(z)=1+2z+z^2$, the word is $(1,4,4,1,0)$. Corrupt the entry at evaluation point two to obtain $(1,4,0,1,0)$. Interpolating the uncorrupted points zero, one, and three recovers coefficients $(1,2,1)$. A decoder not knowing the error location can try all ten three-point subsets and retain a candidate within distance one of the received word. The distance theorem makes that candidate unique. This small enumeration is illustrative, not the efficient algebraic decoder used for large codes. The original source is Reed and Solomon, Polynomial Codes Over Certain Finite Fields (1960).

BCH codes instead prescribe consecutive roots of cyclic codewords. Let $n$ divide $q^m-1$, take $\alpha\in\mathbb F_{q^m}$ of order $n$, and choose a monic generator divisor $g(z)$ of $z^n-1$ over $\mathbb F_q$ vanishing at $\alpha,\alpha^2,\ldots,\alpha^{\Delta-1}$. Codewords are its multiples modulo $z^n-1$. The designed distance is $\Delta$; the actual distance is at least $\Delta$ and may be greater.

The BCH bound has a Vandermonde proof. If a nonzero codeword had $s\lt\Delta$ nonzero coefficients at distinct positions $e_j$, its evaluations at the first $s$ prescribed roots would give $\sum_jc_j(\alpha^{e_j})^{\ell}=0$ for $\ell=1,\ldots,s$. The coefficient matrix has determinant equal to the product of its distinct nonzero evaluation values times their Vandermonde differences, so it is invertible. All $c_j$ would vanish, a contradiction.

Solved BCH example. In $\mathbb F_8=\mathbb F_2[\alpha]$ with $\alpha^3+\alpha+1=0$, the element $\alpha$ has order seven. For designed distance three, $g(z)=z^3+z+1$ vanishes at $\alpha$ and its conjugate $\alpha^2$. It divides $z^7-1$, giving dimension four. The generator itself has weight three, so the actual distance is three. This cyclic code is a Hamming code, with a coordinate ordering that need not match the foundation matrix's binary-integer ordering.

Exercise. Why can the Reed–Solomon example recover any two erased symbols? Hint: three evaluations remain. Solution: three distinct evaluation points uniquely determine a degree-at-most-two polynomial. This is also the $d-1=2$ erasure guarantee. Knowing erasure positions is what allows selecting the three intact values directly.

41.7 MacWilliams identities

Optional extension; not required to complete the chapter foundation.

For a linear $q$-ary code, its homogeneous weight enumerator is $W_C(X,Y)=\sum_{c\in C}X^{n-\operatorname{wt}(c)}Y^{\operatorname{wt}(c)}$. The MacWilliams identity relates the dual enumerator:

$$ W_{C^{\perp}}(X,Y)=\frac1{|C|}W_C(X+(q-1)Y,X-Y). $$

The hypotheses include linearity and the field dual under the dot product. A general nonlinear code does not have a vector-space dual with this formula.

The proof uses a nontrivial additive character $\psi$ of $\mathbb F_q$. Orthogonality gives $1_{C^{\perp}}(v)=|C|^{-1}\sum_{c\in C}\psi(c\cdot v)$. Sum this expression against the coordinate weight monomial. A zero coordinate of $c$ contributes $X+(q-1)Y$; a nonzero coordinate contributes $X-Y$ because the nontrivial character sums to zero over the field. Factoring the coordinate sums proves the identity. Existence of additive characters is a standard finite-field background fact; the binary case uses $\psi(t)=(-1)^t$ directly.

Solved example. The binary repetition code of length three has $W_C=X^3+Y^3$. Its dual is the even-weight code, with words $000,011,101,110$. The identity gives

$$ W_{C^{\perp}}=\tfrac12\bigl((X+Y)^3+(X-Y)^3\bigr)=X^3+3XY^2. $$

The odd-degree terms cancel, matching the explicit enumeration.

For the foundation Hamming code,

$$ W_C=X^7+7X^4Y^3+7X^3Y^4+Y^7, \qquad W_{C^{\perp}}=X^7+7X^3Y^4. $$

Substituting $X+Y,X-Y$ and dividing by sixteen verifies the second polynomial. Evaluating at $(1,1)$ gives sixteen and eight, consistent with dimensions four and three. Duality turns a detailed weight distribution into another one without separately listing every dual word.

Exercise. Find the weight enumerator of the dual of the full space $\mathbb F_2^3$. Hint: the full space enumerator is $(X+Y)^3$. Solution: substitution gives $((X+Y)+(X-Y))^3/8=X^3$, the enumerator of the zero code. The dual has one word, not another eight-word space.

41.8 Association schemes and Delsarte's linear-programming bound

Optional extension; not required to complete the chapter foundation.

The Hamming association scheme groups pairs of words by their Hamming distance. Its distance matrices have entries one when a pair is at distance $i$ and zero otherwise. These matrices share eigenspaces, allowing spectral positivity to constrain code distance distributions even for nonlinear codes. For a code of size $M$, define

$$ a_i=\frac1M|\{(x,y)\in C^2:d_H(x,y)=i\}|. $$

Then $a_0=1$, $a_i\ge0$, $\sum_i a_i=M$, and $a_i=0$ for $1\le i\lt d$. The $q$-ary Krawtchouk polynomials are

$$ K_j(i)=\sum_{\ell=0}^j(-1)^\ell(q-1)^{j-\ell}\binom i\ell\binom{n-i}{j-\ell}. $$

The spectral constraints are $\sum_i a_iK_j(i)\ge0$ for every $j$. In the binary scheme they follow from sums of squared character correlations of the code indicator, grouped by character weight. The general association-scheme development is due to Delsarte (1973). The full spectral decomposition is omitted; the following bound uses one explicit constraint.

Maximize $\sum_i a_i$ over these linear constraints. Every actual code supplies a feasible distribution, so the optimum is an upper bound, even if a feasible LP distribution is not realized by any code. This is an upper-bound certificate rather than a construction.

Solved example. For binary length three and distance at least three, only $a_0=1$ and $a_3$ may be nonzero. Since $K_1(i)=3-2i$, the constraint is $3-3a_3\ge0$. Hence $a_3\le1$ and $M=1+a_3\le2$. The repetition code attains the bound. The remaining constraints also hold: $K_2(0)=K_2(3)=3$ and $K_3(0)=1,K_3(3)=-1$.

For a linear code, each difference occurs equally often among ordered pairs, so $a_i$ is its weight count. The Hamming distribution $(1,0,0,7,7,0,0,1)$ therefore supplies another exact check; its Krawtchouk transform equals sixteen times the dual weight counts from MacWilliams.

Exercise. Why does the distribution definition divide by $M$ rather than $M^2$? Hint: check its total. Solution: there are $M^2$ ordered pairs, so division by $M$ makes the sum $M$, the code size to be bounded. Division by $M^2$ would instead produce a probability distribution summing to one and would require a differently normalized LP.

41.9 Locally testable and locally decodable codes

Optional extension; not required to complete the chapter foundation.

Local testing asks whether a received word is a codeword or far from every codeword by querying only a few positions. A tester has completeness on valid words and a stated rejection probability in terms of relative distance. Local decoding asks for one original message symbol, with a bounded number of queries, even when an adversary corrupts a specified fraction of the codeword. These are different tasks from recovering the entire message, and code length and rate remain part of the parameters.

A classical established example is the binary Hadamard code. For $m\ge1$ and message $u\in\mathbb F_2^m$, its length-$N=2^m$ word is the truth table $f_u(x)=u\cdot x$ for all $x\in\mathbb F_2^m$. Every nonzero linear functional has weight $N/2$, so the parameters are $[2^m,m,2^{m-1}]_2$. Its rate $m/2^m$ tends to zero; constant query counts here do not imply a constant-rate construction. The testing and self-correction ideas are established in Blum, Luby, and Rubinfeld, Self-testing/correcting with applications to numerical problems (1993)90044-W).

Solved local decoder. To recover message coordinate $u_i$, choose uniform $x$ and query the received table at $x$ and $x+e_i$. For the true table, their sum is $u_i$. If at most a fraction $\tau$ of positions are corrupted, each queried position is uniform, so the probability either is corrupted is at most $2\tau$. The answer is correct with probability at least $1-2\tau$. For $\tau\lt1/4$ this exceeds one half and can be amplified by independent repetitions and majority vote. The two queried positions need not be independent; the union bound does not require that.

The three-query linearity test chooses independent uniform $x,y$ and checks $f(x)+f(y)=f(x+y)$. Every codeword passes. Its soundness has a concise Fourier proof. Put $g(x)=(-1)^{f(x)}$ and $\widehat g(a)=\mathbb E_xg(x)(-1)^{a\cdot x}$. Parseval gives $\sum_a\widehat g(a)^2=1$, and the rejection probability is $(1-\sum_a\widehat g(a)^3)/2$. Since this cube sum is at most $\max_a\widehat g(a)$, rejection is at least

$$ \frac{1-\max_a\widehat g(a)}2=\min_a\Pr(f(x)\ne a\cdot x). $$

Thus distance $\rho$ from the Hadamard code implies rejection probability at least $\rho$. This proves the stated testing guarantee; it is not presented as an optimal soundness or query–rate tradeoff.

Solved finite instance. For $m=3$ and $u=(1,0,0)$, in lexicographic input order $000,001,010,011,100,101,110,111$, the table is $00001111$. Flip its entry at input $000$. To recover $u_1$, exactly two choices of $x$ make one of the two queries hit that corrupted position, so success is $6/8=3/4$. The relative corruption is $1/8$, and $1-2\tau=3/4$ is exact here.

Exercise. Why does the local decoder's proof not imply reliable majority recovery when $\tau=1/3$? Hint: its lower bound on success drops below one half. Solution: the bound is $1-2/3=1/3$. Repetition amplifies a known positive advantage above one half, not this weaker guarantee. A different decoding argument or corruption regime would be needed.

41.10 Combinatorial constructions for coding and pseudorandomness

Optional extension; not required to complete the chapter foundation.

Designs, linear codes, and pseudorandom distributions can reuse the same incidence data while providing distinct guarantees. The seven weight-three supports of the Hamming code form the Fano design. Their complements are the seven weight-four supports of the simplex dual and form a $2$-$(7,4,2)$ design: each point appears in three original blocks, so each pair is excluded from $7-3-3+1=2$ blocks and therefore belongs to two complements.

Solved bounded-independence construction. Choose a uniform seed $U\in\mathbb F_2^3$ and output seven bits $Y_j=U\cdot h_j$, using the foundation columns. Each column is nonzero, so each bit is fair. Distinct columns are linearly independent over $\mathbb F_2$, so each pair of outputs is jointly uniform. Yet $Y_1+Y_2+Y_3=0$ always because those columns sum to zero. The distribution is pairwise independent but not three-wise independent and not fully uniform. Its eight possible outputs are the simplex codewords.

Uniform sampling from the sixteen Hamming codewords instead gives three-wise independence. If any nonzero parity supported on at most three coordinates were fixed across the code, its indicator vector would belong to $C^{\perp}$. But the dual has minimum weight four. Character orthogonality therefore makes every projection onto at most three coordinates uniform. Four-wise independence fails, for example on positions $1,3,5,7$, whose parity is one of the defining checks. Limited independence and control of every parity are different conditions.

A distribution on $\mathbb F_2^r$ is $\varepsilon$-biased if $|\mathbb E(-1)^{a\cdot X}|\le\varepsilon$ for every nonzero $a$. To connect this to coding, take generator columns $v_1,\ldots,v_N\in\mathbb F_2^r$ and sample one uniformly. For each nonzero message $a$, its encoded word has weight $w(a)$, and the parity bias is $1-2w(a)/N$. Thus codewords with weights close to $N/2$ yield small-bias column distributions. General explicit constructions are established by Naor and Naor, Small-Bias Probability Spaces; their construction proof is omitted here.

Solved small-bias example. Sample one of the seven nonzero columns of $H$ uniformly, obtaining a three-bit output. Every nonzero linear functional is one on four columns and zero on three, so its bias is $-1/7$. This is a $1/7$-biased space. It differs from the earlier seven-bit output obtained by choosing a uniform three-bit seed: the same matrix is being used in two different directions. Small-bias control of parities also does not assert cryptographic security against arbitrary efficient tests.

Exercise. Why is the seven-bit pairwise-independent output not $\varepsilon$-biased for any $\varepsilon\lt1$? Hint: test the parity on positions $1,2,3$. Solution: that parity is always zero, so its sign expectation is one. Pairwise independence tests only one- and two-coordinate marginals, leaving this three-coordinate parity uncontrolled.

Construct a code and compare its parameters with packing bounds

The investigation constructs the Hamming code, proves its distance and decoder guarantee, and then reads design and pseudorandom structure from the same columns. Enumeration supplies finite checks of all codewords and received words; the rank, distance, and syndrome arguments provide the conceptual proof.

Worked solution: encoding and distance. Columns $1,2,4$ form a basis, so the rank is three. Four free data coordinates give sixteen codewords. For message $(1,0,1,1)$ the parity bits are $(c_1,c_2,c_4)=(0,1,0)$ and the complete word is $0110011$. A flip at position five produces $0110111$ with syndrome $(1,0,1)^T=h_5$.

No column is zero and no two columns coincide, so every nonzero kernel word has weight at least three. The word supported on $123$ is in the kernel, proving the minimum is exactly three. One error has a unique nonzero syndrome; two flips at one and two instead have syndrome $h_3$, causing the one-error decoder to flip three and return a different valid word. The assumption of at most one error cannot be omitted.

Worked solution: bounds. For the Hamming code, $M=16$ and $V_2(7,1)=8$, giving $16\cdot8=128$. Disjointness plus equality proves the balls cover every received word. Singleton permits up to $2^{7-3+1}=32$ words, so this code does not attain it.

For Reed–Solomon, $M=5^3=125$ and $V_5(5,1)=1+5\cdot4=21$. The ball total is $2625$, strictly below $5^5=3125$, so it is not perfect. Singleton gives $M\le5^{5-3+1}=125$, equality, proving it is MDS. A symbol here is an element of $\mathbb F_5$, not a binary bit.

Worked solution: exhaustive checks. Enumerating all four-bit messages gives the sixteen kernel words with weight counts $A_0=1,A_3=7,A_4=7,A_7=1$ and all other counts zero. For each codeword, its own word and the seven single-bit flips form a ball of size eight. Testing all received words gives exactly one membership per word. The 128 zero-or-one-error transmission scenarios therefore partition the 128 possible received words, and syndrome decoding recovers every transmitted codeword under that promise.

The homogeneous enumerator is $X^7+7X^4Y^3+7X^3Y^4+Y^7$. Substituting $X+Y,X-Y$ and dividing by sixteen gives $X^7+7X^3Y^4$, matching the independently enumerated row span of $H$. This supplies both a count and an algebraic consistency check.

Worked solution: design and randomness. The weight-three supports are $123,145,167,246,257,347,356$. Their seven blocks have twenty-one pair occurrences, matching $\binom72=21$. More strongly, each pair $i,j$ determines exactly one third column $h_i+h_j$, proving every pair occurs once rather than merely matching the aggregate count.

For the simplex seed sampler, each pair of coordinate values occurs exactly twice among its eight seed outputs, so every pair has probability $1/4$. The parity on $123$ is always zero. For the column sampler, each nonzero parity is zero three times and one four times among seven outputs, giving absolute bias $1/7$. These distributions share a matrix but have different output lengths and guarantees.

Application and extension. Error-correcting codes can protect stored blocks or transmitted symbols when the number of corruptions stays inside the designed correction radius. A perfect one-error code uses all available received-space volume efficiently, but does not make rare multi-error events impossible; an application needs a channel model and a policy for errors beyond the promise. Designs organize parity relations, while bounded-independence or small-bias constructions can reduce randomness for tests that need those specific guarantees. Reliability, statistical pseudorandomness, and cryptographic unpredictability remain distinct properties.

For $r=4$, the binary Hamming parity checks use all fifteen nonzero vectors of $\mathbb F_2^4$. Rank four gives dimension eleven, distinct nonzero columns give minimum distance at least three, and a zero-sum triple gives equality. Each radius-one ball has sixteen words, and $2^{11}\cdot16=2^{15}$. This predicts perfection from the same algebraic proof without enumerating the much larger collection first.