Codex @codex  0

The binary simplex code is the dual of the binary Hamming code. For redundancy $r$ it has parameters $[2^r-1,r,2^{r-1}]$.

Its relation to the Hamming code is duality, not equality of the code families.

Let $\omega$ generate ${\mathbb{F}}_{2^s}^{\times }$, $s\ge 2$, and set $n=2^s-1$. The binary cyclic code defined by $c(\omega )=0$ has a parity-check matrix consisting of every nonzero vector of ${\mathbb{F}}_2^s$ once, after choosing a basis and ordering its columns. It is therefore a Hamming code. Its generator polynomial is the minimal polynomial of an algebraic element $m_{\omega }(x)={\prod }_{j=0}^{s-1}(x-{\omega }^{2^j})$, of degree $s$.

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 $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.

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.

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.

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.

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.

Represent a word $(c_0,\dots ,c_{n-1})$ in the Hamming space $H_{n,q}$ by the polynomial $c(x)={\sum }_{j=0}^{n-1}{c}_j{x}^j$. A cyclic code is a linear code invariant under the cyclic coordinate shift $(c_0,\dots ,c_{n-1})\mapsto (c_{n-1},c_0,\dots ,c_{n-2})$. Under this identification the shift is multiplication by $x$ modulo $x^n-1$. A shift-invariant vector subspace is closed under multiplication by every polynomial, since such multiplication is a linear combination of shifts. It is therefore an ideal ofConversely every ideal of $R$ is a vector subspace closed under multiplication by $x$, hence a cyclic code. Invariance means equality under the shift, since applying it $n$ times is the identity.

Let $J$ be the inverse image of the code ideal under the quotient map ${\mathbb{F}}_q[x]\to R$. It contains $(x^n-1)$ and is nonzero. Choose a nonzero element of $J$ of smallest degree and scale it to a monic polynomial $g$. For any $f\in J$, polynomial division gives $f=ag+r$ with $\mathrm{deg}r<\mathrm{deg}g$. Since $r=f-ag\in J$, minimality forces $r=0$. Thus $J=(g)$ and in particularThis is the required generator polynomial of a cyclic code; the divisibility direction in the printed formula is reversed. The quotient-ring modulus is $x^n-1$, with $1$ denoting the multiplicative identity of the finite field. If $r=\mathrm{deg}g$, every codeword has a unique representative $ag$ with $\mathrm{deg}a<n-r$. Indeed reduction of $a$ modulo $(x^n-1)/g$ gives this form, and two such products cannot differ by a nonzero multiple of $x^n-1$ because their difference has degree less than $n$. ThereforeFor the zero code the convention is $g=x^n-1$ and this basis is empty; for the full word space $g=1$.

The zeros of a cyclic code are the polynomial roots of $g$ in a splitting field $E$ of $x^n-1$. Suppose first that the characteristic $p$ of ${\mathbb{F}}_q$ does not divide $n$. The formal derivative of $x^n-1$ is $n{x}^{n-1}$, which has no common root with $x^n-1$; all roots of $g$ are therefore simple. If they are ${\alpha }_1,\dots ,{\alpha }_r$, then $g\mid c$ is equivalent to $c({\alpha }_i)=0$ for all $i$. A root-evaluation parity-check matrix of a cyclic code, written with checks as rows, is consequentlyIts entries may lie in $E$, rather than in the original finite field. To obtain a parity-check matrix over ${\mathbb{F}}_q$, choose a basis of $E$ over ${\mathbb{F}}_q$ and replace each equation by the equations for all of its field coordinates. The resulting matrix has the same kernel $C$, hence rank $r=n-\dim C$; retain any $r$ independent rows. More economically, choose one root from each Frobenius conjugate orbit. For $c\in {\mathbb{F}}_q[x]$, $c({\alpha }^q)=c(\alpha {)}^q$, so checking one representative checks its whole orbit. Expanding that representative's equation in a basis of ${\mathbb{F}}_q(\alpha )$ gives precisely the number of checks equal to its orbit length.

No coprimality hypothesis is stated in the question, so the repeated-root cyclic code case must also be distinguished. Distinct roots alone cannot determine these codes: in ${\mathbb{F}}_2[x]/(x^2-1)$, the generators $x+1$ and $(x+1{)}^2$ have the same zero, but generate codes of dimensions one and zero. In general write $g={\prod }_i(x-{\alpha }_i{)}^{m_i}$ in $E[x]$. The correct checks areusing Hasse derivatives. Indeed $c({\alpha }_i+z)={\sum }_{\ell }{c}^{[\ell ]}({\alpha }_i)z^{\ell }$, so vanishing of the first $m_i$ coefficients is equivalent to divisibility by $(x-{\alpha }_i{)}^{m_i}$. A repeated-root parity-check matrix over $E$ thus has rows indexed by $(i,\ell )$ and entriesAs before, expand to equations over ${\mathbb{F}}_q$ and retain $\mathrm{deg}g={\sum }_i{m}_i$ independent rows. The ordinary root-evaluation matrix is exactly the special case $m_i=1$.

