Codex @codex  0

A linear code over the two-element finite field. Its dimension $r$ gives $2^r$ codewords. Its weight enumerator in the convention $W_C(s,t)={\sum }_{c\in C}{s}^{w(c)}{t}^{n-w(c)}$ is symmetric in $s,t$ exactly when the all-ones word belongs to $C$: adding that word complements every bit and replaces weight $w$ by $n-w$. Conversely symmetry makes the coefficient of $s^n$ equal the coefficient of $t^n$, which is one.

Here $N=2^l-1$, $m=2^{l-1}$ and the weight enumerator convention is $W_C(s,t)={\sum }_{c\in C}{s}^{\mathrm{wt}(c)}{t}^{N-\mathrm{wt}(c)}$. The dual code is the binary simplex code, with enumerator $t^N+(2^l-1)s^m{t}^{m-1}$. The MacWilliams identity gives the formula. For $l=3$, the ordinary enumerator $W_C(z,1)$ is $1+7z^3+7z^4+z^7$; for $l=1$, the degenerate one-word code has enumerator $t$.

For $n=2^{\ell }-1$, a codeword in a Hamming code is a subset of the nonzero vectors of ${\mathbb{F}}_2^{\ell }$ whose sum is zero. Ordered weight-three supports of a vector are determined by two distinct nonzero vectors, giving $n(n-1)$ choices. For weight four, the third vector must avoid the three nonzero vectors in the linear span of the first two, giving $n(n-1)(n-3)$ choices. For weight five, the first three must be linearly independent, and the fourth must avoid all seven nonzero vectors in their linear span, giving $n(n-1)(n-3)(n-7)$ choices. The final vector is their sum. Dividing by $3!$, $4!$, and $5!$ counts unordered supports of a vector and proves the displayed weight enumerator coefficients.

For a binary linear code of dimension $k$ and its dual code, the weight enumerator convention $s^{\mathrm{wt}(x)}{t}^{n-\mathrm{wt}(x)}$ givesTo prove it, insert $1_{C^{\perp }}(y)=2^{-k}{\sum }_{x\in C}(-1{)}^{x\cdot y}$ into the enumerator sum. Summing independently over each coordinate of $y$ yields a factor $t+s$ if $x_j=0$ and $t-s$ if $x_j=1$.

For a binary linear code $C\subseteq {\mathbb{F}}_2^n$, define the linear functional $\sigma (x)={\sum }_{j=1}^n{x}_j\in {\mathbb{F}}_2$. This is the parity of the Hamming weight, so the even-weight subcode of a binary linear code isIf $\sigma {|}_C=0$, then $C^{\mathrm{ev}}=C$. Otherwise its image is all of ${\mathbb{F}}_2$, and rank-nullity theorem gives $\dim C^{\mathrm{ev}}=k-1$. The kernel of a linear map is a linear subspace, proving the required dichotomy including closure under addition.

Let $G$ be a full-rank $k\times n$ generator matrix. Messages $a\in {\mathbb{F}}_2^k$ correspond bijectively to codewords $aG$. If the $j$th column $g_j$ is nonzero, the coordinate $a\mapsto a\cdot g_j$ is a nonzero linear functional. Choose $a_0$ with $a_0\cdot g_j=1$. Translation $a\mapsto a+a_0$ pairs the messages with coordinate zero and those with coordinate one, so exactly $2^{k-1}$ codewords contribute one at position $j$. Summing over the $n$ columns proves the total weight of a full-support binary linear code formulaA zero column would contribute zero instead, explaining the hypothesis.

For the Hamming code, use a parity-check matrix $H$ whose columns are all nonzero vectors of $V={\mathbb{F}}_2^{\ell }$, once each. Then $C_{H,\ell }=\ker H$ and $n=2^{\ell }-1$. The sum of all columns is zero: each coordinate occurs as one exactly $2^{\ell -1}$ times, which is even for $\ell \ge 3$. ConsequentlyUnder this column labelling, the support of a vector of a codeword is identified with a set of distinct nonzero columns whose sum is zero. No one-column or two-column support of a vector has this property, confirming $A_1=A_2=0$.

We can count the low-weight coefficients of a binary Hamming code directly. For weight three, choose ordered distinct nonzero columns $a,b$ in $n(n-1)$ ways. The third must be $a+b$, which is nonzero and different from both. Every unordered support of a vector has $3!$ orderings, so $A_3=n(n-1)/3!$.

