\documentclass[11pt]{article}
\usepackage{header}
%%% Change these %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def
\title{HW 7}
\def
\due{Friday, October 14, 2016}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\maketitle
\fontsize{12}{15}
\selectfont
\section{Sundry}
Before you start your homework, write down your team. Who else did you work with on this homework? List names and email addresses. (In case of hw party, you can also just describe the group.) How did you work on this homework? Working in groups of 3-5 will earn credit for your "Sundry" grade.
Please copy the following statement and sign next to it:
\textit{I certify that all solutions are entirely in my words and that I have not looked at another student's solutions. I have credited all external sources in this write up.}
\newpage
\section{Problems}
\begin{Questions}
%%% Include questions here %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Question{\bf Error-Correcting Codes}
\begin{enumerate}
\renewcommand{\labelenumi}{(\alph{enumi})}
\item Recall from class the error-correcting code for erasure errors, which
protects against up to $k$ lost packets by sending a total of $n+k$ packets
(where $n$ is the number of packets in the original message). Often the number
of packets lost is not some fixed number $k$, but rather a
\emph{fraction}
of
the number of packets sent. Suppose we wish to protect against a fraction
$
\alpha$ of lost packets (where $0 <
\alpha < 1$). What is the total number of packets that we need
to send (as a function of $n$ and $
\alpha$)?
\item Repeat part (a) for the case of general errors.
\end{enumerate}
%
\Question
\textbf{Berlekamp-Welch for general errors}
Suppose that Hector wants to send you a length $n=3$ message, $m_0,m_1,m_2$, with the possibility for $k=1$ error. For all parts of this problem, we will work mod 11, so we can encode 11 letters as shown below:
$$
\begin{tabular}{|ccccccccccc|}
\hline
A & B & C & D & E & F & G & H & I & J & K \\
\hline
0 & 1 & 2 & 3 & 4 & 5 & 6 & 7& 8 & 9 & 10 \\
\hline
\end{tabular}
$$
Hector encodes the message by finding the degree $
\leq 2$ polynomial $P(x)$ that passes through $(0,m_0)$, $(1,m_1)$, and $(2,m_2)$, and then sends you the five packets $P(0),P(1),P(2),P(3),P(4)$ over a noisy channel. The message you receive is
$$
\text{DHACK}
\Rightarrow 3,7,0,2,10 = r_0,r_1,r_2,r_3,r_4$$
which could have up to 1 error.
\begin{enumerate}
\item First, let's locate the error, using an error-locating polynomial $E(x)$. Let $Q(x) = P(x)E(x)$. Recall that
$$Q(i) = P(i)E(i) = r_i E(i),
\quad
\text{for}
\quad 0
\leq i < n+2k$$
What is the degree of $E(x)$? What is the degree of $Q(x)$? Using the relation above, write out the form of $E(x)$ and $Q(x)$ in terms of the unknown coefficients, and then a system of equations to find both these polynomials.
\item Solve for $Q(x)$ and $E(x)$. Where is the error located?
\item Finally, what is $P(x)$? Use $P(x)$ to determine the original message that Hector wanted to send.
\textit{Hint: The message refers to a US federal agency.}
\end{enumerate}
\Question{\bf Why Work with Primes?}
In class, you learned about erasure codes and error correcting codes, and prime
numbers played a central role in both kinds of codes~--~since all calculations
were supposed to be done modulo a
\textit{prime number}
. In this problem, we
will see why this is a crucial requirement, and explore what happens if this
requirement is relaxed in a naive manner.
For this problem, assume that Alice wants to send $n$ packets to Bob, across
an ``erasure channel'' (Check detailed definition below). Let us say all calculations are
done modulo $N=12$ (note that this is
\textit{not}
a prime number).
\textbf{Erasure Channel}
: Let us say Alice sends $n+1$ packets to Bob, and Bob
receives at least $n$ of these packets intact. That is, the channel can erase at
most $1$ packet, and if it does so, Bob gets to know which packet was erased
(although he does not know the contents of the erased packet).
\begin{Parts}
\Part Suppose $n = 1$. That is, Alice wants to send only 1 packet to Bob (plus one redundant packet to compensate for erasure). Would the scheme discussed in class work with $N = 12$? What are all the possible 2-packet lists that Alice could transmit? In each case, would Bob be able to recover Alice's message in spite of a possible erasure? Would Alice or Bob face any problems because they are doing their calculations modulo $12$?
\Part Now suppose $n = 2$. That is, Alice now wants to send 2 packets to Bob (plus one redundant packet to compensate for erasure). Now, would there be any problems because $N=12$?
\Part Now let $n = 3$ (3 packets plus one additional packet
to compensate for erasure). Assume that Alice wants to encode
messages into ``systematic'' codewords (with the first few
evaluations of the polynomial being the message itself). Prove
that Alice can no longer send arbitrary messages of her liking to
Bob, by showing that it would be impossible for Alice to send the
message $(11, 6, 2)$. Find $2$ other examples of messages that
Alice cannot send to Bob.
\end{Parts}
\Question{\bf To Infinities and Beyond}
Show whether each of the following sets is finite, countably
infinite, or uncountable:
\begin{enumerate}
\item $
\N$ (the set of all natural numbers)
\item $
\Z$ (the set of all integers)
\item $
\Q$ (the set of all rational numbers, i.e., numbers that can
be expressed in the form $a/b$, where $a,b
\in
\Z$ and $b
\ne 0$)
%We can create a one-to-one function $f$ from $
\Q$ to $
\N$.
%Given $z
\in
\Q$, $f(z)$ is the number of steps walked on the two-dimensional integer lattice in
%a spiral fashion from $(0,0)$ until getting to the first point $(x, y)$ such that $z =
{x \over y}
$. See note 10 for a picture
%and a more elaborate explanation. This shows that $|
\Q|
\leq |
\N|$.
%Also, since $
\N
\subset
\Q$, $|
\N|
\leq |
\Q|$, and so $|
\N| = |
\Q|$.
\item $
\R$ (the set of all real numbers)
\item $
\mathbb{C}
$ (the set of all complex numbers)
\item $
\{
0,1
\}
^*$ (the set of all finite-length binary strings)
\item $
\{
0,1,2
\}
^*$ (the set of all finite-length ternary strings)
\item The set of all primes.
\item The set of all graphs
\end{enumerate}
\Question
\textbf{More Countability}
Given:
\begin{itemize}
\item $A$ is a countable set, non-empty set. Forall $i
\in A$, $S_i$ is an uncountable set.
\item $B$ is an uncountable set. Forall $i
\in B$, $Q_i$ is a countable set.
\end{itemize}
For each of the following, decide if the expression is
"Always Countable", "Always Uncountable", "Sometimes Countable,
Sometimes Uncountable."
For the "Always" cases, prove your claim. For the "Sometimes" case, provide
two examples -- one where the expression is countable, and one where
the expression is uncountable.
\begin{enumerate}
\item $
\cup_{i \in A}
S_i$
\item $
\cap_{i \in A}
S_i$
\item $
\cup_{i \in B}
Q_i$
\item $
\cap_{i \in B}
Q_i$
\item $A
\cap B$
\end{enumerate}
\Question
\textbf{Printing All $x$ Where $M(x)$ Halts}
Prove that it is possible to write a program $P$ which:
\begin{itemize}
\item takes as input M, a java program
\item runs forever, and prints out strings to the console
\item for every x, if M(x) halts, then P(M) eventually prints out x
\item for every x, if M(x) does NOT halt, then P(M) never prints out x
\end{itemize}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{Questions}
\end{document}