Codes correcteurs Ann. Univ.

2020-21

Université Hassan II-Mohammedia Filières Ingénieurs GMI 3

Faculté des Sciences et Techniques Module : Codes correcteurs
Département de Mathématiques Pr O. Khadir

Chap. 1. GENERALITES SUR LES CODES CORRECTEURS

Dans ce chapitre, nous allons voir trois points :

1. Introduction.
2. Premiers exemples sur les code correcteurs.
3. Distance de Hamming.

I. Introduction

Les informations se communiquent d’ordinaire par un codage au moyen de lettres, de chiffres,

de sons, etc.. Mais en informatique et télécommunications seuls les symboles 0 et 1 sont utilisés
habituellement pour un codage et une transmission sous forme de courants électriques, d’ondes
radio, de signaux lumineux...
Il est cependant concevable que lorsqu’une transmission se prolonge, des erreurs finissent par
se produire : certains 0 sont remplacés par des 1 et certains 1 par des 0. A la vitesse d’un bit par
microseconde, en une seconde un million de bits sont expédiés. Si le risque d’erreurs est très
faible, ce qui est souvent le cas, au bout de quelques minutes, beaucoup de bits sont transmis de
façon erronée. Il est donc indispensable de se prémunir contre les erreurs de transmission.

On peut penser à demander une seconde transmission lorsqu’on s’aperçoit qu’une erreur
a été détectée lors de la réception d’un message, mais ce n’est pas toujours possible car le
message originel peut-être perdu (un satellite qui s’éloigne trop, un résultat d’un calcul non
enregistré,..) ou bien on n’a pas le temps d’attendre cette seconde transmission. Sans perdre
de l’esprit que des transmissions additives engendrent d’autres erreurs. C’est la raison pour la-
quelle, lorsqu’une erreur est détectée, il est préférable de chercher à la corriger localement et
directement plutôt que de chercher à retransmettre le message. C’est ainsi que la théorie des
codes vise deux objectifs : d’abord la détection des erreurs, ensuite leur correction. Il s’agit ici
de codage de canal par opposition au codage de source qui lui s’occupe uniquement de coder
le message en question.

1
Codes correcteurs Ann. Univ. 2020-21

L’idée de base est assez simple, si n’importe quelle séquence de bits est susceptible d’être
transmise à un destinataire, ce dernier n’a aucun moyen pour porter un doute sur les messages
qu’il reçoit. Par contre si les messages sont codés de manière à contenir certaines particula-
rités facilement reconnaissables le destinataire rejettera les messages reçus et dépourvus de ces
particularités et pourra même les remplacer par des messages proches et plus vraisemblables.

Exemple 1. Si le destinataire reçoit le message M = 00101011110010001110101011110 et

qu’il n’a aucune indication sur ce qu’il aurait dû recevoir, il n’a pas de raison de le suspecter et
doit l’accepter tel quel est. Par contre s’il reçoit le message M2 = 111000111111001000111 et
s’il sait par avance que les bits des messages sont expédiés par paquets de trois bits identiques,
il sera tenté de corriger le cinquième paquet et d’y remplacer le 1 par un 0.

Schéma de communication

Les codes sont des ensembles particuliers fort utiles pour la correction des erreurs lors de trans-
mission de messages. En effet, seuls les éléments du code sont envoyés. Ainsi à la réception
d’un mot, on a le moyen de savoir s’il est correct ou erroné en vérifiant qu’il appartient ou
non au code utilisé. Cependant, quand il y appartient, on ne peut pas conclure immédiatement
sans d’autres investigations. Les messages à envoyer sont supposés découpés en blocs de même
longueur, ce sont les mots ; c’est pourquoi l’on parle de codes en blocs. Autrement, il s’agit de
codes convolutifs (ou convolutionnels ou récurrents, convolutional codes en anglais).

2
Codes correcteurs Ann. Univ. 2020-21

II. Premiers exemples de codes correcteurs

