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