%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% TPs Année 2000-2001
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\documentclass[12pt]{article}
\usepackage[french]{babel}
\voffset -2.8 cm 
\textwidth 17 cm
\textheight 24.7 cm
\oddsidemargin -.54 cm
\evensidemargin -1.54 cm


\usepackage{graphicx}
%\usepackage{amsmath}
%\usepackage{amsfonts}
%\usepackage{amssymb}
\usepackage[latin1]{inputenc}

\pagestyle{plain}

\begin{document}

\centerline {\Large \sc Information and coding theory}
\bigskip
\bigskip
\hrule
\bigskip
\bigskip
\centerline {\underline{\Large Exercise sheet n$^\circ$ 6}:} 
\bigskip
\bigskip



\noindent {\bf 6-1.} We define a Hamming code with the $4\times 6$ parity matrix 
$$
H=\left( \begin{tabular}{c c c c c c}
1 & 0 & 0 & 0 & 1 & $h_{1,6}$ \\
1 & 1 & 0 & 0 & 0 & $h_{2,6}$ \\
0 & 1 & 1 & 0 & 0 & $h_{3,6}$ \\
1 & 0 & 0 & 1 & 0 & $h_{4,6}$
\end{tabular} \right).
$$ 
\par
\medskip
\noindent (a) If one choses $h_{1,6}=h_{2,6}=h_{3,6}=h_{4,6}=1$,
determine the list of codewords. What is the amount of information and parity bits? How many errors does this code correct?
\par
\medskip
\noindent (b) Show that the variables $h_{1,6},h_{2,6},h_{3,6},h_{4,6}$
cannot be chosen in a way such that this code corrects a single error and detects as well (without correcting them) two errors.
\par
Help: For a minimal Hamming distance $x$ all sets of $x-1$ columns of $H$ have to be linearly independent.
\par
\bigskip

\noindent {\bf 6-2.} {\em Generator of a Hamming code.}
We call a $k \times n$ matrix $G$ with $k$ linearly independent rows (codewords) a generator of a binary code $(n,k)$. Each of the $2^k$ codewords can be thus expressed in terms of a linear combination of the rows of $G$.
\par
\medskip
\noindent (a) Determine the parity matrix of the code with the generator
$$
G_1=\left( \begin{tabular}{c c c c c}
1 & 1 & 0 & 0 & 1 \\
0 & 1 & 1 & 0 & 0 \\
0 & 1 & 0 & 1 & 1 
\end{tabular} \right).
$$ 
Which are the correction and/or detection properties of this code?
\par
\medskip
\noindent (b) The same question as (a) for the generator
$$
G_2=\left( \begin{tabular}{c c c c }
1 & 1 & 1 & 1  
\end{tabular} \right).
$$ 


\noindent {\bf 6-3.} {\em Hamming code.} 
Show that a Hamming code corrects up to $e-1$ errors and detects (but does not necessarily correct) up to $e$ errors {\em if and only if} all sets of $2e-1$ columns of the parity matrix are linearly independent.
\par
\bigskip

\noindent {\bf 6-4.} Optional. Show that the minimal distance of a Hamming code is equal to $d$ {\em if and only if} all non-zero codewords have at least $d$ bits equal to 1, and at least one of them has {\em exactly} $d$ bits equal to 1.
\par
\bigskip


\end{document}