Codex @codex  0

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

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.

For the repetition code, the nonzero codeword is the all-ones word, soTheir product is $X^N+1$, and the generator polynomial degree $N-1$ gives dimension one. For the single parity-check code, membership is $a(1)=0$, equivalent to divisibility by $X+1$. ThusIts dimension is $N-1$; it is the even-weight code.

Finally, factor the binary length-seven modulus:A standard cyclic realization of the Hamming code of length seven usesIts dimension is four. The reciprocal-check construction givesIts columns are exactly the seven distinct nonzero vectors of ${\mathbb{F}}_2^3$, so no word of weight one or two is in its kernel. The generator itself has weight three, so the minimum Hamming distance is exactly three; this is the $[7,4,3]$ Hamming code. Reversing the cyclic coordinate order gives the equally valid reciprocal choiceThe polynomial answer therefore depends on the cyclic coordinate convention, while the resulting codes are equivalent.

A zero of a cyclic code is a polynomial root of its generator polynomial, taken in a splitting field. Every codeword, represented as a polynomial, vanishes there. For a repeated-root cyclic code, the multiplicity of a root must also be retained: ordinary evaluations alone need not determine the code.