\magnification=\magstep1
\centerline{Mathematics 392 -- Seminar in Coding Theory}
\centerline{Midterm Problem Set}
\centerline{\it February 20, 2002}
\bigskip
\noindent
{\it Ground Rules}
\bigskip
The problems below  
form the midterm problem set announced in the course syllabus.
This is an open book, open notes, open Swords 335 assignment.
You must work {\it independently} on these problems, and you
may not consult with other faculty members or students.  You may 
consult other sources in the library, on the Internet, etc.
but if you find something relevant there, please {\it footnote
it}.  When you have finished your solutions, please write
out a short statement that you have abided by these ground
rules, sign it, and return it with your solutions.
\bigskip
\noindent
This assignment is due no later than {\it 5:00pm on Wednesday, 
February 27}.
\bigskip
\noindent
I.  
\item{A)}  Show that if a binary code of length $n = 8$ can correct
any single error then it contains at most 28 different words.
\bigskip
\item{B)}  Is it possible for a binary code $C$ (not necessarily linear)
to contain two words $u$ and $v$ (among others) such that if $u$ is 
transmitted, then any error of weight at most 2 can be corrected, 
while if $v$ is transmitted, then there is some error of weight 1 
that cannot be corrected?  If so give an example; if not say why not.
\bigskip
\noindent
II.  Two additional code constructions.  Let $C$ be an $(n,k,d)$ 
binary linear code.  
\bigskip
\item{A)} We say the code $C'$ is obtained by 
{\it puncturing $C$ at location $i$} if the words of $C'$ are constructed
by deleting the $i$th locations in all the words of $C$.  Show that 
$C'$ is also linear with parameters $(n',k',d')$ satisfying 
$n' = n - 1$, $k - 1 \le k' \le k$, and $d - 1\le d' \le d$.  
Show by examples that both of these values for $k',d'$ are
possible.
\bigskip 
\item{B)}  We say the code $C''$ is obtained by {\it shortening $C$
at location $i$} if the words of $C''$ are constructed by deleting
the $i$th locations in all words in $C$ {\it that have a 0 in location $i$}.
Show that $C''$ is also linear and discuss its possible parameters
$(n'',k'',d'')$.  Show by example that $d'' > d$ is possible.
\bigskip
\noindent
III.
\item{A)}  Let $C$ be the linear code with $n = 8, k = 4$ and
the $4 \times 8$ generator matrix:
$$G = \pmatrix{1&0&0&0&1&1&0&0\cr
               0&1&0&0&1&1&1&1\cr
               0&0&1&0&1&1&1&0\cr
               0&0&0&1&1&0&1&1\cr}$$
Construct the SDA for this code, and use
it to decode the received words $y = 11110111$, $y = 00100010$.
\bigskip
\noindent
IV.  The minimum distance of the code in III is $d = 3$.  Can you 
do better with $n = 8$, $k = 4$?  For instance, are there 
$(8,4,4)$ binary linear codes?  If so construct one; if not say why not.
(Hint:  You can specify a code by giving a parity check matrix. 
What has to be true about $H$ to get $d = 4, 5$, etc.)
\bigskip
\noindent
V.  Let $C$ be the linear code with parity check matrix
$$H = \pmatrix{1&1&1\cr 1&1&0\cr 1&0&1\cr 0&1&1\cr 1&0&0 \cr 0&1&0\cr 0&0&1\cr}$$
The rows of $H$ are all the nonzero words of length 3, listed
in a particular order.  $n = 7$, and $k = 4$ for this code.
\bigskip
\item{A)}  What is the minimum distance of $C$ and what does
this say about error-correcting capacity of $C$?  
\bigskip
\item{B)}  We want next to understand a very interesting
feature of this example.  Show that every coset of this code
has a {\it unique} coset leader of weight 0 or 1, and that 
that the Hamming ball of radius 1 centered at
each codeword of $C$ contains exactly one vector from each of the cosets 
of $C$.   (Don't work too hard!)  Note:  what you are proving here 
shows that {\it every received
word\/} would be decoded to some codeword by syndrome decoding -- there 
are no cases where the SDA contains more than one
possible error vector of smallest weight in a coset. 
\bigskip
\item{C)}  For which combinations of a blocklength $n$ and dimension
$k$ is it possible for a binary linear code to have the property from part 
B (that is:  the Hamming ball of radius 1 centered at
each codeword contains exactly one vector from each of the cosets of $C$).
\bye