Este es un trabajo que simula el código hamming visite el enlace para ver como funciona:
Ver Ejemplo en PHP:
PROGRAMA DE DETECCION DE ERRORES Codigo Hamming
Teoria Del Funcionamiento:
Hamming (7,4)
Hoy, el código de Hamming se refiere al (7.4) que Hamming introdujo en 1950. El código de Hamming agrega tres bits adicionales de comprobación por cada cuatro bits de datos del mensaje.
El algoritmo de Hamming (7.4) puede corregir cualquier error de un solo bit, pero cuando hay errores en más de un bit, la palabra transmitida se confunde con otra con error en un sólo bit, siendo corregida, pero de forma incorrecta, es decir que la palabra que se corrige es otra distinta a la original, y el mensaje final será incorrecto sin saberlo. Para poder detectar (aunque sin corregirlos) errores de dos bits, se debe añadir un bit más, y el código se llama Hamming extendido. El procedimiento para esto se explica al final.
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…
- Y así sucesivamente.
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.
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 cambiado)
|
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 |
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 paridad |
| 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.
El paso final es evaluar los bits de paridad (recuerde que el fallo se encuentra en d7). El valor entero que representan los bits de paridad es 11 (si no hubieran ocurrido errores este valor seria 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 décimo primero 10001100100 se obtiene de nuevo 10001100101. Eliminando los bits de paró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 sólo se detectaría un error, justo el correspondiente al bit de paridad causante del mismo.
.
) para salir a las 12:00 p.m. de Querétaro, o incluso conseguir reemplazo para que el sábado alguien más se ocupara de nuestras responsabilidades, el pasado Sábado 6 de Junio, estuvo de poca madre.
