Genere palabras clave de hamming con una distancia mínima dada

Mi comprensión del código hamming (agregando esto, ya que podría ayudar a alguien en el futuro):

Descripción: El código de Hamming es básicamente un código de verificación de paridad extendida. El mensaje se divide en bloques y se agregan múltiples bits de paridad en cada bloque de mensaje (por el transmisor) de manera que estos bits indiquen la posición del bit de error en ese bloque.

Palabra clave: Cada bloque (mensaje + bits de paridad) forma una palabra clave. La lista de palabras de código válidas es conocida tanto por el transmisor como por el receptor. Cada vez que se encuentra un bloque que no coincide con la lista de palabras de código, se considera un error y se aplica una corrección.

Distancia de Hamming: Es el número de bits que difieren entre un par de palabras clave válidas. La distancia mínima entre todos los pares posibles de códigos válidos se denomina distancia mínima de hamming.

Preguntas:

Actualmente estoy usando el método de paridad para generar códigos de hamming. Como ejemplo, haré lo siguiente para generar un código de hamming (7,4)

  • Defina las posiciones 1-7 para los 7 bits del bloque.
  • Designe la posición {1,2,4} , que son potencias de 2, para bits de paridad.
  • Designe otras posiciones {3,5,6,7} para bits de datos
  • Calcule los bits de paridad que serán una función de los bits de datos presentes en el subconjunto de las posiciones anteriores y forme el código.

¿Garantizará el algoritmo anterior que las palabras clave generadas tendrán una distancia mínima de hamming de 3? Si no, ¿qué algoritmo debo usar para resolver el problema de generar códigos hamming con la distancia mínima dada (o especificada)?

Nota: Dado que fue una tarea laboriosa encontrar la distancia mínima de las palabras de código de 7 bits generadas, publico esta pregunta aquí para conocer el procedimiento general para generar códigos Hamming con la distancia mínima dada (o especificada).

Pensando... Esta pregunta podría ser mejor en Signal Processing SE porque se trata más de teoría de la información que de diseño de circuitos.
@KingDuken. Se trata de comunicaciones digitales, por lo que está bien aquí, pero Hamming Code está ampliando los límites.
Tenga en cuenta que su segunda y tercera viñetas son completamente inútiles. Intercalar el orden de bits no tiene efecto sobre la distancia de hamming.

Respuestas (1)

Para tener una distancia mínima de 3, es necesario que un solo cambio en un bit de datos cambie también al menos dos bits de paridad. Por lo tanto, cada bit de datos debe aparecer en las ecuaciones de 2 o 3 bits de paridad.

Además, dos bits de datos no pueden tener el mismo patrón de aparición en los bits de paridad o, de lo contrario, cambiar esos dos bits de datos daría como resultado una segunda palabra de código válida a una distancia de solo 2.

Como hay cuatro bits de datos, y

( 3 2 ) + ( 3 3 ) = 3 + 1 = 4

deben aparecer todas las combinaciones de 2 y 3 bits de paridad.

Así la matriz de generación es

[ 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 0 1 1 1 1 0 1 1 1 1 0 ]

y todas las demás matrices de generación de forma estándar válidas son solo permutaciones.

Todas las palabras de código se pueden generar luego mediante la multiplicación de matrices utilizando un campo finito, comúnmente denominado GF(2), donde la operación aditiva es XOR y la operación multiplicativa es AND.

[ 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 0 1 1 1 1 0 1 1 1 1 0 ] [ d 0 d 1 d 2 d 3 ] = [ d 0 d 1 d 2 d 3 d 0 ⊕ d 2 ⊕ d 3 d 0 ⊕ d 1 ⊕ d 3 d 0 ⊕ d 1 ⊕ d 2 ]

Si sus viñetas son requisitos en lugar de un plan, reordene las filas para colocar los bits de paridad en las posiciones especificadas.

Muchas gracias por la respuesta!. Estoy tratando de comprender tu respuesta. ¿Puede ayudarme a entender que "dos bits de datos no pueden tener el mismo patrón de apariencia en los bits de paridad" proporcionando un ejemplo? Tengo dificultades para agarrarlo.
@VivekMaran: Digamos que todas las ecuaciones de bits de paridad contienen
d 0 ⊕ d 1
o ninguno de estos bits de datos. Luego, para cualquier palabra clave válida
( d 0 , d 1 , d 2 , d 3 , pag 1 , pag 2 , pag 3 )
, la palabra clave
( d 0 ¯ , d 1 ¯ , d 2 , d 3 , pag 1 , pag 2 , pag 3 )
también es válido, y la distancia entre estos es solo 2. Necesita al menos un bit que dependa de d_0 pero no de d_1 o al menos uno que dependa de d_1 pero no de d_0.
Gracias, en general 1. Asegúrese de que cada bit de datos afecte a 'n' bits de paridad, donde 'n' debe ser mayor que (o) igual a 'reqd_min_hamming_dist' 2. Asegúrese de que no aparezcan dos bits de datos en el mismo patrón en la ecuación de paridad. Entonces, entiendo lo que dices :). Pero me preocupa que sea fácil para mí pasar por alto cualquier otro caso especial que pueda tener que manejar en problemas similares. Gracias por la respuesta. Votaré y aceptaré.
Genere palabras clave de hamming con una distancia mínima dada
RespuestasAquíPolítica de privacidad1y, 0v