<page> <title>Code de Hamming (7,4)</title> <id>1375459</id> <revision> <id>28944290</id> <timestamp>2008-04-24T11:15:59Z</timestamp> <contributor> <username>Jean-Luc W</username> <id>53231</id> </contributor> <minor /> <comment>/* Références */ catégorie</comment> <text xml:space="preserve">Le '''Code de Hamming (7,4)''' est un [[code correcteur]] [[code linéaire|linéaire]] [[système binaire|binaire]] de la famille des [[code de Hamming|codes de Hamming]]. A travers un message de sept [[bit]]s, il transfère quatre bits de données et trois [[somme de contrôle|bits de parité]]. Il permet la correction de toute erreur portant sur un unique bit. C’est-à -dire que si, sur les sept bits transmis, un est altéré (un ''zéro'' devient un ''un'' ou l'inverse), alors il existe un [[Algorithmique|algorithme]] permettant de corriger l'erreur, quel que soit le bit altéré. Il fut introduit par [[Richard Hamming]] <small>([[1915 en science|1915]]-[[1998 en science|1998]])</small> en [[1950 en science|1950]] dans le cadre de son travail pour les laboratoires [[Laboratoires Bell|Bell]]. ==Histoire== Depuis [[1946 en science|1946]] Richard Hamming travaillait sur un modèle de [[calculateur]] à [[carte perforée]] de faible fiabilité. Si, durant la semaine, des ingénieurs pouvaient corriger les erreurs, les périodes chômées comme la fin de semaine voyaient les machines s'arrêter invariablement sur des [[Bogue (informatique)|bogues]]. La frustration<ref>[http://itswww.epfl.ch/~courssisy/slides2004/040525%20-%20codes%20lineaires.pdf Présentation du code de Hamming par l'Ecole Polytechnique fédérale de Lausanne]</ref> d'Hamming le conduisit à inventer le premier code correcteur véritablement efficace. Cette période correspond à la naissance de la [[théorie de l'information]]. [[Claude Shannon]] <small>([[1916 en science|1916]] - [[2001 en science|2001]])</small> formalise cette théorie comme une branche des mathématiques<ref>[[Claude Shannon]] ''A mathematical theory of communication'' Bell System Technical Journal, vol. 27, pp. 379-423 et 623-656, Juil et Oct [[1948 en science|1948]]</ref>. Hamming développe<ref>[[Richard Hamming]] ''Error-detecting and error-correcting codes'' Bell Syst. Tech. J. 29 pp 147 à 160 [[1950 en science|1950]]</ref> les prémisses de la théorie des codes et décrit sa solution comme un exemple. ==Objectif== {{Article détaillé|Code correcteur}} L'objectif du code est la transmission d'un message de ''quatre'' bits avec suffisamment de redondances pour que, même si une altération se produit, le récepteur soit capable de corriger automatiquement l'erreur. Le message envoyé est en conséquence plus long. Dans la pratique il contient ''sept'' bits, quatre composent le message et les trois autres servent à détecter et à corriger l'erreur, si nécessaire. L'erreur que protège ce code est nécessairement limitée, si les sept bits transmis sont tous modifiés, il est vain d'espérer retrouver le message original. La protection contre la modification d'un unique bit est parfois largement suffisant, c'était le cas de la situation d'Hamming. Une modification d'un unique bit, c’est-à -dire d'un trou non lu sur la carte perforée ou d'une absence de trou considéré comme un trou est ''relativement'' rare. Supposons que cette situation se produit sur une série de quatre en moyenne une fois sur mille. Alors cinquante heures d'exécution de programme, qui utilisent par exemple de l'ordre de mille séries voit sa probabilité d'arrêt supérieure à soixante pour cent. La probabilité de trouver deux erreurs sur une série de sept est inférieur à un sur cinq cent mille. L'utilisation de mille séries de longueur sept possède une probabilité d'arrêt inférieure à deux pour mille dans le cas d'une utilisation de cinquante heures si les messages sont protégés par le code. C'était largement suffisant pour éradiquer la frustration d'Hamming. ==Approche intuitive== ===Code parfait=== {{Article détaillé|code parfait}} La première question que l'on peut se poser est : combien d'informations la redondance doit-elle contenir? Ces informations sont contenues dans le message transmis par l'intermédiaire de ''p'' bits. Il existe donc quatre + ''p'' erreurs possibles, et en plus de ces informations il en faut une pour indiquer l'absence d'erreur. Cinq plus ''p'' informations doivent donc être stockées dans ''p'' bits. Or ''p'' bits peuvent au maximum contenir 2<sup>p</sup> informations. Cette situation est obtenue si chaque état décrit une information. On peut s'en rendre compte par un exemple, deux bits peuvent décrire quatre états : 00, 01, 10, 11 ce qui correspond à compter de ''zéro'' à ''trois'' en [[Base (arithmétique)|base]] deux. Si le code est idéal, ''p'' vérifie l'égalité 5 + ''p'' = 2<sup>p</sup> le terme de gauche décrit les informations nécessaire à la correction et celui de droite la quantité d'informations stockées dans les bits de parité. Cette [[équation]] admet une unique solution : ''p'' est égal à trois. Un code vérifiant ce type de propriété est dit '''parfait''', l'article associé formalise cette approche. ===Bit de parité=== {{Article détaillé|bit de parité}} [[Image:Hamming(7,4).svg|right|thumb|250px|Représentation graphique des quatre bits de données et des trois bits de parité]] La figure de droite indique le mode de construction du code. Les valeurs ''d''<sub>1</sub>, ''d''<sub>2</sub>, ''d''<sub>3</sub> et ''d''<sub>4</sub> symbolisent les quatre bits du message. Les valeurs ''p''<sub>1</sub>, ''p''<sub>2</sub>, ''p''<sub>3</sub> correspondent aux bits de parité. Le bit ''p''<sub>1</sub> correspond à la parité du cercle vert, si ''d''<sub>1</sub> + ''d''<sub>2</sub> + ''d''<sub>4</sub> est pair ''p''<sub>1</sub> est égal à ''zéro'', sinon ''p''<sub>1</sub> vaut ''un''. En conséquence, si aucune altération ne se produit, la somme des bits du cercle vert est paire. Cette logique est poursuivie sur les cercles rouge et bleu. Si une altération se produit par exemple sur ''p''<sub>1</sub> alors la parité du cercle de ''p''<sub>1</sub> est modifiée, en revanche celles des cercles de ''p''<sub>2</sub> et de ''p''<sub>3</sub> ne sont pas modifiées. Si la parité de ''d''<sub>1</sub> est modifiée, alors celles des cercles de ''p''<sub>1</sub> et de ''p''<sub>2</sub> le sont mais celle de ''p''<sub>3</sub> ne l'est pas. Le récapitulatif de la situation est donné dans le tableau suivant. Les sept colonnes correspondent aux sept possibles altérations des différents bits du message, les trois lignes correspondent aux parités des cercles associés. Si la parité du cercle est conservée alors la cellule associée est verte avec le texte ''oui'', dans le cas contraire la cellule est rouge avec le texte ''non''. <center> {|class="wikitable" !Bit # !! 1 !! 2 !! 3 !! 4 !! 5 !! 6 !! 7 |- ! bit transmis !! <math>p_1</math> !! <math>p_2</math> !! <math>d_1</math> !! <math>p_3</math> !! <math>d_2</math> !! <math>d_3</math> !! <math>d_4</math> |- |<math>p_3</math> |bgcolor="#66FF66"|Oui |bgcolor="#66FF66"|Oui |bgcolor="#66FF66"|Oui |bgcolor="#FF6666"|Non |bgcolor="#FF6666"|Non |bgcolor="#FF6666"|Non |bgcolor="#FF6666"|Non |- |<math>p_2</math> |bgcolor="#66FF66"|Oui |bgcolor="#FF6666"|Non |bgcolor="#FF6666"|Non |bgcolor="#66FF66"|Oui |bgcolor="#66FF66"|Oui |bgcolor="#FF6666"|Non |bgcolor="#FF6666"|Non |- |<math>p_1</math> |bgcolor="#FF6666"|Non |bgcolor="#66FF66"|Oui |bgcolor="#FF6666"|Non |bgcolor="#66FF66"|Oui |bgcolor="#FF6666"|Non |bgcolor="#66FF66"|Oui |bgcolor="#FF6666"|Non |} </center> Si, par exemple les trois parités des trois cercles sont modifiées, alors il existe une erreur sur le bit ''d''<sub>4</sub>. Pour chaque bit, une erreur engendre un jeu de parité différent. Si aucune erreur n'altère le message alors les trois parités sont à ''oui''. L'ordre des différentes colonnes n'est pas choisi au hasard. On remarque que si l'on transforme dans le tableau les ''Non'' en ''un'' et les ''Oui'' en ''zéro'' alors on obtient la suite des nombres de ''un'' à ''sept'' en binaire. Cette propriété permet par la suite un décodage aisé. ==Construction du code== ===Code linéaire=== {{Article détaillé|Code linéaire}} Un code linéaire dispose d'une [[structure (mathématiques)|structure]] [[structure algébrique|algébrique]] plus riche que celle du cadre général des codes correcteurs. L'ensemble ''E'' des messages à envoyer est celui de mots de quatre lettres prises dans l'ensemble {0,1}, le message est codé en un mot de sept lettres encore prises dans le même ensemble. On note ''F'' l'espace des mots de sept lettres binaires. ''E'' et ''F'' peuvent être considérés comme des [[espace vectoriel|espaces vectoriels]] sur le corps binaire {0,1}. Les tables d'addition et de multiplication sont les suivantes: <center> {|class="wikitable" | {|border="1" |&nbsp;'''+'''&nbsp;||&nbsp;'''0'''&nbsp;||&nbsp;'''1'''&nbsp; |- |&nbsp;'''0'''&nbsp;||&nbsp;0||&nbsp;1 |- |&nbsp;'''1'''&nbsp;||&nbsp;1||&nbsp;0 |} | {|border="1" |&nbsp;'''.'''&nbsp;||&nbsp;'''0'''&nbsp;||&nbsp;'''1'''&nbsp; |- |&nbsp;'''0'''&nbsp;||&nbsp;0||&nbsp;0 |- |&nbsp;'''1'''&nbsp;||&nbsp;0||&nbsp;1 |} |} </center> L'addition est intéressante car la somme d'une suite de valeurs est égale ''zéro'' dans le corps si la somme est paire dans les [[entier naturel|entiers]] et ''un'' sinon. La multiplication est habituelle, multiplier par ''zéro'' donne toujours ''zéro'' et multiplier par ''un'' ne modifie pas la valeur. L' ''encodage'', c’est-à -dire l'opération consistant à transformer le message de ''E'' de quatre lettres en un code de ''F'' de sept lettres apparait alors comme une ''application linéaire'' de ''E'' dans ''F''. Elle se décrit par une [[matrice (mathématiques)|matrice]]. Même si le corps est inhabituel, tous les résultats de l'[[algèbre linéaire]] s'appliquent ici. Pour cette raison, un tel code est dit '''linéaire'''. L'encodage consiste à multiplier le [[vecteur]] de quatre lettres binaires par une matrice 7x4 pour obtenir un vecteur composé de sept lettres binaires. ===Matrice génératrice=== {{Article détaillé|Matrice génératrice}} [[Image:Hamming(7,4) as bits.svg|thumb|250px|Ordre des différents bits]] La connaissance de l'image de chaque vecteur de la [[base canonique]] détermine entièrement l'application d'encodage φ. Les quatre vecteurs de la base correspondent aux messages suivants : ''d''<sub>1</sub> = '''1000''', ''d''<sub>2</sub> = '''0100''', ''d''<sub>3</sub> = '''0010''' et ''d''<sub>4</sub> = '''0001'''. L'image de ''d''<sub>1</sub>, le message qui a des coordonnées nulles en ''d''<sub>2</sub>, ''d''<sub>3</sub> et ''d''<sub>4</sub>, possède deux parités égales à ''un'', celle de ''p''<sub>1</sub> et ''p''<sub>2</sub> et une égale à ''zéro'':''p''<sub>3</sub>. En respectant l'ordre de la base de ''F'' : ''p''<sub>1</sub>, ''p''<sub>2</sub>, ''d''<sub>1</sub>, ''p''<sub>3</sub>, ''d''<sub>2</sub>, ''d''<sub>3</sub> et ''d''<sub>4</sub>, on obtient l'image du premier vecteur : <center><math>\varphi (1000) = 1110000</math></center> Calculons de la même manière les images des autres vecteurs de la base de ''E'' : <center><math>\varphi (0100) = 1001100\; ,\quad \varphi (0010) = 0101010\; et\quad \varphi (0001) = 1101001\; </math></center> La matrice de φ, appelée '''matrice génératrice''' est formée des quatre colonnes correspondant aux images des vecteurs de la base canonique par φ, on obtient : <center><math>\mathbf{G} = \begin{pmatrix} 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{pmatrix}</math></center> ===Exemple=== {{Article détaillé|Produit matriciel}} [[Image:Hamming(7,4) example 1011.svg|thumb|250px|Représentation graphique de l'exemple ''d'' = '''1011''']] Considérons l'exemple du message à communiquer ''d'' = '''1011'''. Les bits de parités sont alors égaux à ''zéro'' pour ''p''<sub>1</sub>, ''un'' pour ''p''<sub>2</sub> et ''zéro'' pour ''p''<sub>3</sub>. En respectant l'ordre des vecteurs de la base de ''F'', on obtient ''manuellement'' le vecteur ''c'' = '''0110011'''. Le produit matriciel de la matrice génératrice ''G'' par la matrice colonne ''D'' du vecteur ''d'' fournit la matrice colonne ''C'' du vecteur ''c'': <center><math>\mathbf{D} = \begin{pmatrix} 1 \\ 0 \\ 1 \\ 1 \end{pmatrix} \quad \mathbf{G.D}= \begin{pmatrix} 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{pmatrix} \begin{pmatrix} 1 \\ 0 \\ 1 \\ 1 \end{pmatrix} = \begin{pmatrix} 0 \\ 1 \\ 1 \\ 0 \\ 0 \\ 1 \\ 1 \end{pmatrix} \quad et \quad \mathbf{C} = \mathbf{G.D}=\begin{pmatrix} 0 \\ 1 \\ 1 \\ 0 \\ 0 \\ 1 \\ 1 \end{pmatrix} </math></center> Les deux résultats sont égaux, cependant le calcul matriciel est simple et rapide à implémenter. Le destinataire reçoit le code ''c'' contenant à la fois des données et les bits de parité. ==Décodage== ===Matrice de contrôle=== {{Article détaillé|Matrice de contrôle}} Le récepteur, sous réserve d'absence d'erreur peut facilement décoder le message ''c''. Il sait que le code reçu : '''<font color=red>01</font><font color=blue>1</font><font color=red>0</font><font color=blue>011'''</font> contient les données en bleu, en position trois, cinq, six et sept. Il lui faut maintenant savoir si aucune altération n'a modifié le code reçu, ce qui correspond à l'un des rôles des bits de parité en rouge. Une approche analogue à celle de l'encodage permet la détection d'erreur. Trois conditions doivent être remplies, une par cercle de la figure représentative. Chaque condition s'exprime comme une somme devant être paire, ou encore nulle dans le corps binaire. Ces trois conditions forment les trois lignes d'une matrice dite '''matrice de contrôle'''. Un message reçu est sans erreur si et seulement si le produit de la matrice de contrôle ''H'' par la matrice colonne ''C'' du vecteur ''c'' est égal à la matrice colonne nulle. La condition associée au cercle rouge ''p''<sub>3</sub> signifie que la somme ''p''<sub>3</sub> + ''d''<sub>2</sub> + ''d''<sub>3</sub> + ''d''<sub>4</sub> doit être paire. La première ligne de la matrice correspond aux coordonnées '''0001111'''. Cette ligne correspond à la première ligne du tableau du paragraphe ''bit de parité''. Il en est de même pour les autres lignes, correspondant aux cercles bleu et vert. On obtient la matrice ''H'' : <center><math>\mathbf{H} = \begin{pmatrix} 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ \end{pmatrix} </math></center> Il est possible de vérifier sur l'exemple que le produit de la matrice ''H'' par celle du mot du code ''c'' est bien nul. De manière plus générale, il est aussi possible de vérifier que le produit de ''H'' par ''G'' est bien nul, ce qui assure que tout message reçu est bien validé si aucune altération n'a été commise. <center><math>\mathbf{H.C} = \begin{pmatrix} 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ \end{pmatrix}. \begin{pmatrix} 0 \\ 1 \\ 1 \\ 0 \\ 0 \\ 1 \\ 1 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix} \quad et \quad \mathbf{H.G} = \begin{pmatrix} 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ \end{pmatrix}. \begin{pmatrix} 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{pmatrix} = \begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ \end{pmatrix}</math></center> ===Correction d'erreur=== {{Article détaillé|décodage par syndrome}} [[Image:Hamming(7,4) example 1011 bit 5 error.svg|thumb|250px|Conséquence d'une erreur sur le bit ''d''<sub>2</sub>]] L'objectif du code est la protection contre une erreur. Etudions le cas où le bit de donnée ''d''<sub>2</sub> est altéré durant le transfert. Le message reçu n'est plus ''c'' = '''0110011''' mais ''x'' = '''0110<font color=red>1</font>11'''. Deux conditions, correspondant au cercles rouge et verts, ne sont plus remplies. Le vecteur ''x'' ne peut passer le test de la matrice de contrôle : <center><math>\mathbf{H.X} = \begin{pmatrix} 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ \end{pmatrix}. \begin{pmatrix} 0 \\ 1 \\ 1 \\ 0 \\ 1 \\ 1 \\ 1 \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix} </math></center> L'erreur est donc détectée, la matrice de contrôle présente un vecteur non nul, correspondant à la valeur ''cinq'' exprimée en binaire. La valeur de ''H''.''X'' est appelée '''syndrome'''. La correction associée correspond au mot ''e''<sub>5</sub> composé de sept lettres égales à ''zéro'' sauf une, la ''cinquième'' est égale à ''un''. Le décodage, dans le cas d'un syndrome non nul correspond à soustraire (ce qui revient à additionner dans un code binaire) l'erreur ''e''<sub>5</sub> = '''0000<font color=red>1</font>00'''. On obtient : <center><math>\mathbf{C} = \mathbf{X} + \mathbf{E}_5= \begin{pmatrix} 0 \\ 1 \\ 1 \\ 0 \\ 1 \\ 1 \\ 1 \end{pmatrix} + \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \\ \overline{1} \\ 0 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 1 \\ 1 \\ 0 \\ 0 \\ 1 \\ 1 \end{pmatrix} </math></center> Quelque soit l'erreur, à partir du moment où elle n'intervient que sur un bit, la matrice de contrôle fournit en binaire le numéro de la colonne fautive. Une fois l'erreur corrigée, il est possible d'extraire les données et reconstruire le message initial. Une telle méthode est appelée '''décodage par syndrome'''. ===Description du mécanisme=== La linéarité de l'application associée à la matrice ''H'' filtre totalement le message pour proposer une image ne dépendant que de l'erreur : <center><math>\mathbf{H.X}=\mathbf{H}.(\mathbf{C} + \mathbf{E}_5)=\mathbf{H.C}+\mathbf{H.E}_5= 0 + \mathbf{H.E}_5=\mathbf{H.E}_5</math></center> C'est la raison qui permet de parler de syndrome, il ne dépend que de l'erreur et non du message lui-même. De plus, l'ordre de la base de ''F'' : ''p''<sub>1</sub>, ''p''<sub>2</sub>, ''d''<sub>1</sub>, ''p''<sub>3</sub>, ''d''<sub>2</sub>, ''d''<sub>3</sub> et ''d''<sub>4</sub>, ainsi que celui des lignes de la matrice ''H'' ont été choisis de telle manière à ce qu'une lecture de gauche à droite correspondent à une liste de colonnes aux représentions binaires des nombres de ''un'' à ''sept'' ordonnées, l'image de ''e''<sub>5</sub> par l'application est donc '''101''' et une telle propriété est vraie pour tous les ''e''<sub>i</sub> si ''i'' est un entier compris entre ''un'' et ''sept''. ==Code de Hamming (8,4)== En cas d'une double erreur, le code détecte une anomalie. Cependant le syndrome propose un chiffre binaire correspondant toujours à une troisième colonne différente des deux précédentes. Ainsi une troisième erreur est ajoutée, car le code ne dispose d'aucun moyen pour différencier une simple d'une double erreur. Pour pallier cet état de fait, ainsi que pour obtenir un code de dimension exactement égale à un octet, un huitième bit est souvent ajouté, il correspond à la parité des sept bits précédents. Une deuxième erreur est ainsi détectée, elle ne peut être corrigée, en revanche l'information d'une double erreur est disponible remplaçant une tentative maladroite, par une demande de retransmission. Le décodage se fait de la manière suivante : * S’il n’y a aucune erreur le syndrome est nul. * Si une erreur s’est produite sur les sept premiers bits, les trois premiers éléments du syndrome donnent la position de l'erreur. L'existence d'un nombre d'erreur impair est confirmé par le huitième bit. * Si deux erreurs se sont produites, les trois premiers éléments du syndrome ne sont pas tous nuls et le huitième bit indique une parité exact, signal d'un nombre pair d'erreurs. Une retransmission est nécessaire. * Si une erreur s'est produite sur le huitième bit, l'absence d'erreur sur les trois premiers éléments du syndrome permet de localiser l'erreur et le message est validé. Le tableau suivant décrit les quatre premiers messages ainsi que leurs encodages pour Hamming (7,4) et (8,4) <center> {|class="wikitable" |- !rowspan="2"|Données<BR><math>({\color{blue}d_1}, {\color{blue}d_2}, {\color{blue}d_3}, {\color{blue}d_4})</math> !colspan="2"|Hamming(7,4) !colspan="2"|Hamming(7,4) avec bit de parité (Hamming(8,4)) |- ! Transmis<BR><math>({\color{red}p_1}, {\color{red}p_2}, {\color{blue}d_1}, {\color{red}p_3}, {\color{blue}d_2}, {\color{blue}d_3}, {\color{blue}d_4})</math> ! Diagramme ! Transmis<BR><math>({\color{red}p_1}, {\color{red}p_2}, {\color{blue}d_1}, {\color{red}p_3}, {\color{blue}d_2}, {\color{blue}d_3}, {\color{blue}d_4}, {\color{green}p_4})</math> ! Diagramme |- |<font color="blue">0000</font> |<font color="red">00</font><font color="blue">0</font><font color="red">0</font><font color="blue">000</font> |[[Image:Hamming(7,4) example 0000.svg|150px|Hamming code for 0000 becomes 0000000]] |<font color="red">00</font><font color="blue">0</font><font color="red">0</font><font color="blue">000</font><font color="green">0</font> |[[Image:Hamming(7,4) example 0000 with extra parity.svg|150px|Hamming code for 0000 becomes 0000000 with extra parity bit 0]] |- |<font color="blue">1000</font> |<font color="red">11</font><font color="blue">1</font><font color="red">0</font><font color="blue">000</font> |[[Image:Hamming(7,4) example 1000.svg|150px|Hamming code for 1000 becomes 1000011]] |<font color="red">11</font><font color="blue">1</font><font color="red">0</font><font color="blue">000</font><font color="green">1</font> |[[Image:Hamming(7,4) example 1000 with extra parity.svg|150px|Hamming code for 1000 becomes 1000011 with extra parity bit 1]] |- |<font color="blue">0100</font> |<font color="red">10</font><font color="blue">0</font><font color="red">1</font><font color="blue">100</font> |[[Image:Hamming(7,4) example 0100.svg|150px|Hamming code for 0100 becomes 0100101]] |<font color="red">10</font><font color="blue">0</font><font color="red">1</font><font color="blue">100</font><font color="green">1</font> |[[Image:Hamming(7,4) example 0100 with extra parity.svg|150px|Hamming code for 0100 becomes 0100101 with extra parity bit 1]] |- |<font color="blue">1100</font> |<font color="red">01</font><font color="blue">1</font><font color="red">1</font><font color="blue">100</font> |[[Image:Hamming(7,4) example 1100.svg|150px|Hamming code for 1100 becomes 1100110]] |<font color="red">01</font><font color="blue">1</font><font color="red">1</font><font color="blue">100</font><font color="green">0</font> |[[Image:Hamming(7,4) example 1100 with extra parity.svg|150px|Hamming code for 1100 becomes 1100110 with extra parity bit 0]] |} </center> ==Notes et références== {{Code correcteur}} ===Notes=== <references /> ===Liens externes=== * {{fr}} [http://zanotti.univ-tln.fr/enseignement/divers/chapter3.html Code correcteur C.I.R.C] par J.P. Zanotti * {{fr}} [http://www.univ-lille1.fr/bustl-grisemine/pdf/articles/A1998-14.pdf L'algèbre et la correction des erreurs] par Dany-Jack Mercier Université Antilles-Guyane * {{fr}} [http://www.math.u-bordeaux.fr/~zemor/codes06.pdf Code Linéaire] Université de Bordeaux * {{fr}} [http://www.ufr-mi.u-bordeaux.fr/CSI/Cours/code.pdf Cours de code] par Christine Bachoc Université de Bordeaux ===Références=== * FJ MacWilliams & JJA ''Sloane The Theory of Error-Correcting Codes'' North-Holland, 1977 * A Spataru ''Fondements de la Théorie de l'Information'' Presses Polytechniques Romandes, 1991 {{Portail|mathématiques|sécurité informatique|informatique}} [[Catégorie:Algèbre linéaire]] [[Catégorie:Détection et correction d'erreur]] [[en:Hamming(7,4)]]</text> </revision> </page>