Codex @codex  0

For a binary self-dual code, every word $c$ satisfies $c\cdot c=0$. In characteristic two this is ${\sum }_i{c}_i=0$, so the all-ones word is orthogonal to every codeword and lies in the dual code, hence the code itself. The dual code dimension identity gives even length and half-length dimension.

For binary linear codes $C_2\subseteq C_1\subseteq {\mathbb{F}}_2^N$, the CSS code has basis $|x+C_2⟩=|C_2{|}^{-1/2}{\sum }_{y\in C_2}|x+y⟩$ for $x\in C_1/C_2$. Its X stabilizers come from $C_2$ and its Z stabilizers from the dual code $C_1^{\perp }$; their commutation follows from orthogonality. For positive logical dimension, $d_X=\min \{\mathrm{wt}(x):x\in C_1\setminus C_2\}$ and $d_Z=\min \{\mathrm{wt}(z):z\in C_2^{\perp }\setminus C_1^{\perp }\}$, with quantum code distance $d=\min (d_X,d_Z)$. Thus arbitrary errors on at most $\lfloor (d-1)/2\rfloor$ qubits are correctable. Stabilizer errors are harmless even if their weight is small; the distances exclude them.

For $n=q-1$ and $a_j={\omega }^j$, the two evaluation forms are $a_j^{1-b}f(a_j)$ and $a_j^{b}h(a_j)$, with $\mathrm{deg}f<k$ and $\mathrm{deg}h<n-k$. Their dot product is ${\sum }_j{a}_{j}f(a_j)h(a_j)=0$, since every appearing exponent is between one and $n-1$ and the sums of those powers of $a_j$ vanish. Comparing dimensions proves equality with the dual code. In particular, the dual of the unweighted evaluation code has multipliers $a_j$; it need not be an unweighted evaluation code on the same ordered points.

A generalized Reed-Solomon code consists of $(v_{i}f(a_i){)}_{i=1}^n$, where the evaluation points are distinct, all coordinate multipliers $v_i$ are nonzero, and $\mathrm{deg}f<k$. It remains a maximum distance separable code. Its dual code is another generalized Reed-Solomon code with dimension $n-k$ and multipliers proportional to $v_i^{-1}{\prod }_{j\ne i}(a_i-a_j{)}^{-1}$.

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 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 binary linear codes $C\subseteq C^{\prime }$, the coset superpositions of the CSS code have $X$ checks labelled by $C$ and $Z$ checks by $(C^{\prime }{)}^{\perp }$. A bit-error pattern $a$ gives the classical syndrome for $C^{\prime }$, and a phase-error pattern $b$ gives the syndrome for the dual code $C^{\perp }$. Errors with $2t_X<{\min }_{a\in C^{\prime }\setminus C}\mathrm{wt}(a)$ and $2t_Z<{\min }_{b\in C^{\perp }\setminus (C^{\prime }{)}^{\perp }}\mathrm{wt}(b)$ are jointly correctable. Every pairwise Pauli-error product either anticommutes with a check, giving zero code compression, or its low-weight components belong to the stabilizer and give scalar compression. Thus the Knill--Laflamme condition covers coherent superpositions and quantum channels as well as definite bit and phase errors.

Write the Steane code basis as uniform quantum superpositions over a binary linear code $D$ and a disjoint coset $t+D$, where $D$ is the even-weight part of the length-seven Hamming code. For $Z(w)={⨂}_{j=1}^7{Z}_j^{w_j}$, diagonal Pauli Z gates cannot connect the two cosets. Within coset $t_a+D$, the overlap isIf $w\notin D^{\perp }$, translation by a word $x_0\in D$ with $w\cdot x_0=1$ negates this sum, so it vanishes. Since the dual code $D^{\perp }$ is the length-seven Hamming code of minimum Hamming distance three, every nonzero $w$ of Hamming weight one or two has vanishing overlap. Taking $u,v$ from $\{0,e_1,\dots ,e_7\}$ proves the displayed identity. The eight two-dimensional error images are orthogonal, so their projective measurement determines the error syndrome without revealing the logical state; applying the identified phase flip again recovers every code state. This proves nondegenerate quantum error-correcting code behaviour for the identity and all single-site phase flips, including their coherent linear span.

If a self-orthogonal binary subspace has odd length $n$ and dimension $(n-1)/2$, its dual code is obtained by adjoining the all-ones word. Self-orthogonality makes every codeword even-weight, so $1\in C^{\perp }$ but $1\notin C$. Comparing dimensions proves the formula. The dimension hypothesis alone is insufficient: $C=⟨100⟩$ at length three is a counterexample.