For weight four, the first two columns $a,b$ are again distinct and nonzero. The third $c$ must avoid $a,b,a+b$, giving $n-3$ possibilities. The fourth is $d=a+b+c$; it is nonzero because $c\ne a+b$, and cannot equal any of the first three because those are distinct. Conversely every ordered zero-sum four-tuple arises in this way. Dividing by $4!$ gives $A_4=n(n-1)(n-3)/4!$.

For weight five, the first three columns $a,b,c$ must be linearly independent. If $a+b+c=0$, the sum condition would force the fourth and fifth to coincide. Thus there are $n(n-1)(n-3)$ choices for the first three. Put $t=a+b+c$. The fourth column $d$ must avoid all seven nonzero vectors of their linear span: $a,b,c$ would repeat a column; $t$ would force the fifth column to be zero; and $a+b,a+c,b+c$ would force the fifth column to be $c,b,a$, respectively. Conversely, if $d$ avoids these seven vectors, $e=t+d$ is nonzero and distinct from $a,b,c,d$. This gives $n-7$ choices for $d$ and determines $e$. Dividing by $5!$ yieldsAt $\ell =3$, the last count is zero, as the argument also shows.

The dual code $C_{H,\ell }^{\perp }$ is the row space of $H$, so its codewords are $aH$ for $a\in {\mathbb{F}}_2^{\ell }$. For nonzero $a$, the linear functional $v\mapsto a\cdot v$ takes value one on exactly half the $2^{\ell }$ vectors of $V$, by the same translation-pairing argument used above. Removing the zero vector removes only a zero value, so the Hamming weight is still $m=2^{\ell -1}$. Since $H$ has matrix rank $\ell$, distinct $a$ give distinct codewords. This proves the constant weight of a binary simplex code and its full distribution:In particular, the ordinary weight enumerator of the binary simplex code is $1+n{z}^m$.

Apply the MacWilliams identity to this dual code, whose size is $2^{\ell }=n+1$. For $W_C(z)={\sum }_s{A}_s{z}^s$, the result isThe coefficient of $z^s$ in the second product is a value of the binary Kravchuk polynomialsThese bounds merely enforce $0\le j\le m$ and $0\le s-j\le n-m$. Since $n-m=2^{\ell -1}-1$, they agree with the bounds in the PDF. Therefore the requested formula isFor a further check on the low-weight counts, $n=2m-1$ givesThus $K_3(m)=m-1$, $K_4(m)=\left(\genfrac{}{}{0ex}{}{m-1}{2}\right)$, and $K_5(m)=-\left(\genfrac{}{}{0ex}{}{m-1}{2}\right)$. Substituting these into the boxed formula and using $m=(n+1)/2$ reproduces the three direct combinatorial counts above.

Finally, at $s=n$ the only possible term in the defining sum has $j=m$, so $K_n(m)=(-1{)}^m=1$, because $m=2^{\ell -1}$ is even. ConsequentlyThe unique length-$n$ binary word of weight $n$ is the all-ones word, exactly as proved by the parity-check matrix calculation.

Use the homogeneous weight enumerator conventionThus $s$ records ones, $t$ records zeros, and the ordinary weight enumerator is $W_C(z,1)$. For a binary linear code $C$ of dimension $k$ and its dual code $C^{\perp }$, the MacWilliams identity isor, equivalently, $W_C(s,t)=|C^{\perp }{|}^{-1}{W}_{C^{\perp }}(t-s,t+s)$. The second form applies the first to the dual and uses $(C^{\perp }{)}^{\perp }=C$.

One can verify the variable order directly from the character identity $1_{C^{\perp }}(y)=|C{|}^{-1}{\sum }_{x\in C}(-1{)}^{x\cdot y}$. If $y$ is not orthogonal to $C$, translation by a codeword having odd inner product pairs positive and negative terms, giving zero; otherwise all terms are one. After multiplying by $s^{\mathrm{wt}(y)}{t}^{N-\mathrm{wt}(y)}$ and summing over $y$, coordinate $j$ contributes $t+s$ when $x_j=0$, and $t-s$ when $x_j=1$. Their product is exactly the stated substitution.

For a Hamming code with $N=2^l-1$, its dual is the binary simplex code, generated by the $l$ rows of the usual parity-check matrix $H=P^T$. There are $2^l$ dual words. A nonzero message $a\in {\mathbb{F}}_2^l$ produces the evaluations $a\cdot v$ as $v$ runs over all nonzero vectors of ${\mathbb{F}}_2^l$. Exactly $2^{l-1}$ of them are one: the nonzero linear functional $v\mapsto a\cdot v$ takes each value equally often on the whole vector space, and removing zero removes a zero value only. This proves the constant weight of a binary simplex code.

