\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{multicol}
\usepackage{latexsym}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\def\zero{\multicolumn{1}{>{\columncolor{white}}c}{0}}
\def\colCell#1#2{\multicolumn{1}{>{\columncolor{#1}}c}{#2}}

\input{preamble.tex}

\begin{document}
\homework{2: More Error-Correcting Codes}{Due Friday, Week 2}

Do \textbf{three} of the \textbf{six} problems below!   Prove all of your claims.  
\begin{enumerate}
\item Here's a fun problem from a UCSB Ph.D. student\footnote{Todd Ebert, 1998.  The silly framing is me.} from their dissertation:
\begin{quest}
You and two friends have been captured by eeeeevil logicians!  They tell you ahead of time about the following puzzle they have for you:\
\begin{itemize}
\item You will all be led into a locked room.
\item Each person will have a hat placed on their head; hats are either black or white, and randomly decided for each person by flipping a fair coin.  
\item No one can see their own hat.
\item Each person can see other people's hats.
\item You and your friends cannot communicate once in the room.  
\item When the guards say so, you and your friends must all either guess the color of their own hat, or say ``pass.''
\item If at least one person guesses correctly and no one is incorrect, you're free!
\item If anyone guesses incorrectly, you are sad/eaten by bears.
\end{itemize}

Find a strategy that insures that on average, you are not eaten by bears three-quarters of the time.

\end{quest}
\item A $q$-ary length $n$ code $C$ is called \textbf{linear} if the sum of any two codewords in $C$, thought of as elements in $\left(\mathbb{Z} / q\mathbb{Z}\right)^n$, is also a codeword in $C$. 
\begin{enumerate}
\item Find a linear code.  
\item Find a nonlinear code.  
\item Is the Hamming $[7,4]$ code from problem set 1 linear?
\end{enumerate}
\item A $q$-ary length $n$ code $C$ is called \textbf{perfect} if there is some integer $t$ such that for any element $\mathbf{x} \in \left(\mathbb{Z} / q\mathbb{Z}\right)^n$, there is a unique word in $C$ within Hamming distance $t$ of $\mathbf{x}$.   
\begin{enumerate}
\item Find a perfect code
\item Find a nonperfect code.  
\item Is the Hamming $[7,4]$ code from problem set 11 perfect?
\end{enumerate}
\item A \textbf{Hadamard matrix} is the following object: a $n \times n$ matrix, with entries all $\pm1$, such that all of the columns are orthogonal\footnote{Two vectors $(a_1, a_2, \ldots a_n), (b_1, b_2, \ldots b_n)$ are called \textbf{orthogonal} if the sum $\displaystyle\sum_{k=1}^n a_kb_k$ is equal to 0.  For example $(1,-3)$ and $(6, 2)$ are a pair of orthogonal vectors.}.  For example,
\begin{align*}
\begin{bmatrix}
1 & 1 & 1 & 1\\
1 & 1 & -1 & -1\\
1 & -1 & 1 & -1\\
1 & -1 & -1 & 1\\
\end{bmatrix}
\end{align*}
is a Hadamard matrix.
\begin{enumerate}
\item For any $n = 2^k$ for some $k$, find a Hadamard matrix.
\item Take the columns of any $n \times n$ Hadamard matrix, and replace the $-1$'s with $0$'s.  This gives you a binary code, all of whose codewords are length $n$.  What is the distance of this code?  What is the information rate?  (Fun fact: we used these codes to communicate with \href{http://en.wikipedia.org/wiki/Mariner_9}{Mariner 9}, the first spacecraft to orbit another planet!)
\end{enumerate}
\item Prove that $A_q(n,d) \leq q^{n+1-d}$.
\item In class, I claimed that we can assume that the codeword $\overbrace{000\ldots0}^{n \textrm{ zeroes}}$ is in any of our codes.  Justify this claim as follows: given any base $q$, define a \textbf{Hamming-distance-preserving map} $\varphi: \left(\mathbb{Z}/q\mathbb{Z}\right)^n \to \left(\mathbb{Z}/q\mathbb{Z}\right)^n$ as any map with the following property:
\begin{itemize}
\item For any two codewords $w_1, w_2 \in \left(\mathbb{Z}/q\mathbb{Z}\right)^n$, we have that $d(w_1, w_2) = d(\varphi(w_1), \varphi(w_2))$.
\end{itemize}
\begin{enumerate}
\item For $q=2, n=4$, create a Hamming-distance-preserving map that is not the identity.
\item Prove that any Hamming-distance-preserving map is a bijection.
\item For any code $C$, let $\varphi(C)$ denote the code given by $\{\varphi(w) ~|~ w \in C\}$.  Prove that if $C$ is a code with $d(C) = k$, then $d(\varphi(C))$ is equal to $k$ as well.
\item Show that for any code $C$, there is a Hamming-distance-preserving map $\varphi$ that sends one codeword of $C$ to the all-zero codeword $\overbrace{000\ldots0}^{n \textrm{ zeroes}}$.
\end{enumerate}
\end{enumerate}


\end{document}