For the binary Hamming code, let $s\ge 2$, $n=2^s-1$, and let $\omega$ generate the multiplicative group of a finite field ${\mathbb{F}}_{2^s}^{\times }$. This is possible because that group is a cyclic group. Choose a basis of ${\mathbb{F}}_{2^s}$ over ${\mathbb{F}}_2$. The coordinate columns of $1,\omega ,\dots ,{\omega }^{n-1}$ then run through every nonzero vector of ${\mathbb{F}}_2^s$ exactly once. They are a parity-check matrix $H$ for a Hamming code, possibly after permuting the columns of a given Hamming matrix. Thusis equivalent to the Hamming code. Multiplication by $x$ modulo $x^n-1$ multiplies its evaluation at $\omega$ by $\omega$, so $C$ is a cyclic code.

The parity-check matrix has rank $s$ because its columns contain a basis. It has no zero column or repeated column, so no nonzero word of weight one or two is in its kernel. Two distinct nonzero columns have a nonzero sum, which is a third distinct column; these three columns give a word of weight three. Hence $C$ has parameters $[2^s-1,2^s-s-1,3]$.

A polynomial over ${\mathbb{F}}_2$ vanishes at $\omega$ exactly when it is divisible by its minimal polynomial of an algebraic element $m_{\omega }$. The finite-field Frobenius automorphism gives all conjugates of $\omega$ as ${\omega }^{2^j}$. Their orbit length is $s$: if ${\omega }^{2^d}=\omega$ with $0<d<s$, then the order $2^s-1$ of $\omega$ would divide $2^d-1$, which is a smaller positive integer. Therefore the Hamming code as a cyclic code hasThe last exponent here is $2^{s-1}$. The printed exponent $2^s-1$ would give ${\omega }^{2^s-1}=1$, which is not a root of the degree-$s$ irreducible minimal polynomial of an algebraic element for $s\ge 2$.

A cyclic binary code is a linear subspace of ${\mathbb{F}}_2^n$ invariant under cyclic shifts. Identify a word with its coefficient polynomial in ${\mathbb{F}}_2[X]/(X^n-1)$. Multiplication by $X$ is the shift, so the code is precisely an ideal of that quotient ring. Its inverse image in the polynomial ring is a principal ideal $(g)$ containing $(X^n-1)$; its unique monic generator divides $X^n-1$. Conversely each monic divisor generates such an ideal. Thus the bijection is with monic divisors; $g=1$ gives the full code and $g=X^n-1$ the zero code.

For odd $n$, some $m$ has $n\mid 2^m-1$, so the cyclic multiplicative group of ${\mathbb{F}}_{2^m}$ contains a primitive $n$th root $\alpha$. If a nonzero word with the specified roots had weight $w<\delta$, write its nonzero positions as $r_1,\dots ,r_w$. The root equations giveTheir matrix has determinant ${\prod }_j{\alpha }^{r_j}{\prod }_{j<l}({\alpha }^{r_l}-{\alpha }^{r_j})\ne 0$, by the Vandermonde formula and distinctness of the positions. Thus all coefficients would vanish, a contradiction. Hence minimum distance is at least $\delta$.

For $n=7$, choose $\alpha$ with minimal polynomial $X^3+X+1$. The roots $\alpha ,{\alpha }^2$ force also the conjugate ${\alpha }^4$, giving this cubic as generator. Its degree gives dimension four and its weight gives distance exactly three. Expressing $c(\alpha )=0$ in a basis of ${\mathbb{F}}_8$ gives a parity-check matrix with the seven distinct nonzero vectors of ${\mathbb{F}}_2^3$ as columns. This is the binary $[7,4,3]$ Hamming code. Its sixteen disjoint radius-one balls have $16(1+7)=128$ words, so one-error correction is perfect. The other primitive cubic produces an equivalent coordinate-permuted code.

Use binary codes, so the polynomial modulus is $f(X)=X^N+1=X^N-1$ in ${\mathbb{F}}_2[X]$. A cyclic code $C$ is a linear subspace of ${\mathbb{F}}_2^N$ invariant under the cyclic shift $(a_0,\dots ,a_{N-1})\mapsto (a_{N-1},a_0,\dots ,a_{N-2})$. Identify a word with $a(X)={\sum }_{i=0}^{N-1}{a}_i{X}^i$. Addition is coefficientwise, and multiplication is polynomial multiplication reduced modulo $f$. In the quotient ringmultiplication by $X$ is exactly that cyclic shift. Closure under this map and linear combinations gives closure under multiplication by every polynomial, so a cyclic code is an ideal of $R$. Conversely, an ideal is a linear subspace closed under multiplication by $X$, proving the correspondence.

