News :: Erreur :: Statistiques :: ClearType :: Imprimer ::

MÉTHODES NUMÉRIQUES | FRACTALES | SYSTÈMES LOGIQUES | CODES CORRECTEURS CRYPTOGRAPHIE | AUTOMATES | INFORMATIQUE QUANTIQUE

LISTE DES SUJETS TRAITÉS SUR CETTE PAGE

Si la première moitié du vingtième siècle a été celle de la révolution analogique par la radio et la télévision, la seconde moitié de ce siècle est celle de la révolution numérique et de l'utilisation systématique de l'algèbre dans la transmission de données.

Ainsi, après l'apparition du CD audio dans les années 1980, il faut compter sur le développement de la diffusion par satellite de nouveaux moyens de communication tels la télécopie, le réseau Internet ou le téléphone numérique. Les données (textes, images et sons) sont maintenant engrangées sur des CD-ROM dont les lecteurs sont munis de systèmes de codes correcteurs d'erreurs (C.C.D.). Même la photographie et la radio deviennent par ailleurs numériques.

Les techniques de restitution d'images ou de sons sont liées à la transmission et à la lecture correcte de nombreux messages numériques, encore appelés "mots". Un message est formé de mots, eux-mêmes constituées de symboles (un exemple particulier étant le "bit") pris dans un alphabet. Si l'aphabet est binaire alors chaque symbole sera donc un bit.

Prenons le message 00101 formé de 5 bits valant chacun 0 ou 1. Si nous transmettons le message tel quel, une erreur de transmission ou de lecture peut avoir lieu et rendre le message inintelligible. Décidons de répéter ce message trois fois et d'envoyer :

001010010100101   (1)

Si le message reçu comporte une erreur, cette erreur peut être corrigée. S'il comporte deux erreurs, le récepteur est capable de détecter qu'il y a eu erreur mais ne peut pas toujours récupérer le message originel. Enfin, s'il se produit plus de deux erreurs pendant la transmission, le récepteur peut ne pas les détecter.

Nous venons ainsi de voir un premier exemple de C.C.D., appelé "code à répétition". Ce code, qui corrige une erreur et en détecte deux, est utilisé dans certains lecteurs de CD Audio possédant trois têtes de lecteur. Le signal 0 ou 1 est lu indépendamment par chacun de ces trois têtes pour donner un mot de trois chiffres, et une erreur de lecture peut être corrigée.

Remarquons qu'il est naturel d'allonger un message pour le protéger. Prenons les mots d'un langage. Ils sont en général très éloignés les uns des autres, deux mots différant selon leur longueurs et selon les lettres et les syllabe utilisées. Ainsi, nous confondrons difficilement les mots "bibliothèque" et "armoire" même si ces mots sont mal prononcés ou entendus, et nous reconstituerons naturellement le message dans une conversation quand bien même certains sons seraient supprimés ou déformés. Les militaires quant à eux épèlent leurs numéros d'immatriculation en disant "alpha zoulou" pour "AZ"...