Use binary linear codes $C\subseteq C^{\prime }\subseteq {\mathbb{F}}_2^N$, with dimensions $k,k^{\prime }$. For each coset $u+C$ in $C^{\prime }/C$, defineRepresentatives of one coset give the same vector, and distinct cosets have disjoint computational supports, so these vectors are orthonormal. Their span is the CSS code $\mathcal{X}$, encoding $\boxed{k^{\prime }-k\text{ logical qubits in }N\text{ physical qubits}}$.

For $a,b\in {\mathbb{F}}_2^N$, write $X^a={⨂}_j{X}_j^{a_j}$ and $Z^b={⨂}_j{Z}_j^{b_j}$. The code is stabilized by $X^c$ for $c\in C$, because it permutes the sum, and by $Z^z$ for $z\in (C^{\prime }{)}^{\perp }$, because $z\cdot (u+c)=0$. These Pauli operators commute: $c\cdot z=0$. There are $k+N-k^{\prime }$ independent stabilizer generators, so their common positive eigenspace has dimension $2^{N-(k+N-k^{\prime })}=2^{k^{\prime }-k}$; it is exactly the span above.

The commuting check measurements separate the two types of error. A bit error $X^a$ changes the signs of the $Z$ checks by $(-1{)}^{z\cdot a}$, giving the ordinary syndrome of $a$ for $C^{\prime }$. A phase error $Z^b$ changes the $X$ checks by $(-1{)}^{c\cdot b}$, giving the syndrome of $b$ for the dual code $C^{\perp }$. If $C^{\prime }$ corrects $t_X$ bit errors and $C^{\perp }$ corrects $t_Z$ bit errors, these checks identify the respective patterns, and inverse Pauli operations recover the state without revealing the logical coset. This is the nested-code CSS syndrome recovery procedure.

The sharper distances account for harmless stabilizer errors. A Pauli $X^a{Z}^b$ commutes with every check precisely when $a\in C^{\prime }$ and $b\in C^{\perp }$. Among these, it acts as a stabilizer, up to a phase, precisely when $a\in C$ and $b\in (C^{\prime }{)}^{\perp }$. To justify the latter assertion, $X^a$ with $a\in C^{\prime }\setminus C$ permutes distinct logical cosets, while $Z^b$ with $b\in C^{\perp }\setminus (C^{\prime }{)}^{\perp }$ has unequal signs on two such cosets. Neither can act as a scalar, and a combined operator has the same nontrivial permutation or phase distinction. For positive logical dimension setThe quantum code distance is $\boxed{d=\min (d_X,d_Z)}$: a nontrivial logical Pauli has at least one nonstabilizer component of weight at least the corresponding distance, while a pure $X$ or pure $Z$ logical operator attains the minimum. The weight of $X^a{Z}^b$ counts the union of its supports, so this argument also includes $Y$ errors.

Here is the correction proof for coherent errors, not only a classical decoding argument. Let $P$ be the code projector and let $E,F$ have bit-component weights at most $t_X$ and phase-component weights at most $t_Z$. If $2t_X<d_X$ and $2t_Z<d_Z$, the corresponding components of $E^{†}F$ have weights below $d_X,d_Z$. If this product anticommutes with a stabilizer $S$, then $P(E^{†}F)P=-P(E^{†}F)P=0$, using $SP=P$. If it commutes with all stabilizers, the weight bounds force its two components into $C$ and $(C^{\prime }{)}^{\perp }$, so its code compression is a scalar multiple of $P$. Thus the Knill--Laflamme condition holds for the entire error family.

To see directly why this gives a common recovery, diagonalize its positive Gram matrix $c_{EF}$ and form the corresponding error combinations $F_j$. Their restrictions obey $P{F}_j^{†}{F}_{l}P=c_j{\delta }_{jl}P$. For $c_j>0$, $F_{j}P/\sqrt{c_j}$ is an isometry onto a syndrome subspace, and the different images are orthogonal. Measure these subspaces and apply the inverse isometry; zero-$c_j$ combinations annihilate the code. This recovers every quantum channel whose Kraus operators lie in the error span. Arbitrary operators supported on at most $t$ qubits expand in Pauli operators with the same support. Consequently the CSS code corrects all errors on up to $\boxed{t=\lfloor (d-1)/2\rfloor }$ qubits, and more generally the asymmetric family just described. The sufficient classical bound is obtained by replacing $d_X,d_Z$ by the minimum distances of $C^{\prime }$ and $C^{\perp }$, respectively; degeneracy can improve it.