1. Le code de parité
Codage de source : Le code ASCII, au début des années 60, représentait chaque caractère
appartenant à un texte quelconque, lettre chiffre ou symbole de ponctuation, par une suite de 7
bits, ce sont les bits d’information.
Codage de canal : Certains systèmes de transmission, avant d’expédier le caractère d’un point
à un autre, ajoutait un bit à la huitième position calculé de telle manière que la somme des bits
égaux à 1 soit égale à 0 modulo 2. Ce dernier bit est appelé bit de contrôle de parité. Le système
de réception vérifie pour chaque suite de 8 bits que la somme des 1 est paire. Nous avons ici
un code de rendement 7/8 (ou taux d’information) qui permet de détecter les erreurs contenues
dans les suites de 8 bits présentant une anomalie lors de la transmission.
Nous devons noter que :
1- Lorsque le code détecte une erreur, on ne sait pas d’où elle provient.
2- Quand le nombre des erreurs survenues est pair, on ne discerne aucune anomalie.
3- Une anomalie qui n’apparaı̂t que si le nombre de bits erronés est impair, ne permet pas de
connaı̂tre ce nombre.
4- Bien que les 7 bits d’information soient tous correctement transmis, il se peut que l’on détecte
une anomalie si le bit de contrôle a lui même été altéré.

2. Le code à répétition
Soit M = x1 x2 . . . xn un message écrit à l’aide des bits 0 et 1, n ∈ N. Formons, à partir de M, un
nouveau message M 0 de longueur 3n en recopiant chaque bits 3 fois :

M 0 = x1 x1 x1 x2 x2 x2 . . . xn xn xn

Supposons qu’au lieu de transmettre le message M à travers un canal bruité, on transmet le

message M 0 . A la réception on se retrouve avec un message M 00 de longueur 3n qu’on découpe
en morceaux de 3 bits. En analysant chaque mini bloc de 3 bits, on pourra dire s’il y a eu ou
non une erreur et l’on pourra la rectifier. A chaque fois que les 3 bits du mini bloc ne sont pas
identiques, on est face à une ou plusieurs erreurs. Seulement, avec le matériel actuel utilisé lors
de la transmission, les statistiques montre qu’il est très peu probable d’avoir plus d’une erreur
sur 3 bits successifs, d’où la possibilité de corriger le mini bloc reçu. On parle de correction par
vote majoritaire. L’inconvénient de cette méthode est que le temps d’envoi est multiplié par 3.
Le rendement de ce code est 1/3.

3
Codes correcteurs Ann. Univ. 2020-21

Exemple 2. Supposons que le message M à transmettre est de longueur 8 et que l’on a reçu

M 00 = 0 0 0 1 1 0 1 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 1

On a
M 00 = 0 0 0 | 1 1 0 | 1 1 1 | 0 0 0 | 0 0 0 | 1 0 1 | 0 0 0 | 0 1 1

On corrige M 00 en : M 00 = 0 0 0 | 1 1 1 | 1 1 1 | 0 0 0 | 0 0 0 | 1 1 1 | 0 0 0 | 1 1 1.
D’où le message d’origine qu’on a voulu transmettre est M = 0 1 1 0 0 1 0 1

Remarque 1. Si, au lieu de 3, on reproduit chaque bit k fois, k étant un entier impair, on pourra
corriger jusqu’à (k − 1)/2 bits erronés. Mais cela voudrait dire que le canal de transmission est
sérieusement endommagé !

3. Le code de parité croisée

Une amélioration est la construction suivante. Supposons que nous voulions transmettre un mes-
sage binaire (m1 , m2 , m3 , m4 ) de longueur 4 en adjoignant 5 bits de redondance (r1 , r2 , r3 , r4 , r5 ).
Posons ces 9 valeurs dans un tableau à 3 lignes et à 3 colonnes. Les bits additionnels sont définis
de la manière suivante : la somme des bits de chaque ligne et chaque colonne doit-être nulle mo-
dulo 2.

m1 m2 r1
m3 m4 r2
r3 r4 r5

