CÓDIGOS LINEALES

¿Qué tipos de códigos se conocen?

Códigos bloque y códigos lineales

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

La definición tradicional de equivalencia de códigos es la siguiente (véanse, por ejemplo [4, 5, 9]).

2.2.1. Definición. 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.

Un codigo lineal q-ario de longitud n y rango k es un subespacio L ⊂ F n q de dimensión k. Así el subespacio L es un [n, k]q-código;

Si L tiene distancia d entonces L es un [n, k, d]q-código;

Si L ⊂ Z n 2 , en general se escribe simplemente [n, k, d]-código.

Que son los códigos duales u ortogonales

Sea F un cuerpo finito y C ≤ F n un subespacio. Sabemos que dim C ⊥ + dim C = n.

3.2.2. Definición. Sea C un código lineal con matriz de control H = H(C). El código dual de C que denotamos C ⊥ es justo el generado por H. Claramente,

C ⊥ =  x ∈ F n q | xGt = 0 = Ni G t  = Nd (G) y C ⊥ es un [n, n − k]-código lineal si C es un [n, k]-código lineal. Aún más, se puede probar fácilmente que, en la situación de la definición anterior, H = G C ⊥ 

3.2.3. Definición. Un código lineal C se llama auto ortogonal si C ≤ C ⊥ y se llama auto dual si la igualdad se verifica; es decir, C = C ⊥ Claramente, para ser auto dual, es condición necesaria tener dimensión n/2 ∈ N.

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 formula. 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.

3.5.1. Corolario. Sea C un [n, k, 1]-código sobre Fq y sea C ? i el código pinchado en la i-´esima coordenada. Si C ? i 6= 0 entonces es un [n−1, k? , d? ]-código, donde, 1. k ? = k si (0, . . . , 1i , 0 . . . , 0) 6∈ C. 2. Si k > 1, y no se cumple el apartado anterior será un [n−1, k−1, 1]-código.

3.5.2. Sea C un código lineal sobre F. Sea C ? el código pinchado en la ´ultima coordenada y luego extendido (por definición, también en la ´ultima). Entonces C = C ? si y solo si C es de tipo par.

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.

3.5.3. Observación. 1. Extendido de lineal es lineal. Aún más, si C es lineal y tiene parámetros [n, k, d] entonces Cb tiene parámetros h n + 1, k, db i , donde db= {d, d + 1}.

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

La construcción de los códigos de Hamming 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. 1. Consideramos todos los distintos subespacios de dimensión 1 de F r q . Sabemos que hay exactamente q r−1 q−1 (q r son todos, q r − 1, porque el < 0 > tiene dimensión 0, y q r−1 q−1 porque los múltiplos se absorben).

Investigar los siguientes códigos cíclicos:

7.1.1. Definición. Un [n, k]-código lineal C sobre Fq se llama código cíclico si cumple que es cerrado para permutaciones cíclicas; es decir, (x0, . . . , xn−1) ∈ C ⇒ (xn−1, . . . , xn−2) ∈ C.

Códigos cíclicos y anillos de polinomios

Seguimos suponiendo que mcd(n, p) = 1. Considérese F n q con la base canónica En y Rn = F n q /(Xn − 1), como hemos estudiado, con su base canónica Xn =  1, X, X2 , . . . , Xn (abusando de notación, porque deberían de tener barras). Sea φ : En → Xn tal que φ(ei) = Xi−1 , i = 1, . . . , n. Esta correspondencia induce un isomorfismo Ψ : F n q −→ Rn que dejaremos en notación fija.

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-´esima primtitiva de 1, y sea S un juego completo de representantes de las clases q-ciclot´omicas 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 g = Y t∈T ⊆S mξ t .

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.