Un deuxième exemple de détection d'erreurs largement utilisé en informatique est l'adjonction d'un "bit de parité". Reprenons le message 00101 et ajoutons lui un dernier bit obtenu en additionnant les cinq bits du départ modulo 2. Le message devient 001010 et permet de détecter une erreur sans toutefois pouvoir la corriger. Pour cela, nous faisons la somme de tous les bits pour obtenir 0 s'il n'y a pas eu d'erreur, et 1 dans le cas contraire. Ce code appelé "code parité", est utilisé un peu partout : dans les numéros de sécurité sociale où l'on rajoute la clé, dans ceux des comptes bancaires ou encore dans les code-barres des supermarchés où c'est le 13ème chiffre qui constitue la clé de contrôle (Voyager II est un des nombreux utilisateurs des codes de parité pour communiquer de manière fiable ainsi que le 8ème bit de l'ASCII qui est utilisé comme bit de parité).

Pendant de nombreuses années, les boîtiers de DRAM géraient des mots d'un bit ; il fallait donc placer sur la carte mémoire 8 boîtiers pour travailler avec des octets (8 bits). Pourtant, de nombreuses cartes comportaient non pas 8, mais 9 boîtiers ! Le neuvième boîtier était destiné à stocker un bit de parité lors de chaque mise en mémoire d'un octet. Lors de la lecture d'un octet, on vérifiait si, entre le moment de l'écriture et celui de la lecture, la parité n'avait pas été modifiée (suite à un parasite, par exemple).

  (2)

Enfin, voyons un troisième exemple utilisé sur certains serveurs informatiques qui utilisent des disques parallèles en RAID4 ou RAID6 dont ce dernier utilise les codes de Hamming que nous verrons plus loin.

Supposons que nous ayons trois disques durs de données, et que le contenu du premier octet de chaque disque soit le suivant:

  (3)

Alors il suffit de prendre chaque colonne est de compter le nombre p de 1 dans la colonne. La valeur du bit de parité est alors p modulo 2. Nous avons pour la première colonne p qui vaut 2. Donc le bit de parité vaut 0, etc. Nous avons alors sur le disque de contrôle DC:

  (4)

Dès lors, dès qu'un des trois disques tombe en panne il devient aisé de le restaurer grâce au disque de contrôle en faisant la procédure inverse.

Ces trois exemples fondamentaux sont à la base de la théorie du codage et montrent que nous pouvons maîtriser l'apparition d'erreur en allongeant volontairement le message avant sa transmission ou sa lecture. Des techniques algébriques plus sophistiquées sont ensuite utilisées pour améliorer les performances du codage, le but étant :

- De savoir si des erreurs se sont produites (problème de la détection)

- De retrouver le message correct à partir du message reçu (problème de la correction)

- De corriger le plus d'erreurs possibles tout en utilisant le moins de bits supplémentaires possibles (problème de la performance du codage).

Du point de vue mathématique, l'un des intérêts de la théorie des codes est de montrer que l'algèbre s'applique fondamentalement dans notre vie de tous le jours dès que nous écoutons de la musique ou que nous nous installions devant notre téléviseur, et que des notions aussi abstraites que celles d'espaces vectoriels ou de polynômes sur des corps finis nous permettent de lire des message, d'écouter de la musique ou de regarder des films dans des conditions optimum.

Nous distinguons les deux classes suivantes de C.C.D. : les codes en blocs et les codes en treillis. La figure ci-dessous donne un simple résumé de la grande famille de codage. Dans la première classe (à droite sur la figure), citons les codes les plus célèbres comme les codes BCH, Reed-Solomon et Goppa, Golay et Hamming. La deuxième classe (à gauche sur la figure) est moins riche en variété mais présente beaucoup plus de souplesse surtout dans le choix des paramètres et des algorithmes de décodage disponibles. Citons par exemple, les codes convolutifs binaires systématiques récursifs très utilisés dans les modulations codées (TCM) et les codes concaténés parallèles (Turbo Codes).

  (5)

CHECKSUM

Avant de commencer dans la partie de mathématiques pures, nous souhaiterions faire une petite introduction sur le"checksum" (somme de contrôle) qui est un outil très fréquemment utilisé dans les entreprises lors de l'échange de fichier de plus de quelques GB entre deux ordinateurs ou encore lors du téléchargement sur Internet.

La somme de contrôle, parfois appelé aussi "empreinte", est un concept de base de la théorie des codes utilisé pour les codes correcteurs, elle correspond à un cas particulier de contrôle par redondance. Elle est largement utilisée en informatique et en télécommunications numériques.

Les codes utilisant les sommes de contrôle permettent de valider un message. Si le nombre d'altérations durant la transmission est suffisamment petit, alors elles sont détectées. L'utilisation d'une unique somme de contrôle permet la détection mais non la correction des erreurs.

La technique de base consiste à prendre la somme de certaines longeurs de bits (octets, word ou autre...) et de calculer leur module 255 (FF). Par exemple:

  (Eq.6) Source Wikipedia

Certains utilisent aussi le MD5 (Message Digest 5) pour avoir une empreinte d'un message (cf. chapitre de Cryptographie).

ENCODEURS

Soit Q un ensemble fini à q éléments (bits, alphabets). Soient k et n deux entiers naturels non nuls avec . L'ensemble des messages sera une partie E de , et nous introduisons une application bijective (du moins c'est le but) :

  (Eq.7)  

appelée "application de codage" ou "encodeur". Le message ou mot a est un élément de E. Il est modifié pour fournir le mot . C'est le mot c qui sera transmis et lu par un système quelconque pour donner un message reçu éventuellement entaché d'erreurs.

