Skip to main content
Contents Embed Dark Mode Prev Up Next \(\require{mathtools} \setcounter{MaxMatrixCols}{15}
\newcommand{\N}{\mathbb N}
\newcommand{\Z}{\mathbb Z}
\newcommand{\Q}{\mathbb Q}
\newcommand{\R}{\mathbb R}
\newcommand{\cC}{\mathcal{C}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\GF}{\mathrm{GF}}
\DeclareMathOperator{\Span}{Span}
\DeclareMathOperator{\rank}{rank}
\DeclareMathOperator{\rk}{rk}
\DeclareMathOperator{\wt}{wt}
\DeclareMathOperator{\im}{im}
\makeatletter
\@ifundefined{char}{
\DeclareMathOperator{\char}{char}
}{}
\makeatother
\DeclareMathOperator{\GRS}{GRS}
\DeclareMathOperator{\RS}{RS}
\DeclareMathOperator{\BCH}{BCH}
\newcommand{\transpose}[1]{#1^{\top}}
\newcommand{\by}{\mathbf{y}}
\newcommand{\bc}{\mathbf{c}}
\newcommand{\bx}{\mathbf{x}}
\newcommand{\bm}{\mathbf{m}}
\newcommand{\bs}{\mathbf{s}}
\newcommand{\be}{\mathbf{e}}
\newcommand{\bu}{\mathbf{u}}
\newcommand{\bv}{\mathbf{v}}
\newcommand{\bh}{\mathbf{h}}
\newcommand{\br}{\mathbf{r}}
\newcommand{\bzero}{\mathbf{0}}
\newcommand{\balpha}{\boldsymbol{\alpha}}
\renewcommand{\vec}[1]{\boldsymbol{#1}}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\newcommand{\fillinmath}[1]{\mathchoice{\underline{\displaystyle \phantom{\ \,#1\ \,}}}{\underline{\textstyle \phantom{\ \,#1\ \,}}}{\underline{\scriptstyle \phantom{\ \,#1\ \,}}}{\underline{\scriptscriptstyle\phantom{\ \,#1\ \,}}}}
\)
Worksheet Cyclic Codes
Today we will learn the fundamental theorem of cyclic codes and put it into practice to find examples of cyclic codes and compute their generator and check polynomials.
Theorem 92 . Fundamental Theorem of Cyclic Codes.
Let \(C \neq \{\bzero\}\) be a cyclic code of length \(n\) over \(F=\GF(q)\text{.}\) Then
There is a unique monic polynomial \(g(x)\) of minimal degree in \(C\) and it generates \(C\text{:}\)
\begin{equation*}
C= \{ q(x)g(x) \mid q(x) \in F[x]_{n-r}\}\text{,}
\end{equation*}
where \(r=\deg(g(x))\text{.}\) In particular, \(C\) has dimension \(n-r\text{.}\) We call \(g(x)\) the generator polynomial for \(C\text{.}\)
The polynomial \(g(x)\) divides \(x^n-1\) in \(F[x]\) and the polynomial \(h(x)\) such that \(g(x)h(x)=x^n-1\) is called the check polynomial for \(C\text{.}\) It satisfies
\begin{equation*}
C=\{c(x) \in F[x]_n \mid c(x)h(x) = 0 \pmod{x^n-1}\}\text{.}
\end{equation*}
Conversely, every code of the form
\begin{equation*}
C=\{q(x)g(x) \mid q(x) \in F[x]_{n-r}\}
\end{equation*}
where \(r=\deg(g(x))\) and \(g(x)\) is a monic divisor of \(x^n-1\) in \(F[x]\) is a cyclic code.
We formally define
\(x^n-1\) to be the generator polynomial for the zero code
\(\{\bzero\}\text{.}\)
1. Factor
\(x^7-1\) into irreducible polynomials over
\(\GF(2)\text{.}\)
Solution .
\(x^7-1=(x+1)(x^3+x+1)(x^3+x^2+1)\)
2. How many binary cyclic codes of length
\(7\) are there?
Solution .
There are 8: one for each of the
\(2^3\) monic polynomials we can form as factors of
\(x^7-1\) from the previous exercise.
3. For each of the binary cyclic codes of length
\(7\text{,}\) determine the dimension. Identify the generator polynomials which correspond to the length
\(7\) parity check code and repetition code, which we saw are cyclic.
Solution .
This has degree
\(0\) so we get a
\([7,7]\) code, i.e. all of
\(\F_2^7\text{.}\)
This has degree
\(1\) so we get a
\([7,6]\) code. It must be the parity code, as the parity code is cyclic and this code is the only code in this list with dimension 6.
This has degree
\(3\) so we get a
\([7,4]\) code.
This has degree
\(3\) so we get a
\([7,4]\) code.
\((x+1)(x^3+x+1)=x^4+x^3+x^2+1\)
This has degree
\(4\) so we get a
\([7,3]\) code.
\((x+1)(x^3+x^2+1)=x^4+x^2+x+1\)
This has degree
\(4\) so we get a
\([7,3]\) code.
\((x^3+x+1)(x^3+x^2+1)=x^6+x^5+x^4+x^3+x^2+x+1\)
This has degree
\(6\) so we get a
\([7,1]\) code. It must be the repetition code, as the repetition code is cyclic and this code is the only code in this list with dimension 1.
\((x+1)(x^3+x+1)(x^3+x+1)=x^7-1\)
This has degree
\(7\) so we get a
\([7,0]\) code, i.e. the zero code.
4. Give the check polynomial for each binary cyclic code of length
\(7\text{.}\)
Solution .
These pair up as generator/check polynomial pairs.
\((x+1)\) and
\((x^3+x^2+1)(x^3+x+1)\)
\((x^3+x+1)\) and
\((x+1)(x^3+x^2+1)\)
\((x^3+x^2+1)\) and
\((x+1)(x^3+x+1)\)
5. Give the cyclic generator matrix for the binary cyclic code of length
\(7\) with
\(g(x)=x^3+x+1\text{.}\)
Solution .
\begin{equation*}
G = \begin{bmatrix}
1 \amp 1 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0\\
0 \amp 1 \amp 1 \amp 0 \amp 1 \amp 0 \amp 0\\
0 \amp 0 \amp 1 \amp 1 \amp 0 \amp 1 \amp 0\\
0 \amp 0 \amp 0 \amp 1 \amp 1 \amp 0 \amp 1
\end{bmatrix}
\end{equation*}
6.
Let \(h(x)\) be the check polynomial of this code. The reciprocal polynomial of a polynomial \(\sum_{i=0}^d p_i x^i\) is
\begin{equation*}
p^{[-1]}(x)=\sum_{i=0}^d p_{d-i} x^i = x^d p(x^{-1})\text{.}
\end{equation*}
Compute \(h^{[-1]}(x)\text{.}\)
Solution .
\(h^{[-1]}(x)=1+x^2+x^3+x^4\)
7.
Show that
\begin{equation*}
H=\begin{bmatrix}
h_k \amp h_{k-1} \amp \dots \amp h_0 \amp 0 \amp \dots \amp 0 \\
0 \amp h_k \amp h_{k-1} \amp \dots \amp h_0 \amp \dots \amp 0 \\
0 \amp 0 \amp \ddots \amp \ddots \amp \ddots \amp \dots \amp \vdots \\
0 \amp \dots \amp 0 \amp h_k \amp h_{k-1} \amp \dots \amp h_0 \\
\end{bmatrix}
\end{equation*}
is a parity check matrix for the cyclic code with generator \(g(x)\) by showing that the product of a row of the associated generator matrix \(G\) with a row of \(H\) is a zero coefficient in \(g(x)h(x)=x^{n}-1\text{.}\)
Solution .
This product of row \(0\leq i \leq k-1\) of \(G\) and row \(0\leq\ell\leq n-k-1\) of \(H\) is
\begin{equation*}
\sum_{j=0}^{n-1} g_{j-i}h_{k+\ell-j}
\end{equation*}
which is exactly the coefficient of \(x^{k+\ell-i}\) in \(g(x)h(x)=x^n-1\text{.}\) As we also have \(1\leq k+\ell-i \leq n-1\) this is zero.
8. Conclude from the previous two problems that the dual of a cyclic
\([n,k]_q\) code is a
\([n,n-k]_q\) cyclic code and give a generator polynomial (be sure your generator is monic).
Solution .
The matrix \(H\) from the last problem has the form of a cyclic generator except that it is not monic. So we have
\begin{equation*}
g^{\perp}(x)=\frac{1}{h_0} h^{[-1]}(x)=\frac{x^k h(x^{-1})}{h(0)}
\end{equation*}
9. Write the matrix
\(H\) for the binary cyclic code of length
\(7\) with generator
\(g(x)=x^3+x+1\text{.}\) Conclude that
\(C\) is a Hamming code.
Solution .
\begin{equation*}
H=\begin{bmatrix}
1 \amp 0 \amp 1 \amp 1 \amp 1 \amp 0 \amp 0 \\
0 \amp 1 \amp 0 \amp 1 \amp 1 \amp 1 \amp 0 \\
0 \amp 0 \amp 1 \amp 0 \amp 1 \amp 1 \amp 1
\end{bmatrix}\text{.}
\end{equation*}
This matrix has as columns a representative of every one dimensional subspace of \(\F_2^7\text{,}\) so it is a Hamming code.
