News :: Erreur :: Visiteurs :: ClearType :: Imprimer ::

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

Dernière mise à jour de ce chapitre: 2015-09-06 16:35:29 | {oUUID 1.788}
Version: 3.0 Révision 4 | Rédacteur: Vincent ISOZ  | Avancement: ~60%
vues depuis le 2012-01-01: 3'782

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.

Les codes correcteurs d'erreurs sont utilisés pour ajouter de la redondance aux données pour les rendre tolérantes à la transmission (jusqu'à un certain degré). Basiquement, l'idée est d'encoder d'une manière ou d'une autre une séquence d'information et d'ajouter de l'encodage aux données d'origine en guise de contrôle de l'intégrité des données. Ainsi, même si une certaine partie de l'information est corrompue, mais pas trop,... la redondance permettra d'identifier les parties erronées du message.

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 et de nouveaux moyens de communication tels la télécopie, le réseau Internet ou le téléphone numérique qui utilisent tous les 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és de symboles (un exemple particulier étant le "bit" qui est pour rappel, la contraction du terme "binary digit") pris dans un alphabet. Si l'alphabet 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   (60.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 chacune 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 leurs 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 épellent 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 de 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 l'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).

Figure: 60.1 - Exemple de boîtier de DRAM

Enfin, voyons un troisième exemple utilisé sur certains serveurs informatiques qui utilisent des disques parallèles en RAID4 ou RAID6, ce dernier utilisant 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:

  (60.2)

Alors il suffit de prendre chaque colonne et 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:

  (60.3)

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);

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

- corriger le plus d'erreurs possible 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 les jours dès que nous écoutons de la musique ou que nous nous installons 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 messages, d'écouter de la musique ou de regarder des films dans des conditions optimales.

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 aperçu 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).

Figure: 60.2 - Organigramme des codes correcteurs

CHECKSUM

Avant de commencer 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 fichiers de plus de quelques GB entre deux ordinateurs ou encore lors du téléchargement sur Internet.

La somme de contrôle, parfois appelée 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 longueurs de bits (octets, word ou autres...) et de calculer le modulo 255 (FF). Par exemple, si nous prenons deux mots et nous basons sur leur code ASCII hexadécimal (vous pouvez trouver les tables ASCII un peu partout sur Internet):

Figure: 60.3 - Principe du Checksum (source: Wikipédia)

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):

  (60.4)  

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:

  (60.5)

Démonstration:

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

  (60.6)

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

  (60.7)

alors:

  (60.8)

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

1. Il sera requis que:

  (60.9)

est évident.

2. Il sera requis que:

  (60.10)

est évident aussi.

3. Il sera également requis que:

  (60.11)

est évident aussi.

4. Nous avons aussi:

  (60.12)

où signifie que pour donc que .

5. Enfin:

  (60.13)

En effet:

  (60.14)

mais comme:

  (60.15)

car vaut 1 si et 0 sinon, alors:

  (60.16)

C.Q.F.D.

Par exemple, la distance de Hamming entre les mots "ramer" et "cases" ou entre "0100" et "1001" est de 3.

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:

  (60.17)

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:

  (60.18)

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 égale à 2.

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

  (60.19)

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

  (60.20)

Exemple:

Considérons le code redondant noté (5, 4) pour 4 mots codés de longueur 5 suivant:

Distance de Hamming de chacun des couples du code:

  (60.21)

Le plus petit poids minimum non nul est donc 3 et la distance de Hamming la plus petite est 3.

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". Ainsi, le code (7, 4, 3) est un code de longueur sept, c'est-à-dire que le récepteur reçoit sept bits, de longueur quatre c'est-à-dire qu'une fois décodé, le message contient quatre symboles (lettres) et la distance minimale entre chaque mot de code est de trois.

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

  (60.22)

d joue 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 si, 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:

  (60.23)

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" pour corriger au mieux un message erroné du code. De plus, comme le nombre d'erreurs est un entier, il vient naturellement l'écriture:

  (60.24)

Il est clair que le code permet de détecter au plus d-1 erreurs. Effectivement, sinon comment distinguer 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 dans l'ensemble des messages 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.

Exemple:

Considérons le code redondant noté (5, 4) pour 4 mots codés de longueur 5 suivants dont la distance minimale était donc de 3:

Ce code ne permet donc de détecter au plus que:

  (60.25)

erreurs et d'en corriger au plus:

  (60.26)

CODES EN BLOCS - LINÉAIRES

Définition: Un "code en bloc" de taille M et de longueur n 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". L'idée est que chaque mot d'information composé de k symboles est associé à un mot de code unique composé de n symboles. Les vecteurs sont donc de longueur et leurs composantes sont q-aires (donc "2-aires" dans le cas du langage binaire).

La linéarité des codes en blocs signifie que les n symboles du mot code sont obtenus par une combinaison linéaire des k symboles du mot d'information.

Exemple:

Partons des M vecteurs suivants basés sur q = 3 symboles binaires (donc k = 2). Dans ce cas, nous avons :

Nous choisissons alors n comme valant 6 et nous définissons une application bijective telle que:

Comme le montre cet exemple du code en bloc particulier noté traditionnellement (n, k) = (6, 3), le code ne présente aucune structure particulière. L'opération de décodage implique de faire la comparaison exhaustive du mot reçu en sortie du canal avec l'ensemble des modes de code avant de déterminer le mot de code le plus probable.

Ainsi, selon la définition ci-dessus, un code en blocs C est la résultante d'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 codage ajoute au débit initial n-k symboles supplémentaires. La quantité:

  (60.27)

est appelée 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épendante 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) munie 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   (60.28)

La multiplication étant définie par:

  (60.29)

Pour en revenir à notre théorie des codes: l'ensemble 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 le 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 un "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 d'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 fait 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:

  (60.30)

Définition: Soit C un code en blocs [n,k]. Ce code est dit "code systématique", si l'ensemble des mots de code contient les k symboles d'informations non modifiés. Les n-k symboles restants 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éfinitions 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 :

  (60.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 message 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:

  (60.32)

Donc en multipliant, nous obtenons:

  (60.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:

  (60.34)

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

  (60.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 qui est 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 syndrome d'un code de Hamming correspond à une des colonnes de la matrice de contrôle, notons les vecteurs-colonnes 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   (60.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   (60.37)

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

  (60.38)

et:

  (60.39)

Ainsi:

  (60.40)

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:

  (60.41)

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

CODES SYSTÉMATIQUES

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

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

  (60.42)

où, pour rappel, 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:

  (60.43)

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 :

  (60.44)

etc. pour chaque bit de contrôle.

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

  (60.45)

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 erreurs et peut en corriger .

4   0

Notée par 11 visiteur(s) 12345 PageRater 0.5.0 Commentaires: [0]