Notons l'image de f. Comme f est injective, f réalise une bijection de E sur C et C peut être considéré comme l'ensemble de tous les messages possibles. C est appelé "code de longueur n", et les éléments de C s'appellent les "mots" du code. Le cardinal du code est par définition celui de C. Nous le noterons #C ou M. Pour mesurer le degré de différence entre deux mots x et y de , nous utilisons la distance de Hamming d définie par :

  (Eq.8)

Démonstration:

Sur un ensemble Q quelconque nous définissons donc l'application par :

  (Eq.9)

Si nous notons par la fonction caractéristique de x:

  (Eq.10)

alors :

  (Eq.11)

Montrons que d est une distance (cf. chapitre de Topologie) :

1. Il sera supposé que :

  (Eq.12)

est évident.

2. Il sera supposé que :

  (Eq.13)

est évident aussi.

3. Il sera supposé que :

  (Eq.14)

est évident aussi.

4. Nous avons aussi :

  (Eq.15)

où signifie que pour donc que .

5. Enfin :

  (Eq.16)

En effet :

  (Eq.17)

mais comme :

  (Eq.18)

car vaut 1 si et 0 sinon, alors :

  (Eq.19)

C.Q.F.D.

La distance de Hamming (notée dans certains ouvrages) est bien une métrique (cf. chapitre de Topologie) comme nous venons de le démontrer et nous appelons alors "espace de Hamming" sur Q l'ensemble muni de la métrique .

Définition: Si Q est un groupe, le "poids de Hamming" d'un mot est le nombre de ses coordonnées non nulles :

  (Eq.20)

où 0 est le mot (vecteur) de ayant toutes ses coordonnées égales à l'élément neutre de Q. Nous avons par ailleurs la propriété triviale suivante :

  (Eq.21)

