8.1: Ejercicios de salvia

1

Crea el código Golay (binario) con el constructor codes.GolayCode (). Lea la documentación para asegurarse de construir la versión binaria (no ternaria) y no construir la versión extendida (que es la predeterminada).

1. Usa los métodos de Sage para calcular la longitud, la dimensión y la distancia mínima del código.
2. ¿Cuántos errores puede detectar este código? ¿Cuántos puede corregir?
3. Encuentra una palabra de código distinta de cero e introduce tres errores agregando un vector con tres 1 (tu elección) para crear un mensaje recibido. Demuestre que el mensaje se decodifica correctamente.
4. Recicle sus elecciones de la parte anterior, pero ahora agregue un error más. ¿El nuevo mensaje recibido se decodifica correctamente?

2

Una técnica para mejorar las características de un código es agregar un bit de verificación de paridad general, al igual que el bit de verificación de paridad solitario del código ASCII descrito en Ejemplo\(8.3\). Dichos códigos son referidos como la versión extendida del original.

1. Construir el código Golay (binario) y obtener la matriz de comprobación de paridad. Use los comandos de Sage para ampliar esta matriz y crear una nueva matriz de verificación de paridad que tenga un bit de verificación de paridad general adicional. Puede encontrar útiles los métodos matrix .augment () y .stack (), así como los constructores zero_vector () y ones_matrix () (recordando que especificamos las entradas binarias como que son del campo GF (2).)

   Cree el código extendido suministrando su matriz de comprobación de paridad ampliada al constructor codes.from_parity_check_matrix () y calmente la longitud, dimensión y distancia mínima del código extendido.

2. ¿Cómo son mejores las propiedades de este nuevo código? ¿A qué costo?
3. Ahora crea el código Golay extendido (binario) con el constructor Sage codes.GolayCode () y la palabra clave correcta para obtener la versión extendida. Con suerte, las listas ordenadas de tus palabras clave y las palabras clave de Sage serán iguales. Si no, el método de código lineal .is_permutation_equivalent () debería devolver True para indicar que tu código y el de Sage son solo reordenamientos entre sí.

3

Nota: Este problema es de vacaciones (a partir de Sage\(6.7\)), mientras que algún código Sage buggy para la distancia mínima de un código Hamming se soluciona. El caso r = 2 produce un mensaje de error y para r > 5 el cálculo de la distancia mínima se ha vuelto intolerablemente lento. Por lo que es un poco más difícil hacer una conjetura razonable a partir de\(3\) casos justos.

El doble de un código de\((n,k)\) bloque se forma como todo el conjunto de todos los vectores binarios que son ortogonales a cada vector del código original. El ejercicio 8.6.25 describe esta construcción y pregunta por algunas de sus propiedades.

Puedes construir el dual de un código en Sage con el método.dual_code (). Construir los códigos binarios de Hamming, y sus duales, con el parámetro r que va de 2 a 5, inclusive. Construir una tabla con seis columnas (quizás empleando la función html.table ()) que enumera\(r\text{,}\) la longitud de los códigos, las dimensiones del original y el dual, y las distancias mínimas del original y el dual.

Fórmulas de conjetura para la dimensión y distancia mínima del dual del código Hamming como expresiones en el parámetro\(r\text{.}\)

4

Un código con distancia mínima\(d\) se llama perfecto si cada vector posible está dentro de la distancia\((d-1)/2\) de Hamming de alguna palabra de código. Si ampliamos nuestra noción de geometría para dar cuenta de la distancia de Hamming como métrica, entonces podemos hablar de una esfera de radio\(r\) alrededor de un vector (o palabra clave). Para un código de longitud\(n\text{,}\) tal esfera contendrá

\[ 1 + {n\choose 1} + {n\choose 2} + \cdots + {n\choose r} \nonumber \]

vectores dentro de él. Para un código perfecto, las esferas de radio\(d\) centradas en las palabras de código del código particionarán exactamente el conjunto completo de todos los vectores posibles. (Esta es la conexión que significa que la teoría de la codificación se engrana con problemas de empaque de esferas).

Una consecuencia de que un código de dimensión\(k\) sea perfecto es que

\[ 2^k\left({n\choose 0} + {n\choose 1} + {n\choose 2} + \cdots + {n\choose \frac{d-1}{2}}\right) = 2^n \nonumber \]

Por el contrario, si un código tiene distancia mínima\(d\) y la condición anterior es verdadera, entonces el código es perfecto.

Escribe una función Python, llamada is_perfect () que acepta un código lineal como entrada y devuelve True o False. Demuestre su función comprobando que el código Golay (binario) es perfecto, y luego use un bucle para verificar que los códigos Hamming (binarios) son perfectos para todas las longitudes a continuación\(32\text{.}\)