Codi lineal

Un codi lineal en matemàtiques, més precisament a la teoria dels codis, és un tipus de codi bloc amb propietat d'àlgebra lineal. Tot i que habitualment es parla només de «codi lineal», també es coneixen com a codis bloc lineals. Està estructurat com un subespai vectorial sobre un Cos finit. L'espai utilitzat sovint és F₂ⁿ llavors s'anomena codi lineal binari. Com qualsevol codi bloc, queda descrit per tres paràmetres: [n, k, δ]. n descriu la dimensió de l'espai que el conté, i s'anomena longitud del codi. k representa la dimensió del codi, corresponent a la longitud de les paraules una vegada descodificades. Finalment, δ descriu la distància de Hamming mínima del codi, o el nombre de símbols diferents de les dues paraules codi més semblants. Els codis lineals representen l'essència dels codis correctors utilitzats a la indústria. Aquest enfocament cobreix tant els codis que proposen la simple detecció de l'error (ARQ), com els que codis permeten la correcció dels errors (FEC).

La linealitat és una propietat desitjada en els codis correctors, donat que ofereix càlculs molts senzills i ràpids per a codificar i descodificar. L'objectiu dels codis correctors és permetre la correcció d'errors després de la transmissió d'un missatge. Aquesta correcció es fa possible gràcies a afegir informació redundant d'una manera intel·ligent. El missatge se submergeix en un conjunt més gran, la diferència de mida conté la redundància. Un exemple simple és el del codi de repetició: el missatge es codifica enviant-lo n vegades, i la descodificació es fa per majoria. Si per exemple, k=3, el conjunt de paraules que es poden rebre és de dimensió triple a la del missatge inicial.

Recordant els elements base de la formalització. Existeix un conjunt E constituït de successions de longitud k, és a dir que a partir del rang k, tots els valors de la successió són nuls, i amb valors en un alfabet. Aquests elements són l'espai dels missatges que es desitja comunicar. Per proveir el missatge de la redundància desitjada, existeix una applicació φ injectiva de E amb valors en F, l'espai de les successions de longitud n amb valors en un alfabet. La funció φ s'anomena codificació, φ(E) s'anomena el codi, un element de φ(E) paraula del codi, k la longitud del codi i n la dimensió del codi.

Per poder fer servir la potència de les eines matemàtiques, pot ser assenyat utilitzar les estructures algebraiques. Els alfabets de E i F s'escullen com un mateix cos finit. Els elements de E (resp. F) són les successions finites de longitud k (resp. n), E i F hereten naturalment una estructura d'espai vectorial de dimensió finita i una base canònica, la de l'espai de les successions finites amb valors en un cos. L'aplicació codificació s'escull lineal.

L'espai F té una distància anomenada distància de Hamming que deriva d'una pseudo-norma, el pes de Hamming. El pes de Hamming p d'un punt de F correspon al nombre de les seves coordenades no nul·les. La distància de Hamming entre dos elements de F és el pes en el sentit de Hamming de la seva diferència.

Els codis lineals formen una família molt àmplia dins dels codis detectors o correctors. Dins dels codis lineals hi trobem els codis cíclics. Aquests tenen una propietat interessant per a la implementació eficient en hardware, la més popular de totes, és el tipus de checksum CRC.

Si bé el marc d'utilització és àmpliament emprat, no respon no obstant això a la totalitat de les necessitats. Es poden citar dos grans temes, poc tractats per la teoria dels codis lineals. Un bon codi que respon a un criteri d'optimalitat, s'anomena perfecte, i entre altres propietats, aprofiten al màxim els símbols de redundància inserits. Tot i que no hi ha un mètode genèric per a trobar-los, està demostrat que només n'hi ha tres tipus: els codis de Hamming, que responen a una relació determinada entre n i r. Són infinits i es poden trobar en qualsevol base: binària, ternària, etc. El segon tipus de codi perfecte és el codi de Golay binari, i el tercer, el codi de Golay ternari. Després de molts anys de recerca de nous codis perfectes per part de la comunitat científica, un finès va demostrar que els que s'havien trobat fins llavors eren els únics que existien.

