Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Pour nettoyer les erreurs de transmission introduites par l'atmosphère terrestr

Pour nettoyer les erreurs de transmission introduites par l'atmosphère terrestre (à gauche), les scientifiques de Goddard ont appliqué la correction d'erreur Reed- Solomon (à droite), qui est couramment utilisée dans les CD et DVD. Les erreurs typiques incluent les pixels manquants (blanc) et les faux signaux (noir). La bande blanche indique une brève période pendant laquelle la transmission a été interrompue. Code correcteur Un code correcteur, souvent désigné par le sigle anglais ECC (de l'anglais : error-correcting code), aussi appelé code correcteur d'erreur(s) ou code de correction d'erreur(s) (CCE) , est une technique de codage basée sur la redondance. Elle est destinée à corriger les erreurs de transmission d'une information (plus souvent appelée message) sur un canal de communication peu fiable. La théorie des codes correcteurs ne se limite pas qu'aux communications classiques (radio, câble coaxial, fibre optique, etc.) mais également aux supports pour le stockage comme les disques compacts, la mémoire vive et d'autres applications où la garantie de l'intégrité des données est importante. 1 Problème Description intuitive Un exemple simple Classification du problème Redondance et fiabilité Structures mathématiques Formalisation du problème Alphabet Code en bloc Codage Exemples de codes en bloc Code de répétition Somme de contrôle Redondance et fiabilité Distance de Hamming Code parfait Théorie algébrique des codes en blocs Codes linéaires Matrice génératrice Matrice de contrôle Syndrome et décodage Codes cycliques Autres codes Quelques codes correcteurs Quelques applications typiques Différences entre un code correcteur et un code d'authentification Notes et références Voir aussi Articles connexes Bibliographie Lien externe Les codes correcteurs d'erreurs ont leur source dans un problème très concret lié à la transmission de données. Dans la grande majorité des cas une transmission de données se fait en utilisant une voie de communication le Sommaire Problème Description intuitive Dans la grande majorité des cas, une transmission de données se fait en utilisant une voie de communication, le canal de communication, qui n'est pas entièrement fiable. Autrement dit, les données, lorsqu'elles circulent sur cette voie, sont susceptibles d'être altérées. Par exemple lors d'une communication radio, la présence de parasites sur la ligne va perturber le son de la voix. Il y a alors essentiellement deux approches possibles : augmenter la puissance de l'émission ; ajouter de la redondance à l'information. Si l'on reprend l'exemple de la communication radio, augmenter la puissance de l'émission signifie crier ou avoir un meilleur émetteur. Cette technique a bien évidemment ses limites, et aura du mal à être utilisée dans des sondes spatiales, sans même prendre en considération des contraintes sur les ressources en énergie. L'autre solution va consister à ajouter des données, ce qui donne lieu au code des aviateurs qui diront « Alpha Tango Charlie » dans le seul but de transmettre correctement « ATC » à travers leur radio. La séquence « Alpha Tango Charlie », même déformée par la friture, sera bien plus reconnaissable pour l'oreille humaine qu'un « ATC » déformé. On présente ici un exemple élémentaire de code correcteur obtenu en complétant une suite de trois nombres (constituant l'information à transmettre) par deux autres nombres (constituant le code de contrôle de l'information). L'ensemble des cinq nombres permet alors de détecter et de corriger une erreur qui se serait produite sur l'un des trois premiers nombres lors de la transmission. Soit donc un bloc de 3 nombres que l'on souhaite transmettre : 02 09 12 Ajoutons deux nombres de contrôle de l'information. Le premier est la somme des 3 nombres : 02 + 09 + 12 = 23 Le second est la somme pondérée des 3 nombres, chacun est multiplié par son rang : 02×1 + 09×2 + 12×3 = 56 À la sortie du codeur, le bloc à transmettre est : 02 09 12 23 56 À la suite d'une perturbation, le récepteur reçoit : 02 13 12 23 56 À partir des données reçues, le décodeur calcule : Sa somme simple : 02 + 13 + 12 = 27 Sa somme pondérée : 02×1 + 13×2 + 12×3 = 64 La différence entre la somme simple calculée (27) et celle reçue (23) indique la valeur de l'erreur : 4 (27-23 = 4) La différence entre la somme pondérée calculée (64) et celle reçue (56), elle-même divisée par la valeur de l'erreur indique la position où l'erreur se trouve : 2 ((64-56) / 4 = 2). Il faut donc retirer 4 au nombre du rang 2. Le bloc original est donc 02 (13-4=09) 12 23 56 Lors d'une transmission sans perturbation, les différences des sommes simples et des sommes pondérées sont Un exemple simple Les CD utilisent comme code correcteur une variante du code de Reed-Solomon appelée code C.I.R.C.. Illustration d'un code non correcteur et d'un code correcteur. o s d u e t a s ss o sa s pe tu bat o , es d é e ces des so es s p es et des so es po dé ées so t nulles. Les problèmes rencontrés par l'industrie sont divers. Dans le cas de la transmission de données, par exemple sur internet, le rôle du code correcteur se limite parfois à la détection des erreurs. C'est le cas pour le protocole TCP ; lorsqu'une erreur est détectée dans un message, la correction est alors réalisée par une nouvelle demande de transmission du message. Dans le protocole MIDI, un code optionnel, l'active sensing, permet de vérifier si une liaison avec un instrument de musique électronique est défectueuse. Le cas échéant, dans ce contexte, on préfère interrompre temporairement la communication. Pour d'autres situations, l'objectif est la correction d'erreurs, sans nouvelle demande de transmission. Là encore, plusieurs configurations se présentent. La communication sur ordinateur par le port série utilise un code dont l'objectif est la correction de petites erreurs relativement fréquentes mais isolées. Dans le cas du disque compact, les erreurs sont aussi causées par des rayures ou des impuretés du support, elles sont moins fréquentes mais beaucoup plus volumineuses. La norme de la société Philips impose la capacité de correction d'erreurs dans le cas d'une rayure de 0,2 millimètre, dans la pratique, le code utilisé corrige jusqu'à 4 096 bits consécutifs soit une rayure de plus d'un millimètre de large[réf. souhaitée]. Le disque compact présente une nouvelle situation, celle de l'effacement. Dans ce contexte, et à la différence du paragraphe précédent, le message transmis possède l'indication de la détérioration. La détection des erreurs n'est plus nécessaire, toute l'information se concentre sur la reconstitution du message détérioré. Cette variété de situations explique la multiplicité des techniques utilisées pour les codes correcteurs. On peut citer les sommes de contrôle pour la simple détection, le code BCH pour les ports série ou encore une variante du code de Reed-Solomon pour les disques compacts. Beaucoup de solutions industrielles sont hybrides, comme le code de Hamming ou encore celui utilisé pour le Minitel. D'autres contraintes industrielles se greffent sur le problème des codes correcteurs. Le coût d'implémentation en est un exemple. Pour une solution grand public, la technique de codage et de décodage doit être peu onéreuse. La vitesse de reconstitution des messages est aussi un facteur pris en compte. Tous les codes correcteurs subissent une contrainte du même ordre. Si le message contient une information altérée, une information supplémentaire est nécessaire pour soit détecter l'erreur, soit la corriger. La formalisation est la suivante : le message transmis, appelé code, est plongé dans un espace plus vaste comme illustré dans la figure de droite. Le cas d'un code sans redondance est illustré à gauche. Si un message en vert est altéré lors de sa transmission, c'est alors le message rouge qui est reçu. Aucune information ne laisse supposer qu'une erreur a été commise. Pour pallier cet état, l'objectif est d'entourer les messages licites, correspondant aux intersections des quadrillages sur les figures, par des messages connus pour être erronés, et de réaliser la transmission après. Ces redondances sont illustrées sur la figure de droite par les intersections du quadrillage orange. Si seulement une erreur se produit alors le message transmis correspondra à un point rouge Si la redondance a été Classification du problème Redondance et fiabilité une erreur se produit, alors le message transmis correspondra à un point rouge. Si la redondance a été habilement construite, alors il n'existe qu'un point licite en vert proche du point rouge reçu. Un code correcteur propose une géométrie où les messages licites sont le plus possible éloignés les uns des autres. Les boules centrées sur les bons codes, si elles ne s'intersectent pas, permettent de retrouver le bon message correspondant à son centre. Une perturbation, tant qu'elle reste suffisamment petite pour ne pas faire sortir le code de sa boule, est corrigible. Les points noirs ne sont généralement de peu d’utilité pour permettre de corriger une information déjà transmise, mais ils permettent au moins de détecter que des erreurs importantes se sont produites. Dans cet exemple, il est nécessaire de parcourir au moins deux segments du quadrillage pour relier un point noir à un point valide (vert) et tenter de corriger ces erreurs uploads/S4/ codes-correcteurs.pdf