Generar palabras en código Hamming con una distancia mínima dada

Navega tus respuestas
2

Mi comprensión del código Hamming (agregar esto como podría ayudar a alguien en el futuro):

Description: El código 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.

Código-clave: Cada bloque (mensaje + bits de paridad) forma una palabra clave. La lista de palabras de código válidas es conocida tanto para el transmisor como para el receptor. Cuando se encuentra que un bloque 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 difiere entre un par de palabras de código válidas. La distancia mínima entre todos los pares posibles de códigos válidos se denomina la distancia mínima de Hamming.

Preguntas :

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

  • Defina las posiciones 1-7 para los 7 bits de bloque.
  • Designar 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
  • Compute los bits de paridad que serán una función de los bits de datos presentes en el subconjunto de las posiciones anteriores y forman el código.

¿El algoritmo anterior garantizará que las palabras en código generadas tendrán una distancia de hamming mínima 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, estoy publicando esta pregunta aquí para conocer el procedimiento general para generar códigos de Hamming con la distancia mínima dada (o especificada)

    
pregunta Vivek Maran

1 respuesta

1

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

Además, no hay dos bits de datos que puedan tener el mismo patrón de aparición en los bits de paridad, o al cambiar ambos dos bits de datos se obtendría una segunda palabra de código válida a una distancia de solo 2.

Como hay cuatro bits de datos, y $$ \ left (\ array {3 \\ 2} \ right) + \ left (\ array {3 \\ 3} \ right) = 3 + 1 = 4 $$

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

Por lo tanto, la matriz de generación es

$$ \ left [\ array {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} \ right] $$

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

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

$$ \ left [\ array {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} \ right] \ left [\ array {d_0 \\ d_1 \\ d_2 \\ d_3} \ right] = \ left [\ array {d_0 \\ d_1 \\ d_2 \\ d_3 \\ d_0 \ oplus d_2 \ plus d_3 \\ d_0 \ oplus d_1 \ oplus d_3 \\ d_0 \ oplus d_1 \ oplus d_2} \ right] $$

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

    
respondido por el Ben Voigt

Lea otras preguntas en las etiquetas

¿Cómo funciona este circuito inversor de energía? Automatización de producción de electrónica de señal mixta de bajo volumen (prueba de hardware, calibración, parpadeo) [cerrado]