Codi de Hamming (7,4)

El Codi de Hamming (7,4) és un codi corrector lineal binari de la família dels codis de Hamming. A través d'un missatge de set bits, transfereix quatre bits de dades i tres bits de paritat. Permet la correcció de qualsevol error que afecti a un únic bit. És a dir que si, entre els set bits transmesos, un és alterat (un zero es fa un 1 o viceversa), llavors existeix un algorisme que permet corregir l'error, sigui quin sigui el bit alterat.

Va ser introduït per Richard Hamming (1915-1998) el 1950 en el marc del seu treball per als laboratoris Bell.

Història

Des de 1946 Richard Hamming treballava amb un model d'ordinador amb targetes perforades de poca fiabilitat. Si bé, durant la setmana, enginyers podien corregir els errors, els períodes festius com el cap de setmana les màquines s'aturaven invariablement degut als errors. La frustració^[1] de Hamming el va conduir a inventar el primer codi corrector veritablement eficaç.

Aquest període correspon al naixement de la teoria de la informació. Claude Shannon (1916 – 2001) formalitza aquesta teoria com una branca de les matemàtiques.^[2] Hamming desenvolupa. Hamming développe^[3] les premisses de la teoria dels codis i descriu la seva solució com un exemple.

Objectiu

Article principal: Codi corrector

L'objectiu del codi és la transmissió d'un missatge de quatre bits amb prou redundàncies perquè, fins i tot si es produeix una alteració, el receptor sigui capaç de corregir automàticament l'error. El missatge enviat és en conseqüència més llarg. En la pràctica conté set bits, quatre componen el missatge i els tres altres serveixen per detectar i per corregir l'error, en cas necessari.

L'error del que protegeix aquest codi és necessàriament limitat, si els set bits transmesos es modifiquen tots, és en va esperar de trobar el missatge original. La protecció contra la modificació d'un únic bit és de vegades més que suficient, era el cas de la situació de Hamming. Una modificació d'un únic bit, és a dir d'un forat no llegit sobre la targeta perforada o d'una absència de forat considerat com un forat és relativament rar. Suposant que aquesta situació es produeix sobre una sèrie de quatre de mitjana una vegada sobre mil. Llavors en cinquanta hores d'execució de programa, que utilitzen per exemple de l'ordre de mil sèries resulta una probabilitat de parada superior a un seixanta per cent. La probabilitat de trobar dos errors sobre una sèrie de set és inferior a un sobre cinc-cents mil. si els missatges són protegits pel codi, la utilització de mil sèries de longitud set posseeix, tenint en compte que només es produirà la parada si hi ha simultàniament dos errors, porta a una probabilitat de parada inferior a dos per a mil en tot el període de cinquanta hores. Amb això n'hi havia més que prou per erradicar la frustració de Hamming.

Enfocament intuïtiu

Codi perfecte

Article principal: codi perfecte

La primera qüestió que pot formular és: quanta informació ha de contenir la redundància? Aquesta informació s'emmagatzema al missatge transmès per mitjà de p bits. Existeixen doncs quatre + p errors possibles, i a més a més d'aquesta informació en cal una per indicar l'absència d'error. Per tant s'han d'emmagatzemar cinc més p informacions en p bits. Ara bé p bits poden condificar com a màxim 2^p casos possibles. Aquesta situació s'obté si cada estat es descriu amb una combinació de bits. Un se'n pot donar compte amb un exemple, dos bits poden descriure quatre estats : 00, 01, 10, 11 el que correspon a partir de zero a tres en base dos. Si el codi és ideal, p verifica la igualtat 5 + p = 2^p el terme de l'esquerra descriu els estats necessaris per a la correcció i el de la dreta la quantitat d'estats emmagatzemats en els bits de paritat. Aquesta equació admet una única solució: p és igual a tres. Un codi que verifica aquest tipus de propietat s'anomena perfecte, l'article associat formalitza aquest enfocament.

Bit de paritat

Article principal: Checksum

Representació gràfica dels quatre bits de dades i dels tres bits de paritat

La figura de La dreta indica el mode de construcció del codi. Els valors d1, d2, d3 i d4 simbolitzen els quatre bits del missatge. Els valors p1, p2, p3 corresponen als bits de paritat. El bit p1 correspon a la paritat del cercle verd, si d1 + d2 + d4 és parell p1 és igual a zero, si no p1 val u. En conseqüència, si no es produeix cap alteració, la suma dels bits del cercle verd és parell. Aquesta idea es repeteix sobre els cercles de color vermell i blau.

