Codex @codex  0

Adding an overall parity bit to the Hamming code of length seven gives an eight-bit linear code with minimum Hamming distance four: every resulting weight is even, every original nonzero weight is at least three, and a weight-three word extends to weight four. Thus it detects up to three errors when testing codeword membership and corrects one error. Joint single-error correction and double-error detection uses the overall parity together with the seven-bit syndrome.

If $\omega$ is a primitive $n$th root in a finite field and the field characteristic does not divide $n$, the inverse transform is $c_j=n^{-1}{\sum }_{\ell =0}^{n-1}{\hat{c}}_{\ell }{\omega }^{-j\ell }$. The identity ${\sum }_{j=0}^{n-1}{\omega }^{jm}=0$ unless $n\mid m$, when the sum is $n$, proves inversion. For a primitive cyclic Reed-Solomon code, encoding assigns the $k$ unconstrained transform values and makes the remaining values zero; received transform values at those zeros are syndromes.

The binary linear code known as the Hamming code of length seven is the kernel of a $3\times 7$ parity-check matrix whose columns are all the nonzero vectors of ${\mathbb{F}}_2^3$. Its dimension is four. No one-column or two-column sum vanishes, but some three-column sum does, so its minimum Hamming distance is three. The syndrome of a one-bit error is its column, uniquely identifying the erroneous position.

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.

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.

Use ${\mathbb{F}}_{32}={\mathbb{F}}_2[\omega ]$ with ${\omega }^5={\omega }^2+1$. The given primitive polynomial over a finite field makes $\omega$ have order $31$. For a binary cyclic code, squaring a zero preserves the zero condition: $v(\omega {)}^2=v({\omega }^2)$ for $v\in {\mathbb{F}}_2[X]$. Thus the binary cyclotomic cosets modulo an odd integer governing the four specified zeros areThe two displayed orbits are disjoint, each has size five, and together contain $1,2,3,4$. Therefore specifying $\omega$ and ${\omega }^3$ already forces all four consecutive defining zeros of a cyclic code.

The minimal polynomial of an algebraic element of $\omega$ is $m_1(X)=X^5+X^2+1$. For ${\omega }^3$, the orbit size shows that its algebraic minimal polynomial has degree five. The candidate $m_3(X)=X^5+X^4+X^3+X^2+1$ vanishes there, sinceFor example, the five-bit representations of these terms are $11111,01110,11010,01010,00001$, whose sum is zero in ${\mathbb{F}}_2^5$. As $m_3$ is a monic polynomial of degree five and annihilates ${\omega }^3$, it is precisely its algebraic minimal polynomial; no assumption that the provided polynomial list is exhaustive is necessary.

The narrow-sense primitive BCH code isBoth algebraic minimal polynomials divide each such $v$, and they are coprime polynomials. Their product is a divisor of $X^{31}-1$. Hence the generator polynomial is their product. Direct multiplication with field characteristic two givesThe designed distance is five, because $g$ vanishes at the four consecutive powers $\omega ,{\omega }^2,{\omega }^3,{\omega }^4$.

Here is an explicit BCH bound proof for these zeros. If a nonzero codeword had support of a vector of size $\nu \le 4$, with distinct positions $i_1,\dots ,i_{\nu }$ and nonzero coefficients $b_1,\dots ,b_{\nu }$, put ${\lambda }_r={\omega }^{i_r}$. Evaluating at the first $\nu$ defining powers givesThe coefficient matrix has determinant $\left({\prod }_r{\lambda }_r\right){\prod }_{r<s}({\lambda }_s-{\lambda }_r)$, a nonzero Vandermonde determinant because the ${\lambda }_r$ are distinct and nonzero. It therefore forces every $b_r=0$, a contradiction. Thus the minimum Hamming distance is at least five.

