\documentclass[a4paper,12pt]{article}
%\usepackage{claire}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[francais]{babel}
\usepackage{amsmath,amssymb,calc,graphicx,ifthen,fullpage,pst-all,url}
%\usepackage{euler,palatino}

\setlength{\oddsidemargin}{0pt} \setlength{\evensidemargin}{0pt}
\setlength{\marginparwidth}{0pt} \setlength{\marginparpush}{0pt}
\setlength{\topmargin}{0pt} \setlength{\headheight}{0pt}
\setlength{\headsep}{0pt} \setlength{\textheight}{29.7cm-2.5in}
\setlength{\textwidth}{21cm-2in} \setlength{\footskip}{.75in}

\newcount\BoldMath
\BoldMath=0
\DeclareMathAlphabet{\matheu}{U}{eus}{m}{n}
\SetMathAlphabet{\matheu}{bold}{U}{eus}{b}{n}
\newcommand{\R}{\ifcase\BoldMath\ensuremath{\mathbb{R}}\or%
\ensuremath{\pmb{\mathbb{R}}}\fi}%
\newcommand{\C}{\ifcase\BoldMath\ensuremath{\mathbb{C}}\or%
\ensuremath{\pmb{\mathbb{C}}}\fi}%
\newcommand{\N}{\ifcase\BoldMath\ensuremath{\mathbb{N}}\or%
\ensuremath{\pmb{\mathbb{N}}}\fi}%
\newcommand{\Z}{\ifcase\BoldMath\ensuremath{\mathbb{Z}}\or%
\ensuremath{\pmb{\mathbb{Z}}}\fi}%
\newcommand{\Q}{\ifcase\BoldMath\ensuremath{\mathbb{Q}}\or%
\ensuremath{\pmb{\mathbb{Q}}}\fi}%
% Mon \F est pour \F_2
\newcommand{\F}{\ifcase\BoldMath\ensuremath{\mathbb{F}}\or%
\ensuremath{\pmb{\mathbb{F}}}\fi}%
\newcommand{\ie}{c'est-à-dire}
%
% Le joli F est pour l'espace des fonctions
\newcommand{\varF}{\ensuremath{\matheu{F}}}
%
% Pour des jolies bases
\newcommand{\B}{\ensuremath{\matheu{B}}}
%
\hoffset=-0.3cm
%\voffset=-2.3cm
%\topmargin=0cm
%\oddsidemargin=0cm
%\evensidemargin=0cm
%\marginparsep=0pt
%\marginparwidth=0pt
%\marginparpush=0pt
\textwidth=460pt
%\textheight=700pt
%\footskip=14pt
%
\title{\textsc{\bfseries codes correcteurs d'erreurs}}
\author{Samuel \textsc{Thibault}}
\date{}
%
\begin{document}
\addtocounter{page}{-1}
%
%
%
\maketitle

\tableofcontents

\thispagestyle{empty}
\newpage
%
%
%
\par
Lorsque la sonde Mariner 9 transmit en 1971 la première
cartographie de Mars à la Terre par ondes radio, il fallut
résoudre le problème des parasites qui brouillent toute
transmission à longue distance. La solution fut de ne pas envoyer
les images brutes, mais transformées de façon à ce qu'une certaine
redondance permette de corriger quelques bits erronés. On utilisa
alors les codes de \textsc{\textsc{Reed-Muller}} d'ordre 1 dont le
décodage est facilité par la transformation d'\textsc{Hadamard}.
%
%
%
%
%
%
\section{Transformation d'\textsc{Hadamard}}
%
%
%
%
\subsection{Présentation}
%
% Présentation de F_2^m
%
On utilise le corps à deux éléments $\F_2=\{0,1\}$, et l'espace
vectoriel des mots binaires ${\F_2}^m$, totalement ordonné par
l'ordre lexicographique. On posera, pour
$\omega=(\omega_1,...\,,\omega_m)$ et
$\tau=(\tau_1,...\,,\tau_m)$,
\[
< \omega, \ \tau> \ = \sum_{k=1}^m \omega_k \tau_k \in \F_2 \ .
\]
%pour $\omega=(\omega_1,...\,,\omega_m)$ et
%$\tau=(\tau_1,...\,,\tau_m)$.

\par

%
%
On note $\varF(m) = \varF({\F_2}^m,\C)$, qui a pour base
$\B = \left( \varphi_\omega:
\begin{matrix}
{\F_2}^m & \rightarrow & \C \\
\omega & \mapsto & 1\\
\tau \neq \omega & \mapsto & 0
\end{matrix}
\right) $,
%\varphi_\omega)_{\omega \in {\F_2}^m}$ où
%$\varphi_\omega(\tau)=
%\left\{
%\begin{array}{cc}
%1\text{ si }\tau=\omega\\
%0\text{ si }\tau\neq\omega
%\end{array}
%\right.$
 et qui est donc de dimension $2^m$.

\par\medskip

On pose alors pour $f\in\varF(m)$, $\tau\in{\F_2}^m$,
\[
h_{2^m}(f)(\tau) = \sum_{\omega\in{\F_2}^m}
{(-1)}^{<{}\omega,\tau>{}} f(\omega) \ .
\]
\par
On remarque que $h_{2^m} \circ h_{2^m} = 2^m Id$, $h_{2^m}$ est donc un
opérateur linéaire bijectif sur $\varF(m)$ qui ressemble à une transformation de
Fourier discrète.

$h_{2^m}(f)$ est appelée la {\bfseries transformée
d'\textsc{Hadamard}} de f.
%
%
\subsection{Calcul rapide}
%
%
\par
A priori, le nombre d'additions de nombres complexes effectuées
pour calculer la transformée d'\textsc{Hadamard} d'une fonction
$f\in\varF(m)$ est en $O(2^{2m})$.
%
\par
Cependant, en notant $H_{2^m}$ la matrice de $h_{2^m}$ dans la
base $\B$, on peut remarquer que
\[H_2 =
\begin{pmatrix}
1& 1\\
1&-1
\end{pmatrix},\
H_4 =
\begin{pmatrix}
1& 1& 1& 1\\
1&-1& 1&-1\\
1& 1&-1&-1\\
1&-1&-1& 1
\end{pmatrix} =
\begin{pmatrix}
H_2& H_2\\
H_2&-H_2
\end{pmatrix} \ , \]
et plus généralement, $H_{2^{m+1} =
\begin{pmatrix}
H_{2^m}& H_{2^m}\\
H_{2^m}&-H_{2^m}
\end{pmatrix}}$,
soit $H_{2^{m+1}}=H_2 \otimes H_{2^m}$ où $\otimes$ est le
produit de Kronecker.
%
%
\par
Ainsi, le calcul de $H_{2^{m+1}}$ est ramené au calcul de
$H_{2^m}$.


\subsection{Algorithme}


On utilise un tableau pour représenter la matrice d'une fonction
f de $\varF(m)$ dans la base $\B$, l'algorithme est alors
récursif sur les indices de tableaux :
\par
\begin{verbatim}
let hadamard f=
  let g=copy_vect f in
  let rec hadam j n=
    for k=0 to n-1 do
      let aux=g.(j+k) in
      g.(j+ k )<-aux + g.(j+k+n);
      g.(j+k+n)<-aux - g.(j+k+n)
    done;
    if n>=2 then (
      hadam   j   (n/2);
      hadam (j+n) (n/2)
    ) in
  hadam 0 (vect_length f / 2);
  g;;
\end{verbatim}
%
%
\par
En notant $c(i)$ le nombre d'additions et de soustractions de
complexes effectuées lors de l'appel à \texttt{hadam} avec
$n=2^i$, on a $c(0)=2$, et $c(i)=2 \times 2^i+2 \times c(i-1)$ si
$i\geq1$,
\begin{gather*}
\frac{c(i)}{2^i}=2+\frac{c(i-1)}{2^{i-1}}\\ \frac{c(i)}{2^i}=(i+1)
\times 2\text{, aussi vrai pour $i=0$.}
\end{gather*}
Le nombre d'additions et de soustractions de complexes est donc $m
\times 2^m$.
%
%
\section{Codes correcteurs}
%
%
\subsection{Définition}
%
%
\par
Un {\bfseries code} C de longueur m et de dimension k est simplement un
sous-espace vectoriel de ${\F_2}^m$ de dimension k, qui peut donc être
caractérisé comme image d'un morphisme injectif de ${\F_2}^k$ dans ${\F_2}^m$
(une {\bfseries application d'encodage}) ou
comme noyau d'un morphisme surjectif de ${\F_2}^m$ dans ${\F_2}^{m-k}$
(une {\bfseries application de contrôle}).
Ses éléments sont appelés les {\bfseries mots du code}.
%
%
\subsection{Distance minimale}
%
%
\par
On note $d(\omega,\omega') = \text{card} \{i / \omega_i \neq
{\omega'}_i \}$, qui est appelée {\bfseries distance de
\textsc{Hamming}} entre $\omega$ et $\omega'$. On note également
$d(\omega,C) = \inf \{ d(\omega,\tau),\ \tau\in C\}$.
\par
On note
$d_C = \inf \{ d(\tau,\tau'),\ (\tau,\tau') \in C^2,\ \tau \neq \tau' \}$
qui est appelée {\bfseries distance minimale} de C.
On a toujours $d_C \leq n-k+1$.
%
%
\subsection{Pouvoir correcteur}
%
%
\par
Plus la distance minimale de C est grande, plus ses mots sont éloignés les uns
des autres, \ie\ que la famille des boules centrées en les mots de C de rayon
r a tendance à \^etre d'intersection vide.
\par
Plus précisément, soit $t = \lfloor\frac{d-1}{2}\rfloor$ :
si $d(\omega,C) \leq t$,
on est sûr que $\omega$ est dans une seule des boules centrées
en les mots de C de rayon t\ :
\begin{center}
\begin{pspicture}(2,2)
\rput(0.5,0.5){$\omega$}
\pscircle(0.5,0.5){0.5}
\rput(1.5,0.5){$\omega'$}
\pscircle(1.5,0.5){0.5}
\rput(0.9,0.6){$\tau$}
\rput(1,1.5){$\omega''$}
\pscircle(1,1.5){0.5}
\end{pspicture}
\end{center}
\par
On dit alors que {\bfseries C corrige t erreur(s)}.
%
%
\section{Codes de \textsc{Reed-Muller} d'ordre 1}
%
%
\subsection{Codage}
%
%
\par
On considère l'espace vectoriel E des polynômes à m variables, de degré
total au plus 1, à coefficients dans $\F_2$.
\par
E étant isomorphe à ${\F_2}^{m+1}$, on notera $u=u_0 + u_1 X_1 +
... + u_m X_m = (u_0,..., u_m) \in E$.
\par
Soit $\psi : \begin{matrix}
E&\rightarrow&{\F_2}^{2^m}\\
u&\mapsto    &{(u(\omega))}_{\omega\in{\F_2}^m}
\end{matrix}$ morphisme injectif,
on prend $C = \text{Im }\psi$.
C est donc de longueur $2^m$, de dimension m+1.
De plus, on a $d_C=2^{m-1}$, $t=2^{m-2}-1$.
%
%
\subsection{Décodage}
%
%
\par
Soit $f \in {\F_2}^{2^m}$, $f={(f_\omega)}_{\omega\in{\F_2}^m}$.
Il faut trouver $u=(u_0,u_1,...,u_m)\in{\F_2}^{m+1}$ tel que
$d(\psi(u),f)$ soit minimale. Posons déjà $\tau=(u_1,...,u_m)$ et
\begin{gather*}
g_0(\tau)=\psi(  \sum_{i=1}^m u_i X_i),\\
g_1(\tau)=\psi(1+\sum_{i=1}^m u_i X_i) \ .
\end{gather*}
\par
En posant $F(\omega)={(-1)}^{f_\omega}$,
\[h_{2^m}(F)(\tau) = \sum_{\omega \in {F_2}^m}{(-1)}^{<\omega,\tau>-f_\omega}\]
est alors la différence entre le nombre de fois où
\[<\omega,\ \tau>-f_\omega=\sum_{i=1}^m \tau_i \omega_i-f_\omega
                        ={g_0(\tau)}_\omega - f_\omega\]
est nul (noté $N_Z$) et le nombre de fois où il est égal à 1 (qui est $d(g_0(\tau),f)$).

\par\smallskip

On a donc $h_{2^m}(F)(\tau)=N_Z-d(g_0(\tau),f)$, or
$N_Z+d(g_0(\tau),f)=2^m$, d'où
\[d(g_0(\tau),f) = \frac{1}{2} (2^m-h_{2^m}(F)(\tau)) \ .\]
\par
De m\^eme, on obtient
\[d(g_1(\tau),f) = \frac{1}{2} (2^m+h_{2^m}(F)(\tau)) \ .\]
\par
Il suffit donc de trouver $\tau\in{\F_2}^m$ tel que
$\big|h_{2^m}(F)(\tau)\big|$ soit maximal.
\par
Ensuite, si $h_{2^m}(F)(\tau)< 0$, il faut choisir $g_1(\tau)$, \ie\ prendre $u_0=1$.
Sinon, $g_0(\tau)$ convient, \ie\ $u_0=0$.
%
%
\subsection{Algorithme}
%
%
%
L'algorithme est alors très simple :
\begin{itemize}
\item calculer \texttt{F}, à l'aide d'une fonction
\texttt{F\_of\_f} ;
\item calculer sa transformée d'\textsc{Hadamard} \texttt{h2mF} ;
\item chercher l'indice \texttt{i} de l'élément du tableau \texttt{h2mF} de valeur absolue maximale (\texttt{cherche\_max})
et le convertir en sa représentation binaire, en laissant une case
supplémentaire (\texttt{vect\_of\_int}) ;
\item si l'élément ainsi trouvé est négatif, mettre un \texttt{1} dans la case supplémentaire.
\end{itemize}

\begin{verbatim}
let decode f=
  let F=F_of_f f in
  let h2mF=hadamard F in
  let i=cherche_max h2mF
  and m=lg (vect_length h2mF) in
  let u=vect_of_int2 i m in
  if h2mF.(i)<0 then u.(0)<-1;
  u;;
\end{verbatim}
%
\par
La complexité de cet algorithme est donc ramenée à celle du calcul
de la transformée d'\textsc{Hadamard} de F, \ie{} $O(m \times
2^m)$, ce qui est largement mieux qu'avec une méthode brutale,
dont la complexité serait en $O(2^m \times 2^m)$.
%
%
\section{Application}
%
%
Historiquement, les codes correcteurs de \textsc{Reed-Muller} ont
été utilisés pour envoyer des images en 64 niveaux de gris à
travers
l'espace. %, \ie\ $m=5$. On a alors $d=2^{5-1}=16$, $t=2^{5-2}-1=7$,
Dans cette situation $m=5$, et on a alors $d=2^{5-1}=16$,
$t=2^{5-2}-1=7$ ; donc si au plus 7 bits de chaque mot de code
transmis sont altérés, la réception est parfaite. Cependant, il se
peut que ces erreurs se regroupent, le pire étant le cas des
trains de parasites (causés par des éruptions solaires, par
exemple), qui peuvent altérer des mots de codes entiers.
\par
Le codage et le décodage ont été réalisés par des circuits
spécialisés, qui ont donc d\^u effectuer un nombre d'opérations de
l'ordre de $5 \times 2^5 = 160$ par pixel, à comparer, dans le cas
du circuit récepteur, avec $2^{10} = 1024$ : la transformée
d'\textsc{Hadamard} rapide apporte un gain de vitesse appréciable
!
\par
%On trouvera en annexe une simulation de l'effet d'un bruit
%gaussien de 20\% sur la transmission d'une des images de Mars :
%l'image originale, puis celle qui aurait été reçue en utilisant
%une transmission brute, et enfin celle que l'on obtiendrait en
%utilisant le code de \textsc{Reed-Muller}.

On trouvera en annexe B une simulation de l'effet d'un bruit
gaussien de 20\% sur la transmission d'une des images de Mars
(page 7). Soit le bruit est appliqué directement à l'image
originale, ce qui nous donne l'image de la page 8 (transmission
brute) ; soit il est appliqué à l'image encodée, ce qui donne
après décodage l'image de la page 9 (transmission codée).

%puis celle qui aurait été reçue en utilisant une transmission
%brute (B.2), et enfin celle que l'on obtiendrait en utilisant le
%code de \textsc{Reed-Muller}.

%On trouvera à l'annexe B un exemple concret d'application :
%partant d'une image originale (B.1), on applique un bruit gaussien
%de 20\%, ce qui simule une transmission brute de l'image par la
%sonde martienne (B.2). En B.3, on trouve l'image qui aurait été
%reçue en utilisant une transmission encodée selon la méthode de
%\textsc{Reed-Muller} (\ie  l'image est encodée, puis émise par la sonde ;
%la transmission subit également  ).

%
%
\section{Conclusion}
%
%
\par
La difficulté majeure dans l'implémentation de codes correcteurs d'erreurs
réside dans le
décodage, car la complexité d'un algorithme na\"\i f est alors
souvent au moins quadratique.
\par
Une analyse mathématique du problème conduit alors parfois à une
méthode plus rapide, ici sous la forme de la transformée
d'\textsc{Hadamard} rapide, qui est de complexité
semi-logarithmique. Ce sont de telles situations où l'Informatique
est aidée par les Mathématiques.
%
%
%
\newpage

\appendix

\section{Bibliographie}

\urlstyle{sf}
\begin{itemize}
\item
   \textit{Principe de la détection et de la correction des erreurs}\\
   \url{http://www.ireste.fr/~jdiouris/setra/telecom/antennesadaptatives/comdea/com.59.htm}
\item
   Pascal \textsc{Nicolas}, \textit{Détection et correction d'erreurs}, 2000\\
   \url{http://www.info.univ-angers.fr/pub/pn/poly/node13.html}

\item
   Bill \textsc{Cherowitzo}, \textit{Coding Theory I}\\
   \url{http://www-math.cudenver.edu/~wcherowi/courses/m5410/m5410cd1.html}

\item
   Alexandre \textsc{Masselot},
   \textit{Série d'analyse pour informaticiens Code de \textsc{Reed-Muller} et pratique},
   1995\\
   \url{http://cui.unige.ch/~masselot/analyse-info/mars/fiction/fiction.html}

\item
   Ben \textsc{Cooke}, \textit{\textsc{Reed-Muller} Error Correcting Codes},
   MIT Undergraduate Journal of Mathematics

\item
   \textit{Mariner 9},
   NSSDC Master Catalog : Spacecraft,
   2000\\
   \url{http://nssdc.gsfc.nasa.gov/nmc/tmp/1971-051A.html}

\item
   James L. \textsc{Massey},
   \textit{Deep-Space Communications and Coding : A Marriage Made in Heaven}\\
   \url{http://www.isi.ee.ethz.ch/publications/massey_cd/pdf/Bl321.pdf}

\item
   Jean-Pierre \textsc{Zanotti}, \textit{Le code correcteur C.I.R.C.}\\
   \url{http://www.univ-tln.fr/~zanotti/enseignement/divers/chapter3.html}

\end{itemize}

\newpage

\

%\begin{center}
%\includegraphics[angle=90,bb=0 0 720 510]{mars10d.bmp}
%\end{center}

\newpage

\

\newpage

\ 

\end{document}