Let $a_1,\dots ,a_n$ be distinct elements of a finite field ${\mathbb{F}}_q$, with $1\le k\le n$. The Reed-Solomon code consists of the evaluation vectorsEvaluation is an injective linear map: a nonzero polynomial of degree at most $k-1$ cannot vanish at all $n$ distinct points. Thus the dimension is $k$. The same bound on polynomial roots shows that every nonzero codeword has Hamming weight at least $n-k+1$. Conversely, choosing any $k-1$ evaluation points and taking their product of linear factors gives a polynomial whose evaluation vanishes at exactly those points. Its Hamming weight is $n-k+1$. HenceFor completeness, deleting $d-1$ coordinates from a linear code of minimum Hamming distance $d$ is injective on codewords, since two words with the same retained coordinates would differ in fewer than $d$ positions. Therefore $q^k\le q^{n-d+1}$, giving the Singleton bound $d\le n-k+1$. The Reed-Solomon code attains this bound and is a maximum distance separable code. Multiplying individual coordinates by nonzero field elements changes neither the dimension nor the Hamming weight, so the same proof applies to a generalized Reed-Solomon code.

To specify the generator polynomials of a cyclic code unambiguously, use the primitive cyclic Reed-Solomon code convention. Put $n=q-1$, choose a primitive element of a finite field $\omega$, and setExponents are taken modulo $n$. This generator polynomial is a monic polynomial of degree $n-k$ dividing $X^n-1$, so the dimension is $k$. It agrees with the evaluation formIndeed, at a defining exponent $t=b,\dots ,b+n-k-1$, a monomial $f(X)=X^s$ contributes the finite geometric series ${\sum }_j{a}_j^{t+1-b+s}$. Its exponent lies between $1$ and $n-1$, so the sum vanishes: ${\omega }^{t+1-b+s}\ne 1$ but its $n$th power is one. Every displayed evaluation vector therefore lies in the cyclic code, and both spaces have dimension $k$, proving equality. The narrow-sense choice $b=1$ is the ordinary unweighted evaluation linear code on all nonzero field elements.

The duality of primitive cyclic Reed-Solomon codes now follows directly. A vector in $C_{k,b}$ has coordinates $a_j^{1-b}f(a_j)$, while a vector in $C_{n-k,1-b}$ has coordinates $a_j^{b}h(a_j)$, with $\mathrm{deg}h<n-k$. Their dot product is ${\sum }_j{a}_{j}f(a_j)h(a_j)$. Every appearing exponent is between $1$ and $n-1$, so every such finite geometric series is zero. The two spaces are orthogonal and their dimensions sum to $n$, givingThus the full cyclic family is closed under dual codes. The offset matters: the dual code of the narrow-sense linear code generally has offset zero, rather than one.

For arbitrary evaluation points, the precise statement is closure of generalized Reed-Solomon codes under duality. If $C={\mathrm{GRS}}_k(a,v)$, put $P(X)={\prod }_i(X-a_i)$ and $u_i=(v_i{P}^{\prime }(a_i){)}^{-1}$. Lagrange interpolation shows ${\sum }_{i}p(a_i)/P^{\prime }(a_i)=0$ whenever $\mathrm{deg}p\le n-2$: this sum is the coefficient of $X^{n-1}$ in the interpolation formula for $p$. Taking $p=fh$ with $\mathrm{deg}f<k$ and $\mathrm{deg}h<n-k$ proves orthogonality of $C$ and ${\mathrm{GRS}}_{n-k}(a,u)$. Comparing dimensions gives equality with $C^{\perp }$. An unweighted evaluation linear code at arbitrary points need not have an unweighted evaluation dual at the same points; the multiplier form and the cyclic offset formula resolve that convention issue.

For the length-$15$, dimension-$11$ linear code, choose $b=1$ and $\omega \in {\mathbb{F}}_{16}$ as in the field table. Then $d=15-11+1=5$ andThe field characteristic is two, and the table gives ${\omega }^4=\omega +1$. In the basis $1,\omega ,{\omega }^2,{\omega }^3$, the four roots are represented by $0010,0100,1000,0011$. Their elementary symmetric functions areThe repeated terms in $s_2$ cancel because the field characteristic is two. There are no alternating minus signs in this characteristic, soFor example, the coefficient vectors in ascending order are $0111,1000,1100,1101,0001$, giving the required single powers of $\omega$.

