Detector i corrector d'errors

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.^[1] 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 modifica

Descripció intuïtiva modifica

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 modifica

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 l'esborrament. 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 modifica

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 modifica

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 modifica

Alfabet modifica

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 modifica

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 q^k.

Codificació modifica

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ó.
La llargada n de les successions de F s'anomena dimensió del codi o simplement dimensió.
La imatge φ(E), subconjunt de F s'anomena codi.
Una paraula del codi és un element del codi.

Exemples de codis en bloc modifica

Codi de repetició modifica

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 modifica

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 dona 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 és 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 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 modifica

Distància de Hamming modifica

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 què 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 compostes 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.

Aquest concepte permet la definició següent:

La distància mínima d'un codi corrector és la distància més petita en el sentit de Hamming entre dues paraules del codi.

Aquesta definició permet formalitzar els tres paràmetres més important d'un codi en blocs.

Els paràmetres d'un codi en blocs són la longitud del codi n, el nombre M de paraules del codi i la distància mínima δ. En general notats {n, M, δ}

Codi perfecte modifica

Il·lustració d'un codi perfecte

Usualment, es considera que la paraula de codi emesa és aquella que està més prop de la paraula rebuda, el que significa suposar que s'ha modificat un mínim de lletres. Aquest procediment porta a un error de descodificació cada vegada que l'error és superior a la capacitat correctiva del codi. La qüestió natural és la del valor de t corresponent al nombre màxim d'errors corregibles.

Una interpretació geomètrica dona un criteri de resposta. les boles tancades de radi t centrades sobre les paraules de codi han de ser disjuntes. La capacitat de correcció d'un codi correspon al major enter que verifica aquesta propietat, és també el major enter estrictament més petit que δ/2. Permet definir una primera fita superior, anomenada fita 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 figura de l'esquerra correspon a una configuració ideal, el cas en què les boles tancades de radi t i de centre les paraules del codi formen una partició partició de l'espai F. Els punts del codi, en verd, estan espaiats una distància de cinc entre ells. Si la transmissió no produeix mai més de dues alteracions, llavors els errors són corregibles. Els punts a una distància d'un d'una paraula de codi són en blau, aquells en una distància de dos en vermell i la frontera de les boles s'indica en verd. No existeix cap redundància inútil, el codi és el més compacte possible per garantir la correcció certa de t errors. Per a tals codis, la fita superior de Hamming és una igualtat. S'anomenen perfectes. L'exemple més senzill és el de Hamming binari de paràmetres [7,4,3].

Teoria algebraica dels codis en bloc modifica

Si bé l'anàlisi que aporta la distància d'Hamming i els codis perfectes proposa un marc que permetent avaluar l'eficàcia d'un codi, no ofereix solució pràctica per construir-loe.

La solució consisteix a equipar els conjunts E i F amb estructures algebraiques més riques. Per això, els alfabets A i A' s'identifiquen amb i se'ls subministra una estructura de cos finit. El cas més freqüent consisteix a escollir el cos F₂ o una de les seves extensions finites. Aquest cos correspon té l'alfabet binari les taules d'addició i de multiplicació del qual es donen davall:

+	0	1
0	0	1
1	1	0

.	0	1
0	0	0
1	0	1

Aquest cos, o les seves extensions s'adapten a un tractament informàtic, que, en general treballa sobre l'alfabet binari.

Codis lineals modifica

Si els alfabets són ells mateixos un cos finit, E i F hereten de manera natural una estructura d'espai vectorial. Escollir llavors com aplicació φ de codificació una aplicació lineal simplifica molt la problemàtica.

Els paràmetres d'un codi lineal són notats de manera lleugerament diferent dels dels codis qualsevulla. L'espai E és vectorial, i queda descrit de manera única per la seva dimensió, que correspon a la longitud del codi. Aquests paràmetres són notats [n,k, δ].

Pocs codis lineals són perfectes, i són o bé de dimensions petites o bé de distància mínima petita. Existeix un altre augment, més general i d'igual naturalesa que la fita de Hamming:

La desigualtat següent es verifica per a tots els codis lineals. Es diu fita del singletó:

n-k\geq \delta -1

Si la fita es compleix en forma d'igualtat, es parla llavors de codi MDS per a màxima distància separable.

Matriu generadora modifica

La codificació s'obté per l'aplicació d'una matriu, anomenada matriu generadora. Sempre és equivalent a una forma particularment senzilla, anomenada codi sistemàtic, les primeres dades d'una paraula del codi corresponen al missatge, les últimes descriuen la redundància, s'anomenen suma de control o, en el cas d'un codi cíclic control de redundància cíclica.

Matriu de control modifica

La validació de la descodificació se simplifica. Existeix una aplicació lineal de F en un espai de dimensió n -k que té com a nucli exactament el codi. La seva matriu s'anomena matriu de control. En el cas, el més freqüent a la indústria, del codi sistemàtic, la matriu de control s'obté directament a partir de la matriu generadora i té una forma particularment senzilla. Validar un missatge rebut significa verificar que l'aplicació de la matriu de control a aquest missatge és igual al vector nul.

