Codigo Hamming
Enviado por mixmaster • 1 de Diciembre de 2012 • 462 Palabras (2 Páginas) • 490 Visitas
Código Hamming
Es un código que nos va a permitir detectar y corregir errores en bits este fue nombrado así por su inventor Richard Hamming.
Una complicación de este código es que no distingue de los errores de 2 bits y de un bit. Este código representa una mejora con respecto a los bits de pariedad que solo pueden detectar errores en un bit y que no pueden corregirlo.
El algoritmo es el siguiente:
1. Todos los bits cuya posición es potencia de dos se utilizan como bits de paridad (posiciones 1, 2, 4, 8, 16, 32, 64, etc.).
2. Los bits del resto de posiciones son utilizados como bits de datos (posiciones 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, etc.).
3. Cada bit de paridad se obtiene calculando la paridad de alguno de los bits de datos. La posición del bit de paridad determina la secuencia de los bits que alternativamente comprueba y salta, a partir de éste, tal y como se explica a continuación. Posición 1: salta 0, comprueba 1, salta 1, comprueba 1, etc.
Posición 2: salta 1, comprueba 2, salta 2, comprueba 2, etc.
Posición 4: salta 3, comprueba 4, salta 4, comprueba 4, etc.
Posición 8: salta 7, comprueba 8, salta 8, comprueba 8, etc.
Posición 16: salta 15, comprueba 16, salta 16, comprueba 16, etc.
Regla general para la posición n es: salta n-1 bits, comprueba n bits, salta n bits, comprueba n bits...
En otras palabras, el bit de paridad de la posición 2k comprueba los bits en las posiciones que tengan al bit k en su representación binaria. Dicho a la inversa, el bit 13, por ejemplo, es chequeado por los bits 8, 4 y 1, al ser estos los de su representación binaria: 13=1101(2); 8=1000(2); 4=0100(2); 1=0001(2).
Así, por ejemplo, para los primeros términos se tiene:
En la Posición 1 (2^0 = 1), comprobaríamos los bits: 3, 5, 7, 9, 11, 13...
En la Posición 2 (2^1 = 2), los bits: 3, 6, 7, 10, 11, 14, 15...
En la Posición 4 (2^2 = 4), los bits: 5, 6, 7, 12, 13, 14, 15, 20, 21, 22, 23...
En la Posición 8 (2^3 = 8) tendríamos: 9, 10, 11, 12, 13, 14, 15, 24-31...
Siguiendo el algoritmo hasta completar la nueva cadena.
Hamming 7.4
Hamming lo introdujo en 1950 en donde agrega 3 bits mas que van a comprobar cada 4 bits de datos en un mensaje
Puede correr errores de un bit sin embargo presenta complicaciones en errores de mas de un bit, esto por que cuando una palabra es trasmitida puede llegar a confundirla con otra con un error en un solo bit con esto la va a corregir pero de forma equivocada por que esta corrigiendo otra palabra distinta a la original y el mensaje final no será incorrecto y esto no se sabrá.
...