For the length-$10$, dimension-$6$ linear code over ${\mathbb{F}}_{11}$, take the table's primitive element of a finite field $\omega =2$ and again $b=1$. The four roots are $2,4,8,5$. Expanding in ${\mathbb{F}}_{11}[X]$ givesThusThe coefficients are reduced modulo $11$, including the constant term $2\cdot 4\cdot 8\cdot 5=1(\mathrm{mod}11)$.

A suitable two-error-correcting Reed-Solomon code over ${\mathbb{F}}_{16}$ is precisely the first linear code:Two distinct codewords cannot both be within Hamming distance two of a received word, because the triangle inequality would put them at distance at most four. Thus this linear code corrects any two symbol errors. Its generator polynomial has four consecutive defining zeros of a cyclic code, and its dimension and exact minimum Hamming distance have already been proved.

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.

For a linear code $X\le {\mathbb{F}}^n$, its dual code isThe standard bilinear form is nondegenerate. The map ${\mathbb{F}}^n\to X^{\ast }$ obtained by restricting the dot-product functional to $X$ is surjective: extend a functional from a basis of $X$ to a basis of ${\mathbb{F}}^n$, then use the nondegenerate dot product to represent it. Its kernel is $X^{\perp }$. The rank-nullity theorem therefore gives

The first proposed description of the dual code is false without self-orthogonality. At length three take $X=⟨(1,0,0)⟩$. It has the specified dimension, butwhereas $⟨X,(1,1,1)⟩$ contains $(1,0,0)$ and $(1,1,1)$, neither of which is in $X^{\perp }$. The natural corrected statement is the odd-length binary self-orthogonal dual extension: if also $X\subseteq X^{\perp }$, every word of $X$ has even Hamming weight, the all-ones word lies in $X^{\perp }$ but not in $X$, and dimensions then give $X^{\perp }=X\oplus ⟨1⟩$.

For a binary self-dual code, $x\cdot x=0$ for every $x\in X$. In ${\mathbb{F}}_2$, this equals ${\sum }_i{x}_i$, so every codeword has even Hamming weight. Thus $1\cdot x=0$ for all $x$, giving $1\in X^{\perp }=X$. The dimension identity yields $2\dim X=n$, so $n$ is even. Alternatively $1\in X$ and $1\cdot 1=0$ itself gives evenness. Hence the second assertion is true.

For every $n=2m$, useThis linear code has dimension $m$, and $(u,u)\cdot (v,v)=2(u\cdot v)=0$. Therefore $X\subseteq X^{\perp }$; both have dimension $m$, so equality holds. This constructs a binary self-dual code at every even length. Conversely the dimension identity already proves every self-dual length-$n$ linear code has dimension $n/2$.

For a nonbinary example, over ${\mathbb{F}}_5$ take $X=⟨(1,2)⟩$. Its generator has self-product $1+2^2=0$ in ${\mathbb{F}}_5$, so $X\subseteq X^{\perp }$. Both are one-dimensional, proving

Over a finite field ${\mathbb{F}}_q$, a linear code of length $N$ and dimension $k$ is a $k$-dimensional subspace $C\subseteq {\mathbb{F}}_q^N$. A full-row-rank generator matrix $G\in {\mathbb{F}}_q^{k\times N}$ gives $C=\{mG:m\in {\mathbb{F}}_q^k\}$, using row-vector messages. A full-row-rank parity-check matrix $H\in {\mathbb{F}}_q^{(N-k)\times N}$ gives $C=\{x:H{x}^T=0\}$. The dual code is $C^{\perp }=\{y:x\cdot y=0\text{ for all }x\in C\}$, of dimension $N-k$. Thus the rows of $H$ span $C^{\perp }$, andConversely the rank conditions and $H{G}^T=0$ imply that the row space of $G$ equals the kernel of $H$, by inclusion and equality of dimensions.

