Cómo corregir un mensaje utilizando código de Hamming

Question

Así que quiero trabajar en este proyecto de verano para corregir errores en la transmisión de un mensaje utilizando código de Hamming, pero no puedo averiguar cómo funciona realmente. He leído muchos artículos en línea, pero no entiendo muy bien el algoritmo. ¿Alguien puede explicar en términos sencillos?

Gracias.

Answer 1

Se trata de distancia de Hamming .

La distancia de Hamming entre dos de base-2 valores es el número de bits en que difieren. Así que si usted transmita A, pero recibe B, entonces el número de bits que debe haber sido cambiado en la transmisión es la distancia de Hamming entre A y B.

Los códigos de Hamming son útiles cuando los bits en cada palabra de código se transmiten de alguna forma por separado. No nos importa si están en serie o en paralelo, pero no son, por ejemplo combinado en un valor analógico que representa varios bits, o comprimido / encriptado después de la codificación.

Por lo tanto, cada bit es independientemente (al azar con cierta probabilidad fija), ya sea recibida correctamente, o volteado. Suponiendo que la transmisión es bastante fiable, la mayoría de los bits se reciben correctamente. Por lo tanto los errores en un pequeño número de bits son más probables, y los errores simultáneos en un gran número de bits son poco probables.

Por lo tanto, un código de Hamming por lo general tiene por objeto corregir errores de 1 bit, y / o para detectar errores de 2 bits (ver el artículo de Wikipedia para más detalles de los dos tipos principales). / Códigos que detectar los errores más grandes correctos se pueden construir, pero que yo sepa no se utilizan más.

El código funciona por uniformemente espaciamiento de los puntos de código en el "espacio de Hamming", que en términos matemáticos es el espacio métrico que consiste en todos los valores del tamaño de la palabra correspondiente, con distancia de Hamming como la métrica. Imagínese que cada punto de código está rodeado por una pequeña "zona tampón" de los valores no válidos. Si un valor que se recibe no es un punto de código, a continuación, un error debe haber ocurrido, porque sólo los puntos de código válido se transmiten siempre.

Si un valor en la zona de amortiguamiento se recibe, a continuación, en la suposición de que se produjo un error de 1 bit , el valor que fue transmitida debe ser la distancia 1 a partir del valor recibido. Pero debido a que los puntos de código se separan hacia fuera, sólo hay un punto de código que cerrar. Así que ha "corregido" a ese punto de código, basándose en que es más probable que el mayor error que sería necesaria para cualquier otro punto de código para producir el valor recibido un error de 1 bit. En términos de probabilidad, la probabilidad condicional de que ha enviado el punto de código cercano es mayor que la probabilidad condicional de que usted envíe cualquier otro punto de código, dado que he recibido el valor que hice. Así que supongo que ha enviado el uno cerca, con una cierta confianza basada en la fiabilidad de la transmisión y el número de bits en cada palabra.

Si un valor no válido se recibe, que es equidistante de dos puntos de código, entonces no puedo decir que uno es más probable que sea el verdadero valor que el otro. Así que puedo detectar el error, pero no puedo corregirlo.

Obviamente errores de 3 bits no se corrigen por un código de Hamming SECDED. El valor recibido está más alejada del valor que en realidad se envió, lo que es otro punto de código, y yo erróneamente "corregir" a un valor incorrecto. Así que o bien necesita la transmisión suficientemente fiables que no se preocupa por ellos, o de lo que necesita la detección de errores de nivel superior, así (por ejemplo, una CRC sobre todo un mensaje).

Answer 2

específicamente de Wikipedia , el algoritmo es el siguiente:

1. Número de los bits a partir de 1: bit 1, 2, 3, 4, 5, etc
.
2. Escribe los números de bits en binario. 1, 10, 11, 100, 101, etc.
3. Todas las posiciones de bits que son potencias de dos (tener sólo un 1 bit en forma binaria de su posición) son bits de paridad.
4. Todas las otras posiciones de bits, con dos o más 1 bits en la forma binaria de su posición, son bits de datos.
5. Cada bit de datos está incluido en un conjunto único de 2 o más bits de paridad, tal como se determina por la forma binaria de su posición de bit.
   1. Parity bit 1 cubre todas las posiciones de bit que tienen el bit menos significativo: bit 1 (el bit de paridad en sí), 3, 5, 7, 9, etc.
   .
   2. Parity bit 2 cubre todas las posiciones de bit que tienen el segundo menos significativo conjunto de bits: Bit 2 (el bit de paridad en sí), 3, 6, 7, 10, 11, etc
   .
   3. Bit de paridad 4 cubre todas las posiciones de bit que tienen el tercio menos significativo conjunto de bits:. Bits 4-7, 12-15, 20-23, etc.
   4. Bit de paridad 8 cubre todas las posiciones de bit que tienen el cuarto menos significativo conjunto de bits:. Bits 8-15, 24-31, 40-47, etc.
   5. En general, cada bit de paridad cubre todos los bits en el que el binario Y de la posición de paridad y la posición de bit no es cero.

Answer 3

El Wikipedia artículo lo explica bastante bien.

Si usted no entiende un aspecto específico del algoritmo, entonces tendrá que reformular (o detalle) su pregunta, para que alguien pueda abordar su parte específica del problema.