Saltar al contenido
Codifíca.me | Desarrollo web | Programación

Código Hamming | Detectar errores por paridad

11 agosto, 2011

Hamming

El código Hamming sirve para detectar errores en una secuencia de bits por medio de un control de paridad. Para esto se añade un bit de control a la secuencia original que indique si la suma de los bits es par o impar, con el ejemplo se puede entender más facilmente…

Si quieres más información y definiciones sobre este sistema de codificación échale un vistazo al final de la entrada.

Bien, ¿cómo funciona esto?, fácil, imaginemos que el emisor quiere enviar la secuencia de datos 00010011001. ¿Qué secuencia codificada se transmitirá?

En esta tabla podemos observar que las posiciones 1,2,4,8 se incluirá un bit de paridad que mostrará si la secuencia desglosada de esa fila es 0 o 1, así:

* Las posiciones 1 y potencia de 2 serán las que tengamos un dato P (para el control de paridad) las demás posiciones tendrán un dato D (de la secuencia original).

Ahora bien, si el receptor recibiese la secuencia codificada 110100110011011, para saber donde está el error tendríamos que hacer la tabla y sumando al final los bits de paridad podemos detectar donde está el error.

En este ejemplo, para comprobar con el codigo Hamming la secuencia de datos, realizamos la tabla siguiente en la que todos los bits potencia de dos los utilizaremos como bits de paridad, en este caso serán las posiciones 1,2,4, y 8.  El resto de los bits los utilizaremos como bits de datos.

Obtendremos los bits de paridad calculando la paridad de los datos como indica la tabla siguiente:

 

La secuencia que teníamos que haber transmitido sería 110100110011001.

Si comprobásemos con la tabla de paridad el código Hamming nos mostraría un error en el bit D10. Para conocer esto basta con mirar la paridad de los 1 de cada una de las filas P1, P2…P4, como podemos comprobar las filas P2,P3,P4 (si sumamos sus unos) tienen paridad impar, por lo tanto tienen un error, el único bit que engloba a las tres filas es el que ocupa la posición D10 que si lo cambiamos corregiremos el error.

Qué es el código hamming

En informática, el código de Hamming es un código detector y corrector de fallos que lleva el nombre de su inventor, Richard Hamming. En los datos codificados en Hamming se pueden advertir fallos en un bit y corregirlos, no obstante no se distingue entre fallos de 2 bits y de un bit (para lo que se utiliza Hamming extendido). Esto representa una mejora con respecto a los códigos con bit de paridad, que pueden advertir fallos en solo un bit, mas no pueden corregirlo.

Códigos pre-Hamming

Ya antes de los códigos Hamming se emplearon algunos códigos detectores de fallo, como lo fueron el código linteing, mas ninguno llegó a ser tan eficiente como los de Hamming. Ahora se describen ciertos de estos códigos.

Cómo funciona la Paridad

La paridad consiste en agregar un bit, llamado bit de paridad, que indique si el número de los bits de valor 1 en los datos precedentes es par o bien impar. Si un solo bit cambiara por fallo en la transmisión, el mensaje cambiará de paridad y el fallo se puede advertir (nótese que el bit donde se genere el fallo puede ser exactamente el mismo bit de paridad). La convención más habitual es que un valor de paridad 1 señala que hay un número impar de unos en los datos, y un valor de paridad de 0 señala que hay un número par de unos en los datos.

La comprobación de paridad no es muy robusta, puesto que si cambia de forma uniforme un número par de bits, el bit de paridad va a ser válido y el fallo no va a ser detectado. Se emplea cuando se cumplen simultáneamente 2 condiciones: que la probabilidad de que falle un bit es baja y que las fallas de bits son acontencimientos independientes. Así la probabilidad de que fallen 2 (o bien más) bits es bajísima, con lo que cuando no advierte fallo es enormemente probable que el código sea ciertamente adecuado. Se puede destacar que dichas condiciones se ajustan al caso de las memorias de las computadoras modernas mas no ocurre lo mismo con los dispositivos de almacenaje que guardan la información en forma serial (un bit después de otro) ni con los sistemas de transmisión de datos seriales puesto que en estos casos el hecho que falle un bit está vinculado, en forma no abominable, a la falla de otro lindante.

Por otra parte, la paridad, si bien puede advertir que hay fallo, no señala exactamente en qué bit se cometió. Los datos se deben desechar enteramente y volverse a trasmitir. En un medio estruendoso, una transmisión adecuada podría tardar un buen tiempo o bien aun, en el peor caso, no darse jamás. El chequeo de paridad, si bien no es buenísimo, emplea un solo bit, con lo que genera poquísima sobrecarga, y esto es una muy buena noticia en cuanto a optimización de recursos.

4.7/5 - (3 votos)