Application à la théorie du codage

 

Introduction Les messages transmis, comme des données d'un satellite, sont sujets toujours au bruit. C'est important alors de pouvoir coder un message de telle manière qu'après une perturbation du bruit, il puisse être décodé à sa forme originale. Ceci est fait parfois en répétant le message deux ou trois fois, une chose très commune dans le discours humain. Cependant, copier des données stockées sur un disque compact ou sur une disquette une fois ou  deux fois demande un espace supplémentaire de stockage. Dans cette application, nous examinerons des manières de décoder un message après qu'il est perturbé  par un certain genre de bruit. Ce processus s'appelle le codage. Un code qui détecte des erreurs dans un message brouillé s'appelle un détecteur d’erreurs. Si, en outre, il peut corriger l'erreur il s'appelle correcteur d’erreurs. Il est beaucoup plus difficile de trouver un  code correcteur d’erreurs qu’un code détecteur d’erreurs.

 

 

Quelques techniques de base du codage Puisque la plupart des messages sont envoyés numériquement comme des  suites binaires des 0 et des 1, tels que 10101 ou 1010011-supposons  que nous voulons envoyer le message 1011. Ce ``mot``  binaire peut se tenir pour un vrai mot, tel que ``achetez`` ou une phrase telle que ``achetez des stocks``.  Un Codage de 1011 signifie attacher une queue binaire à cette suite binaire de sorte que si le message devient changé par exemple à 0011, nous puissions détecter l'erreur. Une chose simple à faire est d'attacher un 1 ou un 0, selon si nous avons un nombre impair ou pair des 1 dans le mot. De cette façon tous les mots codés auront un nombre pair des 1. ainsi 1011 sera codé en tant que 10111. Maintenant si ceci est tordu à 00111 nous savons qu'une erreur s'est produite, parce que nous avons seulement reçu un nombre impair des 1. Ce code de détection d'erreurs s'appelle le contrôle de parité et est trop simple pour être très utile. Par exemple, si deux chiffres étaient changés, notre arrangement ne détectera pas l'erreur. Ce n'est certainement pas un code correcteur d’erreurs. Une autre approche serait de coder le message en le répétant deux fois, comme 10111011. Alors si 00111011 était reçu, nous savons qu'une des deux moitiés égales a été tordue. Si seulement une erreur se produisait, alors elle est clairement à la position 1. Ce code donne également des résultats faibles et n'est pas souvent employé. Nous pourrions avoir de meilleurs résultats en répétant le message plusieurs fois, mais ceci prend du temps et d’espace.

 

Un technique du codage avancé: Le code Hamming Dans les années 50, R.H. Hamming a présenté un code correcteur d'erreurs simple intéressant qui est devenu connu comme code Hamming. Avant que nous puissions examiner les détails de cette technique, nous avons besoin de quelques notions d'algèbre linéaire.

 

Espaces vectoriels sur Z2

 

Dans un cours linéaire d'algèbre de première année, quand des étudiants sont introduits à la notion d’espace vectoriel, le mot ``scalaire`` signifie un nombre réel ou complexe. Ceci peut être généralisé à un élément arbitraire d'un certain ``corps``.

 

Un corps est un ensemble F muni de deux opérations, l’addition et la multiplication, qui satisfont aux propriétés suivantes :
 
 1.  Fermeture sous l’addition : si x, y sont dans F, alors x+y est dans F. 
 2.  Fermeture sous la multiplication: si x, y sont dans F, alors xy est dans F.
 3.  Associativité de l’addition: si x, y, z sont dans F, alors (x+y)+z=x+(y+z)
 4.  Associativité de la multiplication: si x, y, z sont dans F, alors (xy)z=x(yz)
 5.  La distributivité de la multiplication par rapport à l’addition: si x, y, z sont dans F, alors x(y+z)=xy+yz
 6.  Existence de 0: c’est un élément de F satisfaisant x+0=x pour tout x dans F 
 7.  Existence de 1: c’est un élément de F satisfaisant  x.1=x for all x in F
 8.  Existence de l’opposé additif : si x est dans F, alors il existe un  y dans F tel que  x+y=0
 9.  Existence de l’inverse multiplicatif  (réciproques) : à l’exception de 0, si x est élément dans F, alors il existe un élément y dans F tel que xy=1.
 10. Commutativité de l’addition : si x, y sont dans F, alors x+y=y+x
 11. Commutativité de la  Multiplication: si x, y sont dans F, alors xy=yx.
 
Exemples des corps: Q (nombres rationnels), R (nombres réels), C (nombres complexes), et Z/pZ si p est un entier premier (les entiers modulo un nombre premier  p):
 

 

 

Le dernier exemple des corps est un d'intérêt spécial pour cette application. En particulier le cas  p=2. Dans ce cas-ci, le corps Z/2Z est dénoté par Z2. Il contient deux éléments seulement: 0 et 1:

 

 

 

Dans Z2, l’addition et la multiplication sont définies par les règles suivantes :

 

 

 

 

Par conséquent, l’addition et la soustraction sont les mêmes dans  Z2.

 

Rappelez-vous  la structure d’espace vectoriel sur Rn (R est l’ensemble de tous les nombres réels) sur R:

1.      (x1,…, xn)+ (y1,…, yn)= (x1+ y1,…, xn+yn)

2.      a(x1,…, xn)= (ax1,…,a xn) si a est un nombre réel.

 

