Detector i corrector d'errors

Un codi corrector és una tècnica de codificació basada en la redundància. Està destinada a corregir els errors de transmissió d'una informació (anomenada sovint missatge) sobre un canal de comunicació poc fiable.

La teoria dels codis correctors no es limita només a les comunicacions clàssiques (ràdio, cable coaxial, fibra òptica, etcètera.) sinó també als suports per a l'emmagatzematge com els discs compactes, la memòria RAM i altres aplicacions on la integritat de les dades és important.

Problemàtica

Descripció intuïtiva

Els codis correctors d'errors tenen el seu origen en un problema molt concret vinculat a la transmissió de dades. En la gran majoria dels casos, una transmissió de dades es fa utilitzant un canal de comunicació, que no és completament fiable. En altres paraules, les dades, quan circulen sobre aquesta via, són susceptible de patir alteracions.

Per exemple en el moment d'una comunicació de ràdio, la presència de paràsits sobre pertorbarà el so de la veu. Llavors hi ha essencialment dos enfocaments possibles:

• augmentar la potència de l'emissió
• afegir redundància a la informació

Respecte de l'exemple de la comunicació ràdio, augmentar la potència de l'emissió significa cridar o tenir un emissor millor. Aquesta tècnica evidentment té els seus límits, i farà de mal fer en alguns cassos com per exemple en sondes espacials, fins i tot sense prendre en consideració les restriccions sobre els recursos en energia.

L'altra solució consistirà a afegir dades, el que dóna lloc al codi dels aviadors que diuen «Alfa Tango Charlie» amb l'únic objectiu de transmetre correctament «ATC» a través de la seva ràdio. La seqüència «Alfa Tango Charlie», fins i tot deformada pel soroll de fons, serà més fàcil de reconèixer per a l'orella humana que un «ATC» amb soroll.

Classificació de la problemàtica

Els CD fan servir com a codi corrector una variant del codi de Reed-Solomon anomenada codi I. R. C. .

Les problemàtiques que afronta la indústria són diverses. En el cas de la transmissió de dades, per exemple sobre internet, el paper del codi corrector es limita de vegades a la detecció dels errors. És el cas del protocol TCP. La correcció llavors es realitza per una demanda de que es repeteixi la transmissió del missatge.

En altres situacions, l'objectiu és la correcció d'errors, sense demanda de nova transmissió. En aquest cas encara es presenten diverses configuracions. La comunicació sobre ordinador pel port sèrie utilitza un codi l'objectiu del qual és la correcció de petits errors relativament freqüents però aïllats. En el cas del disc compacte, els errors són causats per ratllats o impureses del suport, són menys freqüents però molt més voluminosos. La norma de la societat Philips imposa la capacitat de correcció d'errors en el cas d'un ratllat de 0,2 mil·límetre, en la pràctica, el codi que es fa servir corregeix fins a 4096 bits consecutius o sigui, un ratllat de més d'un mil·límetre d'ample.

El disc compacte presenta una nova situació, la de l'esborrament. En aquest context, i a diferència del paràgraf precedent, el missatge transmès té la indicació de que s'ha deteriorat. La detecció dels errors ja no és necessària, tota la informació es concentra en la reconstitució del missatge deteriorat.

Aquesta varietat de situacions explica la multiplicitat de les tècniques utilitzades per als codis correctors. Es poden citar les sumes de control per a la simple detecció, el codi BCH per als ports sèrie o una variant del codi de Reed-Solomon per als discs compactes. Moltes solucions industrials són híbrides, com per exemple el codi de Hamming o el que fa sevir Minitel.

Sobre la problemàtica dels codis correctors, s'afegeixen altres restriccions industrials. El cost d'implementació n'és un exemple. En una solució per al gran públic, la tècnica de codificació i de descodificació ha de ser poc onerosa. La velocitat de reconstitució dels missatges també és un factor a tindre en compte.

Redundància i fiabilitat

Il·lustració d'un codi no corrector i d'un codi corrector