Remarque: Lorsque nous parlerons de "code binaire" (nous allons voir de suite plus loin une autre forme d'écriture pour cet ensemble binaire) de dimension n égal à 2.

La "distance minimale" du code C est la distance minimum entre deux mots distincts de ce code. Nous notons ce nombre entier d(C) ou simplement d et donc :

  (Eq.22)

ou encore en utilisant la propriété du poids de Hamming :

  (Eq.23)

Définitions:

D1. Un code C de longueur n, de cardinal M et de distance minimale d est appelé "code (n,M,d)". Les nombres n, M, d sont les "paramètres du code".

D2. Nous appelons "poids minimum" d'un code C l'entier :

  (Eq.24)

d jour un rôle important car il se trouve en relation étroite avec le nombre d'erreurs susceptibles d'être corrigées. Supposons que le message codé soit et qu'il y ait eu moins de e erreurs de transmission ou de lecture. Le message obtenu vérifie . Nous pouvons retrouver c à partir de x set, et seulement si, il existe un seul mot de code situé à une distance de x inférieure ou égale à e (donc que la distance centre à centre entre deux boules soit égale à 2e). Autrement dit, il faut et il suffit que les boules fermées de rayon e et centrées sur les éléments du code C soient disjointes. Un code corrigera e erreurs si cette condition est vérifiée.

Ainsi, un code C de distance minimale d corrige au plus :

  (Eq.25)

erreurs (où [ ] représente la partie entière d'un nombre réel).

Effectivement, si un message du code se trouve à d/2 nous ne pourrons savoir à quel message du code (centre de boule) il appartient puisque se trouvant (de manière imagée) à la tangente de deux boules. C'est la raison pour laquelle nous prendrons qui représente alors la "distance sûre" et pour corriger au mieux un message erroné du code. De plus, comme le nombre d'erreur est un entier il vient naturellement l'écriture :

  (Eq.26)

Il est clair que le code permet de détecter au plus d-1 erreurs. Effectivement, sinon comment détecter un code erroné d'un code juste (code = message codé) ? Mis à part le fait que chaque élément du code soit différent (application injective de l'ensemble des messages à l'ensemble des message codés) il faut en plus pouvoir différencier parmi ceux-ci, ceux qui sont des codes erronés de ceux qui ne le sont pas. D'où le d-1.

CODES EN BLOCS - LINÉAIRES

Définition: Un "code en bloc" de taille défini sur un alphabet de q symboles (1 et 0 pour le langage binaire par exemple) est un ensemble de M vecteurs appelés "mots du code". Les vecteurs sont de longueur et leurs composantes sont q-aires (bin-aire pour le langage du même nom donc...)

Ainsi, selon la définition ci-dessus, un code en bloc C est une application bijective qui associe à chaque vecteur formé de k symboles q-aires (k symboles d'information), un vecteur image de longueur n avec des composantes dans le même alphabet (n symboles codés). Le code ajoute au débit initial n-k symboles supplémentaires. La quantité :

  (Eq.27)

est appelé le "rendement de C", ou encore "taux de codage". L'opération de codage en blocs est "sans mémoire", in extenso les blocs sont codés de manière indépendant sans aucune corrélation entre deux blocs consécutifs.

Maintenant il convient de revenir un peu sur les algèbres de Boole (cf. chapitre de Systèmes Logiques). Aux cinq axiomes qui définissent une algèbre de Boole ajoutons en un sixième qui lui confère une structure de corps :

A6. L'algèbre de Boole (extension d'un anneau unitaire par un axiome) muni de la loi * () est un groupe.

Rappel (théorie des ensembles) : un corps est un anneau non nul dans lequel tout élément non nul est inversible.

Si nous prenons l'algèbre de Boole formée des éléments {0,1} formant un ensemble binaire, nous avons effectivement 1 qui est inversible puisqu'il existe x tel que qui est 1 lui-même.

Ce corps est noté . Dans les codes correcteurs, nous travaillons souvent dans (unique corps à deux éléments) où pour rappel l'addition est définie par :

0+0=0, 1+1=0 (donc 1=-1), 1+0=1   (Eq.28)

La multiplication étant définie par:

  (Eq.29)

Pour en revenir à notre théorie des codes : l'ensembles des messages peut être muni d'une structure d'espace vectoriel de dimension k sur (cf. chapitre de Théorie Des Ensembles). Effectivement, il suffisait pour cela que (E,+) soit un groupe abélien et * une loi externe définie par . Si nous décidons de n'utiliser que des encodeurs qui sont (des applications) linéaires, le code devient un sous-espace vectoriel de (car même si l'application est bijective, comme les corps des messages est fini, nous avons nécessairement un sous-espace vectoriel de l'espace vectoriel de tous les messages codés possibles).

Définition: Un "code linéaire" de dimension k et de "longueur" n est un sous-espace vectoriel de dimension k de (c'est ainsi que cela se dit...). Si la distance minimale de C est d, nous disons que C est une "code [n, k, d]" ou simplement "code [n,k]".

L'ajout de la contrainte de linéarité pourrait nuire à la qualité du code recherché, mais heureusement l'étude des performances montre que les codes linéaires sont très proches des meilleurs codes en blocs. Ainsi, la linéarité facilite l'étude des codes en blocs et permet l'utilisation des outils algébriques très puissants, sans réduire la classe des blocs linéaires à une classe inefficace.

Notons G la matrice de l'application linéaire . G est du type et tout mot c de C s'obtient à partir de tout mot x de E par où et sont des vecteurs lignes avec toujours . Ainsi, .

Remarque: Les bases de sont les bases canoniques courantes (celles dont nous avons souvent fais usage dans le chapitre de calcul vectoriel).

Définition: soit C un code linéaire [n,k] et soit la base de C. Une "matrice génératrice" de C est donc une matrice dont les colonnes sont formées par les vecteurs de la base.

Soit le mot d'information, in extenso le vecteur contenant les k symboles d'information. Alors, nous pouvons écrire la relation matricielle liant le mot de code c et le mot d'information u :

  (Eq.30)

Définition: Soit C un code en blocs [n,k]. Ce code est dit "code systématique", si tous les mots de code contiennent les k symboles d'informations non modifiés. Les n-k symboles restant sont appelés "symboles de parité".

Définition: Soit H une matrice à éléments dans , qui vérifie pour tout mot c d'un code linéaire C (en d'autres termes : dont le noyau est C). Alors, H est dite "matrice de contrôle" du code C. Réciproquement, c appartient au Code si et seulement si . Sinon quoi il y a une erreur !

Remarque: Il est facile de trouver H car celle-ci est "orthogonale" à G puisque la définition ci-dessus implique donc (évidemment il ne faut pas prendre H=0...).

Voyons un exemple de tout cela avec le code de Hamming qui est un code en blocs systématique (attention !! il existerait plusieurs définition d'un "code de Hamming!) :

Cette méthode consiste à doubler l'information, en envoyant autant de bits de parité que de bits de données. Ainsi, à l'aide de matrices, il est possible de détecter et corriger les erreurs qui figurent dans les quartets. Une première matrice est  :

  (Eq.31)

Celle-ci est la matrice de codage G. Elle est de dimension , où n est le nombre de bits reçus par paquet, et k le nombre de bits par paquets contenant l'information (ici et ). Elle permet de générer automatiquement les bits de parité propres à un message. Par exemple pour envoyer le message 1101, il faut, pour respecter la règle de multiplication des matrices, considérer ce quartet comme un vecteur colonne :

  (Eq.32)

Donc en multipliant nous obtenons :

  (Eq.33)

Nous enverrons donc l'octet 11010110, dont les quatre premiers bits forment le message et les quatre derniers les bits de parité, qui servent à vérifier la véracité/intégrité du message.

La matrice de contrôle correspondante H est :

  (Eq.34)

Ainsi lorsque le destinataire reçoit l'octet 11000110 au lieu de 11010110, le décodage donne comme "syndrome" :

  (Eq.35)

Le vecteur colonne obtenu n'est donc pas nul. Il y a donc une erreur. Avec la matrice de contrôle, la théorie permet d'affirmer que comme le vecteur obtenu est le même que celui en quatrième position dans la matrice de décodage, l'erreur est due au quatrième bit. Comme nous sommes en base 2, il suffit de changer le 0 en 1. Ce codage de l'information est coûteux car il occupe deux fois plus de bande passante. Cependant c'est l'un des moyens les plus efficaces pour sécuriser l'information.

Pour montrer que le syndrôme d'un code de Hamming correspond à une des colonnes de la matrice de contrôle, notons les vecteurs colonne de la base canonique sur , avec 1 à la i-ème place. Soit x un mot de code. Nous avons donc par définition de H, . Supposons que le mot reçu, que nous noterons , soit entaché d'une seule erreur et que cette erreur soit sur le j-ème bit. Nous avons donc :

et   (Eq.36)

ainsi il vient que , mais est le j-ème vecteur colonne de la matrice H.

Ceci nous montre bien que lorsque nous recevons et que nous calculons nous obtenons le vecteur colonne de la matrice H situé exactement à l'emplacement de l'erreur (en l'occurrence j).

Notons maintenant :

et   (Eq.37)

alors nous remarquerons que G et H sont formées par les blocs I et A de la manière suivante et . Ainsi :

  (Eq.38)

car 1+1=0 dans .

De façon générale, si nous travaillons avec l'alphabet et si où A est une matrice alors est aussi une matrice de contrôle car de nouveau :

  (Eq.39)

Remarque: Dans , car 1=-1, c'est pour ça que nous avions écrit dans l'exemple précédant.

CODES SYSTÉMATIQUES

Un code systématique consiste à adjoindre à chaque mot du message n-k symboles dépendent linéairement des pour obtenir le mode de code .

Les symboles sont appelées "bits de contrôle" et (nous verrons un exemple juste plus bas) :

  (Eq.40)

où désigne la matrice obtenue en écrivant l'une en-dessous de l'autre, la matrice identité de taille k et une matrice quelconque A. Nous dirons qu'un code C est systématique s'il possède une matrice génératrice de la forme

Exemple:

Nous nous proposons de construire un code linéaire systématique avec n=k=3. Nous notons les bits d'information. Les bits de contrôle seront définis par :

  (Eq.41)

La matrice génératrice G est telle que sa partie supérieure est la matrice identité de dimension 3 (nous avions la même chose pour le code de Hamming). La première ligne (110) de la matrice A correspond à l'expression du bit de contrôle :

  (Eq.42)

etc... pour chaque bit de contrôle.

La matrice génératrice G s'écrit alors :

  (Eq.43)

En multipliant cette matrice par les vecteurs possibles (les mots constitués de trois bits d'information), nous obtenons les mots code :

Nous constatons donc que le poids minimum des mots code est 3. Donc le code détecte 3-1=2 d'erreurs et peut en corriger .