Codigo de Hamming

Código de Hamming.

La transferencia de datos en la memoria puede en ocasiones tener errores que se producen por variaciones en la corriente eléctrica. Una forma de detectar esos errores es usando algún código de detección de errores, o bits de paridad, los cuales se agregan ala dato inicial para poder controlar alguna desviación. Es una forma de funcionamiento análogo al dígito deverificación que se utilizan en los legajos de los alumnos.

Primero se añaden tantos bits de paridad como sean necesarios para formar una palabra que sea igual a:
m + r = n bits
Siendo m la cantidad de bits dados por la palabra del sistema y r la cantidad de bits de paridad que se agregan y n la cantidad de bits resultante.

Los bits se numeran comenzando desde 1 en lugar de hacerlo desde 0 comohabitualmente se hace en todas las funciones de computación, siendo por lo tanto el bit 1el de extrema derecha (también llamado bit de mayor significado especialmente en sistemas numéricos).

Todos los bits cuyo número es potencia de 2 son bits de paridad, los demás se utilizan para datos, por lo tanto los bits 1, 2, 4, 8, 16, 32,... etc. son bits de paridad y el resto son datos.

Es importantesaber cual es el tamaño de los registros porque así sabremos cuantos bits debemos agregarle. De esta manera si la palabra es de 16 bits deberemos agregarle 5 bits de paridad con lo cual tendremos 21 bits en total, cumpliendo con la formula que dimos al principio:
16 + 5 = 21

Recordamos que podemos tener dos tipos de paridad: par e impar, sabiendo que cualquiera sea la que tomemos debemossumar la cantidad de bits con valor 1 y obtener siempre un número par o impar de acuerdo a la forma elegida.

Los bits verifican los siguientes campos:

Bits
Verifica los siguientes bits
Noten que
1
1 3 5 7 9 11 13 15 17 19 21
1 si; 1 no
2
2 3 6 7 10 11 14 15 18 19
2 si; 2 no
4
4 5 6 7 12 13 1 4 15 20 21
4 si; 4 no
8
8 9 10 11 12 13 14 15
8 si; 8 no
16
16 17 18 19 20 21 22 23 2416 si; 16 no

Cada bit de paridad comienza de su número para arriba.

En general un bit es verificado por todos aquellos que respondan a: bp1 + bp2 + bp3 +.... + bpn = b lo que da, por ejemplo que el bit 5 es verificado por el bit de paridad 1 y el bit de paridad 4 lo que cumple con la fórmula dada anteriormente bp1 + bp4 = 5 y el bit 11 es verificado por el 1 + 2 + 8 = 11.

Veamos como secontrola una palabra de 16 bits en memoria.

Tomemos la palabra en memoria 1100111000010111 y apliquemos el código de Hamming para paridad par.

Nro.Bits
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Cantidad
Hamming
H
H
1
H
1
0
0
H
1
1
1
0
0
0
0
H
1
0
1
1
1

Para 16















0
1
0
1
1
1
4
Para 81
1
1
1
0
0
0
0






3
Para 4



1
1
0
0




0
0
0
0




1
1
3
Para 2

0
1


0
0


1
1


0
0


0
1


4
Para 1
1

1

1

0

1

1

0

0

1

1

1
7
Final
1
0
1
1
1
0
0
1
1
1
1
0
0
0
0
0
1
0
1
1
1
12

Si se produce un cambio en el bit 5 deberá ser tomado por el control de los bits 1 y 4 dondese verificará el cambio o error producido en la transmisión o por una variación de corriente eléctrica.

No querramos controlar con los valores de 1 y 4 porque no es así como se debe hacer. Esto se debe hacer de la misma manera en que se construye cada bit. Iniciamos por el 16 y contamos la cantidad de unos que este bit controla y luego seguimos con el 8, luego el cuatro, el 2 y por último el 1.De la misma manera se hace con el error. Si da impar sabremos que ese control está mal.

Es importante indicar que el código de Hamming sólo puede detectar el cambio de 1 bit. Si fueran dos los que cambiaron sería casi imposible y si fueran 3 totalmente imposible más aún si se compensan.

Andrew S. Tanembaum1 desarrolla el siguiente ejercicio, que traducimos en un desarrollo igual que el...