Tots els codis correctors tenen una restricció del mateix ordre. Si el missatge conté una informació alterada, cal una informació suplementària per a, o bé detectar l'error, o bé corregir-lo. La formalització és la següent. El missatge transmès, anomenat codi es submergeix en un espai més vast, com il·lustrat a la figura de dreta.

El cas d'un codi sense redundància s'il·lustra à l'esquerra. Si un missatge en verd pateix, en el moment de la seva transmissió, una alteració, llavors es transmet un nou missatge en vermell. No hi ha cap informació que permeti suposar que s'ha comés un error. Per pal·liar aquest estat, l'objectiu és d'envoltar els missatges lícits, corresponent a les interseccions de les quadrícules de les figures, per missatges dels que és segur que contenen errors (i per tant que mai es transmeten com a missatges vàlids), i realitzar la transmissió després. Aquestes redundàncies (missatges que es poden escriure però que no es fan servir) s'il•lustren a la figura de dreta per les interseccions de la quadrícula taronja. Si es produeix un únic error, llavors el missatge transmès correspon a un punt vermell. Si la redundància ha estat hàbilment construïda, llavors no hi ha més que un punt lícit en verd a prop del punt vermell rebut.

Un codi corrector proposa una geometria on els missatges lícits estan el més allunyats possible uns dels altres. Les boles centrades sobre els codis bons, si no s'intersequen, permeten trobar el missatge bo, corresponent al del seu centre. Una pertorbació, en tant que sigui prou petita per no fer sortir el codi de la seva bola és corregible.

Els punts negres no són de cap utilitat. cal recórrer dos segments de la quadrícula per enllaçar un punt negre amb un punt lícit. El codi corrector il·lustrat engendra llavors una ambigüitat. En efecte, tots els punts vermells són a una distància de dos segments de dos punts verds, un doble error no és per tant en general corregible. Els punts negres no serveixen a res i ocupen lloc. Presenten una redundància inútil.

Estructures matemàtiques

Article principal: cos finit

Fitxer:Ferdinand Georg Frobenius.jpg

Frobenius initiateur de la théorie des corps finis

El problema de crear una bona geometria, òptima, ràpida i poc cara, demana que s'estructuri l'espai dels codis. Aquestes estructures es construeixen essencialment amb eines matemàtiques. La utilització dels cossos finits és gairebé universal. Un d'aquests cossos finits es fa servir amb especial intensitat, és el cos notat F₂ que correspon al cos de dos elements: 0 i 1. La teoria dels cossos finits arrenca pels treballs de Frobenius (1849 – 1917). Fa servir la teoria de Galois per explicitar el seu comportament. Els seus treballs són la base de nombrosos desenvolupaments de la teoria dels codis correctors. Aquest cossos resulten particularment adequats pels següents motius:

• Corresponen a estructures discretes en oposició a les estructures contínues. En conseqüència són més senzilles de implementar i modelar amb els circuits de l'electrònica digital i els algorismes informàtics.

• Constitueixen la base a partir de la qual es fan desenvolupaments. La teoria dels espais vectorials permet la creació de geometria útil. L'àlgebra lineal s'adapta per a la mesura del concepte abstracte equivalent al volum de les redundàncies inútils, això serveix de suport a tota una família de codis correctors: els codis lineals. L'anell dels polinomis amb coeficients en un cos finit és ric en propietats. Permet generalitzar la noció de prova del nou amb notables millore (veure l'article checksum). En aquest cas, si bé la detecció d'alteracions és possible, la correcció automàtica no ho és. Els polinomis tenen propietats anàlogues, i la localització dels errors esdevé possible. A demés, la multiplicació és particularment fàcil. Correspon a la dels enters sense el problema de portar-ne. Ara bé, en informàtica, el portar-ne representa el factor amb més incidència en el temps de càlcul. Molts codis correctors es fonamenten en les propietats dels polinomis, s'agrupen sota el nom de codi cíclic. Finalment, l'aritmètica moderna utilitza àmpliament els cossos finits, a través d'eines com les funcions el·líptiques. Si bé demanen un nivell d'abstracció elevat, també permeten obtenir resultats que d'altra manera serien difícils. Es fan servir per certs codis correctors, com al de Goppa, la seva importància industrial no obstant això, ara per ara, encara és feble.