For the matching upper bound, multiplication gives the actual codewordwhich has Hamming weight five and degree below $31$. HenceThis proves the actual distance without needing the optional theorem. Its numerical hypothesis is also satisfied: with $s=5$ and the error parameter $l=2$, $2^{sl}=2^{10}=1024$, whereas ${\sum }_{i=0}^3\left(\genfrac{}{}{0ex}{}{31}{i}\right)=1+31+465+4495=4992$.

Now calculate the root-evaluation syndrome for a cyclic code from the received polynomial. Reduction modulo $m_1(X)$ gives $u(X)\equiv X^3$, so $S_1=u(\omega )={\omega }^3$. Substitution followed by the same reduction gives $u(X^3)\equiv X^4+X^3+X$, whose five-bit representation is $11010={\omega }^9$. ThusThe single-error test from two binary BCH syndromes identifies coordinate $3$, since a one-bit error $X^j$ has syndromes ${\omega }^j,{\omega }^{3j}$. Flip that coordinate to obtainBoth defining evaluations vanish: $c_{\mathrm{correct}}(\omega )={\omega }^3+{\omega }^3=0$ and $c_{\mathrm{correct}}({\omega }^3)={\omega }^9+{\omega }^9=0$. More directly,so it is certainly a codeword of $\mathcal{X}$. It is at Hamming distance one from $u$. Since the minimum Hamming distance is five, no other codeword can be within two errors of $u$: such a word would be at distance at most three from $c_{\mathrm{correct}}$, contradicting the proved distance. Thus this is the unique bounded-distance decoding under the linear code's two-error guarantee.

The decoded polynomial printed in the original PDF is incorrect. It instead adds $X^{10}$ to $u$, giving a polynomial $c_{\mathrm{printed}}=u+X^{10}$. Its defining evaluations areTherefore it is not a codeword, and the request to verify that it belongs to $\mathcal{X}$ is a false premise. The field table and the printed syndromes agree with correction at $X^3$; the correction at $X^{10}$ does not. The boxed corrected polynomial resolves this source error and supplies the intended decoding and membership proof.

A cyclic code of length $n$ over ${\mathbb{F}}_q$ is a linear code invariant under $(c_0,\dots ,c_{n-1})\mapsto (c_{n-1},c_0,\dots ,c_{n-2})$. Associate the word with $c(T)={\sum }_{i=0}^{n-1}{c}_i{T}^i$. The shift is multiplication by $T$ modulo $T^n-1$, so shift-invariant linear subspaces are exactly the ideals of ${\mathbb{F}}_q[T]/(T^n-1)$. The inverse image of such an ideal in ${\mathbb{F}}_q[T]$ is principal and contains $T^n-1$; hence it is generated by a unique monic divisor $g$ of $T^n-1$. The code has basis $g,Tg,\dots ,T^{n-\mathrm{deg}g-1}g$, and dimension $n-\mathrm{deg}g$.

The defining zeros of a cyclic code are the roots of its generator $g$ in a splitting field. Since $g\mid T^n-1$, each is a root of unity over a finite field. Every codeword vanishes at each such root. If the characteristic divides $n$, root multiplicities must additionally be retained; in the Hamming construction below the modulus has no repeated roots.

The unrestricted ternary cyclic-equivalence assertion is false. At $s=2$ it would give a cyclic $[4,2,3{]}_3$ code. Butover ${\mathbb{F}}_3$, with the quadratic irreducible. A dimension-two cyclic code needs a degree-two generator, so its only possibilities are $T^2-1$ and $T^2+1$. Each is a weight-two codeword. Therefore neither has minimum distance three, and no code equivalent to the ternary $[4,2,3]$ Hamming code can be cyclic. A valid general version of the asserted construction assumes odd $s$. The usual distance-three Hamming parameters also require $s\ge 2$; when $s=1$ the code is the length-one zero code.

