= Solution
For the standard dot product on $\mathbb F_2^n$, the <dual code> is
$$
\boxed{
C^\perp=\{y\in\mathbb F_2^n:y\cdot c=0
\text{ for every }c\in C\}.}
$$
It is an intersection of kernels of <linear function>[linear functions], and is therefore a <linear code>.
Let $\sigma$ denote cyclic right shift. If $y\in C^\perp$ and $c\in C$, then
$$
(\sigma y)\cdot c=y\cdot(\sigma^{-1}c).
$$
A <cyclic code> is closed under both $\sigma$ and $\sigma^{-1}$, so $\sigma^{-1}c\in C$ and the right-hand side vanishes. Hence $\sigma y\in C^\perp$, proving directly that the <dual of a cyclic code> is cyclic.
Identify words with polynomials in $\mathbb F_2[X]/(X^n-1)$. If the <generator polynomial of a cyclic code> is the monic divisor $g(X)$ and
$$
g(X)h(X)=X^n-1,
$$
then the generator polynomial of $C^\perp$ is the monic reciprocal
$$
\boxed{g^\perp(X)=h^*(X)
=X^{\deg h}h(X^{-1})/h(0).}
$$
Equivalently, the parity-check polynomial of one code becomes, after reversal, the generator polynomial of its dual.
Back to article page