Formalització del problema

Alfabet

Per tal de precisar les qüestions que es formula la teoria dels codis, i els problemes que troba, l'article considera el cas d'un canal discret. La informació a transmetre pot ser vista com una successió x de símbols agafats d'un conjunt finit (es tracta molt sovint de bits, per tant del conjunt format pel 0 i l'1).

• Un alfabet és un conjunt finit no buit, els seus elements s'anomenen lletres o símbols.
• Un missatge o una paraula és un conjunt de valors de l'alfabet, correspon a una successió de lletres.

L'objectiu d'un codi corrector és la transmissió fiable d'un missatge. En aquest article els alfabets són notats A o A', el cardinal d'un alfabet (el nombre de lletres que té) és notat q, i un missatge m.

Codi en bloc

En el cas general, els missatges a transmetre no tenen longitud fixa. Aquesta situació es dóna, per exemple, en a una comunicació telefònica. Per contra, és més senzill desenvolupar un codi corrector per a missatges de longitud fixa.

La solució consisteix en segmentar la dificultat. Al principi, és tractat el cas d'un missatge de longitud fixa o bloc. Per al cas general, una solució senzilla consisteix en concatenar una successió de blocs. El mètode més estès, ja que és el més eficaç és la del codi de convolució.

• La longitud d'un missatge designa el nombre de lletres que conté.
• Un codi corrector en bloc és un codi corrector que tracta els missatges de longitud fixa.

En el que segueix de l'article, la longitud d'un missatge és anotat k. El conjunt dels missatges és anotat E i el seu cardinal M. M és un enter inferior o igual a q^k.

Codificació

Com s'ha dir al paràgraf redundància i fiabilitat, no sempre és assenyat transmetre el missatge m i prou. L'afegitó d'una redundància pot ser pertinent. Per assolir aquest objectiu, es construeix una funció φ [[funció injectiva|injectiva] de E en un conjunt F, el que es transmet és φ (m) i no m La injectivitat és necessària, ja que si no dos missatges diferents no serien encara més diferents pel receptor. F és el conjunt de les successions finites de longitud n un enter estrictament positiu amb valors a A' un alfabet. En el cas general l'alfabet de F difereix del de E.

Abans de la transmissió, el missatge es codifica, és a dir que és transformat en una altre successió y=φ(x) de símbols. Llavors, es transmet y per un canal sorollós que eventualment pot modificar-lo i donar y'.. Per acabar, un descodificador intenta trobar el missatge x a partir de y'. Quan y difereix de y', es parla d'error(s) o d'alteració(ons).

• L'aplicació φ de E en F s'anomena codificació.
• La llargada n de les successions de F s'anomena dimensió del codi o simplement dimensió.
• L'imatge φ(E), subconjunt de F s'anomena codi.
• Una paraula del codi és un element del codi.

Exemples de codis en bloc

Codi de repetició

Article principal: Codi de repetició

Un exemple senzill és el del codi de repetició. La cas estudiat aquí és el d'un codi binari, és a dir que els dos alfabets A i A' coincideixen i són iguals a {0,1}. La longitud del codi és igual a un i la dimensió a tres.

L'aplicació φ es defineix sobre els valors: 0 et 1, per una triple repetició del missatge. De manera formal, s'obté:

$\varphi (0)=000\quad et\quad \varphi (1)=111$

Si es produeix una única alteració, llavors un sistema de vot(guanya la majoria) permet trobar el missatge d'origen. Aquest codi corrector té l'avantatge de no només detectar un error, sinó també de permetre una correcció automàtica. Per contra, és car, és a dir que la seva dimensió és elevada respecte a la longitud de les paraules transmeses.