Il est clair que les bits r1 , r2 , r3 , r4 sont bien définis par cette règle. La condition sur la dernière
ligne et celle sur la dernière colonne sont équivalentes vue la règle appliquée au deux lignes et
aux deux colonnes. Ainsi r5 est aussi bien défini.
Si lors de la transmission des neufs bits, un seul bit est passé par erreur de 0 à 1 ou vice versa,
alors le destinataire va le remarquer et procéder immédiatement à la correction. En effet si
l’erreur se produit au croisement de la ligne i et la colonne j, alors le destinataire va observer
une parité impaire dans cette ligne et cette colonne mais une parité paire dans les toutes autres
lignes et colonnes. Supposons que le message est m = 1 1 0 1 alors les bits de redondance sont
(r1 , r2 , r3 , r4 , r5 ) = (0, 1, 1, 0, 1) et c = 1 1 0 1 0 1 1 0 1 sera le message transmis. Supposons
que le message reçu est y = 1 1 0 1 0 0 1 0 1. Le destinataire le pose sur un rectangle 3 × 3 et
repère la ligne et la colonne à parité impaire.

4
Codes correcteurs Ann. Univ. 2020-21

1 1 0
0 1 0 ←
1 0 1
↑

Il corrigera ainsi le bit de la deuxième ligne et la troisième colonne qui est 0 et sera rectifié en
1.
Ce code correcteur est une amélioration du code à 3 répétitions car le taux d’information passe
de 1/3 à 4/9.

5
Codes correcteurs Ann. Univ. 2020-21

4. Le code de Hamming (1950)

C’est un code détecteur et correcteur d’erreurs très connu et très utilisé en pratique. Il consti-
tue une autre amélioration par rapport aux trois codes précédents. Il code les messages sur des
blocs de longueur n = 2k − 1 comme les suites composées de 1, 3, 7, 15, 31, 63, . . . bits. On
le notera H[n, k]. Un trop long message peut-être découpé en morceaux plus courts ayant la
longueur appropriée.

Soit un message à transmettre de la forme : M = a1 a2 a3 a4 . . . an . Découpons le en bloc de 4

bits. On va coder ces 4 bits a, b, c, d dans 7 bits a1 a2 a3 a4 a5 a6 a7 où a1 , a2 , a4 sont des bits de
contrôle et a3 = a, a5 = b, a6 = c, a7 = d.
Le message reçu après transmission est noté : b1 ...b7 .
On suppose que le canal de communication ne peut provoquer qu’une erreur au plus chaque
fois qu’il transmet 7 bits. La position de l’erreur est 1, 2, 3.., ou 7. Donc elle peut-être codée en
binaire par X = ε2 ε1 ε0 où les εi ∈ {0, 1}.

X = ε2 ε1 ε0 =⇒ X ∈ {0, 1, 2, 3, 4, 5, 6, 7}

X = 0 traduit le fait qu’il n’y a pas eu d’erreurs lors de la transmission du message M =

a1 a2 a3 a4 a5 a6 a7 .
Ne confondez pas les bits du message a1 , a2 , a3 , a4 , a5 , a6 , a7 et les bits qui nous donnerons la
position de l’erreur survenue : ε2 , ε1 , ε0 .

Déterminer la position de l’erreur ⇐⇒ Déterminer ε0 , ε1 , ε2 .

a1 , a2 et a4 seront des bits

 de parité respectivement pour les indices dont l’écriture binaire est
 a1 ≡ a3 + a5 + a7 [2]
∗ ∗ 1, ∗1∗ et 1 ∗ ∗. Donc a2 ≡ a3 + a6 + a7 [2]
a4 ≡ a5 + a6 + a7 [2]


Après réception de b1 b2 . . . b7 :
Si b1 6≡ b3 + b5 + b7 [2], alors il y a eu erreur sur les indices 1, 3, 5 ou 7, donc ε0 = 1, sinon
ε0 = 0. Ainsi ε0 est déterminé. Noter que ε0 = b1 + b3 + b5 + b7 [2].
Si b2 6≡ b3 + b6 + b7 [2], alors il y a eu erreur sur les indices 2, 3, 6 ou 7, donc ε1 = 1, sinon
ε1 = 0. Ainsi ε1 est déterminé. Noter que ε1 = b2 + b3 + b6 + b7 [2].
Si b4 6≡ b5 + b6 + b7 [2], alors il y a eu erreur sur les indices 4, 5, 6 ou 7, donc ε2 = 1, sinon
ε2 = 0. Ainsi ε2 est déterminé. Noter que ε2 = b4 + b5 + b6 + b7 [2].
On n’a pas besoin de faire un test pour déterminer la position de l’erreur.

