Codi perfecte

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

Article principal: 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 qⁿ. 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

Article principal: Distància de Hamming

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ó

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

Article principal: Codi de Hamming (7,4)

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 d₁d₂d₃d₄. La paraula del codi està constituïda de tres sumes de control p₁p₂p₃, després dels quatre caràcters de la paraula del missatge. El valor de p_i é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ó d'un error.

Suma de control

Article principal: Checksum

Codi de longitud dos amb un bit de paritat

Missatges = E	Codis = φ(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:

$t=\max \left\{r\in \mathbb {N} \;:\;\forall x,x'\in \varphi (E)\quad x\neq x'\Rightarrow B_{r}(x)\bigcap B_{r}(x')=\varnothing \right\}\quad amb\quad B_{r}(x)=\{y\in F:d(x,y)\leq r\}$

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:

$d(c,c')\leq d(c,m)+d(m,c')\leq t+t<\delta \;$

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 ⁿ 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 l'i-èsim coeficient binomial de rang n. Per a cada element del conjunt existeixen d - 1 caràcters possibles. Se'n dedueix que, si V_t designa el cardinal d'una bola tancada de radi t:

$V_{t}=\sum _{i=0}^{t}{n \choose i}(d-1)^{i}$

Perquè el codi pugui corregir t errors, aquestes boles han de ser disjuntes. El cardinal de la seva unió és igual a M. V_t, 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:

• Si M designa el cardinal del codi, llavors es verifica la següent desigualtat que s'anomena fita de Hamming.

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

Un codi és anomenat perfecte si i només si les boles tancades de centres les paraules del codi i de radi t formen una partició de F, això dona lloc a la proposició següent:

• Un codi és perfecte si i només si s'assoleix la fita de Hamming.

Cas lineal

Codi lineal

Article principal: codi lineal

Un codi lineal disposa d'una estructura algebraica més rica que la del marc general dels codis correctors. Els alfabets A i A' se'ls identifica 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 a l'alfabet binari del qual les taules d'addició i de multiplicació són les que es donen aquí davall:

+ 0 1 0 0 1 1 1 0

. 0 1 0 0 0 1 0 1

Els conjunts E i F estan proveïts de manera natural d'una estructura d'espai vectorial de dimensió respectivament k i n. Si F_d designa el cos finit de cardinal d on d és una potència d'un nombre primer p, llavors l'espai vectorial F s'identifica generalment amb F_dⁿ.

La distància entre dos punts de F correspon al nombre de coordenades no nul·les de la diferència entre els dos punts, a la base canònica, deriva doncs d'una pseudonorma. Un codi es descriu per tres paràmetres, notat [n, k, δ], n és la dimensió del codi, k la longitud del codi i δ la distància mínima entre dues paraules del codi. Aquestes notacions s'utilitzen en la resta de l'article.

Finalment, l'aplicació de codificació φ s'escull lineal, el codi és per tant un subespai vectorial.

Matriu de control

Existeix una aplicació lineal que té per nucli el codi. La seva matriu s'anomena H , aquí s'identifica amb la seva aplicació lineal. En el cas dels codis perfectes, té una propietat forta:

• Si el codi és perfecte, la restricció de H a la bola tancada de centre una paraula del codi i de radi t és bijectiva .

Les imatges de H que s'anomenen síndromes són bijectives amb els errors possibles del codi. Aquesta propietat ofereix una tècnica de descodificació senzilla, anomenada descodificació per síndrome. A més, ofereix una condició necessària i suficient per a caracteritzar un codi perfecte:

• La desigualtat següent que sempre és certa, és una igualtat si i només si el codi és perfecte:

$V_{t}=\sum _{i=0}^{t}{n \choose i}(d-1)^{i}\leq d^{n-k}$

Aquesta propietat és restrictiva, permet trobar una condició necessària per als paràmetres dels codis.

Codi de Hamming

Article principal: Codi de Hamming

Tot seguit se cerquen tots els codis perfectes de distància mínima igual a tres . El valor d t és llavors u i la igualtat de la inequació precedent pren ho és si m designa el valor n- k:

$1+n.(d-1)=d^{m}\quad dons\quad n={\frac {d^{m}-1}{d-1}}\quad i\;k={\frac {d^{m}-1}{d-1}}-m\quad jaque\;k=n-m$

De fet, és possible construir tots aquests codis, s'anomenen codis de Hamming.

• Els únics codis de distància mínima igual a tres són els codis de Hamming. Queden descrits pels paràmetres següents, si m és un enter estrictament positiu i d és el cardinal del cos finit alfabet:

Les seuls codes de distance minimale égale à trois sont les codes de Hamming. Ils sont décrits par les paramètres suivants, si m est un entier strictement positif et d est le cardinal du corps fini alphabet:

$\left[{\frac {d^{m}-1}{d-1}},{\frac {d^{m}-1}{d-1}}-m,3\right]$

Si m és igual a dos i d a dos es troba el codi de repetició de paràmetres [3,1,3]. Si m és igual a tres i d a dos, es troben els paràmetres [7,4,3] de l'exemple precedent.

Codis de Golay

Per a t = 2, l'equació esdevé:

$1+n.(d-1)+{\frac {n.(n-1)}{2}}.(d-1)^{2}=d^{m}$

L'única solució s'obté per a d = 3, n = 11 i m = 5, llavors k és igual a 6, s'obté un codi anomenat el codi de Golay ternari de paràmetre [11, 6, 5]. La bola unitat, així com l'espai dels síndromes conté 243 elements.

Per a t = 3 l'equació es complica, esdevé:

$1+n.(d-1)+{\frac {n.(n-1)}{2}}.(d-1)^{2}+{\frac {n.(n-1).(n-2)}{6}}.(d-1)^{3}=d^{m}$

La solució és encara única, s'obté per a d = 2, n = 23 i m = 11, llavors k és igual a 12, s'obté un codi anomenat el codi de Golay binari de paràmetre [23, 12, 7]. La bola unitat, així com l'espai dels síndromes conté 2048 elements.

No existeix pas cap altre codi lineal perfecte.

Fita de Singleton

Els codis perfectes lineals són massa poc nombrosos per satisfer les necessitats de la indústria, sovint es fa servir una altra desigualtat, menys constrenyedora:

• La desigualtat següent es verifica per a tots els codis lineals. S'anomena fita de Singleton:

$n-k\geq \delta -1$

En efecte, Sigui p. la projecció de F sobre l'espai vectorial engendrat pels k - 1 primers vectors de la base canònica, paral·lelament a l'espai vectorial engendrat pels vectors restants. L'aplicació po φ és necessàriament no injective, ja que la seva imatge és un espai vectorial de dimensió estrictament inferior al de E. Existeixen doncs almenys dues paraules del codi diferents que tenen les mateixes k - 1 primeres coordenades. Aquestes dues paraules del codi difereixen com a màxim en n - k + 1 coordenades, el que demostra la proposició.

S'associa una definició al cas en què s'assoleix la fita:

• El codi és MDS per la màxima distància separable si i només si s'assoleix la fita de Singleton

Aquesta fita correspon a un codi lineal òptim per als paràmetres n i k escollits, és a dir que un codi de dimensió n i de longitud k és MDS si no existeixen altres codis d'igual longitud i igual dimensió que tinguin una distància mínima més gran. Els codis de Reed-Solomon assoleixen aquesta fita. També ho són els codis construïts amb l'ajuda d'una suma de control, per contra, no són perfectes, ja que la distància mínima és igual a dos i un codi perfecte posseeix sempre una distància mínima senar. El codi de Hamming binari de paràmetres [7, 4, 3] no assoleix la fita de Singleton i no és per tant MDS, però és perfecte, la fita de Singleton no és doncs assolible per a un codi de dimensió 7 i de longitud 4.

Referències

• FJ MacWilliams & JJA Sloane The Theory of Error-Correcting Codes North-Holland, 1977
• A Spataru Fondements de la Théorie de l'Information Presses Polytechniques Romandes, 1991
• M. Demazure Cours d'algèbre Cassini, 1997
• 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

• (francès) Code correcteur C.I.R.C Arxivat 2006-11-27 a Wayback Machine. per J.P. Zanotti
• (francès) Code Linéaire Universitat de Bordeaux
• (francès) Cours de code per Christine Bachoc Universitat de Bordeaux
• (anglès) Jacksum (un programa de codi obert que permet calcular nombrosos controls per redundància