Suma de control o checksum

Article principal: Checksum

Codi de longitud dos amb un bit de paritat

Missatges = E	Codis = φ(E)
00	000
01	101
10	110
11	011

A un altre exemple el dóna la suma de control. L'objectiu aquí no és tant la correcció automàtica sinó la detecció d'un únic error. Els dos alfabets són binaris, els missatges són de longitud dos i el codi de dimensió tres.

La codificació consisteix a afegir un bit de paritat, que val zero si la suma de les lletres és parell i un en el cas contrari. La taula de correspondència de la codificació ve donada a la dreta.

La figura de l'esquerra és una il·lustració geomètrica del codi. Representa el conjunt d'arribada F. Les paraules del codi són en verd. Un únic error correspon a un desplaçament sobre el cub al llarg d'una aresta. En aquest cas, el receptor rep un punt negre la suma de totes les lletres del qual és un enter senar. Per tant es possible determinar l'existència d'un error.

Per contra, un punt negre és sempre a prop de tres punts verds, el receptor no disposa doncs de cap mitjà per a una correcció automàtica.

Aquesta tècnica és generalitzable a d'altres alfabets i per a codis d'una longitud qualsevol. És econòmica, és la raó per la qual és àmpliament utilitzada. Per contra, i a diferència de l'exemple precedent, la correcció imposa una nova transmissió.

Redundància i fiabilitat

Distància de Hamming

Article principal: Distància de Hamming

hipercub binari de dimensió quatre

El concepte que més es fa servir per a la modelització de la redundància és el de la distància de Hamming. A cada dues paraules del codi, els hi associa el nombre de lletres en que difereixen.

• La distància de Hamming entre "gatet" i "cases" és 3.

La figura de dreta il·lustra un cas àmpliament estes a la indústria, aquell on els caràcters de l'alfabet són binaris. En l'exemple escollit, les paraules estan composades per quatre caràcters. La distància entre 0110 i 1110 és igual a un ja que és necessari recórrer un segment del gràfic per ajuntar les dues paraules. Tambéus poseu fixar en què les dues paraules difereixen només pel seu primer caràcter. El mateix enfocament mostra que la distància entre 0100 i 1001 és igual a tres.

Ce concept permet la définition suivante :

• La distance minimale d'un code correcteur est la plus petite distance au sens de Hamming entre deux mots du code.

Cette définition permet de formaliser les trois paramètres les plus important d'un code en blocs.

• Les paramètres d'un code en blocs sont la longueur du code n, le nombre M de mots du code et la distance minimale δ. Ils sont en général noté {n, M, δ}

Code parfait

Illustration d'un code parfait

Usuellement, on considère que le mot de code émis est celui se trouvant le plus près du mot reçu, ce qui revient à supposer que le minimum de lettres a été modifié. Ce procédé conduit à une erreur de décodage chaque fois que l'erreur est supérieure à la capacité corrective du code. La question naturelle est celle de la valeur de t correspondant au nombre maximum d'erreurs corrigibles.

Une interprétation géométrique donne un élément de réponse. les boules fermées de rayon t centrées sur les mots de code doivent être disjointes. La capacité de correction d'un code correspond au plus grand entier t vérifiant cette propriété, c'est aussi le plus grand entier strictement plus petit que δ/2. Elle permet de définir une première majoration, appelée borne de Hamming :

$M\leq {\frac {q^{n}}{V_{t}}}\quad avec\quad V_{t}=\sum _{i=0}^{t}{n \choose i}(q-1)^{i}$

