\documentclass{article}
\newcommand{\cC}{\mathcal{C}}
\newcommand{\FF}{\mathbb{F}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\cH}{\mathcal{H}}
\newcommand{\spn}{\mathrm{span}}
\newcommand{\Vol}{\mathrm{Vol}}
\usepackage{fullpage,graphicx}
\usepackage{amsmath,amsfonts,amsthm,amssymb,multirow}
\usepackage{algorithmic,comment,url,enumerate}
\newtheorem{definition}{Definition}
\usepackage{tikz}
\usepackage{framed}
\usepackage{enumitem}
\setenumerate[1]{label=\thesection.\arabic*.}
\usetikzlibrary{decorations.pathreplacing, shapes}
\usepackage[ruled,vlined,commentsnumbered,titlenotnumbered]{algorithm2e}
\definecolor{shadecolor}{gray}{0.95}



\begin{document}
\noindent CS250/EE387: Error Correcting Codes \hfill  Winter 2025\\
\textbf{Problem Set 1} \\
\textbf{Due:} by 11:59pm Friday, January 17 2025, on Gradescope \\
\hrule

\begin{shaded}

\textbf{Team Members: }

\textbf{(Optional) Awesome Team Name: }

\end{shaded}


\vspace{.5cm}
\noindent \textbf{Instructions:} 
\begin{itemize}
\item Please complete all problems in Section 1.  
\item Try to complete 3 of the problems in Section 2.  You are welcome to do more than 3, but please indicate which 3 you want graded.  
\item No problems in Section 3 are required, but they might be fun to think about (some might be open-ended).  
\item Problems are labeled with the class number after which you should be able to do them.  (This is to aid your time management since all HWs are posted up front).
\end{itemize}
\noindent \textbf{Guidelines/rules:}
\begin{itemize}
\item You are encouraged to work in groups (up to 3); each group should turn in one HW assignment.
\item Please refer to the collaboration policy on the course website.  
It is fine to use computational resources like Sage or Mathematica if you want to.
\end{itemize}
Typing up your solutions in \LaTeX \ is encouraged (but I don't type up my lecture notes, so I can't be too strict).  Legibility and complete sentences are required.  
\\
\hrule

\section*{Section 1}
\setcounter{section}{1}
(Do all of these problems.)
\begin{enumerate}

\item (8 pts, Class 2) Please answer the following questions with a brief justification of your answer. Let $\cC$ be the binary linear code with generator matrix
\[ G = \begin{pmatrix} 0 & 0 & 1 \\ 0& 1& 1 \\ 1 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 0 \end{pmatrix} \]
\begin{enumerate}
	\item What is the dimension of $\cC$?

\begin{shaded}
\textbf{SOLUTION:}
Your solution here!
\end{shaded}

	\item Find a parity-check matrix for $\cC$.

\begin{shaded}
\textbf{SOLUTION:}
Your solution here!
\end{shaded}

	\item What is the distance of $\cC$?

\begin{shaded}
\textbf{SOLUTION:}
Your solution here!
\end{shaded}

	\item Find another generator matrix $G'$ for the same code $\cC$ that represents a systematic encoding; that is, so that the encoding map $x \mapsto G'x$ has the form
$(x_1,x_2,x_3) \mapsto (x_1,x_2,x_3,a,b)$ for some $a,b \in \F_2$.

\begin{shaded}
\textbf{SOLUTION:}
Your solution here!
\end{shaded}

\end{enumerate}