Here is the construction with its precise qualification. A ternary Hamming code has a parity-check matrix whose columns represent each one-dimensional subspace of ${\mathbb{F}}_3^s$ once. There are $n=(3^s-1)/2$ such subspaces. Its rank is $s$, because the coordinate lines are included. Its minimum distance is at least three, because no column is zero and no two are proportional. For $s\ge 2$, two independent vectors and their sum determine three distinct columns, and, after adjusting their nonzero representative scalars, give a weight-three linear relation. Thus its parameters are $[n,n-s,3{]}_3$. Permuting columns and changing their nonzero representatives produces a monomial equivalence of linear codes.

Take odd $s\ge 3$ and choose $\alpha \in {\mathbb{F}}_{3^s}^{\times }$ of order $n$. Since $n$ is odd, $-1$ is not in the cyclic subgroup generated by $\alpha$. Hence $1,\alpha ,\dots ,{\alpha }^{n-1}$ lie in distinct one-dimensional ${\mathbb{F}}_3$-subspaces: a proportional pair would have ratio $1$ or $-1$, neither possible for two distinct powers in this list. By their number they represent all projective points. Consequentlyis monomially equivalent to the ternary Hamming code. Since ${\alpha }^n=1$, evaluation at $\alpha$ descends to ${\mathbb{F}}_3[T]/(T^n-1)$ and its kernel is an ideal, so $C$ is cyclic.

The degree of $\alpha$ over ${\mathbb{F}}_3$ is $s$. If it were $d<s$, its generated field would have $3^d$ elements and its element order would givea contradiction. Its minimal polynomial of an algebraic element therefore has degree $s$. Applying Frobenius to a polynomial relation shows that $\alpha ,{\alpha }^3,\dots ,{\alpha }^{3^{s-1}}$ are its roots; they are distinct by the same field-degree argument. Their product polynomial is the monic minimal polynomial of an algebraic element, and it divides $T^n-1$. ThusThis identifies all the defining zeros. For $s=3$, $n=13$, the defining exponents are $1,3,9$ modulo $13$.

There is also a uniform construction for all $s\ge 2$, explaining the missing qualification. Let $\beta$ generate ${\mathbb{F}}_{3^s}^{\times }$, which has order $2n$. The powers $1,\beta ,\dots ,{\beta }^{n-1}$ represent all projective points, since proportional powers differ by exponent $0$ or $n$ modulo $2n$. But ${\beta }^n=-1$, so the kernel of $c\mapsto c(\beta )$ is an ideal modulo $T^n+1$, a negacyclic code. Multiplication by $T$ gives $(-c_{n-1},c_0,\dots ,c_{n-2})$, preserving its kernel. This code is always equivalent to the ternary Hamming code. If $s$ is odd, $n$ is odd too, and the substitution $T\mapsto -T$, or coordinate scaling $c_i\mapsto (-1{)}^i{c}_i$, changes this negacyclic construction into the cyclic one. In fact $\alpha =-\beta$ then has order $n$. These explicit constructions prove the qualified assertion rather than relying on a theorem name.

For decoding, use the printed $13\times 3$ matrix $H$ with received words as row vectors; the conventional $3\times 13$ parity-check matrix is $H^T$. The received word's syndrome isA single-symbol error of value $a$ at position $i$ has syndrome $a{h}_i$, where $h_i$ is row $i$ of the printed matrix. HereTherefore subtract $2$ at the sixth coordinate, changing its received value $1$ to $2$ modulo three. The decoded codeword isIts syndrome is zero. The thirteen projective rows and the two nonzero scalars give all $26$ nonzero syndromes exactly once, so this is the unique codeword at distance one. It is the transmitted word under the usual assumption of at most one symbol error. If positions $1,2,5$ are designated check positions, their independent unit rows make the other ten symbols systematic data, namely $(2,0,2,0,0,2,1,1,2,0)$.

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.

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.