La figure de gauche correspond à une configuration idéale, correspondant au cas où les boules fermées de rayon t et de centre les mots du code forment une partition de l'espace F. Les points du code, en vert, sont espacés d'une distance de cinq entre eux. Si la transmission ne produit jamais plus de deux altérations, alors les erreurs sont toutes corrigibles. Les points à une distance de un d'un mot de code sont en bleu, ceux à une distance de deux en rouge et la frontière des boules est indiquée en vert. Il n'existe aucune redondance inutile, le code est le plus compact possible pour garantir la correction certaine de t erreurs. Pour de tels codes, la majoration de la borne de Hamming est une égalité. Ils sont dit parfaits. L'exemple le plus simple est celui de Hamming binaire de paramètres [7,4,3].

Théorie algébrique des codes en blocs

Si l'analyse qu'apporte la distance de Hamming et les codes parfaits propose un cadre permettant d'évaluer l'efficacité d'un code, elle n'offre pas de solution pratique pour en construire.

La solution consiste à équiper les ensembles E et F de structures algébriques plus riches. Pour cela, les alphabets A et A' sont identifiés et munis d'une structure de corps fini. Le cas le plus fréquent consiste à choisir le corps F₂ ou l'une de ses extensions finies. Ce corps correspond à l'alphabet binaire dont les tables d'addition et de multiplication sont données ci-dessous:

+   0   1   0   0  1  1   1  0

.   0   1   0   0  0  1   0  1

Ce corps, ou ses extensions sont adaptés à un traitement informatique, qui, dans sa grande généralité travaille sur l'alphabet binaire.

Codes linéaires

Plantilla:Article détaillé Si les alphabets sont un même corps finis E et F héritent naturellement d'une structure d'espace vectoriel. Choisir alors l'application d'encodage φ une application linéaire simplifie grandement la problématique.

Les paramètres d'un code linéaire sont notés de manière légèrement différente de ceux des codes quelconques. L'espace E est vectoriel, il est décrit uniquement par sa dimension, correspondant à la longueur du code. Ils sont notés [n,k, δ].

Peu de codes linéaires sont parfaits, et ils sont soit de petites dimensions soit de petite distance minimale. Une autre majoration, plus générale et de même nature que la borne de Hamming existe :

• La majoration suivante est vérifiée pour tous les codes linéaires. Elle se nomme borne du singleton :

$n-k\geq \delta -1$

Si la borne est atteinte, on parle alors de code MDS pour maximum distance séparable.

Matrice génératrice

Plantilla:Article détaillé L'encodage est obtenu par l'application d'une matrice, dite matrice génératrice. Elle est toujours équivalente à une forme particulièrement simple, appelée code systématique, les premières coordonnées d'un mot du code correspondent au message, les dernières décrivent la redondance, elles sont appelées sommes de contrôle ou, dans le cas d'un code cyclique contrôles de redondance cyclique.

Matrice de contrôle

Plantilla:Article détaillé La validation du décodage est encore simplifiée. Il existe une application linéaire de F dans un espace de dimension n -k ayant comme noyau exactement le code. Sa matrice est dite de matrice de contrôle. Dans le cas, le plus fréquent dans l'industrie, du code systématique, la matrice de contrôle s'obtient directement à partir de la matrice génératrice et elle possède encore une forme particulièrement simple.

Valider un message reçu revient à vérifier que l'application de la matrice de contrôle à ce message est bien égale au vecteur nul.

Syndrome et décodage

Plantilla:Article détaillé La linéarité du code assure un décodage aisé. Si un message x est reçu, alors la détection d'erreurs est réalisée par la matrice de contrôle H. En effet, des altérations détectables ont eu lieu si et seulement si H.^tx est différent du vecteur nul. Si le nombre d'erreurs présentes dans le message est inférieur à t, le nombre d'altérations assurément détectables, alors H.^tx possède un unique antécédent e dans la boule fermée de centre le vecteur nul et de rayon t. Le message corrigé est x - e. Le vecteur H.^tx est appelé syndrome.

Dans le cas où le nombre d'erreurs est supérieur à t il existe plusieurs antécédents de poids minimal et les altérations ne sont plus assurément corrigibles. La solution idéale consiste à demander une nouvelle transmission.