Si es produeix una alteració, per exemple sobre p₁ llavors la paritat del cercle de p₁ queda modificada, altrament les dels cercles de p₂ i de p₃ no es modifiquen. Si la paritat de d₁ es modifica, llavors les dels cercles de p₁ i de p₂ ho són però la de p₃ no ho és. El resum de la situació ve donat al quadre següent. Les set columnes corresponen a les set possibles alteracions dels diferents bits del missatge, les tres línies corresponen a les paritats dels cercles associats. Si la paritat del cercle es conserva llavors la cel·la associada és verda amb el text Sí, en el cas contrari la cel·la és vermella amb el text No.

Bit #	1	2	3	4	5	6	7
bit transmis	${\displaystyle p_{1}}$	${\displaystyle p_{2}}$	${\displaystyle d_{1}}$	${\displaystyle p_{3}}$	${\displaystyle d_{2}}$	${\displaystyle d_{3}}$	${\displaystyle d_{4}}$
${\displaystyle p_{3}}$	Sí	Sí	Sí	No	No	No	No
${\displaystyle p_{2}}$	Sí	No	No	Sí	Sí	No	No
${\displaystyle p_{1}}$	No	Sí	No	Sí	No	Sí	No

Si, per exemple les tres paritats dels tres cercles es modifiquen, llavors existeix un error sobre el bit d₄. Per a cada bit, un error engendra un joc de paritat diferent. Si cap error no altera el missatge llavors les tres paritats són Sí.

L'ordre de les diferents columnes no s'ha escollit a l'atzar. Fixeu-vos que si es transforma en el quadre els No en 1 i els Sí el 0 llavors s'obté la successió dels nombres d'u a set en binari. Aquesta propietat permet una descodificació fàcil.

Construcció del codi

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. El conjunt E dels missatges a enviar és el de paraules de quatre lletres preses del conjunt {0,1}, el missatge es codifica en una paraula de set lletres preses en el mateix conjunt. Es nota F l'espai de les paraules de set lletres binàries. E i F poden ser considerats com espais vectorials sobre el cos binari {0,1}. Les taules d'addició i de multiplicació són les següents:

+ 0 1 0  0  1 1  1  0

. 0 1 0  0  0 1  0  1

L'addició és interessant, ja que la suma d'una successió de valors és igual zero al cos si la suma és parell en els enters i u si no. La multiplicació és habitual, multiplicar per zero dona sempre zero i multiplicar per u no modifica el valor.

La codificació, és a dir l'operació consistent en transformar el missatge d'E de quatre lletres en un codi de F de set lletres apareix llavors com una aplicació lineal d'E en F. Es descriu per una matriu. Fins i tot si el cos és inhabitual, tots els resultats de l'àlgebra lineal s'apliquen aquí. Per aquesta raó, tal codi s'anomena lineal. La codificació consisteix a multiplicar el vector de quatre lletres binàries per una matriu 7x4 per obtenir un vector compost per set lletres binàries.

Matriu generadora

Ordre dels diferents bits

El coneixement de la imatge de cada vector de la base canònica determina completament l'aplicació de codificació. Els quatre vectors de la base corresponen als missatges següents: d₁ = 1000, d₂ = 0100, d₃ = 0010 et d₄ = 0001.

La imatge de d₁, el missatge que té coordenades nul·les en d₂, d₃ et d₄, posseeix dues paritats iguals a u, la de p₁ i p₂ i una igual a zero :p₃.

Respectant l'ordre de la base de F: p1, p₁, p₂, d₁, p₃, d₂, d₃ et d₄, s'obté la imatge del primer vector:

${\displaystyle \varphi (1000)=1110000}$

Es calculen d'igual manera les imatges dels altres vectors de la base d'E:

${\displaystyle \varphi (0100)=1001100\;,\quad \varphi (0010)=0101010\;et\quad \varphi (0001)=1101001\;}$

La matriu de φ, anomenada matriu generadora està formada per les quatre columnes que corresponen a les imatges dels vectors de la base canònica per φ, s'obté:

${\displaystyle \mathbf {G} ={\begin{pmatrix}1&1&0&1\\1&0&1&1\\1&0&0&0\\0&1&1&1\\0&1&0&0\\0&0&1&0\\0&0&0&1\\\end{pmatrix}}}$

Exemple

Article principal: Producte de matrius

Representació gràfica de l'exemple d = 1011

Es considera l'exemple del missatge a comunicar d = 1011. Els bits de paritat són iguals a zero per a p₁, u per a p₂ i zero per a p₃. Respectant l'ordre dels vectors de la base de F, s'obté manualment el vector c = 0110011. El producte matricial de la matriu generadora G per la matriu columna D del vector d dona la matriu columna C del vector c:

${\displaystyle \mathbf {D} ={\begin{pmatrix}1\\0\\1\\1\end{pmatrix}}\quad \mathbf {G.D} ={\begin{pmatrix}1&1&0&1\\1&0&1&1\\1&0&0&0\\0&1&1&1\\0&1&0&0\\0&0&1&0\\0&0&0&1\\\end{pmatrix}}{\begin{pmatrix}1\\0\\1\\1\end{pmatrix}}={\begin{pmatrix}0\\1\\1\\0\\0\\1\\1\end{pmatrix}}\quad i\quad \mathbf {C} =\mathbf {G.D} ={\begin{pmatrix}0\\1\\1\\0\\0\\1\\1\end{pmatrix}}}$

Els dos resultats són iguals, tanmateix el càlcul matricial és senzill i ràpid d'implementar. El destinatari rep el codi c que conté a alhora les dades i els bits de paritat.

Descodificació

Matriu de control

El receptor, depenent de l'absència d'error, pot fàcilment descodificar el missatge c. Sap que el codi rebut: 0110011 conté les dades en blau, en posició tres, cinc, sis i set. Li cal ara saber si cap alteració no ha modificat el codi rebut, el que correspon a un dels papers dels bits de paritat en vermell.

Un enfocament anàleg al de la codificació permet la detecció d'error. S'han de complir tres condicions, una per cercle de la figura representativa. Cada condició s'expressa com que una suma ha de ser parell, o bé nul·la al cos binari. Aquestes tres condicions formen les tres línies d'una matriu anomenada matriu de control. Un missatge rebut és sense error si i només si el producte de la matriu de control H per la matriu columna C del vector c és igual a la matriu columna nul·la.

La condició associada al cercle vermell p₃ significa que la suma p₃ + d₂ + d₃ + d₄ ha de ser parell. La primera línia de la matriu correspon a les coordenades 0001111. Aquesta línia correspon a la primera línia de la taula del paràgraf bit de paritat. El mateix per a les altres línies, corresponent als cercles blau i verd. S'obté la matriu H:

${\displaystyle \mathbf {H} ={\begin{pmatrix}0&0&0&1&1&1&1\\0&1&1&0&0&1&1\\1&0&1&0&1&0&1\\\end{pmatrix}}}$

Es pot verificar amb l'exemple que el producte de la matriu H per la de la paraula del codi c exactament nul·la. De forma més general, es pot verificar que el producte de H per G és nul, el que assegura que tot missatge rebut està ben validat si no s'ha comes cap alteració.

${\displaystyle \mathbf {H.C} ={\begin{pmatrix}0&0&0&1&1&1&1\\0&1&1&0&0&1&1\\1&0&1&0&1&0&1\\\end{pmatrix}}.{\begin{pmatrix}0\\1\\1\\0\\0\\1\\1\end{pmatrix}}={\begin{pmatrix}0\\0\\0\end{pmatrix}}\quad i\quad \mathbf {H.G} ={\begin{pmatrix}0&0&0&1&1&1&1\\0&1&1&0&0&1&1\\1&0&1&0&1&0&1\\\end{pmatrix}}.{\begin{pmatrix}1&1&0&1\\1&0&1&1\\1&0&0&0\\0&1&1&1\\0&1&0&0\\0&0&1&0\\0&0&0&1\\\end{pmatrix}}={\begin{pmatrix}0&0&0&0\\0&0&0&0\\0&0&0&0\\\end{pmatrix}}}$

Correcció d'error

Conseqüència d'un error en el bit d₂

L'objectiu del codi és la protecció contra un error. Estudiem el cas on el bit de dada d₂ és alterat durant la transferència. El missatge rebut ja no és c = 0110011 sinó x = 0110111. Dues condicions, corresponents al cercles vermell i verd, ja no es compleixen. El vector x no pot passar la prova de la matriu de control:

${\displaystyle \mathbf {H.X} ={\begin{pmatrix}0&0&0&1&1&1&1\\0&1&1&0&0&1&1\\1&0&1&0&1&0&1\\\end{pmatrix}}.{\begin{pmatrix}0\\1\\1\\0\\1\\1\\1\end{pmatrix}}={\begin{pmatrix}1\\0\\1\end{pmatrix}}}$

Per tant l'error s'ha detectat, la matriu de control presenta un vector no nul, corresponent al valor cinc expressat en binari. El valor de H.X s'anomena síndrome. La correcció associada correspon a la paraula e₅ composta de set lletres iguals a zero excepte una, la cinquena és igual a u. La descodificació, en el cas d'una síndrome no nul·la correspon a sostreure (el que significa sumar el complementari en un codi binari) l'error e₅ = 0000100. S'obté:

