\documentclass[12pt]{amsart}
\pagestyle{empty}
\usepackage[hmargin=1in,vmargin=1in]{geometry}
\usepackage{url,  mathrsfs}
\usepackage{hyperref}
\usepackage{fancyhdr} 
\usepackage[T1]{fontenc}


\usepackage{url,  mathrsfs}
\usepackage{hyperref}
\usepackage{amsmath}
\usepackage{graphicx,  epstopdf}
\usepackage{subfig}
\usepackage{color}
\usepackage{bbm}
\usepackage{subfloat}
\usepackage[draft]{fixme}
\usepackage{bm} 
\usepackage{bbm} 
\usepackage{epigraph}
\usepackage{endnotes}
\usepackage{ifpdf}
\usepackage{array}



\usepackage{multicol}
\usepackage{multirow}
\usepackage{graphicx}
\usepackage{tikz}


\newcommand{\Q}{\mathbb{Q}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\A}{\mathbb{A}}
\renewcommand{\P}{\mathbb{P}}


\theoremstyle{definition}
\newtheorem{prob}{Problem}
\newtheorem*{def*}{Definition}




\begin{document}
 \thispagestyle{empty}

\begin{center} {\large \textbf{Math 437 -- Homework 4}} \smallskip \\ 
Due 10:15am on Thursday, February 9, 2017  \\ \ \\
 \end{center}

Please indicate any sources you used for a given problem on the solution to that problem. 
For example, if you worked with another student to get the solution to a problem, please indicate who.
You are welcome to work together in small groups, but please try the problems on your own first and write up 
your own solutions. \\ \medskip 



\begin{prob}
Let $p(x) = x^3 + x+1 \in \Z_2[x]$, as in Example 4.2 from the book.  
\begin{itemize}
\item[(a)] Give a $3\times 7$ matrix $H$ (with entries in $\Z_2$) that satisfies  
\[ \begin{pmatrix} 1 & a & a^2 \end{pmatrix} H  \ \ = \ \ \begin{pmatrix} 1 & a & a^2 & a^3 & a^4 & a^5 & a^6\end{pmatrix}   \]
in the field $\Z_2[a]/(p(a))$. \smallskip 
\item[(b)] Explain why $H$ is a parity check matrix for the BCH code resulting from the first power of $a$ in $\Z_2[a]/(p(a))$.  \smallskip 
\item[(c)] Explain why the BCH code from part (b) is a Hamming code.
\end{itemize}
\end{prob}\ \\



\begin{prob}
Let $p\in \Z_2[x]$ be a primitive polynomial of degree $n$ and take $F=\Z_2[a]/(p(a))$.  
Show that every element of $F^*$ is a root of the polynomial $f(x) = x^N-1$ where $N = 2^n-1$. 
(This implies that the minimal polynomial of any element of $F^*$ divides $x^N-1$. )
  \end{prob}\  \\





\begin{prob}
Consider the field $F = \Z_2[a]/(p(a))$ where $p(x) = x^4 + x^3 + 1\in \Z_2[x]$.
We see that $p$ is primitive by looking at the powers $a^k$ in $F$: \medskip 

\begin{center}
\begin{tabular}{c|c}
$a^k$ & rep. in $F$\\
\hline
$a^0$ & $1$ 	\\
$a^1$ & $a$	\\
$a^2$ & $a^2$	\\
$a^3$ & $a^3$	\\
\end{tabular} 
\hspace{.2in}
\begin{tabular}{c|c}
$a^k$ & rep. in $F$\\
\hline
$a^4$ & $1+a^3 	$	\\
$a^5$ & $1+ a + a^3$  	\\
$a^6$ & $1+a+ a^2+a^3$	\\
$a^7$ & $1+a+ a^2$ 	\\
\end{tabular}
\hspace{.2in}
\begin{tabular}{c|c}
$a^k$ & rep. in $F$\\
\hline
$a^8$ 	& $a+a^2 + a^3$ 	\\
$a^9 $	& $1+ a^2 $	\\
$a^{10}$ 	& $a + a^3	$	\\
$a^{11}$	& $1+a^2 + a^3	$	\\
\end{tabular}
\hspace{.2in}
\begin{tabular}{c|c}
$a^k$ & rep. in $F$\\
\hline
$a^{12}$ 	& $1+a$ 	\\
$a^{13} $	& $a+a^2		$	\\
$a^{14}$ 	& $a^2 + a^3	$	\\
$a^{15}$	& $1 	$	\\
\end{tabular}
\end{center} \medskip 



\begin{itemize} 
\item[(a)] Find the minimal polynomial of each element in $F^*$. \\
(Using that $b$ and $b^2$ have the same minimal polynomial will save on computations!) \smallskip 
\item[(b)]  For each value of $2t$, give the following data for the BCH code resulting from the first $2t$ powers of $a$ in  $F$ : 
\end{itemize} \medskip
\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline
&  \ \ $\#$ Correctable \ \	& \ \ Degree of 		 \ \	 & \ \ Linear code \ \ & \\
 \ \ $2t$ \ \ 	&  \ \  Errors 	 \ \ 	&  \ \ generator polynomial  \ \	& \ \ parameters \ \ & \ \ $\#$ Codewords \ \ \\
	\hline
2  & & & & \\ \hline	
4  & & & & \\ \hline
6  & & & & \\ \hline	
8 & & & & \\ \hline	
14 & & & & \\	\hline		
\end{tabular}
\end{center}





\end{prob}
\end{document}