Codi de Hamming (7,4)

De Viquipèdia
Dreceres ràpides: navegació, cerca

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[modifica | modifica el codi]

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 (19162001) 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[modifica | modifica el codi]

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 del 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 eradicar la frustració de Hamming.

Enfocament intuïtiu[modifica | modifica el codi]

Codi perfecte[modifica | modifica el codi]

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 2p cassos 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 = 2p 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[modifica | modifica el codi]

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 p1 llavors la paritat del cercle de p1 queda modificada, altrament les dels cercles de p2 i de p3 no es modifiquen. Si la paritat de d1 es modifica, llavors les dels cercles de p1 i de p2 ho són però la de p3 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 , en el cas contrari la cel·la és vermella amb el text No.

Bit # 1 2 3 4 5 6 7
bit transmis p_1 p_2 d_1 p_3 d_2 d_3 d_4
p_3 No No No No
p_2 No No No No
p_1 No No No No

Si, per exemple les tres paritats dels tres cercles es modifiquen, llavors existeix un error sobre el bit d4. 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 .

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 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[modifica | modifica el codi]

Codi lineal[modifica | modifica el codi]

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 dóna 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[modifica | modifica el codi]

Article principal: 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: d1 = 1000, d2 = 0100, d3 = 0010 et d4 = 0001.

La imatge de d1, el missatge que té coordenades nul·les en d2, d3 et d4, posseeix dues paritats iguals a u, la de p1 i p2 i una igual a zero :p3.

Respectant l'ordre de la base de F: p1, p1, p2, d1, p3, d2, d3 et d4, s'obté la imatge del primer vector:

\varphi (1000) = 1110000

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

\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é:

\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[modifica | modifica el codi]

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 p1, u per a p2 i zero per a p3. 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 dóna la matriu columna C del vector c:

\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ó[modifica | modifica el codi]

Matriu de control[modifica | modifica el codi]

Article principal: 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 p3 significa que la suma p3 + d2 + d3 + d4 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:

\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ó.

\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[modifica | modifica el codi]

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

L'objectiu del codi és la protecció contra un error. Estudiem el cas on el bit de dada d2 é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 pa prova de la matriu de control:

\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 e5 composta de set lletres iguals a zero excepte una, la cinquena és igual a u. La descodificació, en el cas d'un síndrome no nul correspon a sostreure (el que significa sumar el complementari en un codi binari) l'error e5 = 0000100. S'obté:

\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 dóna 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[modifica | modifica el codi]

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:

\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 : p1, p2, d1, p3, d2, d3 et d4, 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 a als representem binaris dels nombres de l' u a set ordenats, la imatge de e5 per l'aplicació és doncs 101 i tal propietat és verdadera per a tots els ei si i és un enter comprès entre u i set.

Codi de Hamming (8,4)[modifica | modifica el codi]

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 el 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
({\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
({\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
({\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 Hamming code for 0000 becomes 0000000 00000000 Hamming code for 0000 becomes 0000000 with extra parity bit 0
1000 1110000 Hamming code for 1000 becomes 1000011 11100001 Hamming code for 1000 becomes 1000011 with extra parity bit 1
0100 1001100 Hamming code for 0100 becomes 0100101 10011001 Hamming code for 0100 becomes 0100101 with extra parity bit 1
1100 0111100 Hamming code for 1100 becomes 1100110 01111000 Hamming code for 1100 becomes 1100110 with extra parity bit 0

Referències[modifica | modifica el codi]

  1. Présentation du code de Hamming par l'Ecole Polytechnique fédérale de Lausanne
  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

Enllaços externs[modifica | modifica el codi]

Referències[modifica | modifica el codi]

  • 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