Hi ha un mètode general per a la correcció d'errors, la descodificació per síndrome. Aquest mètode consisteix a crear una taula associant a cada error, la seva solució. La taula creix exponencialment amb el nombre de cartes susceptible de ser erronis. En el cas d'una àmplia capacitat de correcció, aquest enfocament ja no és operatiu.

La teoria dels codis cíclics respon a aquestes dues necessitats fent servir àmpliament les propietats dels cossos finits. Un codi cíclic és un codi lineal amb una estructura algebraica suplementària.

• Sigui p un nombre primer, d una potència de p, n un enter estrictament positiu i k un enter més petit que n. Un codi lineal C de Dimensió k i de longitud n és un subespai vectorial de F_dⁿ de dimensió k. Si d és igual a dos, el codi s'anomena binari si no es parla de codi lineal de base d.

Aquí, F_d designa l'únic cos amb d elements (vegeu l'article cos finit). Fixeu-vos que l'espaia vectorial de les successions amb valors en F_d s'identifica amb F_dⁿ. L'espai vectorial F_dⁿ està proveït de la distància de Hamming.

Com per als altres codis correctors, s'aplica la noció de paràmetres. Tanmateix, per tenir en compte l'estructura d'espai vectorial, es modifica una mica:

• Els paràmetres d'un codi es noten [n, k,δ] on δ designa la distància mínima entre dos punts del codi.

La definició de paràmetre per als codis lineals no és per tant compatible amb aquella, més genèrica utilitzada per als codis correctors. Per aquesta raó, tradicionalment els paràmetres d'un codi lineal es noten [n, k,δ] i els d'un codi corrector general {n, M,δ}.

Com anteriorment, existeix una aplicació de codificació: φ.

• L'aplicació de codificació φ d'un codi lineal és una aplicació lineal injectiva de F_d^k en F_dⁿ.

• La matriu G de F_dⁿ en les bases canòniques s'anomena matriu generadora del codi C. Verifica la igualtat següent:

${\displaystyle \forall x\in \mathbb {F} _{d}^{k}\quad x.G=\varphi (x)\in C\subset \mathbb {F} _{d}^{n}}$

El control que permet la comprovació i les eventuals correccions ve donat per una aplicació lineal h de F_dⁿ en F_d^n-k que té per nucli C. La teoria de l'àlgebra lineal mostra que tal aplicació existeix, n'hi ha prou per exemple amb considerar una projecció sobre un subespai suplementari de C paral·lel a C.

• La matriu H de h en les bases canòniques s'anomena 'matriu de control del codi C. Verifica les propietats següents:

${\displaystyle \forall x\in \mathbb {F} _{d}^{n}\quad H.^{t}x=0\;\Leftrightarrow \;x\in C}$

El terme matriu de paritat també es fa servir per designar la matriu de control.

Observació: Aquestes notacions es fan servir en la resta de l'article.

Totes les propietats de l'àlgebra lineal s'apliquen als codis lineals. Així el codi és alhora més fàcil d'implementar i de desxifrar. A més, les eines de generació d'espais vectorials com les estructures lineals duals o el producte tensorial permeten dissenyar nous codis, de vegades més adaptats a les restriccions industrials.

L'aplicació de codificació és lineal, per tant es representa i es calcula gràcies a la seva matriu generadora. Un codi està completament definit per la seva matriu generadora, de dimensió nxk. A més, com que les propietats del seu codi no depenen més que de la geometria φ(E). Si f és un isomorfisme de E, el codi definit per l'aplicació φof és el mateix que el de φ. El que dona lloc a la definició següent:

• Dos codis sobre un mateix alfabet F_d de longitud k definits per dues matrius generadores G i G' tals que existeix una matriu quadrada inversible P d'ordre k que verifica G =G' .P s'anomenen équivalents.

Existeix una forma particularment simple per a la matriu G:

• Un codi lineal la matriu generadora del qual posseeix per a les k primeres files una matriu identitat d'ordre k s'anomena codi sistemàtica.

L'article associat a aquest paràgraf demostrarà una propietat important:

• Tot codi lineal és equivalent a un codi sistemàtic.

Aquesta escriptura accelera i simplifica la codificació i la descodificació. La matriu pren llavors la forma següent:

${\displaystyle G={I_{k} \choose C}}$

Les coordenades de la matriu C corresponen a la redundància, el seu objectiu és la detecció i la correcció d'eventuals errors:

