Taller N° 15

¿Qué tipos de códigos se conocen?

¿A qué se refiere la equivalencia y automorfismo de códigos?

Dos códigos C y D, q-arios decimos que son equivalentes si se puede obtener uno del otro a través de una combinación de operaciones de los siguientes tipos:

1. Permutación de las posiciones.

2. Permutación de los símbolos de una posición fija.

Como aplicación, un resultado muy útil a la hora de hacer cálculos.

A que se refiere un código lineal.

Como hemos comentado antes, la idea subyacente de los códigos correctores de errores es la redundancia en la información. En este capítulo comentaremos la manera algebraica de controlar dicha redundancia, y de hecho, la codificación y decodificación.

Que son los códigos duales u ortogonales

 Equivalentemente, H es una matriz cuyo espacio nulo es C. Si C es un código con una matriz de generación G en forma estándar, G = (I_k | A), entonces H = (−A^t | I_n − k) es una matriz de comprobación para C. El código generado por H es llamado código dual de C.

Codificación y decodificación de códigos lineales

Ya hemos comentado que para hacer la codificación en códigos lineales usamos una aplicación lineal que tiene que ser inyectiva (1.1.1); luego el espacio de las palabras de longitud k verifica F k ∼= C. Cuando un código es muy grande, se aprecia con claridad la necesidad de codificar y descodificar por fórmula. El proceso de codificación es en general, mucho más fácil que el de decodificación. La razón es que en la decodificación hemos incluido la corrección de errores, lo más costoso.

Cuáles son los constructores con códigos lineales.

- Pinchado Ya hemos visto algunos resultados generales en (2.3.2). En el caso de los códigos lineales podemos mejorarlo. Vamos al caso cuando d = 1. La demostración es trivial.

- Extendido También hemos visto ya los resultados generales en (2.3.7 y 2.3.8). Es muy fácil comprobar cualquiera de los siguientes hechos.

- La construcción de Plotkin Recordemos la definición de la construcción de Plotkin en (2.3.10). Es inmediato comprobar que cuando C1 y C2 son códigos lineales también C1 ⊕ C2 es lineal. Aún más.

A que se refiere la Cota de Hamming, Singleton y Códigos MDS

- Cota de Hamming.- Esta cota viene a completar el estudio de los códigos perfectos. Lo que hemos visto en (2.1.20 y 2.1.21) nos indica fácilmente la demostración del siguiente resultado, que se conoce como cota de Hamming o del empaquetado esférico.

- Cota de Singleton y códigos MDS Esta cota es sencilla pero muy ´útil y da lugar a los códigos de Reed Solomon, que veremos después, y que se usan para la reproducción de los CD.

Investigue sobre los tipos especiales de códigos lineales: Hamming y códigos simples, de Golay y Reed-Muller

- Códigos de Hamming La construcción de los códigos de Haming y algunas de sus propiedades en el caso binario las hemos visto en capítulos anteriores. Vamos a extender la definición. Sea Fq un cuerpo finito cualquiera y consideremos F r q con r ≥ 2. Llamamos código de Hamming y denotamos Hq,r a todo aquel código cuya matriz de control se construye de la siguiente manera. La denotamos con Hq,r.

- Códigos simplex Los códigos simplex son aquellos que se realizan como duales de los códigos de Hamming.

- Códigos de Golay Los códigos de Golay fueron propuestos por M. J. E. Golay en 1949. Hay binarios y ternarios. Los binarios se denotan G24, un [24, 12, 8]-lineal y G23, un [23, 12, 7] código. El segundo se obtiene pinchando el primero. Los ternarios se denotan G12 y el G11.

- Códigos de Golay binarios Se construye la matriz G24 = (I12|A12×12) donde la matriz A tiene una la caja inferior derecha de 11 × 11 y se escribe en la primera fila, en la posición i un 1 si i es cuadrado modulo 11 y un 0 en caso contrario. Después se hace un recorrido (shift) en dirección (←). Así que el bloque tiene forma cíclica

- Códigos de Golay ternarios El código de Golay ternario G12 es el [12, 6]-código sobre F3 con matriz G12 = (I6|A), donde

Se puede comprobar directamente cada una de las siguientes propiedades.

- Códigos de Reed-Muller (binarios) Los propusieron por separado (en trabajos independientes) I. S. Redd y D. E. Muller en 1954. Existe también la definición de código de Reed-Muller sobre cuerpos con otra característica. Su distancia mínima es muy pequeña pero se decodifican muy fácilmente. Hay muchas maneras de construirlos. Una de ellas se basa en la construcción de Plotkin (2.3.10).

Investigar los siguientes códigos cíclicos:

Códigos cíclicos y anillos de polinomios

Los códigos cíclicos también se llaman CRC (Códigos de Redundancia Cíclica) o códigos polinómicos. Su uso está muy extendido porque pueden implementarse en hardware con mucha facilidad.
Estos códigos se basan en el uso de un polinomio generador G(X) de grado r, y en el principio de que n bits de datos binarios se pueden considerar como los coeficientes de un polinomio de orden n-1.

Por ejemplo, los datos 10111 pueden tratarse como el polinomio x4 + x2 + x1 + x0

A estos bits de datos se le añaden r bits de redundancia de forma que el polinomio resultante sea divisible por el polinomio generador, sin generar resto.

El receptor verificará si el polinomio recibido es divisible por G(X). Si no lo es, habrá un error en la transmisión.

Ceros de un código cíclico y matriz de control.

Sea C un código cíclico de orden n sobre Fq, con mcd(n, q) = 1, sea ξ una raíz n-ésima primitiva de 1, y sea S un juego completo de representantes de las clases q-ciclotómicas modulo n. Sea g(X) el generador de C (Observación 6.5.6). Como sabemos del Teorema 6.5.5 si g(X) | Xn − 1 entonces

Codificación y decodificación en códigos cíclicos

Como hipótesis general, supongamos que tenemos un código cíclico C ≤ Rn tal que C = hgi, con g el polinomio generador, con gr(g) = r, así que la dimensión dim C = n − r. Comenzamos con la codificación. Vamos a ver una decodificación sistemática. Supongamos que queremos codificar la palabra a0 · · · an−r−1. 1. Hacemos a(X) = Pn−r−1 i=0 aiXn−i−1 2. Luego operamos a(X) = pg + s, con gr(s) < r. 3. Finalmente hacemos c = a − s = pg. Para decodificar, se puede proceder de la siguiente manera. 1. Se recibe un vector p ∈ Rn. 2. Se divide p = gs + t, con gr(t) < r. Es claro que si p = c + e, entonces existe s 0 ∈ Rn tal que p = c 0 g +e. La unicidad del algoritmo de la división nos dice que c = c 0 ; luego p − t es la palabra buscada. Esta decodificación es en realidad una decodificación por síndrome. Vamos a comprobar que existe una matriz de control cuyos síndromes son precisamente los restos obtenidos