@ccueil Colles

Source LaTeX icone Codes-Correcteurs-erreurs



Fichier
Type: TP
File type: Latex, tex (source)
Télécharger le document pdf compilé pdficon
Description
TP sur les codes correcteurs d'erreurs
Niveau
Post-bac
Table des matières
  • Découpage en bloc du message
  • Code de parité
  • Code de Hamming (7,4,3)
  • Caractéristique des codes correcteurs
    • Matrices génératrice et de contrôle
    • Distance et pouvoir correcteur
    • Codage d'un message
    • Syndrôme: détection et correction
Mots clé
codes correcteurs, transmission numérique, détection dapos;erreurs, correction des erreurs
Voir aussi:

Documentation sur LaTeX
pdficon
Source LaTex icone
Télécharger le fichier source pdficon

\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'intresse  la mise en \oe uvre de codes correcteurs
d'erreurs. 

Comme nous l'avons vu au cours des TP prcdents, s'il est possible de
rduire notablement le taux d'erreurs lors de la transmission
numrique d'un message, ce dernier n'est en gnral, et malgr tous
les efforts fournis, jamais nul. 

Des erreurs persistent toujours dans la transmission, causes par
exemple par des interfrences, une altration du support de
l'information, des rayonnements parasites \dots. 

\vsp
L'objectif de la thorie des codes correcteurs d'erreurs est de
protger l'information transmise de ces ventuelles altrations. 

\vspd
L'objectif de ce TP est, en complment des prcdents permettant de
gnrer des messages binaires, de les convertir en un signal numrique
adapt au canal de transmission porteur de l'information, puis de les
dcoder de manire adapte pour {\it tenter} de retrouver le message
de dpart, 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 linaires en bloc. 

\vsp
La mise en place de ces codes devrait ainsi aboutir  une
communication fiable du message sur un canal de transmission rel. 



\section{Dcoupage en blocs du message}

Ecrire une fonction Matlab {\it bloc} permettant de dcouper 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 dtection et 
la localisation du bloc contenant l'erreur. 

\vspt
Gnrer un message binaire be $n$ bits, $n$ tant un multiple de $7$. 

Dcouper ensuite ce message par blocs de 7 bits, puis,  chacun des
blocs, ajouter le bit de parit adquat. 

\vspd
On rappelle que la matrice gnratrice 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 contrle est: 
\[ H=\lb 1\ \ 1\ \ 1\ \ 1\ \ 1\ \ 1\ \ 1\ \ 1\  \rb
\]

\vspd
Utiliser ensuite l'ensemble de la chane de transmission: codage en
ligne (type polaire NRZ par exemple), transmission dans un canal rel,
rception et dcodage (utiliser le filtrage adapt \dots). 

\vspd
Aprs avoir dcoup le message reu par bloc de $8$ bits, 
dterminer le nombre d'erreurs et les localiser. 


\vspt
Eventuellement, les blocs errons peuvent-tre retransmis, jusqu' ce
qu'il ne subsiste plus aucune erreur \dots\, du moins dtectable par un
code de parit. 


\section{Code de Hamming $(7,4,3)$}

Au contraire du code prcdent, un code de Hamming permet la dtection
\ul{et} la localisation, donc la correction, d'une erreur par bloc. 

\vsp
Il n'est pas donc pas toujours ncessaire d'emettre une requte de
renvoie lors de la rception d'un bloc erron. 

\paragraph{Matrice de contrle $H$.}
On peut former la matrice de contrle $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 gnratrice $G$.} La matrice gnratrice 
associe  la matrice de contrle $H$ est alors la matrice $G$ donne
ci-dessous (le vrifier !) : 

\[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 gnratrice $G$ n'est pas sous sa forme systmatique. 
La mthode du pivot de Gauss permet, si on le souhaite, d'y remdier
(attention, la matrice de contrle $H$ doit aussi tre modifie 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.} 
  Gnrer 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 gnratrice $G$ du code de Hamming suivant le
  produit matriciel (attention toutes les oprations 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 crer un vecteur d'erreurs apparaissant avec une
  probabilit donne: 
  il s'agit d'un vecteur binaire dont la proportion de 1 est la
  probabilit d'erreur choisie. 

  \vspd
  Gnrer 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 Dtection et correction des erreurs.} 
  La dtection d'une erreur se fait par bloc (de 7 bits maintenant),
  et est base sur le calcul du syndrme. 

  Pour chaque bloc $b$ de 7 bits, on calcule le syndrme $s$  l'aide
  la matrice de contrle $H$ : 
  \[ s = H\,b^T
  \]

  \vspd
  \bgit
  \item[a)] Si le syndrme est nul, il n'y a pas d'erreur dans le bloc (ou
    ventuellement plus de deux erreurs)

    \vspd
  \item[b)] Si le syndrme $s$ est non nul, alors $s$ est une colonne
    de la matrice $H$. Le numro de la colonne donne la position de
    l'erreur. 

    \vspd
    L'intrt tout particulier de la forme de la matrice de contrle
    $H$, justement sous forme non systmatique, est que la
    $j^{\mbox{\scz{me}}}$ colonne de $H$ est l'expression du nombre
    $j$ en base $2$. 

    Ainsi, le syndrme $s$ est exactement la position de l'erreur
    exprim en base $2$. 
  \enit

  \vspt
  Pour chaque bloc, calculer le syndrme associ, et le corriger si
  besoin est.

  \vspq
  \item[5)]{\bf Dcodage du message.} 
    Reconstruire alors le message complet, en ne slectionnant
    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
    numrique dans un canal rel.} 
    
    \vspq
    Reprendre l'tude prcdente complte du code de Hamming, en
    utlisant cette fois un canal rel de transmission: 

    \vspd
    \bgit
    \item[a)] gnration 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  caratristiques relles
    \vspd
      (gain, puissance du bruit, et bande passante)
    \vspd
    \item[e)] rception et filtrage (adapt !) du signal
    \vspd
    \item[f)] chantillonnage, et dcision sur le signal reu
    \vspd
    \item[g)] correction d'ventuelles erreurs par bloc 4), 
    \vspd
    \item[h)] dcodage du code de Hamming 5). 
    \enit
\enit


\end{document}

Haut de la page Haut de la page