6
Codes correcteurs Ann. Univ. 2020-21

Exemple 3.

Prenons M = a1 a2 0 a4 1 1 0. Les bits de parité vérifient a1 ≡ 0 + 1 + 0 ≡ 1 [2], a2 ≡ 0 +

1 + 0 ≡ 1 [2] et a4 ≡ 1 + 1 + 0 ≡ 0 [2]. On transmet, à travers un canal de communication
M = 1 1 0 0 1 1 0. Supposons qu’on a reçu : M = 1 1 0 0 1 0 0. Corrigeons les erreurs. La
position de l’erreur en binaire est ε2 ε1 ε0 .
ε0 = b1 + b3 + b5 + b7 = 0.
ε1 = b2 + b3 + b6 + b7 = 1.
ε2 = b4 + b5 + b6 + b7 = 1.
D’où la position de l’erreur en binaire est 1 1 0. Il faut donc corriger le bit numéro 6.

Revenons au cas général : Au sein du message, les k bits a1 , a2 , a22 , a23 , a24 , . . . a2k−1 ,
c’est-à-dire les bits dont l’indice est une puissance de 2, sont des bits de contrôle et vont servir
uniquement à la détection et à la correction d’erreurs éventuelles. Ils se calculent selon la règle
de Hamming en fonction des bits restants, au nombre de m = n − k = (2k − 1) − k, qui sont
n − k 2k − k − 1
les vrais bits d’information. Ainsi le taux d’information de ce code est = .
n 2k − 1
On suppose qu’il ne peut y avoir qu’une seule erreur au plus. Puisque le message M comporte
n = 2k − 1 bits, la position X ∈ {1, 2, 3, . . . , n} d’un bit erroné peut-être déterminée en binaire
par un nombre de la forme X = εk−1 εk−2 . . . ε1 ε0 où les εi ∈ {0, 1}.

Théorème 1. Le code de Hamming, employé lors d’une transmission, est un code correcteur
d’une erreur et la comparaison des k bits de contrôle donne directement l’indice du bit erroné.

Remarque 2. Si tous les indices εi sont nuls alors on déduit qu’il n’a y a pas eu erreur lors de
la transmission, autrement dit la position X = 0 indique que la transmission du message s’est
correctement déroulée.

7
Codes correcteurs Ann. Univ. 2020-21

Exemple 4.

Prenons k = 4. Soit le message M constitué de 4 bits de contrôle de parité et donc de 11 bits

d’information :
↓
Message M a1 a2 1 a4 0 0 0 a8 0 1 0 0 1 1 1
Les indices 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
a1 est le bit de contrôle de parité paire pour les bits l’indice : 3 5 7 9 11 13 15 =⇒ a1 = 1.
a2 est le bit de contrôle de parité paire pour les bits l’indice : 3 6 7 10 11 14 15 =⇒ a2 = 0.
a4 est le bit de contrôle de parité paire pour les bits l’indice : 5 6 7 12 13 14 15 =⇒ a4 = 1.
a8 est le bit de contrôle de parité paire pour les bits l’indice : 9 10 11 12 13 14 15 =⇒ a8 = 0.

Conclusion les bits de contrôle de parité paire sont :

a1 = 1 a2 = 0 a4 = 1 a8 = 0.
Supposons que lors du transfert du message M, le bits d’indice 9 a été altéré et le 0 s’est trans-
formé en 1.
Soit X l’écriture en binaire de l’indice du bit éventuellement erroné.
La position de l’erreur en binaire est X = ε3 ε2 ε1 ε0 , avec :
ε0 = b1 + b3 + b5 + b7 + b9 + b11 + b13 + b15 = 1.
ε1 = b2 + b3 + b6 + b7 + b10 + b11 + b14 + b15 = 0.
ε2 = b4 + b5 + b6 + b7 + b12 + b13 + b14 + b15 = 0
ε3 = b8 + b9 + b10 + b11 + b12 + b13 + b14 + b15 = 1
D’où l’indice du bit erroné est : X = 1001 ≡ 9 en décimal.