La même structure peut être définie sur Z2n. On munit Z2n d’une addition et d’une multiplication par un scalaire (multiplication par 0 et 1). Par exemple, dans Z25 on a:

 

 

Muni de ces deux opérations, Z2n devient un espace vectoriel sur le Z2 (les scalaires ici sont 0 et 1).Toutes les notions de base d’espaces vectoriels comme l’indépendance linéaire, l’enveloppe linéaire, sous-espaces, dimension, espace-lignes, espace de nullité, … s’appliquent dans ce cas. Une grande différence avec l’espace vectoriel Rn est que Z2n contient un nombre fini de vecteurs, notamment 2n vecteurs.

 

Le (7,4)-code Hamming Étant donnés deux entiers k≤ n, un sous-espace de Z2n de dimension k s’appelle un (n,k)-code linéaire. Les éléments d’un code linéaire s’appellent des mots codés. Considérer la matrice H à entrées dans  Z2 et dont les colonnes c1, …, c7 sont les 7 vecteurs non-nuls de Z23:

 

 

L’espace de nullité, Null(H), de H s’appelle un (7,4)-code  Hamming. Rappelez-vous que Null(H) n’est autre que l’ensemble de solutions du système homogène HX=0 associé à  H. On dit que H est une matrice de contrôle de parité pour le code Null(H).  Résolvons le système HX=0 pour voir à quoi ressemble le code  Null(H).

 

En utilisant l’algorithme d’élimination de Gauss-Jordan (avec l’arithmétique de Z2), on obtient la forme échelonnée réduite suivante de H:

 

 

 

 

Comme le rang de H est 3, la dimension de Null(H) est 7-3=4. En fait, on peut montrer facilement (en écrivant la solution générale sous forme paramétrique) que

 

 

est une base de Null(H) sur Z2.

 

Remarque Soit {e1,…,e7} la base standard de  Z27, alors Hei=ci pour tout i=1,…,7 (vérifiez ceci ), et par suite aucun des vecteurs standards ei est dans Null(H). Par conséquent, on a les deux faits suivants :

1.      Si v est un vecteur de Null(H), alors v+ ei n’appartient pas à  Null(H) pour i=1,2,…,7.

1.      Si v est un vecteur de Z27  tel que  Hv=ci pour un certain i, alors v+ ei  est un vecteur de Null(H). De plus, v+ ej n’appartient pas à  Null(H) pour tout  ji.

 

La matrice G dont les lignes sont les éléments de la base B s’appelle la matrice génératrice  du (7,4)-code Hamming:

 

 

Nous sommes maintenant prêts à expliquer le procédé de Hamming pour le décodage et la correction des erreurs

 

 

Algorithme pour la correction des erreurs avec le (7,4)-code Hamming.

 

Supposez qu’on veut envoyer un mot u se composant de quatre chiffres binaires :

u1 u2 u3  u4 et supposez qu'on sait que le mot codé pourrait être perturbé par un bruit changeant seulement un de ses composantes. Soit w le mot reçu.

 

 

1.      Pour coder u, nous formons la combinaison linéaire v  des éléments de la base B ci-dessus avec les quatre chiffres de u comme coefficients. Notez que v peut être obtenu à partir du mot original en exécutant la multiplication matricielle  v=[u1 u2 u3  u4]G,  où G est la matrice ci-dessus. Par construction, le vecteur v est dans Null(H). Notez également que [u1 u2 u3  u4]G donnerait un vecteur de sept composantes dont les quatre premières  représentent le mot original.

2.      Calculer Hw,H est la matrice décrite ci-haut.

3.      Si Hw=0, alors w est dans Null(H). Ainsi, une erreur simple signifierait que w n'est pas dans Null(H) par la première partie de la remarque ci-dessus. Nous concluons qu'il n'y a aucune déformation, et u est les quatre premiers chiffres de w.

4.      Si Hw=ci pour un certain i, alors v+ ei  est un vecteur de Null(H), et v+ ej n’appartient pas à  Null(H) pour tout ji. Ceci suggère de changer la composante i de w (de 0 à 1 ou de 1 à 0) et obtenir un nouveau vecteur w’. Les premières quatre composantes w’ représentent  le mot  u.

 

Voyons comment ceci fonctionne avec ces deux exemples.

 

Exemple 1 Supposez que nous avons reçu le message w=1100011 codé par le (7,4)-code Hamming. Supposez aussi qu’il y a au plus une erreur dans la transmission du message. Trouver le message original.

 

Sloution

 

 

 

 

Comme Hw est la deuxième de H, un changement de la deuxième composante de w donne le mot codé : 1000011. On conclut que le message original est 1000.

 

Exemple 2 Supposez que nous avons reçu le message w=0101010 codé par le (7,4)-code Hamming. Supposez aussi qu’il y a au plus une erreur dans la transmission du message. Trouver le message original.

 

Sloution

 

 

 

 

 

 

 

Comme Hw =0, il n’y a pas d’erreur dans la transmission de ce message, qui était 0101.

 

 

Dans la technique ci-dessus, les mots que nous avons envoyés étaient très courts: 4 chiffres seulement. Il y a seulement 24 tels mots. Dans la vie réelle, les messageries électroniques se composent de beaucoup plus de chiffres. Un autre problème avec le

(4, 7)-code Hamming est qu'il ne peut pas détecter plus d'une erreur dans un message codé. Avec la révolution électronique de notre temps, on peut imaginer qu'il y a d'autres types de codes plus efficaces.