\magnification=\magstep1
\centerline{Mathematics 392 -- Seminar in Coding Theory}
\centerline{Discussion 4 -- Generator Polynomials of Cyclic Codes}
\centerline{March 18, 2002}
\bigskip
\noindent
{\it Background}
\bigskip
Many of the codes that have been used in applications such as the 
CD audio system are  {\it cyclic} codes because
their ``extra structure'' that
facilitates encoding and decoding.  We will
largely focus on these for the remainder of the Coding Theory
Seminar.  The most basic way to say what a cyclic code is to 
say that it is a linear code where the set of codewords is
{\it closed under cyclic permutations.}  We have seen in class
that the algebra of polynomials is very useful to describe these
codes.  This is true because if we make the digits from a 
codeword of length $n$ the coefficients of a polynomial $c(x)$ 
of degree $\le n - 1$, then the cyclic permutation is achieved
by taking the remainder of $xc(x)$ on division by $x^n + 1$.

The {\it generator polynomial} $g(x)$ of a cyclic code $C$ is the nonzero
polynomial of minimal degree corresponding to a codeword.  We have seen
the following key facts about generator polynomials:
\bigskip
\item{$\bullet$}  If $c(x)$ is any codeword polynomial of $C$,
then $g(x)|c(x)$. 
\item{$\bullet$}  $\deg(g) = n - k$, and the polynomials in 
$\{g(x),xg(x),\ldots,x^{k-1}g(x)\}$ form a basis for $C$.
\item{$\bullet$}  $g(x)|(x^n + 1)$, where $n$ is the blocklength.
\bigskip
\noindent
Today we want to see how generator polynomials
for cyclic codes can be used to work with these codes and consider
how {\it all} cyclic codes of a given blocklength might be determined.
\bigskip
\noindent
{\it Discussion Questions}
\bigskip
\item{A)}  Verify that the linear code $C = \langle 11000,01111,11110,01010 \rangle$
is cylic, and find the generator polynomial $g(x)$.
\bigskip
\item{B)} In general, given a spanning set $S$ for a linear code, how could 
you determine (in an economical way!) whether the code is cyclic.  State and prove
a criterion for when this is true.  Hint: The cyclic permutation $\pi$
is a linear mapping.
\bigskip
\item{C)}  If you know a generator polynomial for a cyclic code $C$, how can
you write down a generator matrix for $C$ {\it with no extra work}?  
\bigskip
\item{D)}  Since the generator polynomial for a cyclic code of blocklength
$n$ must be a divisor of $x^n + 1$, if we know the complete {\it factorization}
of $x^n + 1$ in $K[x]$, then we can determine all the cyclic codes for that $n$.
Verify that 
$$x^7 + 1 = (x + 1)(x^6 + x^5 + x^4 + x^3 + x^2 + x + 1) = (x+1)(x^3+x+1)(x^3+x^2+1)$$
Each of the factors in the last product is {\it irreducible} -- it cannot be
factored farther into factors of positive degree.  Using this information,
determine how many cyclic codes of length $n = 7$ there are, and give
the generator polynomial and dimension for each.
\bigskip
\item{E)}  Determine how many cyclic codes of length $n = 12$ there are, and give
the generator polynomial and dimension for each.  Hint:  Look at theorem
4.4.3 and Corollary 4.4.4 in the text.
\bigskip
\noindent
{\it Assignment}
\bigskip
Group writeups due in class on Monday, March 25.
\bye