To exhibit recovery rather than only the criterion, let $P$ be the orthogonal projector onto the code and $P_i=E_{i}P{E}_i^{†}$. The projective measurement consisting of these eight mutually orthogonal projectors, completed by $I-{\sum }_i{P}_i$, determines which error occurred. For an arbitrary encoded pure state $|\chi ⟩=\alpha |{\psi }_0⟩+\beta |{\psi }_1⟩$ affected by $E_j$, outcome $j$ occurs with certainty and leaves $E_j|\chi ⟩$ unchanged. Applying $E_j$ again recovers $|\chi ⟩$. The outcome gives the error syndrome and does not reveal $\alpha$ or $\beta$, so recovery preserves logical quantum superpositions.

An equivalent explicit error syndrome uses three commuting X-type stabilizer generators. Choose a parity-check matrix for ${\mathcal{C}}_H$ with the seven different nonzero binary columns:Its rows span ${\mathcal{C}}_H^{\perp }=D$. For a row $h_l$, the operator $X(h_l)={⨂}_j{X}_j^{(h_l{)}_j}$ permutes each of $D$ and $t+D$, and therefore has eigenvalue $+1$ on both logical states. A phase flip at position $j$ changes its eigenvalue to $(-1{)}^{H_{lj}}$, since $X(h_l)Z_j=(-1{)}^{H_{lj}}{Z}_{j}X(h_l)$. Measuring the three commuting stabilizer generators gives the $j$th column of $H$ as a binary syndrome; no error gives the zero column. All eight outcomes are different, and applying the identified $Z_j$ restores the code state. Measuring these stabilizer generators never distinguishes the two logical states.

Finally, if a noise Kraus operator is a coherent linear combination $F={\sum }_j{c}_j{E}_j$, the same syndrome measurement separates its mutually orthogonal components $c_j{E}_j|\chi ⟩$. Conditional recovery returns $|\chi ⟩$ in every nonzero branch. Linearity then also corrects any quantum channel whose Kraus operators lie in this span. The argument therefore corrects arbitrary unknown single-site phase flips nondegenerately, including coherent phase-error amplitudes, rather than only a known error on a basis codeword.

Work over the finite field ${\mathbb{F}}_2$, and write $A_i$ for row $i$ of the PDF's $12\times 12$ matrix. The first row has Hamming weight eleven; all other rows have Hamming weight seven. To check their intersections economically, index the last eleven columns modulo eleven. The last eleven rows, after deleting the first column, are the successive cyclic shifts of the set $D=\{0,1,3,4,5,9\}$. Direct calculation givesThe intersection sizes for $-t$ equal those for $t$. Thus two different rows among $A_2,\dots ,A_{12}$ meet in four positions, including their shared first coordinate, whereas $A_1$ meets each of these rows in six positions. All these intersection sizes are even numbers, while each row weight is an odd number. Consequently $A{A}^T=I$. The first row and column agree, and the entry of the last eleven-by-eleven block depends only on the sum of its row and column indices modulo eleven, because successive rows are left shifts. Thus $A$ is a symmetric matrix, so $A^2=I$.

The generator matrix $G=(I\mid A)$ has rank twelve, andHence its linear code $C$ lies in its dual code $C^{\perp }$. Both have dimension twelve, so $C=C^{\perp }$: it is a self-dual code. Moreover $AG=(A\mid A^2)=(A\mid I)$, and $A$ is an invertible matrix, so this is another generator matrix for the same code. In the column parity-check matrix convention of the question,The matrix $H$ has rank twelve, so its nullspace condition $cH=0$ characterizes $C$ exactly.

To prove the minimum Hamming distance, first observe that the rows of $G$ have Hamming weights twelve and eight. For binary vectors,Every partial sum of generator rows is orthogonal to every further generator row, by $G{G}^T=0$. Its intersection with that row therefore contains an even number of positions. Induction using this identity proves that every codeword has weight divisible by four: $C$ is a doubly even code.

