Còdic Hamming

Archiu:Cube with binary vertices.png

Hipercubo en {0,1}3, en arestes entre els vèrtiços si diferixen exactament en una posició

En informàtica, el còdic de Hamming és un còdic detector i corrector d'errors que du el nom del seu inventor, Richard Hamming. En les senyes codificades en Hamming es poden detectar errors en un bit i corregir-los, no obstant no es distinguix entre errors de dos bits i d'un bit (per a lo que s'usa Hamming estés). Açò representa una millora respecte als còdics en bit de paritat, que poden detectar errors en solament un bit, pero no poden corregir-ho.

Còdics pre-Hamming

Abans dels còdics Hamming es varen utilisar certs còdics detectors d'error, com lo varen ser el còdic linteing, pero cap va aplegar a ser tan eficaç com els de Hamming. A continuació es descriuen alguns d'estos còdics.

Paritat

La paritat consistix en afegir un bit, denominat bit de paritat, que indique si el número dels bits de valor 1 en les senyes precedents és parell o impar. Si un sol bit canviara per error en la transmissió, el mensage canviarà de paritat i l'error es pot detectar (note's que el bit a on es produïxca l'error pot ser el mateix bit de paritat). La convenció més comuna és que un valor de paritat 1 indica que hi ha un número impar d'uns en les senyes, i un valor de paritat de 0 indica que hi ha un número par d'uns en les senyes.

La comprovació de paritat no és molt robusta, ya que si canvia de forma uniforme un número par de bits, el bit de paritat serà vàlit i l'error no serà detectat. S'utilisa quan es complixen simultàneament dos condicions: que la provabilitat de que falle un bit és baixa i que les falles de bits són successos independents. D'esta forma la provabilitat de que fallen dos (o més) bits és molt baixa, per lo que quan no detecta error és altament provable que el còdic siga efectivament correcte. cal destacar que dites condicions s'ajusten al cas de les memòries de les computadores modernes pero no ocorre lo mateix en els dispositius d'almagasenament que guarden l'informació en forma serial (un bit a continuació d'un atre) ni en els sistemes de transmissió de senyes serial ya que en estos casos el fet que falle un bit està vinculat, en forma no despreciable, a la falla d'un atre adjacent.

Per un atre costat, la paritat, encara que pot detectar que hi ha error, no indica en quin bit es va cometre, si be la sobrecàrrega que produïx este método és molt baixa, des d'un punt de vista computacional com d'espai (un sol bit). Les senyes es deuen rebujar por entero i tornar-se a transmetre. En un mig sorollós, una transmissió correcta podria tardar molt temps o inclús, en el pijor dels casos, no donar-se mai.

Dos entre cinc

En els anys 40, Laboratoris Bell va utilisar un còdic alguna cosa més sofisticat conegut com dos-entre-cinc. Este còdic es basa que cada bloc de cinc bits (conegut com penta-bit) tinguera exactament dos uns, assegurant aixina que tinga una Distància de Hamming igual a dos. D'esta manera, la computadora podria detectar possibles errors quan en la seua entrada no hi havia exactament dos uns en cada penta-bit.

Este còdic seguia únicament detectant errors per canvi en un sol bit; si en un mateix penta-bit (cadena de 5 bits) un 0 canviava a 1 i un 1 canviava a 0, la regla de dos-entre-cinc se seguia complint i l'error quedava sense descobrir.

Repetició

Un atre còdic utilisat, consistia en repetir cada bit de senyes vàries voltes per a assegurar-se de que la transmissió era correcta. Per eixemple, si el bit de senyes que s'envia fora un 1, un còdic de repetició en n=3, enviaria "111". Si els tres bits rebuts no eren idèntics, hi havia un error. En un ambient sense massa soroll, la majoria de les voltes solament canviaria un bit en cada paquet de tres bits. Per lo tant, senyes del tipo 001, 010, i 100 es corresponen al bit 0, mentres que 110, 101, i 011 es corresponen en el bit 1. Un còdic en esta capacitat de reconstruir el mensage original en la presència d'errors es coneix com a còdic corrector d'errors.

No obstant, este còdic no pot reparar correctament tots els errors. En el nostre eixemple, si l'error en la transmissió provocara el canvi simultàneu de dos bits i el receptor rebera "001", el sistema detectaria l'error, pero considerant que el bit original era 0, la qual cosa és incorrecte. Si s'aumenta el número de voltes que es repetix cada bit a quatre (n=4), és possible detectar els errors en dos bits pero òbviament no es podran corregir; en cinc, és possible corregir errors de dos bits, pero no ho podrà fer en errors de tres bits.

Per una atra part, el còdic de la repetició és extremadament ineficaç, puix reduïx la velocitat de transmissió per tres en el nostre eixemple original i la seua eficàcia cau dràsticament en aumentar el número de voltes que cada bit es repetix per a detectar i corregir més errors. L'us del còdic de blocs no llineals per a detecció d'errors no és molt implementat per lo tant amprarem el còdic d'errors llineals per a la correcció d'errors.

Còdics Hamming

Si s'afigen junt al mensage més bits detectors-correctors d'error i si eixos bits es poden ordenar de modo que diferents bits d'error produïxen diferents resultats, llavors els bits erròneus podrien ser identificats. En un conjunt de sèt bits, hi ha solament sèt possibles errors de bit, per lo que en tres bits de control d'error es podria especificar, ademés de que va ocórrer un error, en quin bit va ser.

Hamming va estudiar els esquemes de codificació existents, inclós el de dos entre cinc, i va generalisar les seues conclusions. Per a escomençar, va desenrollar una nomenclatura per a descriure el sistema, incloent el número dels bits de senyes i el dels bits detectors-correctors d'error en un bloc. Per eixemple, la paritat inclou un sol bit per a qualsevol paraula de senyes, aixina que les paraules del Còdic ASCII que són de sèt bits, Hamming les descrivia com un còdic (8.7), açò és, un total de 8 bits dels quals 7 són senyes. En base a l'anterior repetició, seria un còdic (3.1), seguint la mateixa llògica. La relació de l'informació és el segon número dividit pel primer, pel nostre eixemple de la repetició, 1/3.

Hamming també va estudiar els problemes que sorgien en canviar dos o més bits al mateix temps i va descriure açò com "distància" (ara cridada distància de Hamming en el seu honor). La paritat té una distància de 2, ya que qualsevol error en dos bits no serà detectat. La repetició (3.1) té una distància de 3, puix són necessaris el canvi simultàneu de tres bits per a obtindre una atra paraula de còdic. La repetició (4.1) (cada bit es repetix quatre voltes) té una distància de 4, aixina que el canvi de dos bits en el mateix grup quedarà sense definir.

Hamming estava interessat en solucionar simultàneament dos problemes: aumentar la distància tant com siga possible, al mateix temps que s'aumenten al màxim els bits d'informació. Durant els anys 40 va desenrollar varis esquemes de codificació que milloraven notablement els còdics existents. La clau de tots els seus sistemes era intercalar entre els bits de senyes els de paritat.

Hamming (7,4)

Hui, el còdic de Hamming es referix al (7.4) que Hamming va introduir en 1950. El còdic de Hamming agrega tres bits adicionals de comprovació per cada quatre bits de senyes del mensage. L'algoritme de Hamming (7.4) pot corregir qualsevol error d'un sol bit, pero quan hi ha errors en més d'un bit, la paraula transmesa es confon en una atra en error en un sol bit, sent corregida, pero de forma incorrecta, és dir que la paraula que es corrig és una atra distinta a l'original, i el mensage final serà incorrecte sense saber-ho. Per a poder detectar (encara que sense corregir-los) errors de dos bits, es deu afegir un bit més, i el còdic es diu Hamming estés. El procediment per a açò s'explica al final. L'algoritme és el següent:

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

2. Els bits del restant de posicions són utilisats com a bits de senyes (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 senyes. La posició del bit de paritat determina la seqüència dels bits que alternativament comprova i bota, a partir d'este, tal i com s'explica a continuació. Posició 1: bota 0, comprova 1, bota 1, comprova 1, etc. Posició 2: bota 1, comprova 2, bota 2, comprova 2, etc. Posició 4: bota 3, comprova 4, bota 4, comprova 4, etc. Posició 8: bota 7, comprova 8, bota 8, comprova 8, etc. Posició 16: bota 15, comprova 16, bota 16, comprova 16, etc. Regla general per a la posició n és: bota n-1 bits, comprova n bits, bota n bits, comprova n bits... I aixina successivament. En atres paraules, el bit de paritat de la posició comprova els bits en les posicions que tinguen al bit k en la seua representació binaria. Dit a l'inversa, el bit 4, chequea els bits 4, 5, 6, 7, en ser estos els de la seua representació binaria: 4=100(2), 5=101(2), 6=110(2) i 7=111(2). Pel contrari, el mateix bit de paritat no comprova el bit 8, degut a que en la seua representació binaria el bit número 3 (=4) és igual a 0 (8=1000B). Aixina, per eixemple, per als primers térmens es té: En la Posició 1 (2^0 = 1), comprovaríem els bits: 1, 3, 5, 7, 9, 11, 13... En la Posició 2 (2^1 = 2), els bits: 2, 3, 6, 7, 10, 11, 14, 15... En la Posició 4 (2^2 = 4), els bits: 4, 5, 6, 7, 12, 13, 14, 15, 20, 21, 22, 23... En la Posició 8 (2^3 = 8) tindríem: 8, 9, 10, 11, 12, 13, 14, 15, 24-31... Seguint l'algoritme fins a completar la nova cadena.