\documentclass[a4paper,12pt]{article} %\usepackage{claire} \usepackage{amsmath,amssymb,ifthen} \usepackage{french,fullpage,pst-all,url} \usepackage{euler,palatino} \catcode`\à=\active \def à{\`a} \catcode`\â=\active \def â{\^a} \catcode`\é=\active \def é{\'e} \catcode`\è=\active \def è{\`e} \catcode`\ê=\active \def ê{\^e} \catcode`\ù=\active \def ù{\`u} \catcode`\ô=\active \def ô{\^o} \catcode`\û=\active \def û{\^u} \catcode`\ç=\active \def ç{\c c} \catcode`\î=\active \def î{\^\i} \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{Codes correcteurs d'erreurs} \author{Samuel 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 Reed Muller d'ordre 1 dont le décodage est facilité par la transformation d'Hadamard. % % % % % % \section{Transformation d'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, où 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 \] \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 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'Hadamard} de f. % % \subsection{Calcul rapide} % % \par A priori, le nombre d'additions de nombres complexes effectuées pour calculer la transformée d'Hadamard d'une fonction $f\in\varF(m)$ est en $O(2^{2m})$ % \par Cependant, en posant $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}$ % % % \newpage % % \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*2^i+2*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) * 2\text{, aussi vrai pour i=0} \end{gather*} Le nombre d'additions et de soustractions de complexes est donc $m * 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 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 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 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 $|h_{2^m}(F)(\tau)|$ 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'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'Hadamard de $F$, \ie{} $O(m * 2^m)$, ce qui est largement mieux qu'avec une méthode brutale, dont la complexité serait en $O(2^m * 2^m)$. % % \section{Application} % % Historiquement, les Codes correcteurs de 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$, 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 * 2^5 = 160$ par pixel, à comparer, dans le cas du circuit récepteur, avec $2^{10} = 1024$ : la transformée d'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 aurait pu reconstruire en utilisant le Code de Reed Muller. % % \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 apporte alors parfois un moyen plus rapide, ici sous la forme de la transformée d'Hadamard rapide, qui est de complexité semi-logarithmique. Ce sont de telles situations où l'Informatique est aidée par les Mathématiques. % % % \newpage \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 Nicolas, \textit{Détection et correction d'erreurs}, 2000\\ \url{http://www.info.univ-angers.fr/pub/pn/poly/node13.html} \item Bill Cherowitzo, \textit{Coding Theory I}\\ \url{http://www-math.cudenver.edu/~wcherowi/courses/m5410/m5410cd1.html} \item Alexandre Masselot, \textit{Série d'analyse pour informaticiens Code de Reed Muller et pratique}, 1995\\ \url{http://cui.unige.ch/~masselot/analyse-info/mars/fiction/fiction.html} \item Ben Cooke, \textit{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. 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 Zanotti, \textit{Le code correcteur C.I.R.C.}\\ \url{http://www.univ-tln.fr/~zanotti/enseignement/divers/chapter3.html} \end{itemize} \end{document}