Descodificació per síndrome modifica

La linearitat del codi assegura una descodificació fàcil. Si es rep un missatge x, llavors la detecció d'errors es realitza per la matriu de control H. En efecte, les alteracions detectables han tingut lloc si i només si H.^tx és diferent del vector nul. Si el nombre d'errors presents en el missatge és inferior a t, el nombre d'alteracions detectables de forma assegurada, llavors H.^tx té un únic antecedent e a la bola tancada de centre el vector nul i de radi t. El missatge corregit és x - e. El vector H.^tx s'anomena síndrome. En el cas on el nombre d'errors és superior a t existeixen diversos antecedents de pes mínim i les alteracions no són ja corregibles amb seguretat. La solució ideal consisteix a demanar una nova transmissió. Si el nombre de síndromes és petit, una taula de correspondència entre les síndromes i els seus antecedents de pesos més petits és factible. Tal taula s'anomena taula estàndard i la descodificació associada descodificació per taula estàndard. Si l'espai de les síndromes és massa vast, cal calcular el seu antecedent al rebre el missatge alterat.

Codis cíclics modifica

Aquests codis són més complicats i descansen en l'ús de les propietats dels polinomis en un cos finit. El control de redundància cíclica (CRC per Cyclic Redundancy Check) consisteix a considerar un bloc de dades com la representació dels coeficients d'un polinomi que es divideix llavors per un polinomi fix i predeterminat. Els coeficients procedents d'aquesta divisió constitueixen el CRC i serveixen de codi corrector. La comprovació de les dades es fa multiplicant el polinomi fix pels coeficients del CRC i comparant el resultat amb les dades. També es pot calcular el CRC de les dades rebudes i comparar-lo amb el CRC rebut.

Altres codis modifica

Les estructures utilitzades en els codis correctors han estat al començament molt simples (per exemple l'estructura d'espai vectorial), després s'han complicat amb una comprensió millor dels problemes teòrics. La teoria dels codis correctors arriba fins i tot a utilitzar la geometria aritmètica per construir codis.

Alguns codis correctors modifica

Heus aquí diferents tipus de codis correctors:

Codi de Hamming
Codi de Golay
Codi de Reed-Müller
Codi de Goppa
Codi de Xing
Codi de Reed-Solomon

Algunes aplicacions típiques modifica

La transmissions d'informacions pot estar subjecte a pertorbacions. Heus aquí algunes aplicacions afectades per aquestes pertorbacions:

els telèfons mòbils, relativament poc potents, i sovint fets servir o bé lluny de les antenes, o bé en un medi ambient urbà molt sorollós des del punt de vista electromagnètic;
les sondes espacials no tenen a la seva disposició enormes quantitats d'energia per emetre missatges, es troben a distàncies astronòmiques, i la seva antena, fins i tot si s'orienta el millor possible, no és perfecta;
en cas de conflicte armat, les comunicacions enemigues són un dels blancs privilegiats per a la interferència i la guerra electrònica
els discs imatge contenen per a certs formats (per exemple Mode 2 Form 1) els codis EDC i ECC per controlar les dades gravades.

Diferències entre un codi corrector i un codi d'autenticació modifica

El teoria dels codis correctors s'interessa per pertorbacions aleatòries o que segueixen una distribució particular. No hi ha "intel·ligència" en aquest soroll en el sentit que no es tracta d'una temptativa fraudulenta de pertorbació de línia sinó el resultat d'un fenomen físic inherent al canal de transmissió. Els codis d'autenticació per contra es fan servir per oposar-se a un adversari intel·ligent que intentarà modificar les dades segons un procediment particular que s'allunya del soroll sobre la línia. Els objectius i les condicions de funcionament són doncs diferents. El primer concepte està vinculat a la teoria de la informació mentre que el segon és de l'àmbit de la criptografia i no busca restablir la informació, sinó confirmar que la informació és vàlida. Tanmateix, en el cas d'una interferència voluntària (guerra electrònica), les dues nocions s'apropen, ja que cal evitar que l'agressor redueixi les capacitats de transmissió tot assegurant l'autenticitat de les informacions.

Referències modifica

↑ G. J. Simmons, "A survey of Information Authentication". Contemporary Cryptology, The science of information integrity, ed. GJ Simmons, IEEE Press, New York, (1992)

Vegeu també modifica

Bibliografia modifica

B. Martin - "Codage, cryptologie et applications Arxivat 2007-12-12 a Wayback Machine." - (é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) Arxivat 2007-03-10 a Wayback Machine." - (éd Dunod, 2007) - 352 p. - ISBN 978-2-10-050692-7

Enllaços externs modifica

(francès) Polycopié du cours Arxivat 2008-09-15 a Wayback Machine. realitzat a l'ENSIMAG

[1] G. J. Simmons, "A survey of Information Authentication". Contemporary Cryptology, The science of information integrity, ed. GJ Simmons, IEEE Press, New York, (1992)

[1]