Si le nombre de syndromes est petit, une table de correspondance entre les syndromes et leurs antécédents de plus petits poids est envisageable. Une telle table est nommé tableau standard et le décodage associé décodage par tableau standard. Si l'espace des syndromes est trop vaste, il est nécessaire de calculer son antécédent à la réception du message altéré.

Codes cycliques

Plantilla:Article détaillé Ces codes sont plus compliqués et reposent sur l'utilisation des propriétés des polynômes dans un corps fini. Le contrôle de redondance cyclique (CRC pour cyclic redundancy check) consiste à considérer un bloc de données comme la représentation des coefficients d'un polynôme que l'on divise ensuite par un polynôme fixe et prédéterminé. Les coefficients issus de cette division constituent le CRC et servent de code correcteur. La vérification des données se fait en multipliant le polynôme fixe par les coefficients du CRC et en comparant le résultat avec les données. On peut également calculer le CRC des données reçues et comparer avec le CRC reçu.

Autres codes

Les structures utilisées dans les codes correcteurs ont tout d'abord été très simples (par exemple celle d'espace vectoriel), puis se sont complexifiés avec une meilleure compréhension des problèmes théoriques. La théorie des codes correcteurs en arrive même à utiliser la géométrie arithmétique pour construire des codes.

Quelques codes correcteurs

Voici différents types de codes correcteurs :

• Code de Hamming
• Code de Golay
• Code de Reed-Müller
• Code de Goppa
• Code de Xing
• Code de Reed-Solomon

Quelques applications typiques

La transmissions d'informations peut-être sujet à des perturbations. Voici quelques applications touchés par ces perturbations :

• les téléphones cellulaires sont mobiles, relativement peu puissants, et souvent utilisés soit loin des antennes relais, soit dans un environnement urbain très bruyant du point de vue électromagnétique;
• les sondes spatiales n'ont pas à leur disposition d'énormes quantités d'énergie pour émettre des messages, se trouvent à des distances astronomiques, et leur antenne, même si elle est orientée le mieux possible, n'est pas parfaite;
• en cas de conflit armé, les communications adverses sont une des cibles privilégiées pour le brouillage et la guerre électronique
• les images disque contiennent pour certains formats (par exemple Mode 2 Form 1) des codes EDC et ECC pour contrôler les données gravées, et cela par secteur.

Différences entre un code correcteur et un code d'authentification

Le théorie des codes correcteurs s'intéresse à des perturbations aléatoires ou suivant une distribution particulière. Il n'y a pas d'"intelligence" dans ce bruit dans le sens où il ne s'agit pas d'une tentative frauduleuse de perturbation de ligne mais le résultat d'un phénomène physique inhérent au canal de transmission. Les codes d'authentification sont au contraire utilisés pour contrer un adversaire intelligent qui va tenter de modifier les données selon une procédure particulière qui s'éloigne du bruit sur la ligne. Les buts et les conditions de fonctionnement sont donc différents. Le premier concept est lié à la théorie de l'information alors que le deuxième est du ressort de la cryptologie et ne vise pas à rétablir l'information, tout au plus confirmer que l'information est valide.

Toutefois, dans le cas d'un brouillage volontaire (guerre électronique), les deux notions s'approchent puisque il faut éviter que l'attaquant réduise les capacités de transmission tout en assurant l'authenticité des informations.

Voir aussi

• Limite de Shannon
• Turbo code
• Méthode de décodage
• Chipkill

Bibliographie

• B. Martin - "Codage, cryptologie et applications" - (éd. Presses Polytechniques et Universitaires Romandes (PPUR), 2004) - 354 p. - ISBN 978-2-88074-569-1
• J.-G. Dumas, J.-L. Roch, E. Tannier et S. Varrette - "Théorie des codes (Compression, cryptage, correction)" - (éd Dunod, 2007) - 352 p. - ISBN 978-2-10-050692-7

Liens externes

• (francès) Polycopié du cours dispensé à l'ENSIMAG

* ca:Detecció d'errors