Source Latex
\documentclass[12pt]{article}
%\usepackage{french}
\usepackage[french]{babel}
\usepackage{amsmath}
\usepackage[latin1]{inputenc}
\usepackage{a4wide}
\newcommand{\TITLE}{{\bf TP}: Codes correcteurs d'erreurs.}
\title{TP n$^{\circ}$ : Codes correcteurs d'erreurs.}
\author{Yoann Morel}
\date{}
%\pagestyle{headings}
\usepackage{fancyhdr}
\usepackage{lastpage}
% Raccourcis diverses:
\newcommand{\nwc}{\newcommand}
\nwc{\dsp}{\displaystyle}
\nwc{\bgit}{\begin{itemize}}\nwc{\enit}{\end{itemize}}
\nwc{\bgar}{\begin{array}}\nwc{\enar}{\end{array}}
\nwc{\bgmp}{\begin{minipage}}\nwc{\enmp}{\end{minipage}}
\nwc{\ul}{\underline}
\nwc{\ulb}[1]{\textcolor{blue}{\ul{\textcolor{black}{#1}}}}
\nwc{\ulr}[1]{\textcolor{red}{\ul{\textcolor{black}{#1}}}}
\nwc{\la}{\left\{}
\nwc{\lb}{\left[}\nwc{\rb}{\right]}
\nwc{\scz}[1]{\scriptsize#1}
\nwc{\scp}[1]{\scriptstyle#1}
\nwc{\scpp}[1]{\scriptscriptstyle#1}
\nwc{\bgsk}{\bigskip}
\nwc{\vsp}{\vspace{0.1cm}}
\nwc{\vspd}{\vspace{0.2cm}}
\nwc{\vspt}{\vspace{0.3cm}}
\nwc{\vspq}{\vspace{0.4cm}}
% Fin Raccourcis
\begin{document}
\pagestyle{fancyplain}
\setlength{\headheight}{0cm}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0.1pt}
\lhead{}\chead{}\rhead{}
\lfoot{Morel Yoann}
\cfoot{\TITLE \\ \thepage/\pageref{LastPage}}
\rfoot{Master 2}
\centerline{\Large\TITLE}
%\bgsk\bgsk
\vspace{1cm}
\centerline{\rule[2ex]{7cm}{0.1mm}}
\vspace{0.5cm}
\paragraph{\large{\bf Objectifs}:}
Ce TP s'int�resse � la mise en \oe uvre de codes correcteurs
d'erreurs.
Comme nous l'avons vu au cours des TP pr�c�dents, s'il est possible de
r�duire notablement le taux d'erreurs lors de la transmission
num�rique d'un message, ce dernier n'est en g�n�ral, et malgr� tous
les efforts fournis, jamais nul.
Des erreurs persistent toujours dans la transmission, caus�es par
exemple par des interf�rences, une alt�ration du support de
l'information, des rayonnements parasites \dots.
\vsp
L'objectif de la th�orie des codes correcteurs d'erreurs est de
prot�ger l'information transmise de ces �ventuelles alt�rations.
\vspd
L'objectif de ce TP est, en compl�ment des pr�c�dents permettant de
g�n�rer des messages binaires, de les convertir en un signal num�rique
adapt� au canal de transmission porteur de l'information, puis de les
d�coder de mani�re adapt�e pour {\it tenter} de retrouver le message
de d�part, de mettre en \oe uvre deux types de codes correcteurs
d'erreurs: un code de parit� et un code de Hamming.
Ces deux codes correcteurs sont des codes lin�aires en bloc.
\vsp
La mise en place de ces codes devrait ainsi aboutir � une
communication fiable du message sur un canal de transmission r�el.
\section{D�coupage en blocs du message}
Ecrire une fonction Matlab {\it bloc} permettant de d�couper un
message de $n$ bits en blocs de $k$ bits et retournant le
$p^{\mbox{\scz{�me}}}$ bloc.
(on pourra �ventuellement utiliser la fonction Matlab {\it reshape}).
\vspd
\noindent
{\bf Remarque.}
\parbox[t]{13.8cm}{
Pour simplifier, on pourra n'utiliser par la suite que des messages de
longueur $n$ bits, o� $n$ est un multiple de $k$.
}
\section{Code de parit�}
Nous allons mettre en \oe uvre dans cette partie un code � parit�
$(8,7,1)$.
La distance minimale de ce code est 1: il ne permet pas la correction
d'une �ventuelle erreur, mais simplement sa d�tection et
la localisation du bloc contenant l'erreur.
\vspt
G�n�rer un message binaire be $n$ bits, $n$ �tant un multiple de $7$.
D�couper ensuite ce message par blocs de 7 bits, puis, � chacun des
blocs, ajouter le bit de parit� ad�quat.
\vspd
On rappelle que la matrice g�n�ratrice d'un tel code est:
\[G = \lb \ \ I_7\ \ \bgar{c}1\\ \vdots \\1\enar\rb
=\lb\bgar{cccccccc}
1 & 0 & 0 & 0 & 0 & 0 & 0 &1\\
0 & 1 & 0 & 0 & 0 & 0 & 0 &1 \\
0 & 0 & 1 & 0 & 0 & 0 & 0 &1 \\
0 & 0 & 0 & 1 & 0 & 0 & 0 &1 \\
0 & 0 & 0 & 0 & 1 & 0 & 0 &1 \\
0 & 0 & 0 & 0 & 0 & 1 & 0 &1 \\
0 & 0 & 0 & 0 & 0 & 0 & 1 &1
\enar\rb
\]
tandis que sa matrice de contr�le est:
\[ H=\lb 1\ \ 1\ \ 1\ \ 1\ \ 1\ \ 1\ \ 1\ \ 1\ \rb
\]
\vspd
Utiliser ensuite l'ensemble de la cha�ne de transmission: codage en
ligne (type polaire NRZ par exemple), transmission dans un canal r�el,
r�ception et d�codage (utiliser le filtrage adapt� \dots).
\vspd
Apr�s avoir d�coup� le message re�u par bloc de $8$ bits,
d�terminer le nombre d'erreurs et les localiser.
\vspt
Eventuellement, les blocs erron�s peuvent-�tre retransmis, jusqu'� ce
qu'il ne subsiste plus aucune erreur \dots\, du moins d�tectable par un
code de parit�.
\section{Code de Hamming $(7,4,3)$}
Au contraire du code pr�c�dent, un code de Hamming permet la d�tection
\ul{et} la localisation, donc la correction, d'une erreur par bloc.
\vsp
Il n'est pas donc pas toujours n�cessaire d'emettre une requ�te de
r�envoie lors de la r�ception d'un bloc erron�.
\paragraph{Matrice de contr�le $H$.}
On peut former la matrice de contr�le $H$ en �crivant les entiers de
1 � 7 sous forme binaire dans chaque colonne de $H$:
\[H = \lb\bgar{ccccccc}
0 & 0 & 0 & 1 & 1 & 1 & 1 \\
0 & 1 & 1 & 0 & 0 & 1 & 1 \\
1 & 0 & 1 & 0 & 1 & 0 & 1
\enar\rb
\]
\paragraph{Matrice g�n�ratrice $G$.} La matrice g�n�ratrice
associ�e � la matrice de contr�le $H$ est alors la matrice $G$ donn�e
ci-dessous (le v�rifier !) :
\[G = \lb\bgar{ccccccc}
1 & 1 & 1 & 0 & 0 & 0 & 0 \\
1 & 0 & 0 & 1 & 1 & 0 & 0 \\
0 & 1 & 0 & 1 & 0 & 1 & 0 \\
1 & 1 & 0 & 1 & 0 & 0 & 1
\enar\rb
\]
\vspd
\noindent
{\bf Remarque.}
\parbox[t]{13.8cm}{
La matrice g�n�ratrice $G$ n'est pas sous sa forme syst�matique.
La m�thode du pivot de Gauss permet, si on le souhaite, d'y rem�dier
(attention, la matrice de contr�le $H$ doit aussi �tre modifi�e dans
ce cas).
\hspace{0.3cm}
La commande matlab {\it rref} pemret d'effectuer cette conversion.
}
\vspq\vspd
\bgit
\item[1)] {\bf Distance et pouvoir correcteur du code.}
Expliquer pourquoi la distance de ce code est de $3$.
Combien d'erreurs permet-il alors de corriger ?
\vspq
\item[2)]{\bf Codage d'un message.}
G�n�rer un message binaire de $N$ bits et l'encoder suivant le code
de Hamming.
\vspd
Chaque bloc $d$ de 4 bits (utiliser la fonction de la
$1^{\mbox{\scz{�re}}}$ partie) est cod� en un bloc de 7 bits $c$ �
l'aide de la matrice g�n�ratrice $G$ du code de Hamming suivant le
produit matriciel (attention toutes les op�rations se font sur des
nombres binaires, voir la fonction Matlab {\it mod}):
\[ c = d\,G
\]
\vspd
On peut remarquer que les bits de redondances sont
en position 1,2 et 4 dans ce bloc.
En d'autres termes, le bloc original est donn� par les
$3^{\mbox{\scz{�me}}}$,
$5^{\mbox{\scz{�me}}}$,$6^{\mbox{\scz{�me}}}$ et
$7^{\mbox{\scz{�me}}}$ bits du bloc cod�.
\vspq
\item[3)]{\bf Bruitage du message.} On pourra dans un premier temps,
simplement cr�er un vecteur d'erreurs apparaissant avec une
probabilit� donn�e:
il s'agit d'un vecteur binaire dont la proportion de 1 est la
probabilit� d'erreur choisie.
\vspd
G�n�rer un tel vecteur.
\vspd
Le message transmis et bruit� s'obtient alors en ajoutant (toujours
l'addition binaire~\dots) le message cod� au bruit.
\vspq
\item[4)]{\bf D�tection et correction des erreurs.}
La d�tection d'une erreur se fait par bloc (de 7 bits maintenant),
et est bas�e sur le calcul du syndr�me.
Pour chaque bloc $b$ de 7 bits, on calcule le syndr�me $s$ � l'aide
la matrice de contr�le $H$ :
\[ s = H\,b^T
\]
\vspd
\bgit
\item[a)] Si le syndr�me est nul, il n'y a pas d'erreur dans le bloc (ou
�ventuellement plus de deux erreurs)
\vspd
\item[b)] Si le syndr�me $s$ est non nul, alors $s$ est une colonne
de la matrice $H$. Le num�ro de la colonne donne la position de
l'erreur.
\vspd
L'int�r�t tout particulier de la forme de la matrice de contr�le
$H$, justement sous forme non syst�matique, est que la
$j^{\mbox{\scz{�me}}}$ colonne de $H$ est l'expression du nombre
$j$ en base $2$.
Ainsi, le syndr�me $s$ est exactement la position de l'erreur
exprim� en base $2$.
\enit
\vspt
Pour chaque bloc, calculer le syndr�me associ�, et le corriger si
besoin est.
\vspq
\item[5)]{\bf D�codage du message.}
Reconstruire alors le message complet, en ne s�lectionnant
que les bits d'information (oter les bits de redondance),
et comparer le taux d'erreurs introduit de la question~3), au taux
d'erreurs effectif (celui introduit en 3)).
\vspq\vspd
\item[6)]{\bf Mise en \oe uvre du code de Hamming pour la transmission
num�rique dans un canal r�el.}
\vspq
Reprendre l'�tude pr�c�dente compl�te du code de Hamming, en
utlisant cette fois un canal r�el de transmission:
\vspd
\bgit
\item[a)] g�n�ration d'un message binaire,
\vspd
\item[b)] encodage suivant le code de Hamming 2),
\vspd
\item[c)] codage en ligne du message (en polaire NRZ par exemple),
\vspd
\item[d)] transmission dans un canal � carat�ristiques r�elles
\vspd
(gain, puissance du bruit, et bande passante)
\vspd
\item[e)] r�ception et filtrage (adapt� !) du signal
\vspd
\item[f)] �chantillonnage, et d�cision sur le signal re�u
\vspd
\item[g)] correction d'�ventuelles erreurs par bloc 4),
\vspd
\item[h)] d�codage du code de Hamming 5).
\enit
\enit
\end{document}
Télécharger le fichier source 