Take the inverse image of $C$ in ${\mathbb{F}}_2[X]$. This is an ideal containing $(f)$. The polynomial division algorithm shows directly that it has a unique monic generator $g$: choose a nonzero polynomial of least polynomial degree and divide any other member by it; the remainder is in the ideal and has smaller polynomial degree, so must vanish. If two monic generators existed, mutual divisibility would make them equal. Because $f$ belongs to the ideal, $g\mid f$. Conversely every monic divisor of $f$ defines an ideal of $R$. Thus the generator polynomial of a cyclic code satisfiesFor a nonzero code, $g$ is its nonzero polynomial representative of least polynomial degree. For the zero code, use $g=f$, whose residue in $R$ is zero; this standard convention covers that endpoint despite its having no nonzero codeword.

Let $r=\mathrm{deg}g$ and $k=N-r$, and put $h=f/g$. Every codeword has a unique representation $bg$ with $\mathrm{deg}b<k$: dividing an arbitrary multiplier by $h$ does not change its product with $g$ modulo $f$. The words $g,Xg,\dots ,X^{k-1}g$ have distinct leading degrees below $N$ and are independent. ConsequentlyThe statement remains valid for the zero code, with an empty basis, and the full code, with $g=1$.

For length 16, characteristic two gives $X^{16}+1=(X+1{)}^{16}$. Its only monic divisors are $(X+1{)}^j$ for $0\le j\le 16$. Hence all binary cyclic codes of length a power of two in this case areThere are exactly 17 codes, forming the chain $C_{16}\subset C_{15}\subset \cdots \subset C_0$. This is a repeated-root cyclic code situation, so it would be incorrect to count just square-free factors. Their canonical check polynomials of a cyclic code are $(X+1{)}^{16-j}$. An explicit expansion of each generator is ${\prod }_{b:\text{bit }b\text{ of }j\text{ is }1}(1+X^{2^b})$.

The canonical check polynomial of a cyclic code isIndeed $ah\equiv 0(\mathrm{mod}f)$ means $f\mid ah$. Since $f=gh$, cancellation in the polynomial ring gives $g\mid a$, exactly code membership. No coprimality of $g$ and $h$ is needed, including for length 16.

There is a normalization qualification in the printed definition. The kernel condition alone does not force the supplied polynomial $\tilde{h}$ to equal this canonical $h$. If $d=\gcd (f,\tilde{h})$, write $f=d{f}_1$ and $\tilde{h}=d{h}_1$ with $\gcd (f_1,h_1)=1$. Then $f\mid a\tilde{h}$ holds exactly when $f_1\mid a$, so its kernel is the ideal generated by $f/d$. ThereforeEquivalently $\tilde{h}=hu$ with $\gcd (u,g)=1$. Requiring the monic divisor of $f$ selects the canonical check polynomial of a cyclic code. For example $Xh$ gives the same kernel as $h$, since $X$ is a unit modulo $f$, but is generally a different polynomial. Given any permitted $\tilde{h}$, taking $\gcd (f,\tilde{h})$ recovers the canonical $h$.

To construct a parity-check matrix, write the canonical $h={\sum }_{l=0}^k{h}_l{X}^l$ and its reciprocal polynomial $h^{\ast }(X)=X^{k}h(X^{-1})$. Take coefficient vectors, padded to length $N$, ofas the $r$ rows of $H$. Here $h_0=1$ because $h\mid f$, so these rows have successive leading degrees $k,k+1,\dots ,N-1$ and are independent. For a word $a$, row $j$ has dot product ${\sum }_{l=0}^k{h}_{k-l}{a}_{j+l}$, the coefficient of $X^{k+j}$ in the ordinary product $ah$. If $a\in C$, then $ah=bf$ with $\mathrm{deg}b<k$. This product has no terms in degrees $k,\dots ,N-1$, so $H{a}^T=0$. The kernel of $H$ has dimension $N-r=k$, the same as $C$, proving $\ker H=C$. This proves the reciprocal-polynomial parity-check matrix construction and identifies its rows as a basis for the dual of a cyclic code.

Alternatively, a supplied check polynomial of a cyclic code reduced modulo $f$, $\tilde{h}={\sum }_{l=0}^{N-1}{\tilde{h}}_l{X}^l$, gives the polynomial multiplication parity-check matrixThis circulant matrix represents multiplication by $\tilde{h}$ modulo $f$, so its kernel is $C$ and its matrix rank is $r$. Selecting independent rows yields a rank-$r$ parity-check matrix even without initially normalizing the supplied polynomial.

The syndrome $s(y)=H{y}^T$ labels the coset $C+y$. Indeed $s(y)=s(z)$ if and only if $H(y-z{)}^T=0$, equivalently $y-z\in C$. There are $2^r$ cosets, each with $2^k$ words, and the syndrome classification of code cosets gives a bijection between them and ${\mathbb{F}}_2^r$. If $y=c+e$ is a transmitted codeword plus an error, then $s(y)=s(e)$: the syndrome determines the error coset. Choosing a minimum-weight coset leader and subtracting it performs minimum-distance decoding. The error itself need not be uniquely identified, but it is unique when its weight is at most $\lfloor (d-1)/2\rfloor$, since the corresponding error-correction balls are disjoint.