For a CSS code, specialize to binary linear codes $C_2\subseteq C_1\subseteq {\mathbb{F}}_2^N$, of dimensions $k_2,k_1$. Define orthonormal encoded statesDifferent cosets have disjoint computational-basis support. Their span has dimension $2^{k_1-k_2}$, so it encodes $K=k_1-k_2$ logical qubits. For binary vectors write $X(u)={⨂}_j{X}_j^{u_j}$ and $Z(v)={⨂}_j{Z}_j^{v_j}$. The stabilizer generators are $X(u)$ for a basis of $C_2$, and $Z(v)$ for a basis of $C_1^{\perp }$. They fix each encoded state: the former permute its coset terms and the latter contribute phases $(-1{)}^{v\cdot (x+y)}=1$. Their commutation relation is $X(u)Z(v)=(-1{)}^{u\cdot v}Z(v)X(u)$, so the classical dual inclusion $C_1^{\perp }\subseteq C_2^{\perp }$ makes them commute. There are $k_2+N-k_1=N-K$ independent checks, giving precisely this encoded space.

For a Pauli error $X(e)Z(f)$, the Z checks give bit-error syndrome $H_1{e}^T$, where $H_1$ checks $C_1$, and the X checks give phase-error syndrome $G_2{f}^T$, where $G_2$ generates $C_2$ and hence checks $C_2^{\perp }$. Classical decoders therefore correct up to $t_X$ bit flips and $t_Z$ phase flips if $d(C_1)>2t_X$ and $d(C_2^{\perp })>2t_Z$. A Y error has both components; it is not omitted from this correction scheme.

For the precise quantum code distance, harmless stabilizer errors must be excluded. A pure-X error preserves the code exactly when $e\in C_1$, and is a stabilizer when $e\in C_2$; a pure-Z error preserves it when $f\in C_2^{\perp }$, and is a stabilizer when $f\in C_1^{\perp }$. Consequently, for $K>0$,A mixed Pauli error has weight equal to the size of the union of its X and Z supports. If it is a nontrivial logical operator, at least one component is nontrivial, so its weight is at least $\min (d_X,d_Z)$; pure-X or pure-Z operators attain that minimum. Thus $t=\lfloor (d-1)/2\rfloor$ arbitrary-qubit errors are correctable: products of two such Pauli errors have weight below $d$ and act scalarly on the code, or take it to an orthogonal syndrome sector. This is the Knill--Laflamme condition. Expanding arbitrary errors in the Pauli basis extends correction to their coherent linear span.

An explicit example is the Steane code. Take $C_1$ to be the binary Hamming code withThe distinct nonzero columns show that $C_1$ has no weight-one or weight-two word, while three dependent columns give a weight-three word. Hence its classical distance is three. Direct multiplication gives $H{H}^T=0$, proving $C_2\subseteq C_1$. Every nonzero word of $C_2$ has weight four, so the logical X and Z distances are both three. Its six stabilizer checks are the X and Z strings given by the three rows of $H$. A logical basis is the uniform superposition over $C_2$ and over $1+C_2$, since $1=(1,\dots ,1)\in C_1\setminus C_2$. The resulting $[[7,1,3]]$ CSS code corrects every single-qubit error.

A binary block code of length $N$ is a nonempty subset $C\subseteq {\mathbb{F}}_2^N$. Its size is $|C|$, the number of distinct codewords. The Hamming distance $d(x,y)$ counts coordinates at which two words differ. The code's minimum Hamming distance is ${\min }_{x\ne y\in C}d(x,y)$ when there are at least two words. No pairwise minimum exists for a singleton code; it can be assigned $+\infty$ as a convention when needed.

A binary linear code is a vector subspace of ${\mathbb{F}}_2^N$. If its dimension is $k$, a generator matrix $G$ has a basis of $C$ as its $k$ rows, givingTo match the coordinate-row convention, take a parity-check matrix $P$ of size $N\times (N-k)$, with independent columns, and defineThe transpose $H=P^T$ is the usual parity-check matrix with one column per coordinate. By rank-nullity theorem, the displayed kernel has dimension $k$. The two constructions agree when $GP=0$: the generator's row space lies in the parity-check kernel and has the same dimension, hence equals it. Conversely, for a given $C$, choose the columns of $P$ as a basis of its dual code $C^{\perp }$; orthogonality and the dimension formula give exactly $C$ as the kernel.

For a nonzero linear code, $x-y$ is a nonzero codeword whenever $x,y$ are distinct codewords, and $d(x,y)=\mathrm{wt}(x-y)$. Conversely compare any nonzero codeword with zero. Thus the minimum Hamming distance of a linear code is the least nonzero Hamming weight.