• Les n - k últimes coordinades d'una paraula del codi sistemàtic s'anomenen bits de control o de vegades suma de control.

En el cas lineal, el codi és un subespai vectorial de dimensió k. Llavors existeix una aplicació lineal exhaustiva de F en un espai de dimensió n - k que té per nucli exactament el codi:

• Una matriu de control d'un codi φ(E) és una matriu H de dimensió nxn - k tal que:

${\displaystyle x\in \varphi (E)\Leftrightarrow H.^{t}x=0}$

En el cas d'un codi sistemàtic, l'expressió de la matriu generadora ofereix immediatament la d'una matriu de control.

• En el cas d'un codi sistemàtic, si G és l'expressió d'una matriu generadora llavors l'expressió següent és la d'una matriu de control:

${\displaystyle si\quad G={I_{k} \choose C}\quad llavors\quad H=(-C\;I_{n-k})\;}$

Aquí, I_k designa la matriu quadrada identitat d'ordre k. Aquesta matriu ofereix una manera relativament simple de calcular la distància mínima:

• La distància mínima d'un codi lineal és igual a la dimensió del subespai vectorial més petit S de F generat per elements de la base canònica i tal que la restricció de la matriu de control a S sigui no injectiva.

En el cas d'un codi lineal, la distància de Hamming s'expressa com una distància procedent d'una pseudo-norma. El pes de Hamming, que a un codi li associa el nombre de coordenades no nul·les, juga aquí el paper de pseudonorma.

• Si ω designa el pes de Hamming per a un codi lineal C, llavors la distància de Hamming d queda definida per la fórmula següent:

${\displaystyle \forall x,y\in C\quad d(x,y)=\omega (x-y)\;}$

La linealitat de l'estructura subjacent introdueix una propietat directa:

• La distància mínima entre dos punts del codi és igual al mínim del pes de les paraules del codi no nul·les.

Per convèncer-se'n, n'hi ha prou amb fixar-se que si x i y són dues paraules del codi, llavors la seva diferència és també una paraula del codi.

El nombre màxim d'errors corregibles segur t es desprèn directament de la distància mínima δ. En efecte, t és el major enter estrictament inferior a δ/2. La situació ideal és on les boles tancades de centre les paraules del codi i de radi t formen una partició de F. Es parla llavors de perfecte.

• L'augment següent es verifica per a tots els codis lineals. Es diu fita de Singleton:

${\displaystyle n-k\geq \delta -1}$

Si la fita de Singleton s'assoleix, el codi s'anomena MDS.

L'estructura lineal del codi dona porta de manera natural a la noció de codi dual. Si l'espai vectorial que conté C està dotat d'una estructura dual amb l'ajuda del producte escalar canònic, llavors el codi C posseeix de manera natural un espai vectorial dual suplemantari.

• El codi dual d'un codi lineal C és el subespai suplementari ortogonal a C si l'espai està dotat del producte escalar canònic. És un codi d'igual longitud i de dimensió n - k. Sovint es nota ${\displaystyle \scriptstyle {C^{\perp }}}$. Un codi s'anomena autodual si és igual al seu dual.

En el cas d'un codi sistemàtic, cas al qual sempre és possible arribar, la matriu de control de C esdevé una matriu generadora del seu dual. N'hi ha prou llavors amb reordenar la base per obtenir un codi sistemàtic. Igualment una matriu generadora de C és una matriu de control del seu dual.

És possible calcular la distància mínima de ${\displaystyle \scriptstyle C^{\bot }}$ a partir de ${\displaystyle C}$, tanmateix no és suficient conèixer la de ${\displaystyle C}$: cal conèixer el polinomi enumerador dels pesos de ${\displaystyle C}$. Llavors la identitat de Mac Williams dona el de ${\displaystyle \scriptstyle C^{\bot }}$ d'on s'extreu de forma simple la distància mínima d'aquest últim.

L'àlgebra lineal ofereix múltiples tècniques diferents compatibles amb els codis. El producte tensorial n'és un exemple. A dos espais vectorials, n'associa un tercer isomorf a les aplicacions lineals del primer espai en el segon.

• Si C₀ (resp. C₁) és un codi lineal de paràmetre [n₀, k₀, d₀] (resp. [n₁, k₁, δ₁]), llavors el producte tensorial dels dos codis és un codi de paràmetre [n₀.n₁, k₀.k₁, δ₀.δ₁]. Aquest codi s'anomena codi producte de C₀ i C₁.