\item (4 pts, Class 1) Suppose that $\cC$ is a code of length $n$ and distance $d$.  Consider a noise model that has both errors and erasures: that is, when a codeword $c \in \Sigma^n$ is transmitted, the recieved word $y \in (\Sigma \cup \{\bot\})^n$ has
\[ y_i \in \Sigma \setminus \{ c_i \} \] 
for at most $e$ positions $i$, and $y_i = \bot$ for at most $s$ positions $i$.  Show that as long as $2e + s < d$, then $c$ can be determined from $y$.
(Above, the symbol $\bot$ is a place-holder symbol not in $\Sigma$, which corresponds to ``erasure.")

\begin{shaded}
\textbf{SOLUTION:}
Your solution here!
\end{shaded}

\end{enumerate}
\section*{Section 2}
\setcounter{section}{2}
Section 2 problems are worth 10 points each; please do at least 3 of them.  

\vspace{.5cm}
\noindent
\textcolor{red}{
\textbf{IMPORTANT:} In gradescope, please tag all problems you want feedback on.  However, if you tag more than 3, write ``NOT FOR GRADING!!!!'' prominently at the top of all but 3 of them.  }

\vspace{.5cm}

Some of the problems in Section 2 reference the \emph{Hamming Code} $\mathcal{H}$ which we discussed during the in-class work in Class 2.  
Recall the following definition:
\begin{definition} Let $n = 2^r - 1$ for some integer $r$.  The Hamming code $\cH_r$ of length $n$ is the code whose parity-check matrix $H_r \in \F_2^{r \times n}$ is the matrix which has every nonzero vector in $\{0,1\}^r$ as its columns.
\end{definition}

Now onto the problems.

\begin{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\item (\textbf{Fun with linear algebra over finite fields}, Class 2) 


Let $q$ be a power of a prime and $\FF_q$ be the finite field of order $q$.
In this exercise you'll rigorously prove a few statements of the flavor ``linear algebra works over finite fields."  So, for the following problems, \textbf{use only the definitions we've seen and fact that $\FF_q$ is a finite field} (that is, you may use the definitions of ``linear independent," ``subspace," and so on, and the field axioms, but do not appeal to linear algebra ``facts" that you may know).  (See the lecture notes for the list of definitions that ``we've seen.'')


Let $V \subseteq \FF_q^N$ be a subspace over $\FF_q$.  
Recall that a \textbf{basis} for $V$ is any collection of vectors $a_1,\ldots,a_n \in V$ so that the $a_i$ are linearly independent and $\spn(a_1,\ldots,a_n) = V$.
Let $\mathcal{A} = \{a_1,\ldots,a_n\}$ be a basis for~$V$.

\begin{enumerate}
\item[(a)] Prove the following useful statements about finite fields (using the field axioms):
\begin{itemize}
\item Suppose that $\alpha \in \FF_q$.  Then $\alpha \cdot 0 = 0$.
\item Suppose that $\alpha, \beta \in \FF_q$ are both nonzero.  Then $\alpha \cdot \beta \neq 0$.
\end{itemize}

\begin{shaded}
\textbf{SOLUTION:}
Your solution here!
\end{shaded}

\item[(b)]
Suppose that $b_1,\ldots,b_m \in V$ are linearly independent, with $m \leq n$.  Prove that there exists an ordering $a_1,\ldots, a_n$ of $\mathcal{A}$ so that, for all $k \in \{1,\ldots,m\}$, $\{b_1,\ldots,b_k, a_{k+1}, \ldots,a_n\}$ is a basis for $V$. (Hint: use induction on $k$; part (a) might be useful).  

\begin{shaded}
\textbf{SOLUTION:}
Your solution here!
\end{shaded}


\item[(c)] Show (using part (b)) that any two bases of $V$ must have the same cardinality.  (That is, our definition of ``dimension" makes sense).

\begin{shaded}
\textbf{SOLUTION:}

Your solution here!

\end{shaded}
\end{enumerate}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\item (\textbf{Perfect Codes}, Class 2) We say a code $\cC$ over $\F_q$ is $e$-perfect if it has distance $2e + 1$ and meets the Hamming bound: 
\[ q^{n-k} = \Vol_q( n, e ). \]

\begin{enumerate}
	\item 
Suppose that $\cC$ is a binary linear code of length $n$ and dimension $k$, with parity-check matrix $H \in \F_2^{n-k\times n}$.
Show that $\cC$ is $e$-perfect if and only if, for all $v \in \F_2^{n-k}$, there is a unique way to write $v$ as a sum of at most $e$ columns of $H$.

\begin{shaded}
\textbf{SOLUTION:}
Your solution here!
\end{shaded}


	\item Conclude that the Hamming code is the only $1$-perfect binary linear code.  (Up to permutations of codeword symbols).

\begin{shaded}
\textbf{SOLUTION:}
Your solution here!
\end{shaded}

	\item 
Suppose that $\cC \subset \F_2^n$ is $e$-perfect.  Show that the nonzero codewords in $\cC^\perp$ take on at most $e$ distinct weights.  (Recall that the \em weight \em of a vector $x \in \F_2^n$ is the number of nonzero entries).

[\textbf{Note: This one may be tricky. For partial credit you can just show this for $e=1$.}]
(\underline{Hint 1:} Try it first for $e=1$.  \underline{Hint 2:} What can you say about the code 
whose parity-check matrix has as columns all $(\leq e)$-wise sums of columns of $H$?  And, \underline{Hint 3:} Use part (a)).

\begin{shaded}
\textbf{SOLUTION:}
Your solution here!
\end{shaded}

\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\item \label{pr:lb}(\textbf{Another lower bound}, Class 2)
\begin{enumerate}
\item Show that if there exists a linear $(n,k,d)_q$ code, then there also exists a linear $(n-d,k-1,d')_q$ code for some $d' \geq \lceil d/q \rceil$. 

You may find it useful to use the following algebra fact: for any nonzero $\alpha \in \F_q$, the set $\{ \alpha \cdot x \,:\, x \in \F_q\}$ is again $\F_q$.  That is, multiplication by $\alpha$ just permutes the elements of the field. 

\underline{Hint:} Consider dropping the non-zero positions of a minimum-weight codeword from the code.

\begin{shaded}
\textbf{SOLUTION:}
Your solution here!
\end{shaded}

\item Show that if $\cC$ is a linear $(n,k,d)_q$ code, then 
\[n \geq \sum_{i=0}^{k-1} \left\lceil \frac{ d}{q^i} \right\rceil.\]

\begin{shaded}
\textbf{SOLUTION:}
Your solution here!
\end{shaded}

\item Show that the bound above can sometimes be stronger than the Hamming bound.  That is, find 
	some values for $n,k,d$ (and let $q=2$) so that the Hamming bound is satisfied but the bound above is not.
(\underline{Note:} If you do not (yet) have a very good intuition for how the volume term in the Hamming bound behaves, you could enlist a computer to find these parameters.  However, there is a small example ($n=7$), and you might learn more about how the Hamming bound behaves if you do it by hand.)


\begin{shaded}
\textbf{SOLUTION:}
Your solution here!
\end{shaded}
\end{enumerate}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\item (\textbf{Simplex Codes}, Class 2)  Let $\cC_r = \mathcal{H}_r^\perp$, where $\mathcal{H}_r$ is the binary Hamming code of length $n = 2^r - 1$.   
Notice that (by definition) a partity-check matrix for $\mathcal{H}$ is a generator matrix for $\cC_r$.  So the generator matrix for $\cC_r$ is the $n \times r$ matrix that contains every non-zero binary vector of length $r$ as a row.  Let $G \in \F_2^{n \times r}$ be this generator matrix, and let $g_i \in \F_2^r$ denote the $i$'th row of $G$.

The code $\cC_r \subseteq \F_2^n$ is called the \emph{Simplex Code} or (a slight variant of it is called) the \emph{Hadamard Code}.

\begin{enumerate}
\item What is the dimension and distance of $\cC_r$?


\begin{shaded}
\textbf{SOLUTION:}
Your solution here!
\end{shaded}

\item Suppose that $w \in \F_2^n$ and that there is some $c \in \cC_r$ so that $\Delta(w,c) < n/4$, where $\Delta$ denotes Hamming distance.  Explain (using your answer from part (a)) why there is no other codeword $c' \in \cC_r$ with $c \neq c'$ so that $\Delta(w,c') < n/4$.  Explain why this immediately suggests a straightforward algorithm for finding $c$, given $w$.  What is the running time of this algorithm, in terms of $n$?  (In big-Oh notation).

\begin{shaded}
\textbf{SOLUTION:}
Your solution here!
\end{shaded}

\item Suppose that $w \in \F_2^n$ and that there is some $c \in \cC_r$ so that $\Delta(w,c) < n/4$.  In the rest of this part, we will motivate and analyze a more interesting algorithm for finding $c$, given $w$.  
\begin{enumerate}
\item Suppose without loss of generality that the first row of the generator matrix $G$ for $\cC_r$ is the first standard basis vector $(1,0,0, \ldots, 0)$.  Call this row $g_1 \in \F_2^r$.
Let $g_i$ be any other row of $\cC_r$ (so $i \neq 1$). Explain why there is a unique row $g_j$ of $\cC_r$ so that  $g_i + g_j = g_1$.

\begin{shaded}
\textbf{SOLUTION:}
Your solution here!
\end{shaded}

\item Suppose that $g_1 = g_i + g_j$ for some $i,j$.
Let $c = Gx$ be some codeword of $\cC_r$, where $x \in \F_2^r$ is the original message.
Explain why $x_1 = c_i + c_j$.  (Recall that $g_1 = (1,0,\ldots, 0)$.

\begin{shaded}
\textbf{SOLUTION:}
Your solution here!
\end{shaded}

\item   Consider the following algorithm that is supposed to find $x_1$ (the first bit of the message), given $w$ (the corrupted codeword).
\begin{verbatim}
Given input w in F_2^n:
     votes_for_0 = 0
     if w_1 == 0:
          votes_for_0 = votes_for_0 + 1
     for each i=2,...,n:
          Let g_j be the unique row of G so that g_i + g_j = g_1  (in F_2^r)
          If w_i + w_j == 0: 
               votes_for_0 = votes_for_0 + 1. 
     If votes_for_0 > n/2:
          return "x_1 = 0"
     else return "x_1 = 1"
\end{verbatim}
What is the running time of this algorithm?  (In big-Oh notation)

\begin{shaded}
\textbf{SOLUTION:}
Your solution here!
\end{shaded}


\item Prove that the algorithm above indeed returns $x_1$.  (You will need to use the assumption that $\Delta(w,c) < n/4$).  

\underline{Hint 1:} Use part (ii).

\underline{Hint 2:} The rows of $G$ are broken up into pairs $\{g_i, g_j\}$ and the singleton $\{g_1\}$.  How many of these groups can be ``corrupted'', in the sense that they contain an index $i$ so that $w_i \neq c_i$? 

\begin{shaded}
\textbf{SOLUTION:}
Your solution here!
\end{shaded}


\item Adapt the algorithm above to recover all of $x$, given~$w$.  Your algorithm should run in time $O(n \mathrm{polylog}(n))$.

\begin{shaded}
\textbf{SOLUTION:}
Your solution here!
\end{shaded}

\end{enumerate}

\end{enumerate}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\item (\textbf{Coordinated failure}, Class 2) Consider the following $n$-player cooperative game, for $n = 2^r - 1$.   The players $1,\ldots,n$ are placed in separate rooms and are not allowed to communicate during the game.
$n$ values $x_1,\ldots,x_n \in \{0,1\}$ are drawn uniformly at random.
Player $i$ is given $\{ x_j \,:\, j \neq i \}$, (along with labels, so she knows which $x_j$ belongs to which other player), and her goal is to guess $x_i$.  Player $i$ must say ``0," ``1," or ``pass," independently of all the other players.
The players collectively lose if:
\begin{itemize}
	\item Everyone passes, \textbf{OR}
	\item Any player $i$ reports a value that is not equal to $x_i$.
\end{itemize} 
The players collectively win if they do not lose.
The players are allowed to strategize before the game begins.  
\begin{enumerate}
\item Find a strategy where the players win with probability $1 - 1/2^r$. 

\begin{shaded}
\textbf{SOLUTION:}
Your solution here!
\end{shaded}

\item Prove that your strategy is optimal. 

\begin{shaded}
\textbf{SOLUTION:}
Your solution here!
\end{shaded}

\end{enumerate}

\underline{Hint:} Try it first for $n=3$ to get some intuition.  

\underline{Hint 2:} The fact that $n = 2^r - 1$ is not an accident.

\underline{Hint 3:} The title of this problem might be a hint too.

\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Section 3}
\setcounter{section}{3}
(These problems are not required and may be open-ended.  If you try them, you can tag them in gradescope and we'll make a note of it and give you any feedback we have.)
\begin{enumerate}
	\item Hamming codes are the best (that is, with the largest size $|\cC|$) codes with distance $3$ and length $n = 2^r - 1$.  What about other values of $n$?  In particular, what is the best code you can come up with with distance $3$ and length 6? What about length 10? 16? 20?  Do you think your constructions are optimal?  What if you just need to find the best linear code with these parameters?
	\item In Section 2, you showed that all $e$-perfect linear codes have at most $e$ different possible weights of dual codewords.  Show the converse: that any code whose dual has only $e$ different nonzero weights is $e$-perfect.  What is the simplest proof you can find of this fact?	
	\item In Section 2, you showed that the Hamming code is the only $1$-perfect binary linear code. (We also saw this in class!)  We saw in class that this doesn't extend to non-linear codes.  Can you find (or interestingly characterize) \em all \em the $1$-perfect binary non-linear codes of a given length?
\end{enumerate}

\end{document}
