4.1. Définitions

Les codes linéaires sont des codes dont chaque mot du code (noté c) est obtenu après transformation linéaire des bits du mot initial (noté i).

Ces codes sont caractérisés par leur matrice G(k, n) (appelée matrice génératrice) telle que :

• i . G = c

Exemple : . =

 

La matrice H(n-k, n) (appelée matrice de contrôle) permet de savoir si un mot reçu est un mot du code, en calculant son syndrome. Si le syndrome du mot est nul, ce mot appartient au code.

• Syndrome du mot reçu c' : c'. HT = 0(n-k) <==> c' ∈ C(k, n)

L'équation G . HT = 0 définit la relation entre les deux matrices.

• Preuve : c'. HT = i. G. HT = i. 0

4.2. Propriétés

La distance de Hamming d'un code linéaire est égale au plus petit poids de Hamming non nul des mots du code.

Si un code linéaire est systématique, sa matrice génératrice s'écrit :

• G(k, n) = [Id(k), P(k, n-k)]

alors sa matrice de contrôle s'écrit : H(n-k, n) = [PT(n-k,k), Id(n-k)]

Exemples :

. Soit le code C1(4, 6) de matrice G1 = .

 

• Le mot de code c associé au mot initial i=

est le mot c=i.G1 =

. Le code C2(7, 8) associé à la parité paire a pour matrice de contrôle H2T = .

4.3. Correction

Correction par proximité : le procédé de correction transforme un mot reçu et détecté comme erroné dans le mot de code le plus proche au sens de la distance de Hamming.

• Il peut exister plusieurs mots équidistants. On choisit un représentant
• procédé de correction lourd

Exemple :

Le code à répétition C3(1, 4), distance de Hamming de C3 = 4.

4.4. Codes de Hamming

Famille de codes linéaires auto-correcteurs faciles à corriger.

Principe de construction d'un code de Hamming dense C(2m-m-1, 2m-1) :

• Chaque colonne de sa matrice de contrôle H(m, 2m-1) est non-nulle et différente.
• Propriétés :
• leur distance minimale est égale à 3 (au moins)
• correction des erreurs simples et détection des erreurs doubles, au moins.

Auto-correction :

• le syndrome du mot reçu est identique à la colonne de la matrice de contrôle correspondant au bit à corriger.
• si l'on trie les colonnes de H suivant leur poids binaire croissant et que les poids de ses colonnes couvrent l'intervalle [1, 2m-1] alors la valeur binaire du syndrome est égale au numéro de bit erroné.

Un code de Hamming est compact si les 2n-k syndromes différents sont utilisés pour identifier les 2n-k-1 erreurs simples (+ syndrome nul !).

Exemple :

• Code de Hamming C4(4, 7) tel que sa matrice de contrôle H4(3, 7) =
.

Calculez la matrice génératrice G4 puis les syndromes de c1 = ,
de c2 = et de c3 = .

 

Le code est systématique, la transposée de H4 : H4T = donc G4 =

c1. H4T = --> i1 =

c2. H4T = --> erreur sur le dernier bit --> i2 =

c3. H4T = --> erreur sur le 5ème bit --> i3 =

4.5. Conclusion

La méthode matricielle impose de travailler sur des mots de taille fixe, ce qui est un inconvénient majeur pour les réseaux informatiques où les messages sont de taille variable.