${\displaystyle \mathbf {C} =\mathbf {X} +\mathbf {E} _{5}={\begin{pmatrix}0\\1\\1\\0\\1\\1\\1\end{pmatrix}}+{\begin{pmatrix}0\\0\\0\\0\\{\overline {1}}\\0\\0\end{pmatrix}}={\begin{pmatrix}0\\1\\1\\0\\0\\1\\1\end{pmatrix}}}$

El que corregeix l'error, a partir del moment en què no intervé més que sobre un bit, la matriu de control dona en binari el número de la columna culpable.

Una vegada l'error corregit, és possible extreure les dades i reconstruir el missatge inicial. Tal mètode s'anomena descodificació per síndrome.

Descripció del mecanisme

La linealitat de l'aplicació associada a la matriu H filtra totalment el missatge per proposar una imatge que no depenen més que de l'error:

${\displaystyle \mathbf {H.X} =\mathbf {H} .(\mathbf {C} +\mathbf {E} _{5})=\mathbf {H.C} +\mathbf {H.E} _{5}=0+\mathbf {H.E} _{5}=\mathbf {H.E} _{5}}$

És la raó que permet parlar de síndrome, no depèn més que de l'error i no del missatge mateix.

A més, l'ordre de la base de F : p₁, p₂, d₁, p₃, d₂, d₃ et d₄, així com el de les línies de la matriu H han estat escollits de tal manera que en una lectura d'esquerra a la dreta de la llista de columnes corresponen als representem binaris dels nombres de l'u a set ordenats, la imatge de e₅ per l'aplicació és doncs 101 i tal propietat és verdadera per a tots els e_i si i és un enter comprès entre u i set.

Codi de Hamming (8,4)

En cas d'un doble error, el codi detecta una anomalia. Tanmateix la síndrome proposa una xifra binària corresponent sempre a una tercera columna diferent de les dues precedents. Així s'afegeix un tercer error, ja que el codi no disposa de cap mitjà per diferenciar un error de senzilla d'un de doble. Per pal·liar aquest fet, així com per obtenir un codi de dimensió exactament igual a un octet, sovint s'afegeix un vuitè bit, correspon a la paritat dels set bits precedents. Així si es produeix un segon error també és detectat, no pot ser corregit, però com que es té la informació de què hi ha hagut un doble error es pot evitar una temptativa maldestra de correcció i demanar una retransmissió.

La descodificació es fa manera següent:

• Si no hi ha cap error la síndrome és nul.
• Si s'ha produït un error sobre els set primers bits, els tres primers elements de la síndrome donen la posició de l'error. L'existència d'un nombre d'error senar es confirma pel vuitè bit.
• Si s'han produït dos errors, els tres primers elements de la síndrome no són tots nuls i el vuitè bit indica una paritat exacte, senyal d'un nombre parell d'errors. Una és necessària retransmissió.
• Si s'ha produït un error sobre el vuitè bit, l'absència d'error sobre els tres primers elements de la síndrome permet localitzar l'error i el missatge queda validat.

La taula següent descriu els quatre primers missatges així com les seves codificacions per a Hamming (7,4) i (8,4)

Dades ${\displaystyle ({\color {blue}d_{1}},{\color {blue}d_{2}},{\color {blue}d_{3}},{\color {blue}d_{4}})}$	Hamming(7,4)		Hamming(7,4) amb bit de paritat (Hamming(8,4))
	Transmes ${\displaystyle ({\color {red}p_{1}},{\color {red}p_{2}},{\color {blue}d_{1}},{\color {red}p_{3}},{\color {blue}d_{2}},{\color {blue}d_{3}},{\color {blue}d_{4}})}$	Diagrama	Transmes ${\displaystyle ({\color {red}p_{1}},{\color {red}p_{2}},{\color {blue}d_{1}},{\color {red}p_{3}},{\color {blue}d_{2}},{\color {blue}d_{3}},{\color {blue}d_{4}},{\color {green}p_{4}})}$	Diagrama
0000	0000000		00000000
1000	1110000		11100001
0100	1001100		10011001
1100	0111100		01111000

Referències

1. «Présentation du code de Hamming par l'Ecole Polytechnique fédérale de Lausanne». Arxivat de l'original el 2005-03-16. [Consulta: 2 novembre 2008].
2. Claude Shannon A mathematical theory of communication Bell System Technical Journal, vol. 27, pp. 379-423 et 623-656, Juil et Oct 1948
3. Richard Hamming Error-detecting and error-correcting codes Bell Syst. Tech. J. 29 pp 147 à 160 1950

Bibliografia

• 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

Enllaços externs

• (francès) 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