Informatica

Códigos correctores de errores
Código Hamming
Richard Hamming (1950) ideó un método no sólo para detectar errores sino también para corregirlos, y se conoce como código Hamming. En él se añaden kbits de paridad a un carácter de n bits, formando un nuevo carácter de n + k bits. Los bits se enumeran empezando por 1, no por 0, siendo el bit 1, el de la izquierda, el más significativo. Todo bitcuyo número sea potencia de 2 es un bit de paridad y todos los demás se utilizan para datos.
Para un carácter ASCII de 7 bits, se añaden 4 bits de paridad. Los bits 1, 2, 4 y 8 son bits de paridad; 3,5, 6, 7, 9, 10 y 11 son los 7 bits de datos. Cada bit de paridad comprueba determinadas posiciones de bit y se ajusta de modo que el número total de unos en las posiciones comprobadas sea par, si setrata de paridad par.
Las posiciones de los bits comprobados por los de paridad son:
El bit 1 comprueba los bits 1, 3, 5, 7, 9 y 11.
El bit 2 comprueba los bits 2, 3, 6, 7, 10 y 11.
El bit 4comprueba los bits 4, 5, 6 y 7.
El bit 8 comprueba los bits 8, 9, 10 y 11.
En general, el bit n es comprobado por los bits b1, b2,....,bj, tales que b1 + b2 + .... + bj = n. Por ejemplo, el bit 5 escomprobado por los bits 1 y 4 porque 1 + 4 = 5. El bit 6 es comprobado por los bits 2 y 4 porque 2 + 4 = 6.

Consideremos la palabra de datos de 7 bits “0110101”. Para ver como se generan y utilizanlos códigos Hamming para detectar un error, observe las tablas siguientes. Se utiliza la paridad d para indicar los bits de datos y la p para los de paridad.
En primer lugar los bits de datos seinsertan en las posiciones apropiadas y los bits de paridad calculados en cada caso usando la paridad par.

Si se analiza la tabla anterior la paridad que se debe obtener a la derecha tras la llegada delmensaje sin errores deber 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...