Astuce pour trouver les relations entre les bits : Voir en classe.....
Les bits de contrôle sont de la forme a2i . On écrit a2i = A + B.... où A est la somme de 2i
bits d’indices consécutifs à partir de 2i . On saute les 2i bits suivants d’indices consécutifs. On
recommence avec B jusqu’à la fin des indices.

8
Codes correcteurs Ann. Univ. 2020-21

Algorithme de Hamming I. (codage)

Entrée : Le texte à transmettre dont le nombre de bits est un multiple de 4.
Sortie : Son codage.
1. Début
2. Tant que la longueur du texte n’est pas nulle faire
2.1. Prendre les 4 premiers bits du message notés a3 , a5 , a6 , a7 .
2.2. Calculer a1 , a2 , a4 selon les formules de Hamming.
2.3. Transmettre via le canal de communication a1 , a2 , a3 , a4 , a5 , a6 , a7 .
2.4. Aller en 2.
3. Fin

Algorithme de Hamming II. (décodage)

Entrée : Le texte reçu dont le nombre de bits est un multiple de 7.
Sortie : Son décodage.
1. Début
2. Tant que la longueur du texte n’est pas nulle faire
 7 premiers bits du message notés b1 , b2 , b3 , b4 , b5 , b6 , b7 .
2.1. Prendre les
 ε0 = b1 + b3 + b5 + b7 mod 2;
2.2. Calculer ε1 = b2 + b3 + b6 + b7 mod 2
ε2 = b4 + b5 + b6 + b7 mod 2

2.3. La position de l’erreur est p = ε0 + 2ε1 + 4ε2 . Si p = 0 il n’y a pas eu d’erreur
2.4. Aller en 2.
3. Fin

9
Codes correcteurs Ann. Univ. 2020-21

Application concrète du code de Hamming : Le Minitel

En France le Minitel est l’ancêtre de l’internet. Il a été utilisé jusqu’aux années 80 et mani-
pulait des informations transmises par les lignes téléphoniques. Le faible taux d’erreurs, calculé
statistiquement, a justifié l’utilisation d’un code correcteur de Hamming de paramètre k = 7.
Donc les messages seront envoyés par blocs de longueur n = 2k − 1 = 127 bits.
En fait les blocs seront de longueur 136 bits (17 octets) :
127 pour le code de Hamming, dont 7 pour le contrôle de parité. Le 128eme bit est un bit de
parité sur ces 7 derniers. Les 8 bits restants, appelés bits de validation, sont tous nuls et servent
à détecter une trop forte perturbation.

Minitel −→ a1 a2 a3 a4 . . . a127 a128 0| 0 0 0{z0 0 0 0}

les 8 bits de validation
↑
bit de parité des 7 bits de contrôle

Modèle d’appareil pour Minitel

10
Codes correcteurs Ann. Univ. 2020-21

III. Distance de Hamming

Elle sert à quantifier de combien sont différents deux mots ou deux n−uplets de même longueur.
Mais surtout de mesurer de combien est éloigné un mot reçu douteux des autres mots du code,
ceux là même qu’on aurait pu ou dû recevoir.

Définition 1 : On considère l’alphabet A = {0, 1}. Pour n ∈ N, on définit la distance de Ham-

ming d sur An par :

∀ x = (x1 , . . . , xn ), y = (y1 , . . . , yn ) ∈ An d(x, y) = card{ i | xi 6= yi }

Donc d(x, y) représente tout simplement le nombre de bits par lesquels deux mots sont différents.
On peut vérifier que d est bien une distance au sens métrique.

Définition 2 : La distance minimale d’un code C ⊂ An est :

dmin (C) = in f { d(x, y) | (x, y) ∈ C2 , x 6= y}

Ainsi par exemple si C = {01110, 10101, 11001} alors dmin (C) = 2

Le principe du décodage par maximum de vraisemblance

Soit C un code de longueur n utilisé pour la transmission d’un message : C ⊂ {0, 1}n . On
suppose que le code C est disponible simultanément dans les systèmes d’envoi et les systèmes
de réception. Nous devons donc recevoir exclusivement des éléments du code C puisque seuls
des éléments de C ont été expédiés. Le principe du décodage par maximum de vraisemblance
(ou du voisin le plus proche) consiste à adopter la position suivante : lorsque l’élément reçu
n’appartient pas au code C, et donc il y a eu erreur de transmission, on le corrige en le remplaçant
par le mot du code le plus proche par la distance de Hamming, si ce dernier est unique.

