= Solution
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,\ldots,a_{N-1})\mapsto(a_{N-1},a_0,\ldots,a_{N-2})$. Identify a word with $a(X)=\sum_{i=0}^{N-1}a_iX^i$. Addition is coefficientwise, and multiplication is <polynomial> multiplication reduced modulo $f$. In the <quotient ring>
$$
R=\mathbb F_2[X]/(f),
$$
multiplication 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> satisfies
$$
\boxed{C=(g)\subseteq R,\qquad g\mid X^N+1.}
$$
For 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=\deg g$ and $k=N-r$, and put $h=f/g$. Every <codeword> has a unique representation $bg$ with $\deg b<k$: dividing an arbitrary multiplier by $h$ does not change its product with $g$ modulo $f$. The words $g,Xg,\ldots,X^{k-1}g$ have distinct leading degrees below $N$ and are independent. Consequently
$$
\boxed{\dim C=N-\deg g=k.}
$$
The 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\le16$. Hence all <binary cyclic codes of length a power of two> in this case are
$$
\boxed{C_j=((X+1)^j),\qquad\dim C_j=16-j,\qquad0\le j\le16.}
$$
There 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> is
$$
\boxed{h(X)=\frac{X^N+1}{g(X)},\qquad g(X)h(X)=X^N+1.}
$$
Indeed $ah\equiv0\pmod 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> $\widetilde h$ to equal this canonical $h$. If $d=\gcd(f,\widetilde h)$, write $f=df_1$ and $\widetilde h=dh_1$ with $\gcd(f_1,h_1)=1$. Then $f\mid a\widetilde h$ holds exactly when $f_1\mid a$, so its <kernel> is the <ideal> generated by $f/d$. Therefore
$$
\boxed{\ker(a\mapsto a\widetilde h\bmod f)=C\quad\Longleftrightarrow\quad\gcd(f,\widetilde h)=f/g.}
$$
Equivalently $\widetilde h=h u$ 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 $\widetilde h$, taking $\gcd(f,\widetilde h)$ recovers the canonical $h$.
To construct a <parity-check matrix>, write the canonical $h=\sum_{l=0}^k h_lX^l$ and its <reciprocal polynomial> $h^*(X)=X^kh(X^{-1})$. Take coefficient vectors, padded to length $N$, of
$$
\boxed{h^*,\ Xh^*,\ldots,X^{r-1}h^*}
$$
as the $r$ rows of $H$. Here $h_0=1$ because $h\mid f$, so these rows have successive leading degrees $k,k+1,\ldots,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 $\deg b<k$. This product has no terms in degrees $k,\ldots,N-1$, so $Ha^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$, $\widetilde h=\sum_{l=0}^{N-1}\widetilde h_lX^l$, gives the <polynomial multiplication parity-check matrix>
$$
B_{ti}=\widetilde h_{\,t-i\bmod N}\qquad(0\le t,i<N).
$$
This circulant matrix represents multiplication by $\widetilde 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)=Hy^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, so
$$
\boxed{g_{\mathrm{rep}}(X)=1+X+\cdots+X^{N-1},\qquad h_{\mathrm{rep}}(X)=X+1.}
$$
Their 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$. Thus
$$
\boxed{g_{\mathrm{par}}(X)=X+1,\qquad h_{\mathrm{par}}(X)=1+X+\cdots+X^{N-1}.}
$$
Its <dimension> is $N-1$; it is the even-weight code.
Finally, factor the binary length-seven modulus:
$$
X^7+1=(X+1)(X^3+X+1)(X^3+X^2+1).
$$
A standard cyclic realization of the <Hamming code of length seven> uses
$$
\boxed{g(X)=X^3+X+1,\qquad h(X)=(X+1)(X^3+X^2+1)=X^4+X^2+X+1.}
$$
Its <dimension> is four. The reciprocal-check construction gives
$$
H=\begin{pmatrix}1&0&1&1&1&0&0\\0&1&0&1&1&1&0\\0&0&1&0&1&1&1\end{pmatrix}.
$$
Its 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 choice
$$
\boxed{g(X)=X^3+X^2+1,\qquad h(X)=X^4+X^3+X^2+1.}
$$
The <polynomial> answer therefore depends on the cyclic coordinate convention, while the resulting codes are equivalent.
Back to article page
