\documentclass[11pt,a4paper]{article}
\usepackage{etex}
\usepackage[euler,utf8x]{preambuleTrm}
\usepackage{geometry}
\geometry{papersize={21cm,29.7cm}}
\geometry{margin=1cm,top=1.5cm,bottom=2cm}

\usepackage{textcomp}
\usepackage{ mathtools,xlop,longtable}

\hypersetup{
pdftitle={TD codes linéaires}, pdfauthor ={ Guillaume CONNAN}}


\title{ Codes correcteurs d'erreurs: travaux dirigés
}

\author{ Mathématiques pour l'informatique - Licence II}

\date{ \today{} }


\usepackage{algo,bclogo}

\renewcommand{\algocommentfont}{\small\ttfamily\itshape}


\newcounter{definit}\newcounter{exercice}
\newcounter{theor}\newcounter{retenir}
\newcounter{remar}


\newenvironment{Definition}[1][]{%
\refstepcounter{definit}
\begin{bclogo}[ombre=true,logo=\bcbook,arrondi=0.05,couleur=green!20]{\color{blue}\bfseries\fontfamily{ugq}\selectfont    D\'efinition  \thedefinit\ : #1}}
{\end{bclogo}}



\newenvironment{Remarque}[1][]{%
\refstepcounter{remar}
\begin{bclogo}[logo=\bcnote,arrondi=0.05,couleur=white]{\color{blue}\bfseries\fontfamily{ugq}\selectfont  Remarque   \theremar\ : #1}}
{\end{bclogo}}



\newenvironment{exercice}[1][]{%
\refstepcounter{exercice}
\bigskip
\begin{bclogo}[ombre=true,logo=\bccoeur,arrondi=0.05,couleur=white]{\color{blue}\bfseries\fontfamily{ugq}\selectfont  Recherche  \theexercice\ : #1}}
{\end{bclogo}\parskip}




\newenvironment{Theoreme}[1][]{%
\refstepcounter{theor}
\begin{bclogo}[ombre=true,logo=\bctrefle,arrondi=0.05,couleur=green!20]{\color{blue}\bfseries\fontfamily{ugq}\selectfont Th\'eor\`eme
    \thetheor\ : #1}}
{\end{bclogo}}



\newenvironment{Retenir}[1][]{%
\refstepcounter{retenir}
\begin{bclogo}[logo=\bcnote,arrondi=0.05,couleur=white]{\color{blue}\bfseries\fontfamily{ugq}\selectfont    \`A retenir (\theretenir)\ : #1}}
{\end{bclogo}}


\graphicspath{{/home/moi/IUT/Figures/}{/home/moi/PREPA/IPT/2014_15/Poly/}{/home/moi/VISA_III/figures_visa/}{/home/moi/Lycee/TDmaple/2006_7/}{/home/moi/Figures/Arbres_Graphes/}{/home/moi/Figures/FigSTI/}{/home/moi/Figures/FigMaple/}{/home/moi/Photos/Maths/}{/home/moi/Photos/Tehessin/}{/home/moi/Figures/FigSTI/}{/home/moi/Figures/FigSeconde/}{/home/moi/Lycee/Informatique/XCAS/2008_9/}{/home/moi/Lycee/TDmaple/2008_9/}{/home/moi/IUT/Thierry/Conversions/}{/home/moi/Photos/informathix/}{/home/moi/Lycee/Informatique/PafAlgo/}{/home/moi/Figures/figuresAlice/}{/home/moi/Figures/FigSeconde/}{/home/moi/Biocam/robot/}{/home/moi/Biocam/CoursIni3d/}{/home/moi/Biocam/central/figures/}{/home/moi/Biocam/central/}{/home/moi/IUT/INFO2/Images/}{/home/moi/IUT/INFO2/2011_12/graphes/}{/home/moi/IUT/INFO1/CM1/}{/home/moi/Figures/figuresTS/}{/home/moi/Photos/Tehessin/}{/home/moi/Figures/FigSTI/}{/home/moi/Alice/figures3/}{/home/moi/Alice/figures3/newcourbes/}{/home/moi/Alice/figures/}{/home/moi/Figures/figuresAlice/}{/home/moi/Photos/Maths/}{/home/moi/Lycee/TS/}{/home/moi/Lycee/TS/2009_10/}{/home/moi/Figures/FigMaple/}{/home/moi/Figures/figuresTS/newcourbes/}{/home/moi/Figures/FigEspace/}{/home/moi/PROG/HASKELL/FLOAT/}} 


\begin{document}

\maketitle


\section{Quelques rappels}

On  veut transmettre  $2^r$ messages  distincts: on  les code  sur $r$  bits. On
rajoute des bits de contrôle pour vérifier que le message a été bien transmis.

Le message tient donc en fait sur $n$ bits.

Si une transformation linéaire permet de  passer du code initial de $\bbf_2^r$ au
code émis de $\bbf_2^n$, on dit que le code est linéaire.

\begin{exercice}
Par exemple, on veut transmettre des mots de 1 bit. On émet le message en le
triplant (1 est émis en 111). Le code est-il linéaire? Quelle est sa matrice $G$ de codage?
\end{exercice}


Notons $G$ la matrice du code linéaire. 

\begin{exercice}
  Il doit y avoir au moins autant de  mots codés que de mots au départ: comment
  cela se traduit-il quant au rang de $G$?
\end{exercice}


Notons $C$ la matrice de contrôle telle  que $C\cdot m_r=0$ si, et seulement si,
$m_r$ (le message reçu) est un mot de code (qui a donc été transmis sans erreur).


\begin{exercice}
  Que dire du rang de C?
\end{exercice}


On notera \textit{syndrome} la fonction associée à $s$.

On appellera matrice de décodage la  matrice $D$ telle que $x=Dy \Leftrightarrow
y = Gx$.

Par la  méthode de  la $\ell$-réduite échelonnée  de \textsc{Gau\ss  -Jordan} on
peut  déterminer $D$  et $C$:  suivez  les explications  de votre  chargé de  TD
préféré...

\begin{exercice}
  Que donne $R\times (G|m_r)$?
\end{exercice}

Notons $ε$ l'erreur commise que le message codé émis $m_c$. Alors $m_c=m_r+ε$.

\begin{exercice}
  Montrez que $s(m_r)=s(ε)$ et que l'on peut répartir les vecteurs de $\bbf_2^n$
  selon des classes d'équivalences par syndromes.

Montrez que si $u$ est un  message reçu quelconque, ${\rm classe}(u)=u+\CR$ avec
$\CR$ l'ensemble des mots codés.
\end{exercice}

Un  code  de  \textsc{Hamming}  est  un  code  tel  que  tous  les  vecteurs  de
$\bbf_2^{n-r}$, sauf le vecteur nul, apparaissent dans C.


\section{Exercices}

\begin{exercice}
  Déterminez une matrice de contrôle du code défini par la matrice génératrice:


$$G=
\left(
\begin{smallmatrix}
  1&0&0&1\\
  1&1&1&1\\
  0&1&1&0\\
  1&0&0&0\\
  0&1&0&0\\
  0&0&1&0\\
  0&0&0&1\\
\end{smallmatrix}
\right)
$$

Après contrôle d'erreur, décodez les  messages reçus suivants: 0111101, 0100110,
1010010.

Quel est le défaut de ce code?


\end{exercice}



\begin{exercice}
  Même style de questions avec:


$$
G=\left(
\begin{smallmatrix}
  1&1&0&1\\
  1&0&1&1&\\
  1&0&0&0\\
  0&1&1&1\\
  0&1&0&0\\
  0&0&1&0\\
  0&0&0&1\\
\end{smallmatrix}
\right)

$$

On reçoit 1010110, 1100110, 0100001, 0010001.

Quelle est la nature du code? Quelle est la matrice de décodage $D$?




\end{exercice}




\begin{exercice}
  Même style de questions avec:


$$
G=
\left(
\begin{smallmatrix}
1&0&0&0\\
0&1&0&0\\
1&0&1&0\\
1&1&0&1\\
0&1&1&0\\
0&0&1&1\\
0&0&0&1\\
\end{smallmatrix}
\right)

$$

On reçoit 1100101.

Quelle est la nature du code? Quelle est la matrice de décodage $D$?




\end{exercice}


\begin{exercice}
  Si $p$ est la  probabilité d'erreur sur un bit et si les  erreurs par bit sont
  indépendantes, exprimez la  probabilité en fnctin de $p$  qu'un message erroné
  devienne   un  mot   différent   du  mot   émis  lorsque   le   code  est   de
  \textsc{Hamming}.  Donnez  une valeur  approchée  pour  $p=0,1$. (On  rappelle
  que le code de \textsc{Hamming} ne corrige que les erreurs de poids 1).
\end{exercice}




\end{document}
%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
