1
Construya el código (binario) Golay con el constructor codes.GolayCode(). Lea la documentación para asegurarse de construir la versión binaria (y no la ternaria), y no construya la versión extendida (que es el default).
Use métodos Sage para calcular el largo, la dimensión y la distancia mínima del código.
¿Cuántos errores puede detectar este código? ¿Cuántos puede corregir?
Encuentre una palabra distinta de cero en el código e introduzca tres errores sumando un vector con tres 1's (de su elección) para crear un mensaje recibido. Muestre que el mensaje se decodifica correctamente.
Recicle sus elecciones de la parte anterior, pero ahora agregue un error adicional. ¿Se decodifica correctamente el mensaje recibido?
2
Una técnica que permita mejorar las características de un código es agregar un bit de paridad general, tal como el bit de paridad del código ASCII descrito en el Ejemplo 8.3. Tales códigos se conocen como versiones extendidas del código original.
-
Construya el código de Golay binario y obtenga la matriz evrificadora. Use comandos Sage para extender esta matriz creando una nueva matriz de paridad que considere un bit de paridad global adicional. los métodos .augment() y .stack() para matrices le pueden resultar útiles, así como los constructores zero_vector() y ones_matrix() (recordando que especificamos las entradas binarias como pertenecientes al cuerpo GF(2).)
Cree el código extendido entregando la matriz de paridad aumentada al constructor codes.from_parity_check_matrix() y calcule la longitud, dimension y distancia mínima del código extendido.
¿En qué sentido son mejores las características de este nuevo código? ¿A qué costo?
Ahora cree el código de Golay binario extendido con codes.GolayCode() y la opción apropiada para obtener la versión extendida. Con algo de suerte, las listas ordenadas de sus palabras y las del código implementado en Sage, serán las mismas. Si no, el método .is_permutation_equivalent() debiera retornar True indicando que su código y el de Sage son simplemente reordenamientos, el uno del otro.
3
El dual de un código de bloque \((n,k)\) está formado por el conjunto de los vectores bianrios ortogonales a todos los vectores del código original. El Ejercicio 8.5.25 describe esta construcción y pregunta por algunas de sus propiedades.
Se puede obtener el dual de un código en Sage con el método .dual_code(). Construya los códigos de Hamming binarios, y sus duales, con el parámetro r variando desde 2 hasta 5. Construya una tabla con seis columnas (posiblemente usando la función html.table()) que liste \(r\text{,}\) el largo del código, la dimensión del código original, la de su dual, la distancia mínima del código y la de su dual.
Conjeture fórmulas para la dimensión y distancia mínima del dual de un código de Hamming en términos del parámetro \(r\text{.}\)
4
Un código con distancia mínima \(d\) se llama perfecto si todo vector posible está a distancia menor o igual a \((d-1)/2\) de alguna palabra del código. Si expandimos nuestra idea de geometría para incluir la noción de distancia de Hamming como la métrica, entonces podemos hablar de una esfera de radio \(r\) en torno a un vector o palabra. Para un código de longitud \(n\text{,}\) una esfera de este tipo contiene
\begin{equation*}
1 + {n\choose 1} + {n\choose 2} + \cdots + {n\choose r}
\end{equation*}
vectores en su interior. Para un código perfecto, las esferas de radio \((d-1)/2\) centradas en las palabras del código particionan exactamente el espacio de todos los vectores posibles. (Esto es lo que establece una relación entre la teoría de códigos y los problemas de empaquetamiento de esferas.)
Una consecuencia de que un código de dimensión \(k\) sea perfecto es que
\begin{equation*}
2^k\left({n\choose 0} + {n\choose 1} + {n\choose 2} + \cdots + {n\choose \frac{d-1}{2}}\right) = 2^n
\end{equation*}
Recíprocamente, si un código tiene distancia mínima \(d\) y cumple la condición anterior, entonces el código es perfecto.
Escriba una función en Sage, llamada is_perfect() que tome un código lineal como entrada y retorne True o False según si el código es o no perfecto. Demuestre su función verificando que el código de Golay binario es perfecto, y use un bucle para verificar que los códigos de Hamming binarios son perfectos para longitudes menores a \(32\text{.}\)
