DETECCION Y CORRECCION DE ERRORES

CODIGO HAMMING

En informática, el código de Hamming es un código detector y corrector de errores que lleva el nombre de su inventor, Richard Hamming. En los datos codificados en Hamming se pueden detectar errores en un bit y corregirlos, sin embargo no se distingue entre errores de dos bits y de un bit (para lo que se usa Hamming extendido). Esto representa una mejora respecto a los códigos con bit de paridad, que pueden detectar errores en sólo un bit, pero no pueden corregirlo.

Paridad

La paridad consiste en añadir un bit, denominado bit de paridad, que indique si el número de los bits de valor 1 en los datos precedentes es par o impar. Si un solo bit cambiara por error en la transmisión, el mensaje cambiará de paridad y el error se puede detectar (nótese que el bit donde se produzca el error puede ser el mismo bit de paridad). La convención más común es que un valor de paridad de 1 indica que hay un número impar de unos en los datos, y un valor de paridad de 0 indica que hay un número par de unos en los datos.

La comprobación de paridad no es muy robusta, dado que si cambia de forma uniforme más de un solo bit, el bit de paridad será válido y el error no será detectado. Por otro lado, la paridad, aunque puede detectar que hay error, no indica en qué bit se cometió. Los datos se deben desechar por entero y volverse a transmitir. En un medio ruidoso, una transmisión correcta podría tardar mucho tiempo o incluso, en el peor de los casos, no darse nunca. El chequeo de paridad, aunque no es muy bueno, usa un único bit, por lo que produce muy poca sobrecarga, y además permite la corrección de ese bit si es conocida su posición.

EJEMPLO:

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

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 paridad
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

CRC

Los códigos de paridad tienen el inconveniente de que se requiere demasiada redundancia para detectar únicamente errores simples. En el ejemplo que hemos visto, sólo un 8/9 de la información transmitida contenían datos, el resto era redundancia. Los códigos de redundancia cíclica (CRC) son muy utilizados en la práctica para la detección de errores en largas secuencias de datos. Se basan en representar las cadenas de datos como polinomios. El emisor realiza ciertas operaciones matemáticas antes de enviar los datos. El receptor realizará,  a la llegada de la transmisión, una división entre un polinomio convenido (polinomio generador). Si el resto es cero, la transmisión ha sido correcta. Si el resto es distinto significará que se han producido errores y solicitará la retransmisión al emisor.