Code de Hamming (7,4) - Définition

Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

- Introduction - Histoire - Approche intuitive - Objectif - Décodage - Construction du code - Code de Hamming (8,4)

Construction du code

Code linéaire

Un code linéaire dispose d'une structure 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 espaces vectoriels sur le corps binaire {0,1}. Les tables d'addition et de multiplication sont les suivantes:

+	0	1
0	0	1
1	1	0

.	0	1
0	0	0
1	0	1

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 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. 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

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₁ = 1000, d₂ = 0100, d₃ = 0010 et d₄ = 0001.

L'image de d₁, le message qui a des coordonnées nulles en d₂, d₃ et d₄, possède deux parités égales à un, celle de p₁ et p₂ et une égale à zéro:p₃.

En respectant l'ordre de la base de F : p₁, p₂, d₁, p₃, d₂, d₃ et d₄, on obtient l'image du premier vecteur :

Calculons de la même manière les images des autres vecteurs de la base de E :

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 :

\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}

Exemple

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₁, un pour p₂ et zéro pour p₃. 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:

\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}

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é.

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.

Données $({\color{blue}d_1}, {\color{blue}d_2}, {\color{blue}d_3}, {\color{blue}d_4})$	Hamming(7,4)		Hamming(7,4) avec bit de parité (Hamming(8,4))
	Transmis $({\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})$	Diagramme	Transmis $({\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})$	Diagramme
0000	0000000		00000000
1000	1110000		11100001
0100	1001100		10011001
1100	0111100		01111000