Théorème 2. Un code C de distance minimale d, employé pour une transmission, peut détecter
une anomalie lorsque 1, 2, . . . , ou (d − 1) erreurs se sont produites (strictement moins que la
d −1
distance minimale) et corriger jusqu’à erreurs (strictement moins que la moitié de la
2
distance minimale).

Démonstration :

11
Codes correcteurs Ann. Univ. 2020-21

code C
c
d
a d(c0 , c) < z
2

c’
b

x y

Position d’un élément reçu c0

1- D’abord comme on n’envoie que des mots du code C, on ne doit recevoir que des mots du

code C. Soit c ∈ C le mot du code qu’on a transmis via le canal de communication. Supposons
qu’il y a eu moins de d erreurs et qu’on a reçu c0 . Après réception, on calcule la distance entre
c0 et tous les mots du code C. A un moment on arrivera au calcul de d(c0 , c) et l’on trouvera un
nombre strictement inférieur à d. Ceci signifie que c0 ne peut pas être un élément de C et donc
on en déduit qu’il y a eu une erreur.

2- Soit c ∈ C le mot du code qu’on a transmis via le canal de communication. Supposons qu’il
y a eu moins de d/2 erreurs et qu’on a reçu c0 . Après réception, on calcule la distance entre
c0 et tous les mots du code C. A un moment on arrivera au calcul de d(c0 , c) et l’on trouvera
un nombre strictement inférieur à d/2. Premièrement, ceci signifie que c0 ne peut pas être un
élément de C et donc on en déduit qu’il y a eu une erreur. Deuxièmement, c est le seul élément
de C aussi proche de c0 car s’il y avait un autre c” ∈ C, par l’inégalité triangulaire, on aurait
d(c0 , c”) < d, ce qui contredit le fait que la distance minimale du code C est d.

Exemple 5. C = {11001, 11110, 00101} =⇒ d = dmin (C) = 3.

C peut détecter jusqu’à deux erreurs (mais pas trois) et corriger une erreur (mais pas deux).
Supposons qu’on a reçu le message c0 = 11010. On s’aperçoit que d(c0 , 11001) = 2,
d(c0 , 11110) = 1, d(c0 , 00101) = 4. Donc c0 est erroné et il faut le corriger par 11110.

12
Codes correcteurs Ann. Univ. 2020-21

La qualité d’un code correcteur dépend fondamentalement de sa distance minimale. Plus la

distance minimale est grande, meilleur est le code. D’où la course vers la recherche de code
ayant les distances minimales les plus grandes.

A suivre ....

•−−−−−•−−−−−•−−−−−•−−−−−•

13
Codes correcteurs Ann. Univ. 2020-21

Exemple de transmission d’image

Image M= Définition 12x12

 
0 0 0 0 0 1 1 0 0 0 0 0

 0 0 0 0 0 1 1 0 0 0 0 0 


 1 1 1 1 1 1 1 1 1 1 1 1 


 0 0 0 1 1 1 1 1 1 0 0 0 


 0 0 0 1 1 1 1 1 1 0 0 0 

 0 0 0 1 1 1 1 1 1 0 0 0 
Image M =  

 0 0 0 1 1 1 1 1 1 0 0 0 


 0 0 0 1 1 1 1 1 1 0 0 0 


 0 0 0 0 1 0 0 1 0 0 0 0 


 0 0 0 0 1 0 0 1 0 0 0 0 

 0 0 0 0 1 0 0 1 0 0 0 0 
0 0 0 0 1 0 0 1 0 0 0 0
Image M=
000001100000 000001100000 111111111111 000111111000 000111111000 000111111000
000111111000 000111111000 000010010000 000010010000 000010010000 000010010000
Pour la transmission de l’image M d’un endroit à un autre, on va se servir par exemple du code
de Hamming H[15,11]. On suppose que le canal de communication produit au plus une erreur
chaque fois qu’il transmet 15 bits. On commence par séparer le flux des bits par paquets de 11
bits.
Image M=00000110000 00000011000 00000111111 .....

A suivre ....

14