Saltar a contenido principal

Sección 8.8 Sage

Sage contiene una colección importante de códigos lineales y una variedad de métodos que pueden ser usados para investigarlos.

Subsección 8.8.1 Construyendo Códigos Lineales

El objeto codes puede ser usado para obtener una lista concisa de los códigos implementados disponibles. Escriba codes. y presione Tab. La mayor parte de las interfaces a Sage le entregarán una lista. Puede usar el signo de interrogación al final del nombre de un método para aprender más sobre los distintos parámetros.

Usaremos el código binario de Hamming \((7,4)\) clásico como ilustración. “Binario” quiere decir que tenemos vectores con solo ceros y unos, \(7\) es el largo y significa que los vectores tienen \(7\) coordenadas, y \(4\) es la dimensión, lo que significa que este código contiene \(2^4=16\) vectores. La documentación supone que sabemos unas pocas cosas de más adelante en el texto. Usamos GF(2) para especificar que el código es binario — esto tendrá más sentido después de haber estudiado cuerpos finitos. Un segundo parámetro es r y podemos ver de las fórmulas en la documentación que poniendo r=3 nos dará largo \(7\text{.}\)

Subsección 8.8.2 Propiedades de los Códigos Lineales

Podemos ahora examinar el código que acabamos de construir. Primero su dimensión.

El código es suficientemente pequeño como para listar todas sus palabras.

La distancia mínima es posiblemente una de sus propiedades más importantes. Los códigos de Hamming siempre tienen distancia mínima \(d=3\text{,}\) de manera que siempre son correctores de un error.

Sabemos que la matriz verificadora y la matriz generadora son útiles para la construcción, descripción y análisis de los códigos lineales. Los nombres de los métodos en Sage son un poco crípticos. Sage tienen rutinas para analizar matrices con elementos de diferentes cuerpos, de manera que haremos buena parte del análisis de estas matrices dentro de Sage.

La matriz generadora del texto tienen columnas que son palabras del código, y combinaciones lineales de las columnas (el espacio de columnas de la matriz) son palabras del código. En Sage la matriz generadora tiene filas que son palabras del código y el espacio de filas de la matriz es el código. Tenemos acá otro punto en que debemos traducir mentalmente entre una elección hecha en el texto y un elección hecha por los desarrolladores de Sage.

A continuación una verificación parcial de que estas dos matrices son correctas, ejercitando el Lema 8.3.5. Note que necesitamos transponer la matriz generadora por las razones expuestas antes.

Notemos que la matriz verificadora puede no ser canónica y que la matriz generadora puede no ser estándar. Sage puede producir una matriz generadora que tenga un conjunto de columnas que formen la matriz identidad, pero no se garantiza que estas columnas sean las primeras. (Columnas, no filas.) Tal matriz se dice sistemática, y el método Sage es .systematic_generator_matrix().

Subsección 8.8.3 Decodificando un Código Lineal

Podemos decodificar mensajes recibidos originados por un código lineal. Supongamos que recibimos el vector binario de largo \(7\)r.

Podemos reconocer que uno o más errores han ocurrido, pues r no pertenece al código, dado que el siguiente cálculo no resulta en el vector cero.

Un código lineal tiene un método .decode. Usted puede elegir entre distintos algoritmos, pero los códigos de Hamming tienen su algoritmo particular. El algoritmo por defecto es el del uso de síndromes.

Si estamos dispuesto a suponer que solo ha ocurrido un eror (lo que podemos, si la probabilidad de error en una entrada particular del vector es muy baja), entonces vemos que ocurrió un error en la tercera posición.

Recuerde que podría ser que ocurra más de un error. Por ejemplo, supongamos que el mensaje es el mismo de antes y ocurren errores en la tercera, quinta y sexta posiciones.

Entonces parece querecibimos una palabra del código, por lo que suponemos que no hubo errores en absoluto, y decodificamos incorrectamente.