par Hervé Lehning
les messages
oui se corrigent tout seuls
De nos jours, tout message, que ce soit un texte, une image ou une
vidéo, est une longue suite de bits, c'est-à-dire de O et de 1. Il peut
être envoyé par des canaux de communication divers : câbles, fibres
optiques, ondes radio, etc. Quelle que soit la ligne de transmission utilisée, elle ne saurait être à l'abri d ' erreurs. Pour remédier à ce défaut,
l' idéal est que les messages erronés se corrigent d 'eux-mêmes. La tâche
semble impossible .. . et pourtant l'idée est simple : enrichir le message
d ' informations redondantes.
La première solution qui vient à l'esprit est la répétition, par exemple
trois foi s. Ainsi, 0 est codé en 000, et 1, en 111 . À la réception, le message est découpé en blocs de trois bits. Les groupes 000 et 111 sont
EN BREF
i~
, :i·.
\
Rkh;ml. "'"''"•·
191:i~t98.
corrects et ne posent aucun problème. Pour les autres, on remplace le bit minoritaire par le bit opposé.
Ainsi 100, 010 et 001 sont remplacés par 000, 011, 101 et 110, par 111. Inconvénient : la correction
s' avère exacte si une seule erreur a été commise. Autrement dit, le code proposé ne peut corriger qu ' une
erreur tous les trois bits. De plus, il est assez lourd puisqu'il triple la longueur des messages.
Avant d ' aller plus loin, notons qu ' une notion importante se dégage, celle de distance linguistique entre
deux messages, c'est-à-dire le nombre de bits à modifier pour passer de l'un à l' autre.
Les mathématiciens ont inventé de nombreux codes correcteurs d ' erreurs utilisant des notions d'algèbre. Par exemple, un codage dû à Richard Harnrning consiste à transformer chaque groupe de quatre
bits (x 1 , x 2 , x 3
, x 4 ) en un mot de huit bits qui s'écrit:
(x1, x2, x3, x4 , x1 + x2, x3 + x4, x1 + x3, x2 + x4) .
Dans cette transformation,
l'addition se fait suivant la table suivante :
+
0
1
0
1
0
1
1
0
Ainsi, le mot 0110, où x 1 = 0 , x 2 = 1, x 3 = 1 et x 4 = 0 , est transformé en 01101111. Le mot 0010 est
transformé en 00100110. Alors que les deux mots 0110 et 0010 sont à une distance linguistique égale à
1, les deux mots images 01101111 et 00100110 sont à une distance égale à 3. Ce résultat est général :
deux codes distincts génèrent deux images à distance au moins égale à 3. Le code de Harnrning permet
donc de corriger une erreur en étant plus économe que la répétition triple. On peut dresser une table de
correction comme dans le cas précédent mais on peut également donner une formule de correction . ..
R ÉFÉ R ENCES
L'U11i1•ers des codes secrels de l 'A 111iq11i1é à /11/ern e/, Hervé Lehning. Ixe lles
De nombreux a11ic les (vo ire mê me numéros entiers) de Tangenle, de ses hors-séries et de Tange/lie
Sup ont été consacrés à la cryptographie et aux codes correcteurs d' e rreurs. Vo ir par exemple :
• Ta11ge111e 14 7. pages 42 à 50, 20 12.
• ù 1 cryplographie. Bibli othèque Tangente 26, réédité en 201 3.
• Tra 11. 1fe r1 el échange. Ta11ge111e SU P 70- 71 . 201 3.
Hors-série n°52. Mathématiques & informatique Tangente
les messages
oui se corrigent tout seuls
De nos jours, tout message, que ce soit un texte, une image ou une
vidéo, est une longue suite de bits, c'est-à-dire de O et de 1. Il peut
être envoyé par des canaux de communication divers : câbles, fibres
optiques, ondes radio, etc. Quelle que soit la ligne de transmission utilisée, elle ne saurait être à l'abri d ' erreurs. Pour remédier à ce défaut,
l' idéal est que les messages erronés se corrigent d 'eux-mêmes. La tâche
semble impossible .. . et pourtant l'idée est simple : enrichir le message
d ' informations redondantes.
La première solution qui vient à l'esprit est la répétition, par exemple
trois foi s. Ainsi, 0 est codé en 000, et 1, en 111 . À la réception, le message est découpé en blocs de trois bits. Les groupes 000 et 111 sont
EN BREF
i~
, :i·.
\
Rkh;ml. "'"''"•·
191:i~t98.
corrects et ne posent aucun problème. Pour les autres, on remplace le bit minoritaire par le bit opposé.
Ainsi 100, 010 et 001 sont remplacés par 000, 011, 101 et 110, par 111. Inconvénient : la correction
s' avère exacte si une seule erreur a été commise. Autrement dit, le code proposé ne peut corriger qu ' une
erreur tous les trois bits. De plus, il est assez lourd puisqu'il triple la longueur des messages.
Avant d ' aller plus loin, notons qu ' une notion importante se dégage, celle de distance linguistique entre
deux messages, c'est-à-dire le nombre de bits à modifier pour passer de l'un à l' autre.
Les mathématiciens ont inventé de nombreux codes correcteurs d ' erreurs utilisant des notions d'algèbre. Par exemple, un codage dû à Richard Harnrning consiste à transformer chaque groupe de quatre
bits (x 1 , x 2 , x 3
, x 4 ) en un mot de huit bits qui s'écrit:
(x1, x2, x3, x4 , x1 + x2, x3 + x4, x1 + x3, x2 + x4) .
Dans cette transformation,
l'addition se fait suivant la table suivante :
+
0
1
0
1
0
1
1
0
Ainsi, le mot 0110, où x 1 = 0 , x 2 = 1, x 3 = 1 et x 4 = 0 , est transformé en 01101111. Le mot 0010 est
transformé en 00100110. Alors que les deux mots 0110 et 0010 sont à une distance linguistique égale à
1, les deux mots images 01101111 et 00100110 sont à une distance égale à 3. Ce résultat est général :
deux codes distincts génèrent deux images à distance au moins égale à 3. Le code de Harnrning permet
donc de corriger une erreur en étant plus économe que la répétition triple. On peut dresser une table de
correction comme dans le cas précédent mais on peut également donner une formule de correction . ..
R ÉFÉ R ENCES
L'U11i1•ers des codes secrels de l 'A 111iq11i1é à /11/ern e/, Hervé Lehning. Ixe lles
De nombreux a11ic les (vo ire mê me numéros entiers) de Tangenle, de ses hors-séries et de Tange/lie
Sup ont été consacrés à la cryptographie et aux codes correcteurs d' e rreurs. Vo ir par exemple :
• Ta11ge111e 14 7. pages 42 à 50, 20 12.
• ù 1 cryplographie. Bibli othèque Tangente 26, réédité en 201 3.
• Tra 11. 1fe r1 el échange. Ta11ge111e SU P 70- 71 . 201 3.
Hors-série n°52. Mathématiques & informatique Tangente