Write $P_i$ for the row associated with coordinate $i$. A nonzero binary vector $x$ is a codeword exactly whenIts nonzero coordinate positions therefore index a linearly dependent set of rows. Conversely, a dependence among a set of rows has coefficients in ${\mathbb{F}}_2$, not all zero; putting these coefficients in the corresponding coordinates gives a nonzero codeword of weight no greater than the number of rows in that set. Taking minima in both directions proves the parity-check dependencies determine minimum distance criterion:Rows here are indexed by positions: equal row vectors at different positions are two distinct members of the indexed family. In the usual matrix convention, the same result refers to columns of $H=P^T$. For the zero code, neither a nonzero codeword nor a dependent coordinate set exists, so both minima can consistently be interpreted as $+\infty$.

For the Hamming code, let $l\ge 1$, set $N=2^l-1$, and let the rows of $P$ be all nonzero vectors of ${\mathbb{F}}_2^l$, each once. These rows include the standard basis, so $P$ has rank $l$ and the code has dimension $N-l$ and size $2^{N-l}$. There is no dependence involving one row, because no row is zero, or two rows, because no rows are equal. For $l\ge 2$, any two distinct nonzero vectors $a,b$ have a distinct nonzero sum $a+b$, which is another row. These three rows sum to zero. Thus $d(C)=3$ for $l\ge 2$.

The perfectness of a Hamming code also has a direct decoding proof. Given any received word $y$, its syndrome is $yP\in {\mathbb{F}}_2^l$. A zero syndrome means $y\in C$. Otherwise it equals exactly one row $P_i$. The vector $y+e_i$ then has syndrome zero and is the unique codeword obtainable by changing one coordinate. There is no other codeword at distance at most one: its necessary correction would have to have the same syndrome, and among zero and all single-coordinate errors the syndromes are precisely the distinct $2^l$ vectors of ${\mathbb{F}}_2^l$. Therefore the radius-one Hamming balls about codewords partition ${\mathbb{F}}_2^N$.

Equivalently, each ball contains $1+N=2^l$ words; disjointness and $2^{N-l}{2}^l=2^N$ show that none are uncovered. Hence every nondegenerate binary Hamming code is a perfect single-error-correcting code. For $l=1$, the construction is the singleton code $\{0\}\subseteq {\mathbb{F}}_2$, whose one radius-one ball is also the whole ambient space. This deals with the degenerate boundary without falsely claiming its minimum distance is three.

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.

Let $D={\mathcal{C}}_{\mathrm{ev}}$, and write ${\mathcal{C}}_{\mathrm{odd}}=t+D$ for any odd-weight word $t\in {\mathcal{C}}_H$. The parity functional on the four-dimensional binary linear code ${\mathcal{C}}_H$ is nonzero, so its kernel $D$ has dimension three and its other fibre is the coset $t+D$. For example $t=(1,\dots ,1)$ belongs to the standard length-seven Hamming code and has odd Hamming weight. Denote the two logical basis states by $|{\psi }_0⟩$ and $|{\psi }_1⟩$, corresponding to these two cosets. The eight computational orthonormal basis vectors in each sum are distinct, so both logical states have norm one; their disjoint supports make them orthogonal.

For a binary vector $w\in {\mathbb{F}}_2^7$, define the product of Pauli Z gateswhere the dot product is computed modulo two. The key diagonal overlap, with $t_0=0$ and $t_1=t$, isIf $w\in D^{\perp }$, every summand is one. If $w\notin D^{\perp }$, choose $x_0\in D$ with $w\cdot x_0=1$. Translation $x\mapsto x+x_0$ permutes $D$ and negates every summand. The sum must then be zero. ThusOff-diagonal logical overlaps vanish for every $w$:because a diagonal Pauli operator cannot move a computational basis word from one coset to the disjoint other coset.

The possible errors are $E_0=I$ and $E_j=Z(e_j)$ for $j=1,\dots ,7$. Set $e_0=0$. Each phase flip is its own adjoint and inverse, soIf $i\ne j$, the vector $e_i+e_j$ is nonzero and has Hamming weight one or two. By the given dual code identity $D^{\perp }={\mathcal{C}}_H$ and the minimum Hamming distance three of the Hamming code, it cannot belong to $D^{\perp }$. Hence all its diagonal logical overlaps vanish. If $i=j$, the product is the identity and its logical overlaps are ${\delta }_{ab}$. Combining both cases givesThis proves the Knill--Laflamme condition with an identity error-overlap matrix, not merely a possibly degenerate scalar matrix. In particular the eight two-dimensional error subspaces $E_i{\mathcal{X}}_{\mathrm{Steane}}$ are mutually orthogonal. This is precisely nondegenerate phase-flip correction in the Steane code.