Un codi perfecte per a màxim distància separable (o MDS) és un concepte de la teoria dels codis que tracta més específicament dels codis correctors.
Un codi corrector és un codi que permet al receptor detectar i/o corregir alteracions en el missatge produïdes durant la transmissió o a l'emmagatzematge. Això és possible gràcies a una redundància de la informació. Un codi s'anomena perfecte si no conté cap redundància inútil. El concepte correspon a un criteri d'optimalitat. Un codi s'anomena MDS (de màxima distància separable) si verifica un altre criteri d'optimalitat: expressar-se en el context codis lineals.
Existeixen nombrosos codis MDS. Les sumes de control en són els exemples més senzills, es poden citar també codis cíclics com els BCH o els de Reed-Solomon. Els codis perfectes són més rars, es poden citar per exemple els codis de Hamming o els codis de Golay, binari de longitud 23 i ternari de longitud 11..
Context Codi corrector
Els codis correctors tenen el seu origen en un problema molt concret vinculat a la transmissió de dades. En certs casos, una transmissió de dades es fa utilitzant un canal de comunicació que no és completament fiable. Les dades, quan circulen sobre aquesta via, són susceptibles de patir alteracions. L'objectiu d'un codi corrector és l'aportació d'una redundància a la informació de tal manera que l'error pugui ser detectat o ser corregit.
Recordant breument la formalització d'un codi. Un missatge és una paraula formada de 'k caràcters agafats d'un alfabet A, notem E el conjunt dels missatges. Aquest missatge es codifica en una paraula fent servir una aplicació injectiva, la paraula que codifica el missatge conté n lletres d'un alfabet A' no necessàriament igual a A. Dient q al cardinal dA i F al conjunt d'arribada de φ. F és el conjunt de les paraules formades per n caràcters agafades d'un alfabet de q elements, F té doncs cardinal qn. El conjunt φ(E) està inclòs en F i s'anomena codi i un element d'aquest conjunt s'anomena una paraula del codi. La longitud del codi correspon a k, el nombre de caràcters que constitueixen el missatge. Aquestes notacions es faran servir al llarg de tot l'article.
Distància de Hamming
miniatura|hipercub binari de dimensió quatre Un concepte essencial en la teoria dels codis correctors és el de la distància d'Hamming. A dues paraules del codi, els associa el nombre de caràcters 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.
En l'exemple de la figura, l'alfabet és un cos finit, està en efecte dotat de dues lleis: una d'additiva i l'altra multiplicativa. Això confereix al conjunt una estructura d'espai vectorial. En aquest cas allà, la distància deriva d'una pseudonorma anomenada pes de Hamming que associa a un vector el nombre de coordenades no nul·les. La distància de Hamming entre dues paraules és llavors igual al pes de la seva diferència.
Definició i exemple Definició miniatura|Illustració d'un codi perfecte L'objectiu d'un codi corrector és la capacitat de detecció o de correcció d'errors, el mitjà utilitzat és la redundància (vegeu codi corrector). Usualment, es considera un enter t corresponent al nombre d'errors màxim que pot arrossegar la transmissió. Si les boles tancades de centre les paraules del codi i de radi t no s'intersecten pas, llavors es poden corregir t errors. Els punts fora d'aquestes boles arrosseguen un engrandiment inútil de l'espai F. Lo ideal seria que les boles formessin una partició de F.
La figura de la dreta correspon a una configuració d'aquest tipus. Els punts del codi de color verd, estan espaiats entre ells una distància de cinc. Si la transmissió no produeix mai més de dues alteracions, llavors tots els errors són corregibles. A més, no existeixen punts fora de les boles tancades de centre els punts del codi i de radi dos, és a dir de redundància inútil. Els punts a una distància un del codi són els de color blau i aquells a una distància dos de color vermell.
En resum, l'espai està completament farcit per les boles tancades de radi dos i de centre els punts del codi, a més tenen una intersecció buida entre elles. Aquest concepte condueix a la definició següent:
Un codi lineal s'anomena perfecte si i només si existeix un valor t tal que les boles tancades de centre les paraules de codi i de radi t formen una partició de l'espai.
Exemples Cas trivial Si la longitud del codi és un, és a dir si l'espai E no conté més que un caràcter el codi en un alfabet d'un caràcter és trivialment perfecte. Tanmateix l'únic missatge que pot ser transmès és sempre el mateix caràcter, lo que fa el codi poc interessant.
En el cas on l'aplicació de codificació és la identitat, llavors el codi continua sent perfecte, ja que les boles tancades de centre els punts del codi i de radi zero formen una partició de F, aquí igual a E. El codi continua sent poc interessant, ja que només zero errors poden ser corregits. Es parla llavors de codi trivial.
Codi de repetició Sigui A l'alfabet binari, constituït pels caràcters 0 i 1 i es considera el codi de repetició de dimensió tres i de longitud un. Els missatges estan constituïts per un caràcter, per exemple 0, els codis per una triple repetició del caràcter, sigui 000 en l'exemple. Com que l'alfabet no conté més que dos caràcters, dos almenys sobre tres dels caràcters d'un element de F són iguals, en conclusió tota paraula de F és a distància un d'una paraula del codi. A més, cap paraula de F no és a una distància de més d'un d'una única paraula del codi, el que demostra que aquest codi és perfecte. Tanmateix aquesta propietat canvia si el codi conté més de dos caràcters, en efecte existeixen elements de F constituïts de tres caràcters diferents i, per tant, a distància de dues de tres paraules diferents del codi i a distància de un de cap paraula del codi.
Codi de Hamming
miniatura|Description du code de Hamming binaire de paramètre [7,4,3] Els codis correctors realment utilitzats a la indústria són més complexos que els precedents. Els més senzills són els codis de Hamming i més particularment el codi binari de Hamming de paràmetres [7,4,3].
És un codi de dimensió set, és a dir que el receptor rep set bits, de longitud quatre és a dir que una vegada desxifrat, el missatge conté quatre caràcters i la distància mínima entre cada paraula de codi és tres.
La figura de dreta és una representació gràfica d'aquest codi. El missatge és la paraula d1d₂d₃d₄. La paraula del codi està constituïda de tres sumes de control p1p₂p₃, després dels quatre caràcters de la paraula del missatge. El valor de pi és igual a zero si la suma dels tres caràcters del missatge incloses en el seu cercle sobre la figura és parella i un si no.
Fixeu-vos que la suma dels elements de cada cercle és parell si i només si l'element és una paraula del codi. A més, cada element de F és a una distància u d'una paraula del codi. En conseqüència, aquest codi és perfecte i posseeix una capacitat màxima de correcció dun error.
Suma de control
miniatura|esquerra|Codi de longitud dos amb un bit de paritat Missatges = ECodis = φ(E) 00 000 01 101 10 111 11 011 A un altre exemple més ambigu el subministra la suma de control. L'objectiu aquí no és 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 dels caràcters és parell i u en el cas contrari. La taula de correspondència de la codificació es dona 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 de color 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 del qual la suma de tots els caràcters és un enter senar. És doncs possible determinar l'existència d'un error.
En el sentit general de la definició de més amunt, un codi de control no és perfecte, les boles de radi zero no contenen cap punt negre i cada punt negre és a tres boles de radi u diferents. Per contra, en el sentit de la fita de Singleton que es descriurà més avall, per als codis lineals, és MDS.
Cas general Capacitat de correcció i distància mínima Una primera qüestió que apareix en l'anàlisi d'un codi és el valor i el significat del paràmetre t utilitzat en la definició del codi perfecte. el valor t correspon al major enter tal que les boles tancades de radi t i de centre les paraules del codi no s'intersecten pas dos a dos:
Si δ és la distància mínima entre dues paraules del codi, la desigualtat triangular mostra que si t és estrictament inferior a δ/2, llavors la intersecció de les boles tancades de centre les paraules del codi i de radi t tenen una intersecció buida. En efecte, si m una paraula de F fos element de dues boles tancades de centre c i c' i de radi t llavors:
El que implica que c i c' són iguals per definició de la distància mínima δ.
Recíprocament, es mostra que si t és superior o igual a δ/2 llavors existeixen almenys dues boles tancades de radi t i de centre dos punts del codi diferents d'intersecció no buida. La funció distància de Hamming, pren els seus valors en un conjunt finit doncs s'ha assolit el mínim. Siguin c i c' dues paraules del codi tals que d(c, c') sigui igual a δ, on δ, designa la distància mínima. Les dues paraules c i c' difereixen per δ coordenades. Sigui m la paraula que té les mateixes coordenades que c excepte per a les t primeres de les coordenades que difereixen entre c i c' on m posseeix les coordenades de c' , m és a una distància de t de c i a una distància inferior o igual a t de c' , el que permet què concloure que: El major valor t tal que les boles tancades de centre les paraules del codi i de radi t tinguin una intersecció buida és el major enter estrictament inferior a δ /2.
Fixeu-vos a més, que el major nombre d'errors corregibles de manera certa és igual al valor t. En efecte, un error és corregible de manera certa només si existeix una única paraula del codi a prop del missatge transmès, el que correspon a la definició del paràmetre t.
Fita de Hamming Un enfocament per determinar el nombre de redundàncies necessàries a la correcció de t errors és el recompte. És possible calcular el cardinal de l'espai F, el d'una bola tancada de radi t per a la distància de Hamming i, per tant, el nombre màxim de missatges transmissibles pel codi amb una capacitat de correcció de t errors.
L'espai F està format per paraules de n caràcters agafats d'un alfabet que conté d caràcters. Conté per tant d n elements.
Tot seguit es calcula el nombre de punts a una distància de Hamming i d'un punt c donat. El conjunt dels punts a una distància i de c és aquell que conté les paraules que tenen i coordenades diferents de c. A cada punt del conjunt li correspon una subclasse de i elements escollits entre n. El nombre de conjunts d'aquesta naturalesa correspon a li-èsim coeficient binomial de rang n. Per a cada element del conjunt existeixen d - 1 caràcters possibles. Se'n dedueix que, si Vt designa el cardinal d'una bola tancada de radi t:
Perquè el codi pugui corregir t errors, aquestes boles han de ser disjuntes. El cardinal de la seva unió és igual a M. Vt, on M designa el cardinal del codi. Ara bé, aquesta unió no pot tenir un cardinal estrictament superior al de l'espai F, el que dona lloc a la definició i a la proposició següent: