Codi Hamming

En informàtica, el codi Hamming és un codi detector i corrector d'errors que porta el nom del seu inventor, Richard Hamming. En les dades codificades en Hamming es poden detectar errors en un bit i corregir-los, però no es distingeix entre errors de dos bits i d'un bit (per al que es fa servir Hamming estès). Això representa una millora respecte als codis amb bit de paritat, que poden detectar errors en només un bit, però no poden corregir-lo.^[1] En matemàtiques, els codis de Hamming són un tipus de codis binaris lineals. Per a cada nombre enter $m\geq 2$ hi ha un codi amb $m$ bits de paritat i $2^{m}-m-1$ bits de dades. Els codis de Hamming són un exemple de codis perfectes, codis que coincideixen exactament amb el límit superior teòric sobre el nombre de paraules en clau diferent per a un determinat nombre de bits i la capacitat per corregir errors.^[2]

Codis pre-Hamming modifica

Abans dels codis Hamming es van utilitzar certs codis detectors d'error, però cap va arribar a ser tan eficaç com els de Hamming. A continuació es descriuen alguns d'aquests codis.

Paritat modifica

La paritat consisteix a afegir un bit, anomenat bit de paritat, que indiqui si el nombre dels bits de valor 1 en les dades precedents és parell o senar. Si un sol bit canviés per error en la transmissió, el missatge canviaria de paritat i l'error es podria detectar (noti's que el bit on es produeixi l'error pot ser el mateix bit de paritat). La convenció més comuna és que un valor de paritat d'1 indica que hi ha un nombre senar d'uns en les dades, i un valor de paritat de 0 indica que hi ha un nombre parell d'uns en les dades.

La comprovació de paritat no és gaire robusta, ja que si canvia de forma uniforme més d'un sol bit, el bit de paritat és vàlid i l'error no serà detectat. D'altra banda, la paritat, encara que pot detectar que hi ha error, no indica en quin bit es va cometre. Les dades s'han de rebutjar del tot i tornar-se a transmetre. En un medi sorollós, una transmissió correcta podria trigar molt de temps o en el pitjor dels casos pot arribar a no donar-se mai. La revisió de paritat, encara que no és gaire efectiva, fa servir un únic bit, pel que produeix molt poca sobrecàrrega, i a més permet la correcció d'aquest bit si se'n coneix la seva posició.^[3]

Dos entre cinc modifica

Als anys 40, Bell va utilitzar un codi una mica més sofisticat conegut com a dos-entre-cinc. Aquest codi es basa en el fet que cada bloc de cinc bits (conegut com a penta-bit) tingués exactament dos uns. D'aquesta manera, l'ordinador podria detectar possibles errors quan en la seva entrada no hi havia exactament dos uns a cada penta-bit.

Aquest codi seguia únicament detectant errors per canvi en un sol bit, si en un mateix penta-bit un 0 canviava a 1 i un 1 canviava a 0, la regla de dues-entre-cinc se seguia complint i l'error quedava sense descobrir.

Donat que hi ha deu combinacions de cinc bits que tenen exactament dos uns, aquest sistema és útil per transmetre xifres decimals, amb un penta-bit per xifra.

Repetició modifica

Un altre codi utilitzat, consistia a repetir cada bit de dades diverses vegades per assegurar-se que la transmissió era correcta. Per exemple, si el bit de dades que s'envia fos un 1, un codi de repetició amb n = 3, enviaria "111". Si els tres bits rebuts no fossin idèntics, hi hauria hagut un error. En un ambient sense massa soroll, la majoria de les vegades només canviaria un bit en cada paquet de tres bits. Per tant, dades del tipus 001, 010, i 100 es corresponen al bit 0, mentre que 110, 101, i 011 es corresponen amb el bit 1. És com si el bit original s'obtingués per majoria en una "votació". Un codi amb aquesta capacitat de reconstruir el missatge original en la presència d'errors es coneix com a codi corrector d'errors.

No obstant això, aquest codi no pot reparar correctament tots els errors. Seguint amb l'exemple de la repetició amb n=3, si l'error en la transmissió provoqués el canvi simultani de dos bits i el receptor rebés "001", el sistema detectaria l'error, però consideraria que el bit original era 0, la qual cosa seria incorrecte. Si s'augmenta el nombre de vegades que es repeteix cada bit a quatre (n = 4), és possible detectar els errors en dos bits però òbviament no es podran corregir; amb cinc, és possible corregir errors de dos bits però no errors de tres bits.

D'altra banda, el codi de la repetició és extremadament ineficient, ja que redueix la velocitat de transmissió per tres en el nostre exemple original i la seva eficiència cau dràsticament en augmentar el nombre de vegades que cada bit es repeteix per detectar i corregir més errors.

L'ús del codi de blocs no lineals per detecció d'errors no és gaire implementat i per tant emprarem el codi d'errors lineals per a la correcció d'errors.

Codis Hamming modifica

Si s'afegeixen al costat del missatge més bits detectors-correctors d'error i si aquests bits es poden ordenar de manera que diferents bits d'error produeixen diferents resultats, llavors els bits erronis podrien ser identificats. En un conjunt de set bits hi ha només set possibles errors d'un bit, de manera que amb tres bits de control d'error es podria especificar si va ha ocorregut un error i en quin bit ha estat.

Hamming va estudiar els esquemes de codificació existents, inclòs el de dos entre cinc, i en va generalitzar les conclusions. Per començar, va desenvolupar una nomenclatura per descriure el sistema, incloent el nombre dels bits de dades i el dels bits detectors-correctors d'error en un bloc. Per exemple, la paritat inclou un sol bit per a qualsevol paraula de dades, així que les paraules del Codi ASCII que són de set bits, Hamming les descrivia com un codi (8.7), és a dir, un total de 8 bits dels quals 7 són dades. En l'exemple anterior de la repetició, seria un codi (3.1), seguint la mateixa lògica. La relació de la informació és el segon nombre dividit pel primer, pel nostre exemple de la repetició, 1/3.

Hamming també va estudiar els problemes que sorgien en canviar dos o més bits a la vegada i va descriure això com "distància" (ara anomenada distància de Hamming en el seu honor). La paritat té una distància de 2, ja que qualsevol error en dos bits no serà detectat. La repetició (3.1) té una distància de 3, ja que és necessari el canvi simultani de tres bits per obtenir una altra paraula de codi. La repetició (4.1) (cada bit es repeteix quatre vegades) té una distància de 4, així que el canvi de dos bits en el mateix grup quedarà sense definir.

Hamming estava interessat a solucionar simultàniament dos problemes: augmentar la distància tant com sigui possible, al mateix temps que s'augmenten al màxim els bits d'informació. Durant els anys 40 va desenvolupar diversos esquemes de codificació que milloraven notablement els codis existents. La clau de tots els seus sistemes era intercalar entre els bits de dades els de paritat.

Hamming (7,4) modifica

Avui, el codi de Hamming es refereix al (7.4) que Hamming introduir el 1950. El codi de Hamming afegeix tres bits addicionals de comprovació per cada quatre bits de dades del missatge.

L'algorisme de Hamming (7.4) pot corregir qualsevol error d'un sol bit, però quan hi ha errors en més d'un bit, la paraula transmesa es confon amb una altra amb error en un sol bit, sent corregida, però de forma incorrecta, és a dir que la paraula que es corregeix és una altra diferent de l'original, i el missatge final serà incorrecte sense saber-ho. Per poder detectar (encara que sense corregir) errors de dos bits, s'ha d'afegir un bit més, i el codi es diu Hamming estès. El procediment per això s'explica al final.

L'algorisme és el següent:

1. Tots els bits la posició els quals és una potència de dos s'utilitzen com a bits de paritat (posicions 1, 2, 4, 8, 16, 32, 64, etc.).

2. Els bits de la resta de posicions són utilitzats com bits de dades (posicions 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, etc.).

3. Cada bit de paritat s'obté calculant la paritat d'algun dels bits de dades. La posició del bit de paritat determina la seqüència dels bits que alternativament comprova i salta, a partir d'aquest, tal com s'explica a continuació.

* Posició 1: salta 0, comprova 1, salta 1, comprova 1, etc.

* Posició 2: salta 1, comprova 2, salta 2, comprova 2, etc.

* Posició 4: salta 3, comprova 4, salta 4, comprova 4, etc.

* Posició 8: salta 7, comprova 8, salta 8, comprova 8, etc.

* Posició 16: salta 15, comprova 16, salta 16, comprova 16, etc.

* Regla general per a la posició n és: salta n-1 bits, comprova n bits, salta n bits, comprova n bits ...

* I així successivament.

En altres paraules, el bit de paritat de la posició $2^{k}$ comprova els bits en les posicions que tinguin al bit k en la seva representació binària. Dit a la inversa, el bit 13, per exemple, és revisat pels bits 8, 4 i 1, en ser aquests els de la seva representació binària: 13 = 1.101 ₍₂₎; 8 = 1000 ₍₂₎; 4 = 0.100 ₍₂₎; 1 = 0.001 ₍₂₎.

Així, per exemple, per als primers termes es té:

* A la Posició 1 (2^0 = 1), comprovaríem els bits: 3, 5, 7, 9, 11, 13 ...

* A la Posició 2 (2^1 = 2), els bits: 3, 6, 7, 10, 11, 14, 15 ...

* A la Posició 4 (2^2 = 4), els bits: 5, 6, 7, 12, 13, 14, 15, 20, 21, 22, 23 ...

* A la Posició 8 (2^3 = 8) tindríem: 9, 10, 11, 12, 13, 14, 15, 24-31 ...

Seguint l'algorisme fins a completar la nova cadena.

Exemple modifica

Considerem la paraula de dades de 7 bits "0110101". Per veure com es generen i utilitzen els codis Hamming per detectar un error, observeu les taules següents. S'utilitza l ' d per indicar els bits de dades i la p per als de paritat.

En primer lloc, els bits de dades s'insereixen en les posicions apropiades i els bits de paritat calculats en cada cas utilitzant la paritat parell.

	p ₁	p ₂	d ₁	p ₃	d ₂	d ₃	d ₄	p ₄	d ₅	d ₆	d ₇
Càlcul dels bits de paritat en el codi Hamming
Paraula de dades (sense paritat):			0		1	1	0		1	0	1
p ₁	1		0		1		0		1		1
p ₂		0	0			1	0			0	1
p ₃				0	1	1	0
p ₄								0	1	0	1
Paraula de dades (amb paritat):	1	0	0	0	1	1	0	0	1	0	1

P1 = D1 exor D2 exor D4 exor D5 exor D7
P2 = D1 exor D3 exor D4 exor D6 exor D7
P3 = D2 exor D3 exor D4
P4 = D5 exor D6 exor D7

La nova paraula de dades (amb els bits de paritat) és ara "10001100101". Considerem ara que el bit de la dreta, per error, canvia d'1 a 0. La nova paraula de dades serà ara "10001100100".

Sense errors

	p ₁	p ₂	d ₁	p ₃	d ₂	d ₃	d ₄	p ₄	d ₅	d ₆	d ₇	Prova de paritat	Bit de paritat
Comprovació dels bits de paritat (amb primer bit de la dreta canviat)
Paraula de dades rebuda:	1	0	0	0	1	1	0	0	1	0	1	1
p ₁	1		0		1		0		1		1	Correcte	0
p ₂		0	0			1	0			0	1	Correcte	0
p ₃				0	1	1	0					Correcte	0
p ₄								0	1	0	1	Correcte	0

Amb errors

	p ₁	p ₂	d ₁	p ₃	d ₂	d ₃	d ₄	p ₄	d ₅	d ₆	d ₇	Prova de paritat	Bit de paritat
Comprovació dels bits de paritat (amb primer bit de la dreta canviat)
Paraula de dades rebuda:	1	0	0	0	1	1	0	0	1	0	0	1
p ₁	1		0		1		0		1		0	Error	1
p ₂		0	0			1	0			0	0	Error	1
p ₃				0	1	1	0					Correcte	0
p ₄								0	1	0	0	Error	1

Si s'analitza a la taula anterior la paritat que s'ha d'obtenir a la dreta després de l'arribada del missatge sense errors ha de ser sempre 0 (per cada fila), però en el moment en què ocorre un error aquesta paritat canvia a 1, d'allà el nom de la columna "prova de paritat 1". S'observa que a la fila en què el canvi no va afectar la paritat és zero i arriba sense errors.

El pas final és avaluar els bits de paritat (recordeu que la decisió es troba en d ₇ ). El valor sencer que representen els bits de paritat és 11 (si no haguessin passat errors aquest valor seria 0), el que significa que el bit onzena de la paraula de dades (bits de paritat inclosos) és l'erroni i necessita ser canviat.

	p ₄	p ₃	p ₂	p ₁
Binari	1	0	1	1
Decimal	8		2	1	Σ = 11

Canviant el bit onzena 1000110010 0 s'obté de nou 1000110010 1 . Eliminant els bits de patró de la paritat no es tenen en compte els bits de paritat. Si l'error es produís en un d'ells, en la comprovació només es detectaria un error, just el corresponent al bit de paritat causant d'aquest.

Hamming Estès modifica

Finalment, per detectar errors en 2 bits es fa servir un bit addicional de paritat (Hamming Estès) on es pot donar el cas de 3 probabilitats:

 1 .-  'No hi ha error → Hamming = 0, Paritat OK
 2 .-  Un bit d'error → Paritat Decisió llavors
 A)  Hamming = 0, P = incorrecte, en aquest cas es canvia el valor del bit de paritat.
 B)  Hamming <> 0, corregeixo segons Hamming.
 3 .-  Dues bit en error → Paritat Ok, Hamming <> 0, per tant informe, NO corregeixo.

Referències modifica

↑ See Lemma 12 of
↑ Hamming, 1950, p. 153–154.
↑ Moon T. Error correction coding: Mathematical Methods and Algorithms. John Wiley and Sons, 2005.(Cap. 3) ISBN 978-0-471-64800-0

Bibliografia modifica

Hamming, Richard Wesley «Error detecting and error correcting codes». Bell System Technical Journal, 29, 2, 1950, pàg. 147–160. Arxivat de l'original el 16 d’agost 2018. DOI: 10.1002/j.1538-7305.1950.tb00463.x [Consulta: 21 desembre 2018].
Moon, Todd K. Error Correction Coding. Nova Jersey: John Wiley & Sons, 2005. ISBN 978-0-471-64800-0.
MacKay, David J.C.. Information Theory, Inference and Learning Algorithms. Cambridge: Cambridge University Press, setembre 2003. ISBN 0-521-64298-1.
D.K. Bhattacharryya, S. Nandi. "An efficient class of SEC-DED-AUED codes". 1997 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '97): 410–415. DOI:10.1109/ISPAN.1997.645128
«Mathematical Challenge April 2013 Error-correcting codes». swissQuant Group Leadership Team, abril 2013. Arxivat de l'original el 2017-09-12. [Consulta: 21 desembre 2018].

Enllaços externs modifica

[1] See Lemma 12 of

[FOOTNOTEHamming1950153–154-2] Hamming, 1950, p. 153–154.

[Moon-3] Moon T. Error correction coding: Mathematical Methods and Algorithms. John Wiley and Sons, 2005.(Cap. 3) ISBN 978-0-471-64800-0

[1]

[2]

[3]