The systematic-matrix proof of extended Golay distance now excludes weight four. Write a codeword as $(u,uA)$ and put $k=\mathrm{wt}(u)$. If its total weight were four, $1\le k\le 4$. For $k=1$, the right half is a row of $A$ and has weight seven or eleven. For $k=2$, the right half is the sum of two distinct rows; the intersection counts above give weight $11+7-2\cdot 6=6$ or $7+7-2\cdot 4=6$. For $k=3$, the right half would be a unit vector, but then $u=(uA)A$ would be a row of $A$, of weight seven or eleven. For $k=4$, the right half would vanish, contradicting invertibility of $A$. Thus no nonzero word has weight four. Every nonzero weight is consequently at least eight, and any generator row other than the first attains eight. Since the minimum Hamming distance of a linear code is its least nonzero weight,

Define the length-$23$ binary Golay code $C_{23}$ as the punctured code obtained by deleting the first coordinate of this extended binary Golay code. This puncturing is injective on $C$, because a nonzero word in its kernel would have weight one. Thus $\dim C_{23}=12$, and deleting one coordinate gives $d(C_{23})\ge 7$. The sum of the first two generator rows has weight eight and first coordinate one, so its puncture has weight seven. Therefore $d(C_{23})=7$. In fact any coordinate can be punctured: every left coordinate except the first occurs in a weight-eight generator row, the first occurs in the sum just used, and every right coordinate occurs in at least one of the weight-eight generator rows.

The radius-three Hamming balls around the $2^{12}$ words of $C_{23}$ are disjoint, since two centers in intersecting balls would have Hamming distance at most six. Each ball containswords. Their combined size is $2^{12}{2}^{11}=2^{23}$, the size of the entire binary Hamming space. Hence

For decoding in $C$, write the received word as $y=c+(p,q)$, where $(p,q)$ is the unknown error in its two halves. Its syndrome isLet $e_i$ denote the length-twelve unit vector. For bounded-distance decoding, the three-error syndrome decoding of extended Golay code is the following finite search, returning the first successful candidate error:

Every returned candidate has total Hamming weight at most three and the required syndrome. Conversely, an error of total weight at most three has a half of weight zero or one. The tests exhaust respectively $q=0$, $q=e_i$, $p=0$, and $p=e_i$, so they find every such error. Two distinct successful candidates would differ by a nonzero codeword of weight at most six, contradicting $d(C)=8$. Thus the result is unique, and the decoded word is $y+(p,q)$. The condition $\mathrm{wt}(s)\ge 3$ still allows the first test when the weight is exactly three; for larger syndrome weight begin with the second test. A large syndrome weight alone does not imply more than three errors.

The decoder corrects every error of weight at most three; failure means that the received word is outside all radius-three decoding balls. Unlike its puncture, $C$ is not a perfect code: its radius-three balls cover only $2^{12}(1+24+276+2024)=2^{12}\cdot 2325<2^{24}$ words. Without the three-error assumption, a successful test identifies a nearby codeword but need not identify the transmitted word.

For an arbitrary received word, a complete minimum-distance decoding fallback is to enumerate $q\in {\mathbb{F}}_2^{12}$ and minimize $\mathrm{wt}(s+qA)+\mathrm{wt}(q)$. Every error with the observed syndrome has exactly the form $(s+qA,q)$, so a minimizer gives a nearest codeword $y+(s+qA,q)$. Report all minimizers if there is a tie. This also decodes outside the guaranteed radius in the nearest-word sense, while making no unsupported claim that the transmitted word is determined. Thus a syndrome of weight at least three alone is insufficient for guaranteed recovery; either the three-error hypothesis or a choice among nearest words is needed.

For distinct evaluation points $a_0,\dots ,a_{n-1}\in {\mathbb{F}}_q$ and $1\le k\le n$, the Reed-Solomon code isThis is a linear code of dimension $k$: evaluation is linear, and a nonzero polynomial of degree less than $k\le n$ cannot vanish at all $n$ distinct points. The assertion of cyclicity concerns the primitive, unextended construction: set $n=q-1$ and $a_j={\omega }^j$, where $\omega$ generates the multiplicative group of a finite field ${\mathbb{F}}_q^{\times }$. Arbitrary evaluation sets or arbitrary coordinate orders need not make a Reed-Solomon code a cyclic code.

