CHAP.IV. PROGRAMMATION DE LA TRANSMISSION DES
DONNÉES
IV.0. Introduction
Ce chapitre présente un programme qui décrit la
transmission des données dans un réseau. Il s'agit de la
programmation du code de Hamming qui est connu pour son efficacité dans
la transmission des données sans erreur.
Après une brève présentation du code de
Hamming, nous allons exhiber une simulation d'une transmission de l'information
afin de mettre en lumière la façon dont une information est
codée et transmise dans un réseau. Ce réseau peut
être téléphonique, informatique ou autre.
IV.1. PRÉSENTATION DU CODE DE HAMMING
Le code de Hamming est utilisé dans les transmissions
des données, car il permet de détecter et de corriger une erreur
survenue dans un bloc
transmis. Son principe est simple. On fixe un entier k et on code
chaque bloc de m = 2k-k - 1 bits de données par un bloc de n
= 2k - 1 bits en ajoutant donc k bits, dits de correction, à
certaines positions au bloc de m bits. Le tableau suivant indique les nombres
de bits de correction, de données pour certaines valeurs de k.
|
k = 3
|
m = 4
|
n = 7
|
|
k = 4
|
m = 11
|
n = 15
|
|
K = 5
|
m = 26
|
n = 31
|
A. Position de k bits de correction
Les k bits de correction sont placés dans le bloc
envoyé aux positions d'indice une puissance de 2 en comptant à
partir de la gauche. Ainsi, en notant k1 k2 k3 les bits de correction et m1 m2
m3 m4 les bits de données, le bloc envoyé est :
A = k1 k2 m1 k3 m2 m3 m4.
B. Calcul de k bits de correction
Les k bits de correction sont calculés en utilisant une
matrice de parité H, représentée ci-dessous pour k = 3.
- 49 -
H
Remarque : La colonne i de la matrice représente
en binaire la valeur de i. Les k bits de correction sont tels qu'en
considérant le vecteur
|
? ?
k1
? ?
? ?
k2
? ?
m1
? ?
A= ?k3
? ?
m2
? ?
? ?
m3
? ?
? ?
m4
|
? ?
0
, on ait H.A = ? ?
? ?
0
? ?
? ?
0
|
|
On obtient ainsi 3 équations scalaires que doivent
vérifier les k bits de
correction :
0mod2
?+ + + = k m m m ?1 1 2 4
? + + + = k m m m
? + + + =
?k m m m
0 2 1 2 4 mod2
0 3 1 2 4 mod2
Remarque : les opérations d'addition sont faites
à modulo 2. Le bloc A parfaitement déterminé est alors
envoyé.
C. Réception des données et
vérification
Le bloc A est alors envoyé. Le bloc C= c1 c2 c3
c4 c5 c6 c7, reçu, peut être différent du bloc A s'il y a
eu des perturbations la ligne.
Si on considère qu'il n'y a eu qu'une seule
erreur de transmission, alors on peut écrire C = A + E où E,
vecteur d'erreur, est un bloc contenant 6 bits à 0 et un bit à 1.
Les positions des 0 et du 1 sont inconnues dans le bloc.
On calcule le vecteur S tel que
~ 50 ~
? ? s1 S s
? ?
= ? ?
2 = H.C = H . (A + E) = H.A + H.E = H.E
? ?
? ?
s3
Finalement, S est une des colonnes de la matrice de
parité dont l'indice nous donne la position de l'erreur dans le bloc C.
L'erreur est corrigée en changeant le bit considéré
d'état.
s3 s2 s1 est le code binaire de positon de l'erreur dans le
bloc C que nous obtenons à partir des équations suivantes :
s1 =
??
?
? s =
? 3
=
s2
mod2
mod2
mod2
(((c c c c 1 3 5 7 + + + ) c c c c 2 3 6 7 + + + ) c c c c 4
5 6 7 + + + )
Si s3 = s2 = s1 = 0, alors il n'y a pas eu d'erreur lors de la
transmission du
message.
D. Correction d'erreurs par le code de
Hamming
Un code correcteur d'erreur est utilisé pour
transmettre un message dans un canal bruité. Il permet de reconstituer
le message émis même si des erreurs (en nombre limité),
dues au bruit, ont altéré le message.
L'alphabet source, comme l'alphabet du code, est {0,1}. On
s'intéresse au codage par blocs : chaque mot de longueur m est
codé par un mot de longueur n avec n supérieur ou égal
à m. Le codage est donc une application de {0,1}m vers
{0,1}n. Parmi les n bits du mot-code que nous allons décrire,
m reproduisent le mot source, les n-m autres sont les bits de correction. Le
taux de transmission est de n/m.
On montre que si deux mots distincts du code diffèrent
au moins en d
d - 1
erreurs.
2
bits, alors le code permet de corriger exactement
Les codes de Hamming, pour lesquels n = 2k -1 et
m = n - k, permettent de corriger une erreur. Pour k fixé et n
grand, le taux de transmission est voisin de 1.
~ 51 ~
E. Famille de code de Hamming
Il existe une famille de code de Hamming, le plus
célèbre et le plus simple après le code de
répétition binaire de dimension trois et de longueur un est sans
doute le code binaire de paramètres [7, 4, 3]. Pour chaque alphabet
ayant pour nombre de lettres une puissance d'un nombre premier et pour chaque
longueur l de code, il existe un code de Hamming utilisant cet alphabet et de
longueur au moins égal à l.
Il est possible d'utiliser les outils de l'algèbre
linéaire et particulièrement la théorie des matrices pour
construire un code de Hamming. Par exemple, un mot de p bits est
représenté par un vecteur binaire de longueur p,
c'est-à-dire un élément de l'espace vectoriel (Z/2Z)p, par
exemple
? ?
1
? ?
pour 110, on a ? ?
1
? ?
? ?
0
|
.
|
|
La matrice de parité d'un code de Hamming est une
matrice binaire à k lignes et n colonnes : les colonnes contiennent les
représentations binaires des entiers entre 1 et n.
F. Eléments de base de la
formalisation
Il existe un ensemble E constitué de suites à
valeurs dans un alphabet et de longueur k, c'est-à-dire qu'à
partir du rang k, toutes les valeurs de la suite sont nulles. Ces
éléments sont l'espace des messages que l'on souhaite
communiquer. Pour munir le message de la redondance souhaitée, il existe
une application ça injective de E à valeurs dans F,
l'espace des suites de longueur n et à valeurs dans un alphabet. La
fonction ça est appelée encodage, ça(E)
aussi noté C est appelé le code, un élément de
ça(E) est un mot du code, k est la longueur du code et n la
dimension du code.
Par exemple, un mot du code utilisé par le Minitel
comporte 17 octets. Les 16 premiers octets forment un code de Hamming à
7 bits de correction : k=7, m=120 (soit 15 octets), n=127, le
128ème bit, dit bit de parité est tel que le nombre de
1 dans ces 16 octets soit pair. Le 17ème octet est
formé de 8 zéros ; il permet de détecter des incidents
importants (par exemple, la foudre). On s'intéresse ici seulement aux
127 premiers bits.
~ 52 ~
| 