Put $m=2^{l-1}$, so $N-m=m-1$. The dual enumerator is therefore $t^N+(2^l-1)s^m{t}^{m-1}$. Applying the MacWilliams identity gives the Hamming code weight enumeratorIn one variable this isFor example, $l=3$ gives $1+7z^3+7z^4+z^7$; $l=2$ gives $1+z^3$. For $l=1$, the expression is $1$, agreeing with the singleton code. Setting $s=t=1$ in the homogeneous formula gives $2^{N-l}$, the correct number of codewords.

Take the parity-check matrixover ${\mathbb{F}}_2$. Its columns are all the nonzero vectors of ${\mathbb{F}}_2^3$. The Hamming code is $C=\ker H$. Since $H$ has rank three, $C$ is a binary linear code of length seven and dimension four. No nonzero codeword has weight one or two, since no column is zero and no two columns coincide. Columns $u,v,u+v$ give a codeword of weight three, so $C$ has parameters $[7,4,3]$.

For a received vector $w=c+e$, its syndrome is $Hw=He$. A single error in position $j$ gives exactly column $j$ of $H$, so the syndrome identifies that position uniquely; zero syndrome means no error under the one-error assumption. The radius-one Hamming balls around the $16$ codewords are disjoint and have total size $16(1+7)=128=2^7$, so this is also a perfect code.

There are $\left(\genfrac{}{}{0ex}{}{7}{2}\right)/3=7$ weight-three codewords: every pair of columns determines the third, and each triple is counted three times. The all-ones vector is a codeword because the column sum is zero, so complementation gives seven weight-four codewords. Together with zero and the all-ones vector these account for all sixteen. The weight enumerator is therefore

For a binary linear code $C\le {\mathbb{F}}_2^n$, its rank is its dimension of a vector space $r$. Use the weight enumerator conventionwhere $w(c)$ is the Hamming weight. This convention is essential here: $W_C(1,0)$ counts words of weight $n$, rather than zero words. There are $2^r$ codewords, so $\boxed{W_C(1,1)=2^r}$.

There is only one binary word of weight $n$, namely $1=(1,\dots ,1)$. Thus $W_C(1,0)=1$ precisely when $1\in C$. If this holds, the linear map $c\mapsto c+1$ is a bijection of $C$ and replaces weight $w$ by $n-w$; hence $W_C(s,t)=W_C(t,s)$. Conversely this symmetry gives $W_C(1,0)=W_C(0,1)=1$, because the zero word is the unique word of weight zero.

The repetition code consists of $0,1$, givingThe single parity-check code consists of all words of even weight. Exactly $\left(\genfrac{}{}{0ex}{}{n}{j}\right)$ words have weight $j$, so the binomial theorem gives

A linear code of length $n$ and rank $k$ is a $k$-dimensional linear subspace of ${\mathbb{F}}_2^n$. The Hamming weight of a vector counts its nonzero coordinates. Thus the sum of the coefficients of the weight enumerator is the number of codewords:Since the zero vector is the unique word of weight zero, $W_C(0,1)=1$. Symmetry of the enumerator therefore implies $W_C(1,0)=1$. Conversely $W_C(1,0)=1$ means that the all-one vector $1$ belongs to $C$. Translation $x\mapsto x+1$ is then a bijection of $C$ which replaces weight $j$ by $n-j$, proving the polynomial symmetry. For length zero the same conclusion holds with the unique empty vector.

The dual code is $C^{\perp }=\{y:x\cdot y=0\text{ for every }x\in C\}$, using the standard bilinear form over ${\mathbb{F}}_2$. If $y\in C^{\perp }$, each summand of the character sum equals one. Otherwise choose $x_0\in C$ with $x_0\cdot y=1$; replacing $x$ by $x+x_0$ permutes the summands and reverses their sign. The sum equals its own negative and must be zero. ConsequentlyThis is character orthogonality for the additive group of the code.

The code consisting of all even-weight binary words. For $n\ge 1$ its dimension is $n-1$, and its weight enumerator is $[(t+s{)}^n+(t-s{)}^n]/2$, by selecting the even terms of the binomial theorem. The length-one code contains only zero.

The homogeneous weight enumerator of a length-$n$ linear code $C$ is the polynomialIts coefficients count words of each Hamming weight. In this convention $W_C(1,1)=|C|$; some references interchange $s,t$.