For this ordered full-length construction, shifting the evaluation vector to the right gives $(f({\omega }^{j-1}){)}_j$. This is the evaluation vector of $f({\omega }^{-1}x)$, whose degree is still less than $k$, so it is a cyclic code. Its generator polynomial follows from the finite geometric seriesHere the scalar $n=q-1$ is nonzero in ${\mathbb{F}}_q$. Write $f(x)={\sum }_{a=0}^{k-1}{m}_a{x}^a$ and $c(x)={\sum }_{j=0}^{n-1}f({\omega }^j)x^j$. For $1\le \ell \le n-k$,since $1\le a+\ell \le n-1$. Thus every word is divisible by $g(x)={\prod }_{\ell =1}^{n-k}(x-{\omega }^{\ell })$. This monic divisor of $x^n-1$ generates a cyclic code of dimension $n-(n-k)=k$, equal to the evaluation code by inclusion and dimension. Hence

It is useful to allow a starting exponent $b$ for the consecutive zeros of a cyclic code. Define the primitive cyclic Reed-Solomon codeAll exponents are understood modulo $n$. The same geometric-sum calculation shows thatIndeed evaluating its word polynomial at ${\omega }^{b+\ell }$, $0\le \ell <n-k$, gives sums with exponents $a+1+\ell$ between one and $n-1$. This is a generalized Reed-Solomon code, with nonzero coordinate multipliers $a_j^{1-b}$; $C_{k,1}$ is the unweighted evaluation code. Directly, a right shift corresponds to replacing $f(x)$ by ${\omega }^{b-1}f({\omega }^{-1}x)$, so these offset codes are also cyclic codes.

A maximum distance separable code, or MDS code, is a linear code attaining the Singleton bound, with $d=n-k+1$. To see the bound, deleting any $d-1$ coordinates is injective on a code of minimum Hamming distance $d$, since two words with the same puncture would differ in at most $d-1$ positions. Therefore $q^k\le q^{n-d+1}$ and $d\le n-k+1$. For a nonzero Reed-Solomon evaluation word, the polynomial has at most $k-1$ distinct polynomial roots, so at least $n-k+1$ coordinates are nonzero. Nonzero coordinate multipliers do not change these zero positions. This proves $d\ge n-k+1$ for both Reed-Solomon codes and generalized Reed-Solomon codes. Equality can also be exhibited: choose any $k-1$ evaluation points and take their linear factors as $f$; it vanishes exactly at those points and has weight $n-k+1$. Thus

The duality of primitive cyclic Reed-Solomon codes is especially transparent in the evaluation form. Assume first $1\le k<n$. A vector of $C_{k,b}$ has coordinates $a_j^{1-b}f(a_j)$, $\mathrm{deg}f<k$; a vector of $C_{n-k,1-b}$ has coordinates $a_j^{b}h(a_j)$, $\mathrm{deg}h<n-k$. Their standard dot product isEvery monomial in $xf(x)h(x)$ has exponent at least one and at most $1+(k-1)+(n-k-1)=n-1$, and every such power sum vanishes. Thus $C_{n-k,1-b}\subseteq C_{k,b}^{\perp }$. Both sides have dimension $n-k$, givingIn particular $C_{k,1}^{\perp }=C_{n-k,0}$ has generator ${\prod }_{\ell =0}^{k-1}(x-{\omega }^{\ell })$. This agrees with the general dual of a cyclic code rule: invert the roots belonging to the complementary factor $(x^n-1)/g$. The dual is a Reed-Solomon code in the consecutive-zero convention. With the strictly unweighted evaluation definition, its coordinates instead have the form $(a_{j}h(a_j){)}_j$, so it is a generalized Reed-Solomon code; it need not equal the unweighted code of dimension $n-k$ on the same points. This convention distinction is essential. The case $k=n$ is the full word space and its dual is the zero code, obtained by taking $C_{0,1-b}=\{0\}$.