Código Hamming

Antes de los códigos Hamming se utilizaron ciertos códigos detectores de error, como lo fueron el código linteing, pero ninguno llegó a ser tan eficaz como los de Hamming. A continuación se describen algunos de estos códigos.

Si se añaden junto al mensaje más bits detectores-correctores de error y si esos bits se pueden ordenar de modo que diferentes bits de error producen diferentes resultados, entonces los bits erróneos podrían ser identificados. En un conjunto de siete bits, hay solo siete posibles errores de bit, por lo que con tres bits de control de error se podría especificar, además de que ocurrió un error, en qué bit fue.

Hamming estudió los esquemas de codificación existentes, incluido el de dos entre cinco, y generalizó sus conclusiones. Para empezar, desarrolló una nomenclatura para describir el sistema, incluyendo el número de los bits de datos y el de los bits detectores-correctores de error en un bloque. Por ejemplo, la paridad incluye un solo bit para cualquier palabra de datos, así que las palabras del Código ASCII que son de siete bits, Hamming las describía como un código (8.7), esto es, un total de 8 bits de los cuales 7 son datos. Con base a la anterior repetición, sería un código (3.1), siguiendo la misma lógica. La relación de la información es el segundo número dividido por el primero, por nuestro ejemplo de la repetición, 1/3.

Hamming también estudió los problemas que surgían al cambiar dos o más bits a la vez y describió esto como "distancia" (ahora llamada distancia de Hamming en su honor). La paridad tiene una distancia de 2, dado que cualquier error en dos bits no será detectado. La repetición (3.1)tiene una distancia de 3, pues son necesarios el cambio simultáneo de tres bits para obtener otra palabra de código. La repetición (4.1) (cada bit se repite cuatro veces) tiene una distancia de 4, así que el cambio de dos bits en el mismo grupo quedará sin definir.

Hamming estaba interesado en solucionar simultáneamente dos problemas: aumentar la distancia tanto como sea posible, a la vez que se aumentan al máximo los bits de información. Durante los años 40 desarrolló varios esquemas de codificación que mejoraban notablemente los códigos existentes. La clave de todos sus sistemas era intercalar entre los bits de datos los de paridad.

Consideremos la palabra de datos de 7 bits "0110101". Para ver cómo se generan y utilizan los códigos Hamming para detectar un error, observe las tablas siguientes. Se utiliza la d para indicar los bits de datos y la p para los de paridad.

En primer lugar los bits de datos se insertan en las posiciones apropiadas y los bits de paridad calculados en cada caso usando la paridad par.

Cálculo de los bits de paridad en el código Hamming

	p1	p2	d1	p3	d2	d3	d4	p4	d5	d6	d7
Palabra de datos (sin paridad):			0		1	1	0		1	0	1
p1	1		0		1		0		1		1
p2		0	0			1	0			0	1
p3				0	1	1	0
p4								0	1	0	1
Palabra de datos (con paridad):	1	0	0	0	1	1	0	0	1	0	1

${\displaystyle P_{1}={D_{1}}\oplus {D_{2}}\oplus {D_{4}}\oplus {D_{5}}\oplus {D_{7}}}$
${\displaystyle P_{2}={D_{1}}\oplus {D_{3}}\oplus {D_{4}}\oplus {D_{6}}\oplus {D_{7}}}$
${\displaystyle P_{3}={D_{2}}\oplus {D_{3}}\oplus {D_{4}}}$
${\displaystyle P_{4}={D_{5}}\oplus {D_{6}}\oplus {D_{7}}}$

La nueva palabra de datos (con los bits de paridad) es ahora "10001100101". Consideremos ahora que el bit de la derecha, por error, cambia de 1 a 0. La nueva palabra de datos será ahora "10001100100".

Sin errores

Comprobación de los bits de paridad (con primer bit de la derecha sin cambiar)

	p1	p2	d1	p3	d2	d3	d4	p4	d5	d6	d7	Prueba de paridad	Bit de comprobación
Palabra de datos recibida:	1	0	0	0	1	1	0	0	1	0	1	1
p1	1		0		1		0		1		1	Correcto	0
p2		0	0			1	0			0	1	Correcto	0
p3				0	1	1	0					Correcto	0
p4								0	1	0	1	Correcto	0

Con errores

Comprobación de los bits de paridad (con primer bit de la derecha cambiado)

	p1	p2	d1	p3	d2	d3	d4	p4	d5	d6	d7	Prueba de paridad	Bit de comprobación
Palabra de datos recibida:	1	0	0	0	1	1	0	0	1	0	0	1
p1	1		0		1		0		1		0	Error	1
p2		0	0			1	0			0	0	Error	1
p3				0	1	1	0					Correcto	0
p4								0	1	0	0	Error	1

Si se analiza en la tabla anterior la paridad que se debe obtener a la derecha tras la llegada del mensaje sin errores debe ser siempre 0 (por cada fila), pero en el momento en que ocurre un error esta paridad cambia a 1, de allí el nombre de la columna "prueba de paridad 1". Se observa que en la fila en que el cambio no afectó la paridad es cero y llega sin errores. SI se observa que en la fila en que el cambio no afecte la paridad es cero y llega sin errores

El paso final es evaluar los bits de paridad (recuerde que el fallo se encuentra en d₇). El valor entero que representan los bits de paridad es 11 (si no hubieran ocurrido errores este valor sería 0), lo que significa que el bit décimo primero de la palabra de datos (bits de paridad incluidos) es el erróneo y necesita ser cambiado.

	p4	p3	p2	p1
Binario	1	0	1	1
Decimal	8		2	1	Σ = 11

Cambiando el bit undécimo primero 10001100100 se obtiene de nuevo 10001100101. Eliminando los bits de patrón de la paridad no se tienen en cuenta los bits de paridad. Si el error se produjera en uno de ellos, en la comprobación solo se detectaría un error, justo el correspondiente al bit de paridad causante del mismo.

Finalmente, para detectar errores en 2 bits se utiliza un bit adicional de paridad (Hamming Extendido) donde puede darse el caso de 3 posibilidades:

1.-' No hay error ->   Hamming =0, Paridad OK

2.- Un bit de error -> Paridad Fallo entonces
a) Hamming = 0, P = incorrecto, en este caso se cambia el valor del bit de paridad.
b) Hamming <> 0, corrijo según Hamming.

3.- Dos bit en error -> Paridad Ok, Hamming <> 0, por lo tanto informó, NO corrijo.