Permet corregir tota configuració que contingui menys de δ₀.δ₁/4 errors.

La tècnica més simple de tractament dels errors es limita a una validació. Si el missatge no és un element del codi, llavors es declara fals. En general, la tècnica de correcció és una nova demanda de transmissió. El mètode més freqüentment utilitzat consisteix a adjuntar al missatge un o diversos bits de control corresponents a la suma al cos finit dels coeficients del missatge. Aquesta tècnica és l'equivalent de la prova del nou. A risc d'augmentar el nombre de bits de control, aquest mètode pot fer créixer el seu nivell de fiabilitat. Si la probabilitat és prou forta per suposar que com a màxim hi pot haver un sol error en el missatge, llavors un bit de control compleix la condició. En el cas d'un únic bit de control, llavors els paràmetres del codi són [n, n - 1, 2]. Tal codi no pot procedir a la correcció de l'error per ell mateix. En efecte per a cada errors, existeixen n - 1 punts del codi que hi són propers. Es necessiten informacions suplementàries per a una autocorrecció.

La implementació és simple, el càlcul de la imatge del missatge per la matriu de control subministra la informació. Si la imatge és nul·la llavors el missatge correspon a un codi i és sense error, si no es detecta que hi ha un error en el missatge.

La qüestió és tractada aquí només en el cas dels codis sistemàtics. No només és la solució considerada per la indústria, sinó que, a més, tota altra configuració és equivalent a aquesta.

Al principi, és possible considerar només el problema del vector nul. El missatge rebut posseeix per tant com k primeres coordenades 0 i els bits de control c no tots nuls. Aquesta situació correspon a un error, ja que la imatge del vector nul per la matriu generadora no dona el vector nul i per tant els bits de control són tots nuls per a un codi que té les seves k primeres coordenades nul·les.

La correcció correspon al missatge m de pes de Hamming més petit i que té per imatge per la matriu de control -H.c . Si el nombre d'alteracions que ha generat el vector (0, c) és inferior a (δ - 1)/2, llavors existeix un únic m tal que H.m = -H.c . Aquí, H.c designa per abús del llenguatge el vector H.(0,c). El codi associat és m - c i el missatge inicial és m. Es verifica de fet que H.(m - c) = 0 i m - c és un codi. Llavors és possible, a cada valor de H.c , d'associar-li una correcció m.

• El valor H.(0,c) on H és una matriu de control sistemàtic i 'c un conjunt de bits de control no nuls s'anomena un syndrome.

En el cas general, si l és un missatge rebut que no és element del codi, la seva imatge per la matriu de control és un valor corresponent a un H.c donat. Resulta que m és la correcció més petita a aplicar a l per obtenir un codi. En efecte, H(l + m) és igual a H.c - H.c i la minimalitat és una conseqüència del paràgraf precedent.

La determinació del valor m per a un H.c depèn àmpliament de la tria del codi. Correspon al problema clàssic cobert per la programació lineal. En la pràctica, és rar que tals mètodes siguin utilitzats. Sigui perquè els bits de control són un nombre reduït, i la combinatòria és reduïda, sigui perquè l'espai és vast i el codi disposa d'altres propietats sovint polinòmiques i descrites a l'article codi cíclic.

La implementació, en la mesura que l'espai dels bits de control és reduït és en general realitzada per una taula de hachage. Aquesta taula estableix una bijecció entre cada síndrome i el missatge de pes mínim que té per a imatge per la matriu de control la síndrome.

• Una implementació de la correcció amb l'ajuda d'una taula de hachage subministra una bijecció entre les síndromes i els missatges de pes mínim s'anomena un descodificació per síndrome.

• 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

• Code correcteur C.I.R.C Arxivat 2006-11-27 a Wayback Machine. par J.P. Zanotti (francès)
• L'algèbre et la correction des erreurs par Dany-Jack Mercier Université Antilles-Guyane (francès)
• Code Linéaire Université de Bordeaux (francès)
• Cours de code par Christine Bachoc Université de Bordeaux (francès)
• Code correcteur par M. Coste, A. Paugam, R. Quarez Université de Lille (francès)