miniatura|Per netejar els errors de transmissió introduïts per l'atmosfera terrestre (a l'esquerra), els científics de Goddard van aplicar la correcció d'errors Reed-Salomon (dreta), que s'utilitza habitualment en CD i DVD. Els errors típics inclouen píxels que falten (blanc) i senyals falses (negre). La franja blanca indica un període breu quan la transmissió es va aturar. La detecció i correcció d'errors en informàtica i teoria de la informació és l'ús de mètodes per detectar i corregir errors en la transmissió i emmagatzematge de dades.G. J. Simmons, "A survey of Information Authentication". Contemporary Cryptology, The science of information integrity, ed. GJ Simmons, IEEE Press, New York, (1992) En el cas de la transmissió, això també inclou la retransmissió selectiva de segments de dades incorrectes. Els mètodes de detecció i correcció d'errors requereixen l'ús de bits redundants. En general, calen més bits redundants per la correcció que per la detecció d'errors.
É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 de 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 casos 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 dona 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 miniatura|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 què 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 lesborrament. En aquest context, i a diferència del paràgraf precedent, el missatge transmès té la indicació de què 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 servir 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 miniatura|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 se 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
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 d'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 (vegeu 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 mé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 a 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 dona, 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 a 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 a 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 qk.
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ó φ 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 altra 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ó.