Grado en matem´aticas. Curso 2013-2014 C´odigos correctores de errores Juan Jacobo Sim´on Pinero 21 de septiembre de 2013

´Indice general 1. Informaci´ on y c´ odigos 1.1. La transmisi´ on de la informaci´on . . . . . . . . . . . . . . . . . . 1.1.1. Tipos de c´ odigos . . . . . . . . . . . . . . . . . . . . . . . 1.2. Transmisi´ on de s´ımbolos a trav´es de un canal con interferencias . . . . . . . . . . . . . . . . . . . . . . .

3 3 5 6

2. Generalidades sobre C´ odigos 11 2.1. Conceptos b´ asicos . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2. Equivalencia y automorfismos de c´odigos . . . . . . . . . . . . . . 19 2.3. Construcci´ on de c´ odigos a partir de otros . . . . . . . . . . . . . 19 3. C´ odigos lineales 3.1. Conceptos b´ asicos . . . . . . . . . . . . 3.2. C´ odigos duales u ortogonales . . . . . . 3.3. Pesos y distancias . . . . . . . . . . . . 3.4. Codificaci´ on y decodificaci´on en c´odigos lineales . . . . . . . . . . . . . . . . . . . 3.5. Construcciones con c´odigos lineales . . . 4. Cotas a los par´ ametros 4.1. Generalidades . . . . . . . . . . . 4.2. Cota de Hamming . . . . . . . . 4.3. Cota de Singleton y c´odigos MDS 4.4. Otras cotas . . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22 22 26 26

. . . . . . . . . . . . . . . . . . . . . . . . . . . .

29 33

. . . .

36 36 38 38 39

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

5. Tipos especiales de c´ odigos lineales 40 5.1. C´ odigos de Hamming y c´odigos simplex . . . . . . . . . . . . . . 40 5.2. C´ odigos de Golay . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 5.3. C´ odigos de Reed-Muller (binarios) . . . . . . . . . . . . . . . . . 44 6. Cuerpos finitos 47 6.1. Suma y producto en cuerpos finitos . . . . . . . . . . . . . . . . . 47 6.2. Polinomios y n´ umeros algebraicos . . . . . . . . . . . . . . . . . . 49 6.3. Existencia y unicidad. . . . . . . . . . . . . . . . . . . . . . . . . 51

1

´INDICE GENERAL

2

6.4. Ejemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.5. El anillo Fq [X]/(X n − 1) . . . . . . . . . . . . . . . . . . . . . . 6.6. Automorfismos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7. C´ odigos c´ıclicos 7.1. Conceptos b´ asicos . . . . . . . . . . . . 7.2. C´ odigos c´ıclicos y anillos de polinomios . 7.3. Ceros de un c´ odigo c´ıclico y matriz de control . . . . . . . . . . . . . . . . . 7.4. Codificaci´ on y decodificaci´on en c´odigos c´ıclicos . . . . . . . . . . . . . . . . . . .

53 55 60

. . . . . . . . . . . . . . . . . . . . . . . . . . . .

61 61 62

. . . . . . . . . . . . . .

65

. . . . . . . . . . . . . .

66

8. C´ odigos cl´ asicos 68 8.1. C´ odigos de Hamming (de nuevo) . . . . . . . . . . . . . . . . . . 68 8.2. C´ odigos BCH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 8.3. C´ odigos de Reed-Solomon . . . . . . . . . . . . . . . . . . . . . . 72

Cap´ıtulo 1

Informaci´ on y c´ odigos 1.1.

La transmisi´ on de la informaci´ on

La transmisi´ on de la informaci´on digital consiste en enviar mensajes, o cadenas de “palabras” que son, a su vez, cadenas de elementos de un “alfabeto” o conjunto de s´ımbolos, donde incluimos tambi´en a las se˜ nales de cualquier tipo. As´ı, los mensajes ser´ an cadenas de s´ımbolos que separaremos en palabras (tal vez una o tal vez, muchas). Los s´ımbolos se env´ıan a trav´es de un canal. Un canal es cualquier medio de transmisi´ on, como puede ser el cable de tel´efono, la fibra ´optica, las ondas de radio, el empleado del supermercado que “teclea” en la caja el c´odigo de barras de un producto cuando ha fallado el lector, etc´etera; aunque al final siempre trabajaremos con algunas restricciones. Desde el punto de vista de la fiabilidad de la transmisi´ on hay dos tipos fundamentales de canales; a saber, los canales con interferencia (o ruido) y los canales sin interferencia. Nosotros s´ olo nos ocuparemos del estudio de los canales con interferencia o ruido, que, obviamente, es el caso donde se pueden producir errores. En este texto, adem´ as, s´olo nos ocuparemos de la parte cuantitativa de la transmisi´ on de la informaci´ on y no del significado (si analizamos el contenido de los mensajes que normalmente se transmiten en el mundo, seguro que nos desanimamos). El siguiente cuadro refleja el proceso directo de la transmisi´on de mensajes. Figura 1.1.1: Esquema general emisor

-

canal

-

receptor

Codificar mensajes es reescribirlos (en el caso no trivial) en forma diferente, incluso usando un alfabeto distinto, pero nosotros siempre lo haremos bajo 3

´ Y CODIGOS ´ CAP´ITULO 1. INFORMACION

4

determinadas reglas. Una de ellas es que cada palabra no pueda tener m´as de una correspondiente en el c´ odigo; formalmente, la codificaci´on es una aplicaci´on. Vamos a verlo. Para cualquier alfabeto A, denotamos con P al(A) el conjunto de todas sus palabras. A lo largo de todo el curso los alfabetos ser´an siempre conjuntos finitos. 1.1.1. Definici´ on. Sean A, F alfabetos y sea M ⊆ P al (A) un subconjunto finito. 1. Una codificaci´ on del alfabeto es una aplicaci´ on inyectiva C : A → P al(F). 2. Una codificaci´ on de palabras de M es una aplicaci´ on inyectiva C : M → P al(F). Llamamos c´ odigo a la imagen de C y se llama palabra c´ odigo o simplemente palabra a cada uno de sus elementos. 1.1.2. Observaci´ on. Sean A, F alfabetos y sea M ⊆ P al (A) un subconjunto finito. Supongamos que estamos transmitiendo informaci´on codificada a trav´es de un canal. El proceso de decodificaci´on lo realizaremos siempre en dos pasos; a saber: 1. Separaremos (de alguna forma) la lista de s´ımbolos en partes a las que asignaremos palabras del c´odigo. 2. A cada palabra de c´ odigo le asignaremos su imagen inversa (que es u ´nica) bajo C. 1.1.3. Ejemplo. Supongamos que somos un GPS para un punto que se va a mover en un tablero. Partimos de una casilla “salida” y tenemos que mostrarle la ruta a la casilla “meta”. Nuestro alfabeto y palabras ser´an A = {↑, ↓, ←, →} = M. Vamos a transmitir la ruta al punto de forma codificada; es decir, definiremos una aplicaci´ on C : M → P al (F), para alg´ un conjunto F. Luego se decodificar´a y entonces el punto seguir´ a la ruta que aparece en el tablero. s

 

Elegimos una ruta que se transmitir´a completa ↓, ↓, →, →, ↓, →, →, ↓

  



m

Ahora codificamos. Lo haremos con tres c´odigos diferentes: Codificaci´ on 1: Hacemos F = Z2 , y C (↑) = 0, C (↓) = 1, C (→) = C (←) = 01. Entonces enviamos la cadena 111010110101 que se transmite sin errores y ahora se tiene que decodificar. El problema es que, quien recibe la cadena tiene 10,

´ Y CODIGOS ´ CAP´ITULO 1. INFORMACION

5

m´ as posibilidades de decodificar que la contemplada por nosotros. Vamos a ver dos opciones m´ as: Una es: que se decodifica: Otra: que se decodifica:

1 ↓

1 1 ↓ ↓ 1 ↓

1 ↓

1 ↓ 0 ↑

01 ← 1 ↓

01 10 10 ← → → 0 ↑

1 ↓

1 ↓

0 ↑

1 ↓ 1 ↓

0 ↑

1 ↓

Como se puede apreciar, estas decodificaciones conducen a rutas no deseadas. Para resolver este problema agregamos un s´ımbolo, el “STOP”, digamos ], como en la Clave Morse. Codificaci´ on 2: Hacemos F = Z2 ∪{]}, y C (↑) = 0], C (↓) = 1], C (→) = 10], C (←) = 01] con tres s´ımbolos, pero si s´olo podemos enviar binarios podr´ıamos que hacer algo como F = Z2 , y C (↑) = 01, C (↓) = 001, C (→) = 0001, C (←) = 00001, o sea que el n´ umero de cifras “0” nos indica la direcci´on de la flecha y el “1” el STOP. Entonces enviamos 1]1]10]10]1]10]10]1] o, en binario, 0010010001000100100010001001 Estas codificaciones no dejan lugar a dudas sobre la decodificaci´on. A este tipo de c´ odigos los llamaremos c´odigos de decodificaci´on u ´nica. Hay una tercera alternativa: Codificaci´ on 3: C (↑) = 00, C (↓) = 11, C (→) = 10, C (←) = 01 Esta decodificaci´ on no necesita s´ımbolo de separaci´on porque tiene una propiedad permanente que de antemano sabr´a siempre el decodificador: que las palabras tienen longitud fija; a saber, longitud 2. As´ı que usa dos s´ımbolos y es de decodificaci´ on u ´nica. Enviamos 1111101011101011 y tiene s´ olo una interpretaci´on, la que queremos.

1.1.1.

Tipos de c´ odigos

En general, el uso de los c´odigos abarca tres grandes objetivos en la transmisi´ on de la informaci´ on: 1. Comprimir mensajes. 2. Detectar y corregir posibles errores. 3. Garantizar la privacidad.

´ Y CODIGOS ´ CAP´ITULO 1. INFORMACION

6

En pocas palabras, hacer la transmisi´on r´apida, fiable y segura. La teor´ıa aborda por separado cada uno de estos objetivos, porque son, de hecho, independientes. As´ı, tenemos tres tipos diferentes de c´odigos; a saber, 1. Los c´ odigos compresores. 2. Los c´ odigos correctores de errores. 3. Los c´ odigos criptogr´ aficos o secretos. Nosotros s´ olo nos ocuparemos de los c´odigos correctores de errores. El proceso de codificar, enviar y decodificar, modifica la Figura 1.1.1 a la Figura 1.1.2. Figura 1.1.2: Transmisi´on codificada emisor

-

- codificador 

canal

-

receptor

6 - decodificador 

6

1.1.4. Definici´ on. Decimos que un c´ odigo es de decodificaci´ on u ´nica si cada vez que recibimos una cadena de s´ımbolos, o mensaje, ´esta corresponde con una u ´nica lista de palabras. 1.1.5. Definici´ on. 1. Decimos que una palabra tiene longitud n ∈ N si utiliza exactamente n s´ımbolos. 2. Decimos que un c´ odigo es un c´ odigo en bloques (o bloqueado) si existe n ∈ N, tal que toda palabra es de longitud n. Se tiene por supuesto la definici´on, obvia, de c´odigo de longitud variable. Nosotros s´ olo nos ocuparemos del estudio de los c´odigos en bloques. Un ejemplo t´ıpico e importante de c´ odigo de longitud variable es la Clave Morse. Uno de bloques es el c´ odigo de barras donde, adem´as, todo mensaje tiene exactamente una palabra. 1.1.6. Observaci´ on. Es claro que todo c´odigo en bloques es de decodificaci´on u ´nica.

1.2.

Transmisi´ on de s´ımbolos a trav´ es de un canal con interferencias

Vamos a establecer el contexto que ser´a nuestra hip´otesis de trabajo. Tenemos un canal discreto y sin memoria, digamos C y un conjunto (finito) de

´ Y CODIGOS ´ CAP´ITULO 1. INFORMACION

7

s´ımbolos de entrada al canal (el alfabeto), A, junto con una distribuci´on de probabilidades; la de que aparezcan al enviar mensajes. A la pareja del alfabeto y la distribuci´ on de probabilidades se le llama una fuente de entrada. Por su parte, tenemos tambi´en un P conjunto de s´ımbolos de salida, F con una distribuci´on dada por p(F = v) = A p(v|a)p(a = A), en la notaci´on habitual del c´alculo de probabilidades. Para cada entrada a ∈ A hemos elegido un u ´nico s´ımbolo sa ∈ F, que llamaremos el s´ımbolo correspondiente o deseado para a. Diremos que se ha producido un error de transmisi´ on cuando habiendo enviado el s´ımbolo a, el s´ımbolo recibido no sea sa . Supondremos que la correspondencia es biyectiva. Vamos a hacer algunos c´ alculos suponiendo que la correspondencia naterior es biyectiva. 1. La probabilidad de cometer un error habiendo enviado el s´ımbolo a ∈ A a trav´es de C, es X pe,C (a) = p (s 6= sa |a) = 1 − p (sa |a) . (1.2.1) s∈S

2. Entonces, la probabilidad de que se cometa un error al enviar alg´ un simbolo es la media ponderada X X Pe,C = p(a)pe,C (a) = p(a) (1 − p (sa |a)) a∈A

=

X

a∈A

p(a) −

a∈A

=

1−

X

p(a ∩ sa ) = 1 −

a∈A

X

X

p(a ∩ sa )

a∈A

p(a|sa )p(sa ).

a∈A

De la lista de igualdades anteriores uno usa la que convenga. 1.2.1. Ejemplo. Supongamos que tenemos un cuerpo finito F como conjunto de s´ımbolos de entrada y salida, con distribuciones equiprobables en un canal C. Si p (x|x) = 1 − p entonces peC (x) = p y Pe,C = p. Correcci´ on de errores de transmisi´ on. Esquemas y errores de decisi´ on El objetivo de los c´ odigos correctores de errores es a˜ nadir informaci´on (redundancia) al mensaje para poder recuperarlo a´ un cuando se hayan producido (no muchos) errores durante la transmisi´on. Como veremos, la clave est´a en la manera como agregamos la informaci´on; es decir, c´omo codificamos y tambi´en c´ omo descodificamos. Es ah´ı donde interviene la matem´atica. Vamos a ver c´ omo afectan la interferencia y la correcci´on a la Figura 1.1.2. En la pr´ actica, para trabajar con c´odigos en bloques podemos sustituir, respetando la distribuci´ on de probabilidades, los s´ımbolos de entrada y salida por un cuerpo finito F al que seguiremos llamando alfabeto. Haremos M =

´ Y CODIGOS ´ CAP´ITULO 1. INFORMACION

8

Figura 1.2.1: Correcci´on de errores

canal con interferencia

emisor

receptor

6 - codificador 



6 decodificador



6 correcci´on de - errores 

P alk (A) = Fk y la codificaci´on ser´a una aplicaci´on C : Fk → Fn y as´ı, nuestro c´ odigo en bloques ser´ a ImC = C ⊆ Fn . n Consideremos F , el conjunto de las palabras de longitud n. Un esquema de decisi´ on es una funci´ on parcial de Fn a las palabras del c´odigo; es decir, una relaci´ on donde no todo elemento del dominio tiene imagen (aquellas palabras, que no sepamos c´ omo corregir, no tendr´an imagen). Para cada c ∈ C, definimos Bc = {v ∈ Fn | f (v) = c} .

(1.2.2)

Como f es aplicaci´ on parcial entonces los {Bc }c∈C son disjuntos aunque tal vez no sean una partici´ on de Fn . parcial Consid´erese, pues, un esquema de decisi´on f : Fn −−−−−−→ C. Para una n palabra s ∈ F , si f (s) est´a definido, entonces el esquema “decide” que la palabra enviada fue f (s). Si f (s) no fue la palabra enviada decimos hemos cometido un error de decisi´ on. A continuaci´ on, vemos un gr´afico del proceso completo, donde denotamos C Fn Fn la transmisi´ on a trav´es del canal C. codificaci´ on

Fk −−−−−−−−→ C ⊆ Fn

C

esquema

decodificaci´ on

Fn −−−−−−→ C −−−−−−−−−−→ Fk

1.2.2. Observaci´ on. Ya cuando estemos concentrados en los c´odigos, a estos errores los llamaremos errores de decodificaci´on. La raz´on es que se considera la decisi´ on o correcci´ on como parte de la decodificaci´on. Vamos a calcular la probabilidad de cometer un error de decisi´on al “corregir” errores. Una vez fijado un c´odigo, C, tendremos que calcular la probabilidad de que una palabra c ∈ C sea enviada, y esto necesariamente determina una distribuci´ on de la fuente. N´ otese que esto no influye en la probabilidad de cometer un error una vez que se tome una palabra, pues viene dado por la Igualdad 1.2.1. Por su parte, para cada vector v ∈ Fn tendremos que calcular la probabilidad

´ Y CODIGOS ´ CAP´ITULO 1. INFORMACION

9

P de que aparezca en una decodificaci´on. Se calcula como p(v) = c∈C p(v|c)p(c). Como el canal Qnes sin memoria se tiene que, si c = c1 . . . cn y v = v1 . . . vn entonces p(v|c) = i=1 p(vi |ci ), donde p(vi |ci ) es la probabilidad condicionada de las fuentes de entrada y salida de la Igualdad 1.2.1. Por definici´ on, decimos que hemos cometido un error de decisi´on cuando habiendo enviado la palabra c ∈ C recibimos la palabra v 6∈ Bc ; luego la probabilidad condicionada que elegimos usar es p(v|c), y la calcularemos de diversas maneras. As´ı, para una palabra c ∈ C enviada, la probabilidad es ! X X p(b|c) p(v|c) = 1 − pe (c) = v6∈Bc

b∈Bc

y la probabilidad total de error de decisi´on es, en vista de que   X X X p(v|c) Pe (C) = p(c)pe (c) = p(c)  c∈C

=

c∈C

1−

X X

P

c∈C

p(c) = 1

v6∈Bc

p(c)p(b|c) = 1 −

c∈C b∈Bc

X

p(v ∩ f (v))

v∈Fn

ya que, si b ∈ Bc entonces c = f (b) y as´ı p(c)p(b|c) = p(b ∩ f (v)). La suma se completa a todo v ∈ Fn asumiendo que si v 6∈ ∪c∈C Bc entonces p(v ∩ f (v)) = 0, dado que f (v) no existe. Para eliminar la suma doble quitamos la dependencia de que aparezca cada palabra y tomamos el error m´aximo; es decir, definimos Pemax (C) = m´ax {pe (c) | c ∈ C} . Claramente, Pe (C) ≤ Pemax (C) Es tambi´en posible establecer la probabilidad de error en t´erminos de la otra probabilidad condicionada. Recordemos que, para v ∈ Fn , se tiene que P p(v) = c∈C p(v|c)p(c). entonces X X Pe (C) = 1 − p (v ∩ f (v)) = 1 − p(v)p (f (v)|v) v∈Fn

=

X v∈Fn

p(v) (1 − p (f (v)|v)) =

v∈Fn

X

p(v)pe (v).

v∈Fn

Entonces, para poder calcular la probabilidad total de error de decisi´on necesitamos tres ingredientes: el primero es la distribuci´on {p(c) | c ∈ C}, el segundo es la distribuci´ on {p(v|c) | (c, v) ∈ C × Fn } y el otro es la familia {Bc }. 1.2.3. Ejemplos. Vamos a ver algunos esquemas de decisi´on. Transmitimos en un canal discreto y sin memoria con s´ımbolos de entrada y salida F. Sea C ⊂ An un c´ odigo con |C| = M . Consid´erense los siguientes esquemas de parcial

decisi´ on f : Fn −−−−−−→ C,

´ Y CODIGOS ´ CAP´ITULO 1. INFORMACION

10

1. Supongamos que para cada c ∈ C y v ∈ Fn conocemos p(c|v). Con estos datos definimos p (C|v) = {p(c|v) | c ∈ C} y podemos definir f (v) ∈ C como el vector tal que p (f (v)|v) = m´ax p (C|v). Este esquema se conoce como error m´ınimo en la decodificaci´ on de probabilidad a posteriori y tiene la propiedad de que minimiza el error de decisi´on medio. 2. Un esquema alternativo es considerar la otra probabilidad condicionada. En este caso, para cada v ∈ Fn , definimos p (v|C) = {p(v|c) | c ∈ C} y f (v) como el vector tal que p (v|f (v)) = m´ax p (v|C). Este esquema se conoce como m´ axima verosimilitud en la decodificaci´ on de probabilidad a posteriori.

Cap´ıtulo 2

Generalidades sobre C´ odigos 2.1.

Conceptos b´ asicos

Una vez que hemos fijado la intenci´on y el contexto del estudio de los c´odigos correctores de errores, vamos tambi´en a fijar un poco la notaci´on. 2.1.1. Definici´ on. Sea A un alfabeto (finito), con |A| = q, y consid´erese An , como siempre. Llamamos c´ odigo q-ario en bloques de longitud n a cualquier subconjunto no vac´ıo de An . Al propio An lo llamamos el conjunto ambiente. Sea M = |C|. Decimos que C tiene par´ ametros (n, M ), o que C es un (n, M )c´ odigo sobre A. A los elementos de C les llamaramos palabras del c´ odigo. 2.1.2. Notaci´ on. A los largo de todo el texto, nuestros alfabetos ser´ an siempre cuerpos finitos que denotaremos F o Fq , para q = pr , con p, r ∈ N y p primo (cuando queramos hacer ´enfasis en el cardinal) y entenderemos por c´ odigo un c´ odigo corrector de errores definido en bloques. El conjunto ambiente ser´ a Fn , a quien llamaremos el espacio ambiente. 2.1.3. Ejemplo. [C´ odigos de repetici´on] Consideremos a F2 y supongamos que s´ olo queremos enviar los mensajes “s´ı” y “no”. Vamos a suponer tambi´en que de alguna manera sabemos que el canal comete a lo m´as dos errores cada 5 emisiones. Usamos entonces 5 d´ıgitos como sigue. s´ı 7→ 00000. no 7→ 11111. El c´ odigo es entonces C = {00000, 11111}. Para crear este c´ odigo hemos hecho posiblemente lo m´as antiguo que se hace para eliminar errores, REPETIR la palabra (5 veces). Este tipo de c´odigos se llaman c´ odigos de repetici´ on. 11

´ CAP´ITULO 2. GENERALIDADES SOBRE CODIGOS

12

2.1.4. Ejemplo. El ISBN (International Standard Book Number) es un c´odigo de 11 s´ımbolos; a saber, {0, 1, . . . , 9, X}, y palabras de longitud 10 divididas en 4 grupos de datos, que describimos a continuaci´on. Todos los s´ımbolos, salvo posiblemente el u ´ltimo, son num´ericos. El primer grupo tiene un d´ıgito e indica el idioma en que est´a escrito el libro. El siguiente grupo tiene 2 d´ıgitos e indica la editorial. El tercer grupo tiene 6 d´ıgitos y los asigna la propia casa editorial. El cuarto grupo tiene un solo d´ıgito (num´erico o X). El d´ıgito de control (check sum). El d´ıgito de “control” es lo que nos interesa. Se calcula con la forma “completa a 10”; es decir, si x1 , . . . x9 son los d´ıgitos, hacemos −10x10 ≡ x10 ≡

9 X

i · xi

mod 11

i=1

porque 10 ≡ −1 mod 11. Es decir que x10 cumple que 10 X

i · xi ≡ 0

mod 11.

i=0

La parte izquierda de la congruencia se llama suma de verificaci´ on del pesado de x1 . . . , x10 . El problema aqu´ı es que x10 = 10 es un valor posible y s´olo podemos escribir UN d´ıgito. Entonces, en ese caso hacemos x10 = X y a efectos de c´alculo ya sabemos qu´e n´ umero asignar. Por ejemplo, el c´ odigo 0 − 19 − 859617 − 0 (los guiones se pueden poner donde uno quiera). El primer d´ıgito nos dice 0, que es ingl´es. Los dos siguientes 19 P9 son de Oxford University Press, el 859617 es el asignado por la Casa y i=1 i · xi = 253 ≡ 0 mod 11. Vamos a ver los par´ ametros de este c´odigo. El espacio ambiente es F10 11 . Los d´ıgitos x1 , . . . , x9 s´ olo tienen restricci´on en el alfabeto (no pueden ser 10 o X); as´ı que M = 109 seg´ un la proposici´on anterior, y el m´ınimo de las distancias posibles es d(ISBN ) = 2, ya que lo menos que difieren dos palabras ANTES del d´ıgito de control es 1, pero luego van a diferir en el d´ıgito, as´ı que ser´an al menos 2. Vamos a ver que si se comete un error entonces el c´odigo lo detecta. Sean x = x1 . . . x10 y supongamos que se comete un error que cambia xi0 por yi0 . Hacemos y la palabra alterada. Entonces x − y = i0 (xi0 − yi0 ). N´otese que ni i0 ni xi0 − yi0 son m´ ultiplos de 11, por lo que 11 - y.

´ CAP´ITULO 2. GENERALIDADES SOBRE CODIGOS

13

Distancia m´ınima y correcci´ on Vamos a abordar un nuevo esquema de decisi´on que tambi´en ser´a del tipo de m´ axima verisimilitud. Esta noci´on corresponde a la idea “m´as cerca mientras menos errores se hayan cometido”, sin importar cu´ales fueron los d´ıgitos que se cambiaron. Vamos a formalizar un poco a este esquema de decisi´on porque es el u ´nico que usaremos en el curso. 2.1.5. Definici´ on. Sea F un cuerpo. La distancia de Hamming entre dos vectores u, v ∈ Fn es el n´ umero natural: d(u, v) = |{ı ∈ {1, . . . , n} | u(ı) 6= v(ı)}| . La distancia m´ınima de un c´ odigo, C ⊆ Fn es d(C) = m´ın {d(u, v) | u, v ∈ C} . La siguiente definici´ on es una variante u ´til en algunos c´alculos, pero sobre todo lo ser´ a cuando los c´ odigos sean espacios vectoriales. 2.1.6. Definici´ on. Sea F un cuerpo. Para un vector u ∈ Fn definimos el peso de u como ω(u) = |supp(u)| = d(0, u). 2.1.7. Proposici´ on. Sea C un c´ odigo sobre un alfabeto F. Entonces la distancia de Hamming cumple los axiomas de m´etrica; a saber, 1. d(u, v) = 0 si y s´ olo si u = v. 2. d(u, v) = d(v, u). 3. d(v, u) ≤ d(u, z) + d(z, v). 2.1.8. Observaci´ on. Es f´ acil comprobar las siguientes afirmaciones sobre la distancia y el peso. Sean u, v ∈ Fn . 1. d(u, v) = ω(u − v). 2. ω(v) + ω(u + v) ≥ ω(u). 3. Si F = F2 ; o sea, el caso binario, d(u, v) = ω(u) + ω(v) − 2ω(u ? v), donde “?” es el producto coordenada a coordenada. 4. En el caso no binario, hay contraejemplos al apartado anterior. Una vez que tenemos la m´etrica, para determinar el esquema (v´ease la Ecuaci´ on 1.2.2) usaremos bolas cerradas de alg´ un radio con centro en las palabras del c´ odigo; es decir, si c ∈ C ⊆ F y r ∈ N, Br (v) = {w ∈ Fn | d(v, w) ≤ r} . Es importante tomar en cuenta que si construimos un esquema de decisi´on, las bolas (cerradas) han de ser disjuntas dos a dos. Esto pone fuertes limitaciones al radio y nos hace detenernos en su estudio.

´ CAP´ITULO 2. GENERALIDADES SOBRE CODIGOS

14

2.1.9. Lema. Sea C un c´ odigo en Fn con distancia m´ınima d y sea r ∈ N. Las bolas {Br (c) | c ∈ C} son disjuntas si y s´ olo si r ≤ b d−1 2 c = t. Demostraci´ on. ⇒]. Supongamos que r > t. N´otese primero que si r > d−1 2 entonces 2r > d − 1, as´ı que r + 1 > d − r, luego r ≥ d − r. Ahora bien, Sean x = (x1 , . . . , xn ) e y = (y1 , . . . , yn ) tales que d(x, y) = d, con xij 6= yij y los otros xk = yk , k 6= ij , con j = 1, . . . , d. Sea z = (z1 , . . . , zn ) tal que zij = xij para j = 1, . . . , r. y zik = yik para k = r + 1, . . . , d. El resto, iguales. Entonces d(y, z) = r y d(x, z) = d − r ≤ r, por tanto z ∈ Br (x) ∩ Br (y), lo cual es imposible. ⇐] Supongamos que z ∈ Br (x) ∩ Br (y). Entonces d(x, y) ≤ d(x, z) + d(z, y) ≤ b

d−1 d−1 c+b c ≤ d − 1 < d, 2 2

lo cual es imposible. Por eso, al n´ umero t = b d−1 en como radio de empaque2 c se le conoce tambi´ tado; es f´ acil ver que es el m´aximo de los radios que hacen a las bolas disjuntas dos a dos (v´ease [9, 10]). Como veremos un poco m´as adelante, a t tambi´en se le conoce como la capacidad de correcci´ on. 2.1.10. on. Entonces, para un c´odigo C ⊆ Fn , se tiene que si r ≤  d−1  Observaci´ , el conjunto de bolas {Br (c) | c ∈ C} induce el esquema de decisi´on 2 parcial

f : Fn −−−−−−→ C tal que f (u) = c ⇔ d(u, c) ≤ r para c ∈ C y u ∈ Fn . De la definici´ on de nuestro esquema se puede deducir con facilidad la segunda parte del siguiente resultado. 2.1.11. Teorema. Sea C un c´ odigo y d(C) la distancia m´ınima. Entonces 1. C puede detectar hasta d(C) − 1 errores. c errores. 2. C puede corregir hasta b d(C)−1 2 Demostraci´ on. (1) Sea c la palabra enviada y v la palabra recibida. Si v provine de haber cometido menos de d(C) − 1 errores al transmitir c entonces d(c, v) ≤ d(C) − 1 y por tanto x 6∈ C. (2) Sea de nuevo, c la palabra enviada y v la recibida. Si se han cometido a lo m´ as t = b d(C)−1 c errores entonces v ∈ Bt (c) y se corregir´a con ´exito. 2 2.1.12. Definici´ on. Para un c´ odigo C, se define la capacidad de correcci´ on d(C)−1 como t = b 2 c. 2.1.13. Definici´ on. Un (n, M, d)-c´ odigo es un c´ odigo de longitud n, que contiene M palabras y tiene distancia m´ınima d.

´ CAP´ITULO 2. GENERALIDADES SOBRE CODIGOS

15

Errores de decisi´ on en el esquema de la distancia de Hamming Vamos a calcular la probabilidad de cometer un error en este esquema de decisi´ on. Sea F un cuerpo finito y C ⊆ Fn un c´odigo con distancia m´ınima d(C) = d y capacidad de correcci´on t = b d(C)−1 c. Ya sabemos que si se cometen 2 a lo m´ as t errores en la transmisi´on no habr´a error de decisi´on. Vamos a calcular entonces la probabilidad de que se cometan m´as de t errores. Eso depende de las probabilidades de cometer errores al enviar los s´ımbolos. La probabilidad de que se cometa un error al enviar un s´ımbolo x ∈ Fq es p(Fq \ {x}|x) = p. As´ı que la probabilidad de que se cometan k ≤ n errores en unas posiciones espec´ıficas de una palabra es pk (1 − p)(n−k) . St Sea Sk (c) = {s ∈ Fn | d(c, s) = k}, con k ≤ t. Entonces Bt (c) = k=0 Sk (c)
(uni´ on disjunta). Claramente |Sk (c)| = nk (q − 1)k , luego 1 − pe (c)

= p (≤ t errores) =

X

p(b|c)

b∈Bt (c)

=

t X

n−k

|Sk (c)| pk (1 − p)

k=0

=

t   X n k=0

k

(q − 1)k pk (1 − p)n−k .

Pero esto u ´ltimo ocurre con cada palabra; as´ı que la probabilidad de error (o acierto) en el c´ odigo C es independiente de las palabras y podremos sacarlo como factor com´ un. As´ı, ! t   X X n Pe (C) ≤ p(c) 1 − (q − 1)k pk (1 − p)n−k k c∈C k=0 ! ! t   X X n k k n−k = p(c) 1− p (q − 1) (1 − p) k c∈C k=0 t   X n k = 1− p (q − 1)k (1 − p)n−k . k k=0

2.1.14. Ejemplo. Consideremos el c´odigo binario de repetici´on, de longitud 3. ( 000 . C= 111 En este caso, la distancia m´ınima es d(C) = 3 y t = 1; luego las bolas son B1 (000) = {000, 100, 010, 001}, B2 (111) = {111, 011, 101, 110}. N´otese que B1 ∪ B2 = F 3 . A´ un m´ as, seg´ un lo visto enP el cap´ıtulo si la probabilidad asociada
anterior, 1 n−k a C es uniforme, Pe (C) = 1 − k=0 k3 pk (1 − p) = 3p2 − 2p3 2.1.15. Ejemplo. Volvamos al ejemplo en (1.1.3) del GPS. En ese caso, hab´ıamos

´ CAP´ITULO 2. GENERALIDADES SOBRE CODIGOS

16

definido el c´ odigo  ↑    ↓ C1 = →    ← C1 es un (2, 4, 1)-c´ odigo binario y no Ahora vamos a agregar redundancia  ↑    ↓ C2 = →    ←

7→ 7 → 7 → 7 →

00 11 10 01

detecta ni corrige error alguno. 7→ 7→ 7→ 7→

00|0 11|0 10|1 01|1

C2 es un (3, 4, 2)-c´ odigo binario y detecta 1 error, pero no puede corregir. Un c´ odigo que s´ olo detecta un error se llama c´ odigo detector de un error. Mientras m´ as redundancia agregamos, mejor para la correcci´on y peor para la tasa de trasmisi´ on. Si agregamos dos d´ıgitos m´as,  ↑ 7→ 00|000    ↓ 7→ 11|011 C3 = → 7→ 10|110    ← 7→ 01|101 C3 es un (5, 4, 3)-c´ odigo binario, tiene tasa 1/2, corrige un error y detecta 2, pero NO A LA VEZ. Por ejemplo, si recibimos la palabra 00001. Tenemos dos posibilidades: 1. Si asumimos que s´ olo se puede cometer un error, entonces corregimos 00001 7→ 00000. 2. Si asumimos que se puede cometer m´as de un error entonces 00001 puede provenir de 01101 con dos errores o de 00000 con un error. Entonces detectamos pero no corregimos. Las bolas que determina C3 que tiene t = 1, son B1 (00000) = {00000, 10000, 01000, 00100, 00010, 00001}. B1 (11011) = {11011, 01011, 10011, 11111, 11001, 11010}. B1 (10110) = {10110, 00110, 11110, 10010, 10100, 10111}. B1 (01101) = {01101, 11101, 00101, 01001, 01111, 01100}. Fuera quedan {11000, 00011, 01110, 10101, 11100, 00111, 01010, 10001}. Se deja como ejercicio calcular Pe (C3 ). 2.1.16. Observaci´ on. Normalmente tenemos que decidir si un c´odigo es detector o corrector, aunque los c´odigos detectores no los estudiaremos aparte. 2.1.17. Ejemplo. El c´ odigo del ISBN (2.1.4), como vimos, tien distancia m´ınima d(ISBN ) = 2, entonces detecta un error y no corrige ninguno.

´ CAP´ITULO 2. GENERALIDADES SOBRE CODIGOS

17

2.1.18. Ejemplo. Todo c´ odigo q-ario de longitud n, de repetici´on, es un (n, q, n)c´ odigo.

C´ odigos perfectos y radio de recubrimiento Los c´ odigos perfectos son aquellos para los cuales el esquema de decisi´on inducido por las bolas cerradas tiene una aplicaci´on o funci´on (en el sentido habitual) en vez de una funci´on parcial. En [4] se llama c´odigo de decodificaci´on u ´nica a aquellos que verifican que su esquema es una aplicaci´on. 2.1.19. Definici´ on. Un c´ odigo C sobre un alfabeto F se llama perfecto si la distancia m´ınima es de la forma d = 2t + 1 y [ Fn = Bt (x) x∈C

es decir, si Fn es uni´ on de las bolas de radio d−1 2 ∈ N y centro en las palabras. Vamos ahora a dar un criterio meramente aritm´etico para determinar cu´ando un c´ odigo es perfecto. 2.1.20. Lema. Sea Fq un cuerpo finito. En Fnq , una bola de radio r y centro en un punto v tiene exactamente r   X n j (q − 1) |Br (v)| = j j=0 elementos. Demostraci´ on. Ya visto que para Sj (c) = {s ∈ Fn | d(c, s) = j} se tiene
hemos n j que |Sj (c)| = j (q −1) . El resultado se deduce entonces de la igualdad Bt (c) = St on disjunta). j=0 Sj (c) (uni´ Ahora caracterizaremos a los c´odigos perfectos. 2.1.21. Teorema. Un (n, M, d)-c´ odigo q-ario es perfecto si y s´ olo si M·

t   X n j=0

 d−1 (q − 1) = q , con t = . j 2 j



n

Demostraci´ on. Por hip´ otesis, las bolas son disjuntas, as´ı que t   [ X n Bt (u) = M · |Bt (x)| = M · (q − 1)j j u∈C

j=0

donde hemos fijado un x ∈ C cualquiera. De aqu´ı, es inmediato el resultado. 2.1.22. Ejemplo. Para cualquier (5, M, 3)-c´odigo binario se tiene entonces que M (1 + 5) ≤ 25 , luego M ≤ 5.

´ CAP´ITULO 2. GENERALIDADES SOBRE CODIGOS

18

2.1.23. Ejemplos. Algunos c´odigos perfectos. 1. Todo c´ odigo binario de repetici´on de longitud impar es perfecto (v´ease 2.1.14). Efectivamente. Por la f´ormula del binomio y el hecho de que n−1   X   n 2 X n n = k n−k n+1

k=

k=0

2

se tiene n

2

=

n

(1 + 1) =

n   X n j=0

j

n−1

=

  2 X n j=0

j

+

  n X n k n+1

k=

2

n−1 2

=

n−1   t   2 X n  n  X X n n 2· =M + = (2 − 1)j j j n − j j j=0 j=0 j=0

2. El c´ odigo total.  3. Los c´ odigos binarios de longitud impar de la forma c, 1 + c . Pero estos c´ odigos son triviales. Un problema muy interesante es encontrar TODOS los c´ odigos perfectos. Trataremos este problema m´as adelante. Por lo pronto s´ olo mencionar que hay familias importantes de c´odigos perfectos como los c´ odigos de Hamming. Cuando un c´ odigo no es perfecto, nos interesa saber cu´anto dista de serlo. Para ello usamos el siguiente concepto. 2.1.24. Definici´ on. Sea C un (n, M, d)-c´ odigo sobre F. El radio de recubrimiento de C es ( ) [ n ρ(C) = m´ın r ∈ N | F = Br (c) . c∈C

Es decir, el menor natural tal que la familia de bolas con dicho n´ umero cubre el espacio ambiente. 2.1.25. Observaci´ on. Equivalentemente se puede ver que   ρ(C) = m´axn m´ın (d(v, c)) . v∈F

c∈C

2.1.26. Definici´ on. Sea C un (n, M, d)-c´ odigo sobre F, con radio de empaquetamiento (o capacidad de correcci´ on) t. Decimos que C es cuasi perfecto si ρ(C) = t + 1. 2.1.27. Ejemplo. El c´ odigo C3 de (2.1.15) verifica b d−1 2 c = 1 y ρ (C3 ) = 2. Luego, C3 es quasi perfecto.

´ CAP´ITULO 2. GENERALIDADES SOBRE CODIGOS

2.2.

19

Equivalencia y automorfismos de c´ odigos

La definici´ on tradicional de equivalencia de c´odigos es la siguiente (v´eanse, por ejemplo [4, 5, 9]). 2.2.1. Definici´ on. Dos c´ odigos C y D, q-arios decimos que son equivalentes si se puede obtener uno del otro a trav´es de una combinaci´ on de operaciones de los siguientes tipos: 1. Permutaci´ on de las posiciones. 2. Permutaci´ on de los s´ımbolos de una posici´ on fija. Como aplicaci´ on, un resultado muy u ´til a la hora de hacer c´alculos. 2.2.2. Lema. Todo (n, M, d)-c´ odigo sobre F es equivalente a un (n, M, d)-c´ odigo sobre F, que contiene al vector 0 ∈ Fn . Demostraci´ on. Inmediato del hecho de que las traslaciones son isometr´ıas. A su vez, cada c´ odigo tiene asociado su grupo de automorfismos o autoequivalencias. 2.2.3. Definici´ on. Sea F un cuerpo finito y C ⊆ Fn un c´ odigo. El grupo de automorfismos de C es Aut(C) = {x ∈ Isomn (F) | Cx = C} . De especial inter´es es el grupo de aquellos automorfismos que s´olo hacen permutar a las coordenadas; 2.2.4. Definici´ on. Dos c´ odigos C, D ⊂ Fn , decimos que son permutaci´ on equivalentes si existe una permutaci´ on σ ∈ Sn , tal que Cσ = D. 2.2.5. Definici´ on. Sea F un cuerpo finito y C ⊆ Fn un c´ odigo. El grupo de automorfismos de permutaci´ on es PAut(C) = {x ∈ Sn | Cx = C} .

2.3.

Construcci´ on de c´ odigos a partir de otros

C´ odigos pinchados 2.3.1. Definici´ on. Decimos que pinchamos un c´ odigo C ⊂ Fnq , cuando eliminamos una coordenada fija en todas las palabras; es decir, proyectamos sobre las otras. Una pregunta importante desde el punto de vista de la teor´ıa de c´odigos es qu´e ocurre con los par´ ametros. Es decir, si tenemos un (n, M, d)-c´odigo y denotamos con Ci? al c´ odigo pinchado en la i-´esima corrdenada ¿podemos dar directamente los nuevos par´ ametros?

´ CAP´ITULO 2. GENERALIDADES SOBRE CODIGOS

20

2.3.2. Proposici´ on. Sea C un (n, M, d)-c´ odigo sobre Fq y sea Ci? el c´ odigo pinchado en la i-´esima coordenada. Si d > 1 entonces Ci? es un (n − 1, M, d?i )c´ odigo, donde ( d − 1 si existen u, v ∈ C, con d(u, v) = d y u(i) 6= v(i) d?i = d otro caso. Demostraci´ on. Si |Ci? | < M = |C| entonces tendr´an que existir u, v ∈ C con u 6= v, pero v ? = u? lo cual implica que d(u, v) = 1. Imposible. Luego, |Ci? | = M . El c´ alculo de d?i es inmediato. Para los siguientes resultados, necesitamos el concepto de subgrupo de permutaciones transitivo. 2.3.3. Definici´ on. Decimos que un subgrupo H ≤ Sn es transitivo si act´ ua transitivamente en {1, . . . , n}; es decir, para cualesquier 1 ≤ i, j ≤ n, existe σ ∈ H tal que σ(i) = j (es decir, s´ olo hay una ´ orbita). 2.3.4. Proposici´ on. Sea C un (n, M, d)-c´ odigo. Si P Aut(C) es transitivo entonces los n c´ odigos obtenidos de pinchar C en cada coordenada son permutaci´ on equivalentes. Demostraci´ on. Vamos a ver que C1? es equivalente a Cj? para j = 2, . . . , n. Sea a ∈ C tal que a = (a1 , . . . , aj , . . . , an ) y sea b = aσ1j ∈ C (por la transitividad). Entonces b = (aj , a2 , . . . , aj−1 , a1 , aj+1 , . . . , an ) y en consecuencia b?j = (aj , a2 , . . . , aj−1 , aj+1 , . . . , an ). Hacemos σ = σ12 σ23 . . . σj−2j−1 y se tiene que b?j = (a2 , . . . , aj , . . . , an ) = a?1 . As´ı, (aσ1j )?j σ = a?1 , pero aσ1j ∈ C, luego Cj? σ = C1? . 2.3.5. Ejemplo. Sea C = {00000, 11000, 00111, 11111}. Se puede construir C1? y C5? , y comprobar que no son equivalentes.

C´ odigos extendidos Esencialmente, extender c´odigos es agregar informaci´on, digamos en dos pasos. Hay muchas maneras (lineales) de hacerlo; una especial, es la que se llama “agragar el d´ıgito de control” (de paridad, parity check, en ingl´es). Se hace as´ı, 2.3.6. Definici´ on. Sea C un (n, M, d)-c´ odigo sobre Fq . Hacemos ) ( n+1 X b C = (v1 , . . . , vn , vn+1 ) | (v1 , . . . , vn ) ∈ C y vı = 0 ı=1

Otra vez, queremos conocer los par´ametros por f´ormula. b es un 2.3.7. Proposici´ on. Sea C un (n, M, d)-c´ odigo sobre Fq . Entonces C h i b b n + 1, M, d -c´ odigo, donde d = d o d + 1. Demostraci´ on. Trivial.

´ CAP´ITULO 2. GENERALIDADES SOBRE CODIGOS

21

2.3.8. Observaci´ on. Obtener leyes para los c´odigos extendidos en el caso binario es muy simple. Aqu´ı, trivialmente, db = d + 1 si d es impar y es d en caso contrario.

Concatenaci´ on o suma directa Es importante distinguir entre la suma directa del ´algebra lineal y la suma directa de c´ odigos, que no coinciden. 2.3.9. Definici´ on. Sean C1 , C2 (n1 , M1 , d1 ) y (n2 , M2 .d2 ) c´ odigos q-arios. La concatenaci´ on o suma directa es el c´ odigo {(u | v) | u ∈ C1 , v ∈ C2 } El estudio de los par´ ametros aqu´ı es muy sencillo y el propio lector puede completar la secci´ on.

La construcci´ on de Plotkin 2.3.10. Definici´ on. Sean Ci dos (n, Mi , di )-c´ odigos q-arios, con i = 1, 2, pero n fijo. Formamos un nuevo c´ odigo que llamamos la construcci´ on de Plotkin. C1 ⊕ C2 = {(u | u + v) | u ∈ C1 , v ∈ C2 } 2.3.11. Proposici´ on. Sean Ci dos (n, Mi , di )-c´ odigos q-arios, con i = 1, 2. Entonces C1 ⊕ C2 es un (2n, M1 M2 , d)-c´ odigo, donde d = m´ın {2d1 , d2 }. Demostraci´ on. Sean x = (u1 |u1 + v1 ) e y = (u2 |u2 + v2 ). Entonces d(x, y) = d (u1 , u2 ) + d (u1 + v1 , u2 + v2 ) = ω (u1 − u2 ) + ω (u1 − u2 + v1 − v2 ) . Ahora separamos en casos. Si v1 6= v2 entonces por (2.1.8), d(x, y) ≥ ω (v1 − v2 ) ≥ d2 y la igualdad se alcanza para palabras v1 y v2 que tengan la distancia m´ınima de C2 y u1 = u2 . Si v1 = v2 entonces d(x, y) = 2d (u1 , u2 ) ≥ 2d1 y tambi´en hay palabras que la alcanzan. De aqu´ı, se tiene de inmediato.

Cap´ıtulo 3

C´ odigos lineales 3.1.

Conceptos b´ asicos

Como hemos comentado antes, la idea subyacente de los c´odigos correctores de errores es la redundancia en la informaci´on. En este cap´ıtulo comentaremos la manera algebraica de controlar dicha redundancia, y de hecho, la codificaci´on y decodificaci´ on. Como viene ocurriendo, F siempre denotar´a un cuerpo finito. Cuando se quiera hacer ´enfasis en su cardinal, escribiremos Fq , donde q = |Fq |. Por ejemplo, en el caso del c´odigo C1 = {00, 10, 01, 11} del GPS (1.1.3 y 2.1.15) que vimos antes, lo ampliamos al c´odigo C2 = {000, 101, 011, 110}. Es f´ acil ver que, la regla para ampliarlo es (x, y) 7→ (x, y, x + y) en t´erminos del algebra lineal; es decir, la redundancia puede obtenerse mediante aplicaciones ´ lineales. Vamos a identificarlo. Tenemos C1 = F22 y hacemos f : F22 → F32 , tal que f (x, y) = (x, y, x + y). Claramente C1 ∼ on = C2 . Llamaremos matriz de codificaci´ a la matriz asociada a la codificaci´on (en las bases can´onicas, como escalares opuestos). Se tiene, C2 =< M (f ) >, la matriz en las bases can´onicas. M´as adelante, llamaremos a M (f ) (una) matriz generadora 1 . Ahora hacemos δ : C2 ∼ = F22 → F52 tal que δ(x, y) = (x, y, x + y, x, y) y se obtiene C3 . Esta forma de agregar la redundancia manteniendo fijas la primeras coordenadas (y dejando intacto el c´odigo original) nos produce matrices del tipo M (δ) = (Ik |A) Vamos a formalizar la situaci´on. 3.1.1. Definici´ on. Sea F un cuerpo finito. Un c´ odigo lineal, C, es un subespacio del espacio vectorial Fn . Escribimos [n, k, d]-c´ odigo para un c´ odigo lineal de Fn 1 ¿Generadora o generatriz? Las opiniones est´ an divididas (v´ eanse [4, 7]). Seg´ un el diccionario de la RAE, generadora es “que genera”, mientras que generatriz los reserva para f´ısica y geometr´ıa. En todo caso, ambas est´ an en el diccionario y aunque no estuvieran cada uno las usar´ıa como quisiera. Aqu´ı diremos generadora porque matriz generatriz, todo junto, no nos gusta.

22

´ CAP´ITULO 3. CODIGOS LINEALES

23

con dimF C = k y distancia m´ınima d. Escribiremos s´ olo [n, k]-c´ odigo cuando no nos interese hacer ´enfasis en la distancia m´ınima. 3.1.2. Observaci´ on. Un [n, k]-c´odigo sobre Fq tiene exactamente q k elementos. Para la presentaci´ on de los c´odigos lineales se usan dos tipos de matriz; a saber, la matriz generadora y la matriz de control (parity check matrix ). Comencemos con la matriz generadora. 3.1.3. Definici´ on. Sea C un [n, k]-c´ odigo sobre F. Una matriz generadora de C es cualquiera cuyas filas formen una base para C. Se denota G(C). Sea M una matriz de orden n × n. Denotamos M (i1 , . . . , ir ; j1 , . . . , js ) la submatriz de M que proviene de la intersecci´on de las filas i1 , . . . , ir y las columnas j1 , . . . , js . Abreviemos, M (1, . . . , n; X) = M (−; X) y M (X; 1, . . . , n) = M (X; −) 3.1.4. Definici´ on. Sea C un [n, k]-c´ odigo sobre F. Un conjunto de informaci´ on o conjunto de posiciones de informaci´ on, es un subconjunto I ⊂ {1, . . . , n} tal que, dada cualquier palabra del c´ odigo, (c1 , . . . , cn ) ∈ C y cualquierP posici´ on j = 1, . . . , n existe un u ´nico conjunto de coeficientes {ai,j }i∈I , tal que i∈I ai,j ci = cj . Es decir, que el c´ odigo C puede obtenerse conociendo los valores de las posiciones I. Por ejemplo, si se considera el c´odigo C = {(x, y, z) | z = x + y}, entonces I = {2, 3} es un conjunto de informaci´on. Vamos a comprobarlo. Sean (x, y, x+y) y (x0 , y 0 , x0 + y 0 ) tales que y = y 0 y x + y = x0 + y 0 . Claramente x = x0 . 3.1.5. Definici´ on. Sea C un [n, k]-c´ odigo sobre F con un conjunto de informaci´ on I. Se llama conjunto de redundancia o de posiciones de control a {1, . . . , n} \ I. El ejemplo m´ as simple es la codificaci´ on sistem´ atica. Decimos que un c´odigo es sistem´ atico si al agregar la redundancia hemos mantenido las primeras filas intactas. As´ı, su matriz generadora ser´a de la forma G(C) = M (I|A). Las primeras columnas tienen la informaci´on y las siguientes la redundancia. Un criterio sencillo y muy u ´til para encontrar conjuntos de informaci´on se tiene en el siguiente toerema. 3.1.6. Teorema. Sea C un [n, k]-c´ odigo sobre F con matriz generadora G. Si G tiene k columnas linealmente independientes entonces los ´ındices de dichas columnas forman un conjunto de informaci´ on. (N´ otese que al menos seguro uno hay). Rec´ıprocamente, si I ⊂ {1, . . . , n} es un conjunto de informaci´ on entonces existe una matriz generadora G tal que las columnas con ´ındices en I son linealmente independientes. Demostraci´ on. Supongamos primero que G es una matriz generadora y que tiene ciertas columnas con ´ındices {i1 , . . . , ik }, que son linealmente independientes. Consid´erese la submatriz de las columnas i1 , . . . , ik , sea G(i1 , . . . , ik ). Entonces existe una matriz de operaciones elementales por fila E tal que la submatriz EG(i1 , . . . , ik ) = I. Adem´ as, EG es matriz generadora, tambi´en. Sea c ∈ C

´ CAP´ITULO 3. CODIGOS LINEALES

24

cualquier palabra. Entonces existe a ∈ Fk tal que aEG = c. Por la forma que P tiene EG es claro que c = a y que, para cualquier l = 1, . . . , n, c = r a ij j l jl j = P rjl cij . Rec´ıprocamente, supongamos que I = {i1 , . . . , ik } es un conjunto de informaci´ on. Sea b1 , . . . , bk una base para C y sean a1 , . . . , ak las proyecciones de los bj en las coordenadas de I; es decir, aj = (bj (i1 ), . . . , bj (ik )). Se afirma que a1 , . . P . , ak es linealmente independiente en Fk . Consid´erese una combinaci´ on lineal rj aj = 0. Entonces, tomando cualquier componente, P se tiene rj bj (il ) = 0, lo cual implica que rj = 0 para todo j = 1, . . . , k pues I es conjunto de informaci´ on y por tanto las expresiones son u ´nicas. Finalmente, se considera la aplicaci´on inducida por la correspondencia aj 7→ bj . La matriz asociada a esta aplicaci´on en las bases {aj } y cualquier extensi´on de {bj } nos vale. Sea ahora C un [n, k]-c´ odigo sobre F con matriz generadora G. Sabemos que si las primeras k columnas de G forman un conjunto de informaci´on (o sea, son linealmente independientes) entonces existe una matriz de operaciones elementales exclusivamente por filas, digamos E, tal que EG = (Ik |A). Es obvio que EG tambi´en es matriz generadora de C. Esta forma tiene nombre propio. 3.1.7. Definici´ on. Sea C un [n, k]-c´ odigo sobre F con matriz generadora G. Decimos que G est´ a en forma t´ıpica (est´ andar) si G = (Ik |A) para alguna matriz adecuada A. f

η

3.1.8. Ahora consideremos la sucesi´on exacta 0 → Fk −−→ Fn −−→ Coker(f ) → η ι 0. Entonces C = Im(f ), el c´ odigo nos da la sucesi´on 0 → C −−→ Fn −−→ Fn /C → 0. El´ıjase, por lo pronto, una base cualquiera en el espacio cociente, digamos γ. Hacemos Hk×n = Mεγ (η)t . Sabemos que C = ker f = {x ∈ Fn | Hxt = 0} y por tanto, dimF (C) = n − rg(H). Desde el punto de vista de H, ker f es la nulidad a la derecha de H y se denota Nd (H). Tambi´en hay, claro, la nulidad a la izquierda. A la matriz H se la conoce como matriz de control (parity check) de C. 3.1.9. Teorema. Si G = (Ik |A)k×n es la matriz generadora en forma t´ıpica de un [n, k]-c´ odigo lineal entonces H = (−At |In−k ) es una matriz de control de C. Demostraci´ on. Basta hacer las cuentas y luego considerar dimensiones. El siguiente resultado nos muestra que esencialmente todo c´odigo puede suponerse con matriz en forma t´ıpica. 3.1.10. Teorema. Todo c´ odigo lineal C es permutaci´ on equivalente a un c´ odigo cuya matriz generadora est´ a en forma t´ıpica. Demostraci´ on. Sea G la matriz generadora. Por ´algebra lineal (m´etodo de GaussJordan) sabemos que existen matrices invertibles (de operaciones elementales), E, F , tales que EGF = (Ik |A), donde Ik es la identidad y A alguna matriz

´ CAP´ITULO 3. CODIGOS LINEALES

25

adecuada. Tambi´en sabemos que podemos elegir F como s´ olo producto de permutaci´ on de los pivotes (o cualquier permutaci´on que pusiera en las primeras columnas un conjunto de informaci´on). Entonces EG genera el mismo c´odigo C y por tanto CF es permutaci´on equivalente y tiene la matriz de la forma deseada. 3.1.11. Ejemplos. f

1. El c´ odigo binario de repetici´on F2 −−→ F52 que vimos en (2.1.3) tiene matriz de codificaci´ on   1 y la matriz generadora es G = (1|1111),   M (f ) =  ...  que est´a en forma t´ıpica. 1 5×1 En este caso, el conjunto de informaci´on es {1} y la redundancia es 6. La matriz de control es     1 −1
    I4  =  ... I4  porque estamos en F2 . H = At |I4 =  ... 1 −1 2. M´ as adelante, veremos con detalle un tipo de c´odigos llamados c´odigos de Hamming. Por lo pronto llamaremos H3 al c´odigo con matriz generadora   0 1 1  1 0 1   G=  I4 1 1 0  1 1 1 y de control  H=

0 −1 −1

−1 0 −1

−1 −1 0

−1 −1 −1

 I3  .

´ Este es un [7, 4]-c´ odigo. 3. En el ejemplo del ISBN (2.1.4) tenemos C = F911 y agregamos la informa10 ci´ on (d´ıgito de control de aplicaci´  pesos) con la on lineal f : C → F11 dada P9 por f (x1 , . . . , x10 ) = x1 , . . . , x9 , − i=1 ixi . En este caso, la matriz generadora es   −1  ..  . G(ISBN) =  I9 .  −9

´ CAP´ITULO 3. CODIGOS LINEALES

3.2.

26

C´ odigos duales u ortogonales

3.2.1. Sea F un cuerpo finito y C ≤ Fn un subespacio. Sabemos que dim C ⊥ + dim C = n. 3.2.2. Definici´ on. Sea C un c´ odigo lineal con matriz de control H = H(C). El c´ odigo dual de C que denotamos C ⊥ es justo el generado por H. Claramente, 
C ⊥ = x ∈ Fnq | xGt = 0 = Ni Gt = Nd (G) y C ⊥ es un [n, n − k]-c´ odigo lineal si C es un [n, k]-c´odigo lineal. A´ un m´as, se puede probar f´ a cilmente que en la situaci´ o n de la definici´ o n anterior, H =
G C ⊥ , la matriz generadora de C ⊥ . 3.2.3. Definici´ on. Un c´ odigo 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 autodual, es condici´on necesaria tener dimensi´on n/2 ∈ N. 3.2.4. Ejemplos. 1. Consid´erese el c´ odigo H3 en (3.1.11). Se puede probar haciendo las cuentas c3 es auto dual porque la matriz generadora es que el c´ odigo extendido H nilpotente de ´ındice 2 y tiene rango 4. 2. El [4, 2]-c´ odigo ternario llamado tetrac´ odigo tiene matriz   1 0 1 1 . G= 0 1 1 −1 Trivialmente, es autodual. 3.2.5. Teorema. Sea C un c´ odigo lineal. Si I y R son las posiciones (´ındices) de informaci´ on y redundancia para C entonces R y I los son, respectivamente, para C ⊥ . Demostraci´ on. Si R = ∅ el caso es trivial. Supongamos que |I| = k. Sea F la permutaci´ on tal que F (I) = {1, . . . , k} y F (R) = {k + 1, . . . , n}. Sabemos que existe un matriz E, producto de elementales tal que EGF = (Ik |A). Hacemos H = (−At |I) F −1 . En este caso, puede elegirse como conjunto de informaci´ on de H, I(H) = F −1 {k + 1, . . . , n} = R y el de redundancia R(H) = −1 F {1, . . . , k} = I.

3.3.

Pesos y distancias

En el cap´ıtulo anterior (2.1.5) vimos las nociones de distancia de Hamming y distancia m´ınima, adem´ as de la noci´on de peso de un vector (2.1.6). En el caso de los c´ odigos lineales, la noci´on de peso se usa de forma equivalente al de distancia de Hamming, pues es la “distancia al 0”. Vamos a ver entonces la definici´ on de peso m´ınimo.

´ CAP´ITULO 3. CODIGOS LINEALES

27

3.3.1. Definici´ on. Para un c´ odigo C, se define el peso m´ınimo de forma obvia. w(C) = m´ın {w(c) | 0 6= c ∈ C} El siguiente resultado es inmediato. 3.3.2. Proposici´ on. Sea C un c´ odigo lineal. Entonces ω(C) = d(C).

Peso m´ınimo y matriz de control 3.3.3. Teorema. Sea C un c´ odigo lineal con matriz de control H. Para cada c ∈ C, las columnas de H correspondientes con las coordenadas no cero de c son linealmente dependientes. Rec´ıprocamente, si entre ciertas r columnas de H hay dependencia lineal entonces existe c ∈ C tal que ω(c) = r y las r-coordenadas no cero de c tienen el mismo ´ındice que las r-columnas de H. Demostraci´ on. Inmediato de la definici´on de matriz de control (3.1.8). 3.3.4. Corolario. Sea C un c´ odigo lineal con matriz de control H. Entonces ω(C) = d si y s´ olo si H tiene d-columnas linealmente dependientes, pero no tiene conjunto alguno que sea linealmente dependiente y con menos de d columnas. As´ı que rg(H) ≥ d − 1; es decir que n − k ≥ d − 1 y de aqu´ı se tiene que n − d + 1 ≥ k. Se puede probar algo mucho m´as fuerte; a saber, que cualquier elecci´ on de al menos n − d + 1 columnas de la matriz generadora G, tiene un conjunto de informaci´ on; o sea, tiene k-columnas linealmente independientes. 3.3.5. Teorema. Sea C un [n, k, d]-c´ odigo lineal con matriz generadora G. Entonces, todo conjunto de (n − d + 1)-columnas de G contiene un conjunto de informaci´ on (o sea, k-columnas linealmente independientes). A´ un m´ as, d es el mayor n´ umero con esta propiedad. Demostraci´ on. Consideremos cualquier elecci´on de columnas de G, digamos i1 , . . . , is y llamemos A a la matriz rsultante de dicha elecci´on. Queremos ver que, si s ≥ n − d + 1 entonces rg(A) ≥ k; o por contrapositiva, si rg(A) < k entonces s ≤ n − d. Supongamos que rg(A) < k. Como A tiene k-filas entonces rg(A) es menor que el n´ umero de filas de A, as´ı que existe r ∈ Fk tal que rA = 0. Consid´erese ahora r · G = (r1 , . . . , rn ), donde al ser rA = 0, cada rij = 0, con j = 1, . . . , s. Obviamente, cG ∈ C, y adem´as, ω (cG) ≤ n − s. As´ı que d ≤ n − s y por tanto s ≤ n − d.

Distribuci´ on de peso o espectro de peso 3.3.6. Definici´ on. Sea C un c´ odigo y sea Ar (C) = |{x ∈ C | ω(x) = r}| . A la lista A1 , A2 , . . . se le llama la distribuci´ on de peso de C.

´ CAP´ITULO 3. CODIGOS LINEALES

3.3.7. Ejemplo. Consid´erese el  1  0 1

28

c´odigo binario con matriz generadora  1 0 0 0 0 1 1 0 0 0 . 1 1 1 1 1

El c´ alculo de la distribuci´on de pesos se deja como ejercicio. Otro ejemplo que se puede comprobar f´acilmente es el c´alculo en un c´odigo de repetici´ on. Vamos a ver algunas propiedades b´asicas. 3.3.8. Teorema. Sea C un [n, k, d]-c´ odigo lineal sobre Fq . Entonces: Pn k 1. i=0 Ai (C) = q . 2. A0 (C) = 1 y A1 (C) = · · · = Ad−1 (C) = 0, si d > 1. 3. Si C es binario y (1, . . . , 1) ∈ C entonces Ai (C) = An−i (C), para todo i. 4. Si C es binario y auto ortogonal entonces toda palabra tiene peso par y C ⊥ tiene al (1, . . . , 1) (porque anula a todo C). 5. Si C es c´ odigo ternario y auto ortogonal entonces el peso de cada palabra es divisible por 3. Demostraci´ on. Sea 1 = (1, . . . , 1). (1) y
(2) son inmediatos. (3) Inmediato del hecho de que para todo v ∈ Fn2 , ω 1 − v = n − ω(v). (4) En el caso binario, uu = 0 implica que u tiene peso par. Ahora, si un vector tiene peso par, entonces 1 · v = 0, luego 1 · C = 0 y por tanto 1 ∈ C ⊥ . (5) Es obvio. En vista de los resultados anteriores nos preguntamos por el subc´odigo de las palabras de peso par. 3.3.9. Teorema. Sea C, un [n, k]-c´ odigo binario. Sea Ce el conjunto de todas las palabras de peso par (en sentido llano). Entonces 1. Ce es un subc´ odigo lineal (subespacio) de C. 2. dimF2 (C/Ce ) ≤ 1. Demostraci´ on. (1) Es obvio. (2) Se sigue directamente de (2.1.8) Vamos a ver una generalizaci´on muy interesante de la noci´on de palabra par e impar. 3.3.10. on. Decimos que un vector v ∈ Fnq es de tipo par (even-like) Pn Definici´ si i=1 v(i) = 0. En caso contrario decimos que es tipo impar. En el caso binario, tipo par es equivalente a par, pero no en general, claro. 3.3.11. Definici´ on. Decimos que un c´ odigo lineal es de tipo par si cada palabra lo es. En caso contrario, decimos que es de tipo impar.

´ CAP´ITULO 3. CODIGOS LINEALES

29

3.3.12. Observaci´ on. Un c´odigo de tipo impar puede tener palabras de tipo par. 3.3.13. Teorema. Sea C un [n, k, d]-c´ odigo sobre Fq . Sea Ce el conjunto de palabras tipo par en C. Entonces Ce es subespacio de C y dimFq (C/Ce ) ≤ 1. Demostraci´ on. La primera parte es trivial. Para la segunda parte, supongamos que existe u, v ∈ C tales que noPson pares. Supongamos = (u1 , . . . , un ) y P P que uP v = (v1 , . . . , vn ). Hacemos r = vi / ui . Entonces vi − r ui = 0, as´ı que v − ru ∈ Ce . De aqu´ı es inmediato.

3.4.

Codificaci´ on y decodificaci´ on en c´ odigos lineales

Ya hemos comentado que para hacer la codificaci´on en c´odigos lineales usamos una aplicaci´ on lineal que tiene que ser inyectiva (1.1.1); luego el espacio de las palabras de longitud k verifica Fk ∼ = C. Cuando un c´odigo es muy grande, se aprecia con claridad la necesidad de codificar y descodificar por f´ormula. El proceso de codificaci´ on es en general, mucho m´as f´acil que el de decodificaci´on. La raz´ on es que en la decodificaci´on hemos incluido la correcci´ on de errores, lo m´ as costoso.

Correcci´ on de errores Aunque hemos visto dos esquemas de decisi´on en (1.2.3) ya hemos comentado que nos centraremos en el esquema que proviene de la distancia m´ınima. Es importante que tengamos claro que lo que vamos a desarrollar no es un esquema de decisi´ on (´ese ya lo tenemos, el de d(C)) sino un algoritmo para la funci´ on parcial. Al final, comentaremos una variante para completar el dominio de la funci´ on parcial y hacerla aplicaci´on. Comenzamos estableciendo la situaci´on. 3.4.1. Tenemos un [n, k]-c´ odigo C ≤ Fn , con matriz de control H y capacidad de correcci´ on t. Hay una palabra enviada c ∈ C, un vector recibido v ∈ F y un vector “error”, que denotaremos e = v − c. El vector error e contiene la informaci´on de los errores de transmisi´on que se cometieron as´ı como de las posiciones donde ocurrieron. Adem´as, el peso ω(e) nos indica el n´ umero de errores en la transmisi´on. En principio, todo vector puede ser visto como un vector error de cualquier palabra, pero nosotros tenemos por hip´ otesis limitado el n´ umero de errores que se van a cometer, luego, se puede decir que hay muchos vectores en Fn y en C, pero hay pocos vectores error m´as probables; es decir, aquellos con peso menor que la capacidad de correcci´on. Uno por cada combinaci´ on de errores y posiciones admisibles. Los vectores error tienen, en vista de su definici´on, su mejor representaci´on como elementos de clases de equivalencia e ∈ v + C y poseen, en ese sentido, una propiedad notable; a saber, Hv = He

´ CAP´ITULO 3. CODIGOS LINEALES

30

3.4.2. Definici´ on. Sea C ≤ Fn un c´ odigo lineal con matriz de control H. Para un vector v ∈ Fn , su s´ındrome es el vector Hv ∈ Fn /C (abusando de la notaci´ on). ¿C´ omo se distribuyen los vectores error m´as probables en las clases de equivalencia? El siguiente resultado nos da la respuesta. 3.4.3. Proposici´ on. Sea C ≤ Fn un c´ odigo lineal con capacidad de correcci´ on n t y sea e ∈ F tal que ω(e) ≤ t. Entonces e tiene peso m´ınimo en e + C y es u ´nico con la propiedad. Demostraci´ on. Supongamos que hay otro u = e + c distinto, i.e. c 6= 0, y verifica ω(u) ≤ t. Entonces, por la desigualdad triangular y la definici´on de capacidad de correcci´ on ω(c) = ω(u − e) ≤ ω(u) + ω(e) ≤ 2t ≤ d(C) − 1 lo cual es imposible. Luego e ∈ e + C es u ´nico. As´ı que ya sabemos c´ omo est´an distribuidos los vectores error (m´as probables). Uno por clase. 3.4.4. Definici´ on. Sea C ≤ Fn un c´ odigo lineal. Un vector de peso m´ınimo en una clase lateral v + C se llama l´ıder de la clase lateral. 3.4.5. Observaciones. 1. Lo que nos dice la proposici´on anterior es que los l´ıderes de peso menor que t son u ´nicos. 2. Cuando la condici´ on del peso falla, los l´ıderes pueden no ser u ´nicos. 3.4.6. Ejemplo. Volvamos al ejemplo del GPS extendido (2.1.15) , con C3 = {00000, 11011, 10110, 01101}. Tenemos dimF2 C3 = 2, luego dimF2 F5 /C3 = 3; as´ı que hay 23 = 8 clase de equivalencia. Vamos a listarlas.

Clase \ bola B1 (00000) B1 (11011) B1 (10110) B1 (01101)

l´ıder

L´ıderes de peso menor que t 00000 10000 01000 00100 00010 00001

00000, 10000, 01000, 00100, 00010, 00001,

11011, 01011, 10011, 11111, 11001, 11010,

10110, 00110, 11110, 10010, 10100, 10111,

01101 11101 00101 01001 01111 01100

00000 10000 01000 00100 00010 00001

L´ıderes de peso mayor que t  11000

11000,

00011,

01110,

10101

11100

11100,

00111,

01010,

10001

11000  00011 10001 01010

´ CAP´ITULO 3. CODIGOS LINEALES

31

El siguiente teorema nos dice que, cuando un vector recibido v ∈ Fn pertenece a una clase de equivalencia con l´ıder u ´nico, digamos e, entonces v ∈ Bt (v − e) y por tanto el esquema decidir´a que la palabra enviada fue v − e ∈ C. 3.4.7. Teorema. Sea C ≤ Fn un c´ odigo lineal con capacidad de correcci´ on t y v ∈ Fn . Son equivalentes: 1. Existe c ∈ C tal que d(v, c) ≤ t. 2. Existe un u ´nico l´ıder, e, tal que Hv = He y ω(e) ≤ t. En este caso, el esquema decidir´ a que la palabra enviada es v − e. Demostraci´ on. [1 ⇒ 2] Hacemos e = v − c. Entonces ω(e) ≤ t y por (3.4.3) ser´ au ´nico. [2 ⇒ 1]. Hacemos c = v − e. Entonces c ∈ C y d(v, c) = ω(e) ≤ t. 3.4.8. Por tanto, para corregir, lo que realmente necesitamos es conocer los l´ıderes y sus s´ındromes. Es decir, que formaremos la tabla completa de l´ıderes (si queremos corregir siempre) Peso

Peso menor que t l´ıder (eij ) s´ındrome (Heij = sij )

0

e01 = 0

0

1

e11 .. .

s11 .. .

e1n1

s1n1

.. .

.. .

.. .

t

et1 .. .

st1 .. .

etnt

stnt

´ CAP´ITULO 3. CODIGOS LINEALES

Peso

32

Peso mayor que t l´ıder (eij ) s´ındrome (Heij = sij ) et+1,1 .. .

st+1,1 .. .

et+1,nt+1

st+1,nt+1

.. .

.. .

.. .

t+p

e(t+p),1 .. .

s(t+p),1 .. .

e(t+p),nt+p

s(t+p),nt+p

t+1

donde t + 1 < . . . < t + p ≤ m´ax {d, n − k} As´ı que, si recibimos un vector, calculamos su s´ındrome y habr´a un l´ıder (´ unico o no) cuyo s´ındrome sea igual al del vector. 1. Si el n´ umero de errores no excediere la capacidad de correcci´on, el l´ıder correspondiente ser´ a u ´nico (y nos indicar´a los errores cometidos en las posiciones). Adem´ as, se decidir´a la palabra enviada y corregiremos adecuadamente. 2. Si el n´ umero de errores excediere la capacidad de correcci´on entonces, cuando los errores coincidan con un l´ıder, corregiremos (correctamente); si no, habremos cometido un error en la decisi´on. 3. Uno puede optar por hacer la tabla m´as peque˜ na y, de ocurrir que no se encuentre l´ıder para un vector avisar la detecci´on de un error. Si la probabilidad de error es muy baja, incluso es conveniente. 3.4.9. Ejemplos. 1. Continuamos con el ejemplo en (3.4.6).

´ CAP´ITULO 3. CODIGOS LINEALES

Peso

33

l´ıder (eij ) s´ındrome (Heij = sij )

0

0000

000

1

10000 01000 00100 00010 00001

110 101 100 010 011

11000∗ 10001∗

011 111

2 (*) no u ´nicos.

2. Sea C = {0000, 1110} binario. En este caso, hay 1 l´ıder de peso 0, 4 de ´ peso 1 y 3 de peso 2. TODOS UNICOS. 3. Para C = {000000, 111000}, binario, hay un l´ıder de peso 0, 6 de peso 1, ´ hay 12 de peso 2, 10 de peso 3 y 3 de peso 4. TODOS UNICOS. As´ı que hay l´ıderes u ´nicos de peso mayor que la capacidad de correcci´on, de hecho tiene peso igual a la distancia m´ınima.

3.5.

Construcciones con c´ odigos lineales

C´ odigos pinchados Ya hemos visto algunos resultados generales en (2.3.2). En el caso de los c´odigos lineales podemos mejorarlo. Vamos al caso cuando d = 1. La demostraci´on es trivial. 3.5.1. Corolario. Sea C un [n, k, 1]-c´ odigo sobre Fq y sea Ci? el c´ odigo pin? chado en la i-´esima coordenada. Si Ci 6= 0 entonces es un [n − 1, k ? , d? ]-c´ odigo, donde, 1. k ? = k si (0, . . . , 1i , 0 . . . , 0) 6∈ C. 2. Si k > 1, y no se cumple el apartado anterior ser´ a un [n−1, k−1, 1]-c´ odigo. ´ltima 3.5.2. Sea C un c´ odigo lineal sobre F. Sea C ? el c´odigo pinchado en la u coordenada y luego extendido (por definici´on, tambi´en en la u ´ltima). Entonces C = C ? si y s´ olo si C es de tipo par.

C´ odigos extendidos Tambi´en hemos visto ya los resultados generales en (2.3.7 y 2.3.8). Es muy f´ acil comprobar cualquiera de los siguientes hechos.

´ CAP´ITULO 3. CODIGOS LINEALES

34

3.5.3. Observaci´ on. 1. Extendido de lineal es lineal. A´ un m´ahs, si C es ilineal y tiene par´ametros b tiene par´ametros n + 1, k, db , donde db = {d, d + 1}. [n, k, d] entonces C 2. Sean G, H las matrices generadora y de control de un c´odigo C. La extensi´ on, siempre se puede interpretar ·G

·E

Fk −−−→ Fn −−−→ Fn+1 con

  E =  In×n

−1 .. .

  

y

G = (gij )k×n .

−1 Entonces 

−

P

−

.. P.

b= GE = G  G

j

j

g1j

  .

gnj

b ha de cumplir que H b ·G b t = 0, as´ı que H b puede ser Ahora, H   1 ··· 1 1  0   b = H  ..  . H  .  0 ´ Esta es una construcci´ on t´ıpica que llamaremos la matriz de control a˜ nadido Vamos a mejorar el resultado que vimos en (2.3.8) en el caso de los c´odigos lineales. 3.5.4. Proposici´ on. Sea C un c´ odigo lineal, Ce y C0 , las palabras tipo par y tipo impar, respectivamente (v´ease 3.3.10), y de = d (Ce ) y d0 = d (C0 ), definidos de forma obvia. Entonces ( de si de ≤ d0 b d= d0 + 1 otro caso Demostraci´ on. Inmediata. N´otese que d(C) = m´ın {de , d0 } 3.5.5. Ejemplo. Para ilustrar, podemos extender el c´odigo H32 , con matriz     1 0 1 1 −1 −1 1 0 G= yH= 0 1 1 −1 −1 1 0 1 y calcular los par´ ametros.

´ CAP´ITULO 3. CODIGOS LINEALES

35

La construcci´ on de Plotkin Recordemos la definici´ on de la construcci´on de Plotkin en (2.3.10). Es inmediato comprobar que cuando C1 y C2 son c´odigos lineales tambi´en C1 ⊕ C2 es lineal. A´ un m´ as. 3.5.6. Corolario. En la situaci´ on de (2.3.10), si C1 y C2 tienen matrices generadoras y de control, respectivamente, G1 , G2 y H1 , H2 , entonces C1 ⊕ C2 tiene matriz generadora y de control     G1 G1 H1 0 y 0 G2 −H2 H2 respectivamente.

Cap´ıtulo 4

El problema principal de la teor´ıa de c´ odigos. Cotas a los par´ ametros 4.1.

Generalidades

Sea C un (n, M, d)-c´ odigo. Para ser un buen c´odigo debe: Tener palabras, lo m´ as corto posible. Luego n debe de ser peque˜ no. Tener muchas palabras. Luego M ha de ser grande. Corregir muchos errores. Luego d ha de ser grande. ´ Estos son intereses conflictivos a lo cual nos referiremos como el problema principal de la teor´ıa de c´ odigos. Abordar el problema consiste en en optimizar uno de los par´ametros. Una de las versiones m´ as populares consiste en “encontrar el c´odigo con M m´as grande (y los otros par´ ametros fijos)”. 4.1.1. Notaci´ on. Denotamos con Aq (n, d) el m´ as grande valor de M , tal que existe un (n, M, d)-c´ odigo q-ario. Empezamos con los casos triviales. 4.1.2. Proposici´ on. Sea q = pi , con p primo. 1. Aq (n, 1) = q n . 2. Aq (n, n) = q. Demostraci´ on. (1) Si u 6= v ∈ Fnq entonces d(u, v) ≥ 1. De aqu´ı se tiene de inmediato que Fnq es un (n, q n , 1)-c´odigo. (2) Supongamos que C es un (n, M, n)-c´odigo q-ario. Si u, v ∈ C son distintos entonces d(u, v) ≥ n, pero C ⊂ Fnq . As´ı que todas las coordenadas han de ser 36

´ CAP´ITULO 4. COTAS A LOS PARAMETROS

37

distintas; en particular, la primera. Luego M ≤ q. Por otra parte, el c´odigo q-ario de repetici´ on alcanza la cota. 4.1.3. Ejemplo. Vamos a determinar el valor de A2 (5, 3). El c´odigo C3 de (2.1.15) es un (5, 4, 3)-c´ odigo binario. Luego A2 (5, 3) ≥ 4. Podemos ensayar a lo bestia con todos los subconjuntos de 5 elementos de F52 a ver si la distancia m´ınima de alguno es 3. El problema es que son unos 200 000 conjuntos. Vamos entonces a trabajarlo con clases de equivalencia. Supongamos que C tiene M ≥ 4 y que 00000 ∈ C. Claramente, s´olo puede haber una palabra v con 4 o 5 valores 1; ya que si hubiese dos, digamos u y v entonces d(u, v) = 2 y ya no sirve. Como 00000 ∈ C, no hay ninguna palabra con s´olo uno o dos valores 1; as´ı que al menos hay dos palabras que tienen 3 valores 1. Reordenando las posiciones podemos suponer que las siguientes palabras viven en el c´odigo {00000, 11100, 00111}. Ahora, basta mirar para darse cuenta de que s´olo podemos agregar 11011. No hay m´as posibilidades. Por tanto M ≤ 4. Es laborioso establecer cotas y existen muchos resultados generales para ayudar en los c´ alculos, adem´as de cotas especiales. 4.1.4. Teorema. Sea d ∈ N impar. Entonces existe un (n, M, d)-c´ odigo binario si y s´ olo si existe un (n + 1, M, d + 1)-c´ odigo binario. Demostraci´ on. Por hip´ otesis, d es impar. Supongamos tenemos un (n, M, d)c´ odigo y que d = d(u, v), para algunos u, v ∈ C. Como d es impar, entonces el peso de alguna de las dos palabras es impar (v´ease 2.1.8). As´ı que, en el c´odigo extendido, d + 1 = d (b u, vb). Rec´ıprocamente, supongamos que tenemos un c´odigo con par´ametros (n + 1, M, d + 1) para un n´ umero impar d. Otra vez escojemos u, v tales que d + 1 = d(u, v). Consideramos una entrada fija i ∈ {1, . . . , n} tal que u(i) 6= v(i) y pinchamos el c´ odigo en esa entrada. Como d + 1 es par, las palabras var´ıan al menos en dos posiciones y por tanto no se pierde ninguna palabra. As´ı que nos queda el c´ odigo pinchado de par´ametros (n, M, d). 4.1.5. Corolario. Si d es impar entonces A2 (n + 1, d + 1) = A2 (n, d). 4.1.6. Ejemplo. Sabemos por (4.1.3) que A2 (5, 3) = 4. Por el corolario anterior, A2 (6, 4) = 4. En el caso q-ario se tiene la siguiente relaci´on. 4.1.7. Teorema. Para n ≥ 2, se tiene Aq (n, d) ≤ qAq (n − 1, d). Demostraci´ on. Sea C un c´ odigo tal que M = Aq (n, d). Consid´erese la primeraSposici´ on y para cada k ∈ F definimos Dk = {u ∈ C | u(1) = k}. Como k∈F Dk = C entonces debe ocurrir que alg´ un |Dk | ≥ M q . Si pinchamos en la primera coordenada, es claro que todo Dk va a sobrevivir. Luego Aq (n,d) Aq (n − 1, d) ≥ M1? ≥ M q = q

´ CAP´ITULO 4. COTAS A LOS PARAMETROS

38

Ahora vamos a ver algunas cotas especiales.

4.2.

Cota de Hamming

Esta cota viene a completar el estudio de los c´odigos perfectos. Lo que hemos visto en (2.1.20 y 2.1.21) nos indica f´acilmente la demostraci´on del siguiente resultado, que se conoce como cota de Hamming o del empaquetado esf´erico. 4.2.1. Teorema. Aq (n, d) ≤ Pt

j=0

qn
j n j (q − 1)

con

t=b

d−1 c. 2

Entonces, un c´ odigo perfecto es aqu´el que alcanza la cota de Hamming.

4.3.

Cota de Singleton y c´ odigos MDS

Esta cota es sencilla pero muy u ´til y da lugar a los c´odigos de Reed Solomon, que veremos despu´es, y que se usan para la reproducci´on de los CD. 4.3.1. Teorema. Para d ≤ n se tiene que Aq (n, d) ≤ q n−d+1 . Demostraci´ on. Trivialmente, Aq (n, n) = q = q n−n+1 y vamos a hacer descenso. Sea d < n. Aq (n, d) ≤ qAq (n − 1, d) ≤ · · · ≤ q n−d Aq (d, d) = q n−d (q) = q n−d+1 .

4.3.2. Observaci´ on. En particular, para un [n, k, d]-c´odigo lineal q-ario, k ≤ n − d + 1. 4.3.3. Definici´ on. Un c´ odigo que verifica la igualdad en el teorema anterior se conoce como c´ odigo separable de distancia m´ axima (maximum distance separable MDS). La primera propiedad es obvia, aunque muy importante. 4.3.4. Proposici´ on. Los c´ odigos MDS son cerrados para isometr´ıas. Luego un (n, M, d)-c´ odigo MDS verifica que M = Aq (n, d). Ahora veremos algunas propiedades interesantes de los c´odigos MDS lineales. 4.3.5. Teorema. Sea C un [n, k]-c´ odigo lineal sobre Fq , con k ≥ 1. Entonces, las siguientes condiciones son equivalentes. 1. C es MDS. 2. Todo conjunto de k-posiciones es un conjunto de informaci´ on para C. 3. C ⊥ es MDS.

´ CAP´ITULO 4. COTAS A LOS PARAMETROS

39

4. Todo conjunto de (n − k)-posiciones es un conjunto de informaci´ on para C ⊥. Demostraci´ on. [1 ⇒ 2] Aplicando (3.3.5 y 3.1.6) se tiene de inmediato del hecho de que k = n − d + 1, por hip´otesis. [2 ⇔ 4] Inmediato de (3.2.5). [3 ⇔ 4] Es de nuevo consecuencia directa de (3.3.5). 4.3.6. Corolario. Sea C un [n, k]-c´ odigo con matriz generadora G. Entonces C es c´ odigo MDS si y s´ olo si cualesquiera k columnas de G son linealmente independientes. Demostraci´ on. Inmediata.

4.4.

Otras cotas

Existen otras cotas relevantes, como la cota de Plotkin o la cota de la Programaci´ on lineal. Las limitaciones del curso no nos permiten verlas pero vamos a enunciar los resultados. 4.4.1. Teorema [Cota de Plotkin]. Sea C un (n, M, d)-c´ odigo sobre Fq , donq−1 de q−1 n < d. Hacemos r = . Entonces q q 1. M ≤

d d−rn

d o b d−rn c.

d 2. Si q = 2, M ≤ 2b 2d−n c.

4.4.2. Teorema [Cota de la programaci´ on lineal]. Las siguientes cotas ocurren. 1. Cuando q ≥ 2 se tiene que (

n X

Aq (n, d) ≤ m´ax

) Bw

w=0

donde el m´ aximo est´ a tomado de los {Bw } que satisfacen: a) B0 = 1 y Bw = 0 para 1 ≤ w ≤ d − 1. b) Bw ≥ 0, para d ≤ w ≤ n y Pn n,q c) w=0 Bw Kk (w) ≥ 0 para todo 1 ≤ k ≤ n. 2. Cuando d es par y q = 2, ( A2 (n, d) ≤ m´ax

n X

) Bw

w=0

donde el m´ aximo est´ a tomado de los {Bw } que satisfacen: a) B0 = 1 y Bw = 0 para 1 ≤ w ≤ d − 1.que sean impares. b) Bw ≥ 0, para d ≤ w ≤ n y Bn ≤ 1, y Pn n,2 c) w=0 Bw Kk (w) ≥ 0 para todo 1 ≤ k ≤ bn/2c.

Cap´ıtulo 5

Tipos especiales de c´ odigos lineales 5.1.

C´ odigos de Hamming y c´ odigos simplex

C´ odigos de Hamming La construcci´ on de los c´odigos de Hamming y algunas de sus propiedades en el caso binario las hemos visto en cap´ıtulos anteriores. Vamos a extender la definici´ on. Sea Fq un cuerpo finito cualquiera y consideremos Frq con r ≥ 2. Llamamos c´ odigo de Hamming y denotamos Hq,r a todo aquel c´odigo cuya matriz de control se construye de la siguiente manera. La denotamos con Hq,r . 1. Consideramos todos los distintos subespacios de dimensi´on 1 de Frq . Sar −1 bemos que hay exactamente qq−1 (q r son todos, q r − 1, porque el < 0 > tiene dimensi´ on 0, y

q r −1 q−1

porque los m´ ultiplos se absorben).

2. Denotamos con Hq,r al c´odigo que proviene de una matriz del tipo   de cada distinto subespacio tomo Hq,r = . un vector no cero y lo pongo Entonces se tiene: 1. rg (Hq,r ) = r. 2. Sean v1 , v2 ∈ Hq,r . Claramente, existe W ≤< v1 , v2 > (la diagonal) tal que dim W = 1. Sea v3 ∈ W un generador de la diagonal. Entonces v3 es combinaci´ on lineal de los otros, pero cualesquiera dos son linealmente independientes, luego (3.3.4) nos dice que ω (Hq,r ) = 3.

40

´ CAP´ITULO 5. TIPOS ESPECIALES DE CODIGOS LINEALES

41

h r i −1 q r −1 As´ı que Hq,r es un qq−1 , q−1 − r, 3 -c´odigo y cualesquiera dos c´odigos construidos de esta manera y con estos datos ser´an permutaci´on equivalentes. Rec´ıprocamente si H es la matriz de control de un c´odigo, tal que H es de r −1 orden r × qq−1 y tal que cada dos columnas existe una tercera que es combinaci´ on lineal de las dos anteriores entonces trivialmente, H tiene en sus columnas a un generador de cada uno de los distintos subespacios de dimensi´on 1; es decir,hemos probado que. h r i −1 q r −1 5.1.1. Teorema. Todo qq−1 , q−1 − r, 3 -c´ odigo lineal sobre Fq es un c´ odigo de Hamming. A´ un m´ as, cualesquiera dos c´ odigos de Hamming con los mismos par´ ametros son permutaci´ on equivalentes.

C´ odigos simplex Son

h

q r −1 q−1 , r

i

-c´ odigos lineales cuyos pesos de palabras tiene propiedades no-

tables. Por ejemplo, el c´ odigo H3⊥ s´olo tiene palabras de peso 4 y el tetrac´odigo (3.2.4), que denotamos H3,2 , es autodual, y tiene todas sus palabras de peso 3. 5.1.2. Definici´ on. Los c´ odigos simplex son aquellos que se realizan como duales de los c´ odigos de Hamming En general, 5.1.3. Teorema. Las palabras no cero de un c´ odigo simplex sobre Fq tiene todas peso q r−1 . Demostraci´ on. El c´ odigo ha de tener matriz generadora Hq,r de orden r ×  r   q −1 ⊥ = hHq,r i = xHq,r | x ∈ Frq . y sabemos que rg (Hq,r ) = r y que Hq,r q−1 N´ otese que ω (xHq,r ) = n − (columnas de Hq,r , digamos y, tal que xy = 0). r−1 Sabemos que dim x⊥ = r − 1, luego tiene q q−1−1 subespacios de dimensi´on 1 y todos ellos est´ an en las columnas de Hq,r . Por tanto, ω (xHq,r ) =

q r − 1 q r−1 − 1 − = q r−1 . q−1 q−1

Construcci´ on alternativa de c´ odigos simplex binarios Hacemos



1 0

1 1

0···0

1

1···1

G2 = Ahora, para r ≥ 3, definimos 



0 1

.

Gr = 

 

Gr−1

0

Gr−1

´ CAP´ITULO 5. TIPOS ESPECIALES DE CODIGOS LINEALES

42

Se puede comprobar por construcci´on, que las columnas de Gr son la expansi´ on de 1, 2, . . . , 2r − 1 (en binario, claro), as´ı que hGr i = Sr es Hr⊥ . Ahora vamos a verificar la propiedad de los pesos. Tenemos que ver es que todas las filas de Gr tienen peso 2r−1 . N´ otese que G2 tiene 22 − 1, columnas as´ı que, por construcci´on, Gr tiene r 2 − 1 columnas. Vamos con el argumento sobre el peso. Es claro que todas las filas de G2 tienen peso 22−1 = 2. Supongamos que todas las filas de Gr−1 tienen peso 2r−2 (de hecho el subespacio que generan). Analizando la matriz Gr un simple argumento de inducci´on nos muestra que cada una de sus filas tiene peso 2r−1 . Vamos ahora con las combinaciones lineales. Es muy importante tomar en cuenta que no es cierto que cualquier combinaci´on lineal de vectores de peso 2r−1 tiene otra vez ese peso y adem´as, es obvio. La propiedad proviene de la forma como est´ a construida la matriz. Cualquier combinaci´on lineal de la segunda fila en adelante cumple obviamente la propiedad por inducci´on y por la construcci´ on de la matriz. As´ı que basta comprobar que la combinaci´on lineal entre la primera fila y cualquier combinaci´on lineal de las otras tiene el peso deseado. Pero eso es f´ acil de comprobar.

5.2.

C´ odigos de Golay

Los c´ odigos 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´ odigo. El segundo se obtiene pinchando el primero. Los ternarios se denotan G12 y el G11 .

C´ odigos 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´on i un 1 si i es cuadrado m´ odulo 11 y un 0 en caso contrario. Despu´es se hace un recorrido (shift) en direcci´ on (←). As´ı que el bloque tiene forma c´ıclica.   0 1 1 1 1 1 1 1 1 1 1 1      1 1 1 0 1 1 1 0 0 0 1 0     1 1 0 1 1 1 0 0 0 1 0 1     1 0 1 1 1 0 0 0 1 0 1 1     1 1 1 1 0 0 0 1 0 1 1 0     A=  1 1 1 0 0 0 1 0 1 1 0 1   1 1 0 0 0 1 0 1 1 0 1 1     1 0 0 0 1 0 1 1 0 1 1 1     1 0 0 1 0 1 1 0 1 1 1 0     1 0 1 0 1 1 0 1 1 1 0 0     1 1 0 1 1 0 1 1 1 0 0 0  1 0 1 1 0 1 1 1 0 0 0 1

´ CAP´ITULO 5. TIPOS ESPECIALES DE CODIGOS LINEALES

43

Con esta matriz G24 genera un c´odigo que llamaremos c´odigo de Golay G24 . Vamos a ver algunas de sus propiedades. Una propiedad importante es que G24 Gt24 = 0, porque A es binaria, sim´etrica y con cada fila de peso par; luego es nilpotente. A´ un m´ as, lo anterior implica que (A|I) tambi´en es matriz generadora de G24 . Otra propiedad notable se refiere a los pesos. La fila G24 (1; −) tiene peso 12; mientras que las 11 filas restantes tienen peso 8. Vamos a probar que, de hecho, el peso m´ınimo es 8. 5.2.1. Lema. Si C es un c´ odigo auto ortogonal y tiene matriz generadora con cada fila con peso divisible por 4 entonces toda palabra tiene peso divisible por 4. Demostraci´ on. Basta analizar la Observaci´on 2.1.8 (3) Toda palabra de G24 se puede escribir de la forma v = (a|b), con a, b ∈ F12 2 . Adem´ as, si v = (a|b) es una palabra, tambi´en lo ser´a u = (b|a). Por el lema anterior todas las palabras de G24 tienen peso m´ ultiplo de 4. Vamos a ver que es estrictamente mayor que 4. Tomemos un v = (a|b). Podemos suponer que ω(a) ≤ ω(b). Hay tres casos. Caso 1. Si ω(a) = 0, como G24 est´a en forma t´ıpica y v = xG24 se tiene que a = 0 implica b = 0, luego v = 0. Caso 2. Si ω(a) = 1 entonces v es una fila de G24 , que tiene peso mayor o igual a 8. Caso 3. Si ω(a) = 2 entonces v es combinaci´on lineal de dos filas de G24 , y una comprobaci´ on a lo bestia nos da ω(v) = 8. Ahora bien, si ω(a) ≥ 3 entonces ω(b) ≥ 3, por hip´otesis, y como ha de ser m´ ultiplo de 4, ya es mayor o igual a 8. Por tanto G24 es un [24, 12, 8]-c´odigo binario. El c´ odigo G23 Por (3.5.2) sabemos que si pinchamos G24 en la u ´ltima coordenada (de hecho en cualquiera) y extendemos (a la que pinchamos) entonces recuperamos el c´ odigo original. Pinchando G24 obtenemos un [23, 12, 7]-c´odigo lineal, que llamaremos G23 .

´ CAP´ITULO 5. TIPOS ESPECIALES DE CODIGOS LINEALES

44

C´ odigos de Golay ternarios El c´ odigo de Golay ternario G12 es el [12, 6]-c´odigo sobre F3 con matriz G12 = (I6 |A), donde   0 1 1 1 1 1      1 0 1 −1 −1 1    A= 1 0 1 −1 −1   1   1 −1 1 0 1 −1     1 −1 −1 1 0 1  1 1 −1 −1 1 0 Se puede comprobar directamente cada una de las siguientes propiedades. 5.2.2. Proposici´ on. Las siguientes condiciones ocurren. 1. At = A y que A2 = −I. Luego G12 es autodual. 2. G12 es un [12, 6, 6]-c´ odigo lineal. 3. El c´ odigo ternario G11 que obtenemos de pinchar G12 en la u ´ltima coordenada es un [11, 6, 5]-c´ odigo lineal perfecto. 4. Si pinchamos en cualquier otra coordenada no salen c´ odigos equivalentes. 5. Si pinchamos en cualquier coordenada y luego extendemos con el d´ıgito de paridad recuperamos un c´ odigo equivalente a G12 . De hecho, incluso hay equivalencia con c´odigos que no sean lineales. La demostraci´ on del siguiente resultado excede el alcance de nuestro curso. Puede consultarse en [5, Theorem 95] 5.2.3. Teorema. Todo c´ odigo de par´ ametros (12, 36 , 6)-es equivalente a G12 , y 6 todo c´ odigo de par´ ametros (11, 3 , 5)-es equivalente a G11

5.3.

C´ odigos de Reed-Muller (binarios)

Los propusieron por separado (en trabajos independientes) I. S. Redd y D. E. Muller en 1954. Existe tambi´en la definici´on de c´odigo de Reed-Muller sobre cuerpos con otra caracter´ıstica. Su distancia m´ınima es muy peque˜ na pero se decodifican muy f´acilmente. Hay muchas maneras de construirlos. Una de ellas se basa en la construcci´on de Plotkin (2.3.10).

Construcci´ on Elegimos un natural m ∈ N \ {0} y 0 ≤ r ≤ m. Para cada m, vamos a definir m + 1-c´odigos que denotaremos R(0, m), . . . , R(m, m).

´ CAP´ITULO 5. TIPOS ESPECIALES DE CODIGOS LINEALES

45

Les llamaremos c´ odigos RM de longitud 2m . Lo haremos por inducci´on: m Primer paso: R(0, m) es el c´odigo de repetici´on y R(m, m) = F22 , el espacio completo. Ahora, R(r, m) = {(u | u + v) | u ∈ R(r, m − 1), v ∈ R(r − 1, m − 1)} , con 1 ≤ r < m. Por lo que sabemos de la construcci´on (u | u + v), (2.3.10) la matriz ser´a, primero,
G(0, m) = 1 1 · · · 1 y G(m, m) = I2m y luego,  G(r, m − 1) G(r, m) =  0



G(r, m − 1)

 G(r − 1, m − 1)

Una de las grandes ventajas de los c´odigos RM es que sus par´ametros se calculan por f´ ormula. 5.3.1. Teorema. Sea m > 0 y 0 ≤ r ≤ m. Entonces, 1. R(i, m) ⊆ R(j, m), para 0 ≤ i ≤ j < m. 2. La dimensi´ on es

r   X m dimF2 (R(r, m)) = . i i=0

3. El peso m´ınimo es ω (R(r, m)) = 2m−r . 4. El ortogonal es R(m, m)⊥ = (0) y si 0 ≤ r < m entonces R(r, m)⊥ = R (m − r − 1 , m) . Demostraci´ on. (1) Inmediata por inducci´on. Primero se prueba que R(0, 1) ≤ R(1, 1), con eso se tiene que R(j, m) ≤
R(j + 1, m) y de aqu´ı, sale. (2) Primero, dim R(0, m) = 1 = m otese que 0 . Ahora, n´ dim R(m, m) = 2m =

m   X m i=0

i

m

= (1 + 1) .

Por (3.5.6) sabemos que dim R(j, m) = dim R(j, m−1)+dim R(j −1, m−1). Usando esta igualdad, la hip´otesis de inducci´on, que es dim R(j, m − 1) =

 j  X m−1 i=o

i

y dim R(j − 1, m − 1) =

 j−1  X m−1 i=o

i

´ CAP´ITULO 5. TIPOS ESPECIALES DE CODIGOS LINEALES

46

y las igualdades de los coeficientes binomiales           m−1 m m−1 m−1 m = =1y + = 0 0 i i−1 i nos dicen que dim R(j, m) =

j   X m

i

i=o

.

(3) Sabemos por (2.3.10) que d (R(r, m)) = m´ın {2d (R(r, m − 1)) , d (R(r, m))} . Por inducci´ on. Si d (R(r, m − 1)) = 2m−1−r y d (R(r − 1, m − 1)) = 2m−1−(r−1) = 2m−r entonces 2d (R(r, m − 1)) = d (R(r − 1, m − 1)) = 2m−r y se tiene el resultado. (4) Que R(m, m)⊥
= 0 es obvio. El otro lo haremos por induccion.
m m Como i = m−i entonces dim R(m − r − 1, m) =

m−r−1 X  j=0

 m = j

m=(m−0)

X r+1=m−(m−r−1)

  m . j

Luego dim R(r, m) + dim R(m − r − 1, m) =

r   X m 0

j

+

m   X m r+1

j

= 2m .

Por tanto, basta probar que R(m − r − 1, m) ≤ R(r, m)⊥ . Sabemos que R(m − r − 1, m)

= {(u|u + v) | u ∈ R(m − r − 1, m − 1), v ∈ R(m − r − 2, m − 1)}

R(r, m)

= {(u|u + v) | u ∈ R(r, m − 1), v ∈ R(r − 1, m − 1)} .

Sean (u|u + v) ∈ R(r, m) y (x|x + y) ∈ R(m − r − 1, m). Por hip´otesis de inducci´ on ux = 0 = vx y por el apartado (1), v ∈ R(r, m − 1). An´alogamente, uy = vy = 0 luego y ∈ R(m − r − 1, m − 1) tambi´en. 5.3.2. Observaciones. 1. Como R(0, m) es el c´ odigo de repetici´on, R(m − 1, m) = R(0, m)⊥ es el m c´ odigo de todos los vectores pares de F22 . 2. Si m es impar, m = 2r + 1, entonces por los apartados (3) y (4), del teorema anterior se tiene que R(r, m) = R( m−1 2 , m) es autodual con peso m−1 m´ınimo 2 2 .

Cap´ıtulo 6

Cuerpos finitos 6.1.

Suma y producto en cuerpos finitos

Damos por conocidos los conceptos de dominio eucl´ıdeo, dominio de factorizaci´ on u ´nica, cuerpo, extensi´on de un cuerpo y caracter´ıstica de un cuerpo K, que denotamos Car(K). Tambi´en damos por hecho que, para cualquier cuerpo F, el anillo de polinomios F[X] es un dominio eucl´ıdeo, donde todo ideal est´a generado por un polinomio (de grado m´ınimo), y si un elemento p ∈ F[X] tiene una ra´ız α ∈ F, entonces (X − α) | p. Si un polinomio p ∈ F[X] es irreducible entonces el ideal que genera hpi ≤ F[X] es maximal y por tanto, el cociente F[X]/hpi es un cuerpo. Finalmente, si K/F es una extensi´ on y α ∈ K, recordemos que la correspondencia p(X) 7→ p(α) Λ

α es un homomorfismo de anillos, F[X] −−− → K, que llamamos el homomorfismo de evaluaci´ on. Recordemos que a la imagen de Λα se le denota F(α) y es el subcuerpo de K generado por F y el elemento α. Sabemos que todo dominio finito es un cuerpo. El siguiente resultado es menos conocido y las demostraci´on es demasiado larga como para reproducirla aqu´ı. La omitiremos porque no influye en el desarrollo del tema.

6.1.1. Teorema [Wedderburn]. Todo anillo de divisi´ on finito es un cuerpo. Unas observaciones sobre la caracter´ıstica. 6.1.2. Proposici´ on. Sea K un cuerpo. La correspondencia ϕ : Z → K tal que (n)

ϕ(n) = 1+ · · · +1 es homomorfismo de anillos. Demostraci´ on. Trivial, ϕ(n · m)

=

 1+ · · · +1 = 1+ · · · +1 + · · · + 1+ · · · +1   (m) (m) ϕ(n)+ · · · +ϕ(n) = (factorizo) = ϕ(n) 1+ · · · +1

=

ϕ(n)ϕ(m)

=

(nm)



(n)

47



(m)



(n)

CAP´ITULO 6. CUERPOS FINITOS

48

6.1.3. Observaci´ on. Para todo cuerpo K, Car (K) = m´ın {n ∈ N | ϕ(n) = 0}. 6.1.4. Proposici´ on. Sea K un cuerpo finito. Entonces Car (K) es un n´ umero primo. Demostraci´ on. Inmediato del hecho de que Z/ ker ϕ ,→ K. (Todo dominio finito es un cuerpo.) 6.1.5. Corolario. Si F es un cuerpo tal que |F| = p, con p primo, entonces F∼ = Zp . As´ı que podemos hablar de “el cuerpo con p elementos”. 6.1.6. Notaci´ on. Sea p un n´ umero primo. Denotamos con Fp al cuerpo con p elementos. 6.1.7. Observaci´ on. Si F es un cuerpo de caracter´ıstica p entonces claramente Fp ,→ F. 6.1.8. Definici´ on. En la situaci´ on anterior, a la imagen de Fp se le llama el subcuerpo primo de F. M´ as adelante veremos que es u ´nico. 6.1.9. Definici´ on. Sea K/F una extensi´ on. El grado de la extensi´ on es la dimensi´ on que tiene K como F-espacio vectorial. Se denota [K : F]. 6.1.10. Definici´ on. Una extensi´ on K/F decimos que es finita si el grado es un n´ umero natural. Obviamente, en cuerpos finitos las extensiones han de ser finitas. 6.1.11. Teorema. Sea F un cuerpo finito. Entonces, |F| = pt , donde p = Car(F). Demostraci´ on. Trivial; adem´as, t = dimFp (F). 6.1.12. Notaci´ on. A partir de ahora, p se reserva para un n´ umero primo y q, para alguna potencia del primo p. 6.1.13. Proposici´ on. Sea F un cuerpo con Car (F) = p. Entonces, para cualesquiera r, s ∈ F se tiene pt

(r + s)

t

t

= rp + sp .

Demostraci´ on. Inmediato del binomio de Newton, pues  t ( 0 si i 6= 0, pt p = i 1 otro caso. en F. Por la proposici´ on anterior, se tiene entonces que la correspondencia r 7→ rp es un automorfismo.

CAP´ITULO 6. CUERPOS FINITOS

49

6.1.14. Definici´ on. El automorfismo r 7→ rp de Fp se conoce como el automorfismo de Frobenius. Se denota σp . M´ as adelante veremos que todo automorfismo de un cuerpo finito es potencia del automorfismo de Frobenius. 6.1.15. Teorema. Para todo cuerpo F, el grupo multiplicativo F∗ = (F, ·) es c´ıclico. Demostraci´ on. Suponemos que |F| = q > 3, si no, se hacen las cuentas. αm 1 Sea h = q − 1 = pα on en factores primos. Recorde1 · · · pm la descomposici´ ∗ mos que q − 1 = |F |. h Para cada 1 ≤ i ≤ m, consideremos el polinomio X pi − 1. Este polinomio tiene a lo m´ as, phi -ra´ıces en F. Como phi < h, entonces que hay elementos en F h

que no son ra´ıces de X pi − 1. Sea ai uno de esos elementos. α α α (h/p i ) (h/p i ) p i Ahora, hacemos bi = ai i . Es claro que ai i 6= 1; adem´as, bi i = ah = (h/p

(αi −βi )

)

i cualquier 0 ≤ β ≤ αi , ai i 6= 1, 1; luego o (bi ) | pα i . Por otra parte, Qpara m i . Hacemos b = b luego o (bi ) = pα i i=1 i . Finalmente, se puede comprobar de forma directa que o(b) = h.

Curiosamente, se tiene entonces que para un cuerpo finito F, el grupo aditivo es elemental abeliano, mientras que el multiplicativo es c´ıclico. 6.1.16. Definici´ on. A todo generador del grupo multiplicativo F∗ se le llama elemento primitivo de Fq . 6.1.17. Lema. Sea F un cuerpo con q = pt elementos. Entonces todo r ∈ F verifica rq = r. Demostraci´ on. Inmediato del hecho de que el orden del grupo multiplicativo |(F, ·)| = q − 1. Por su parte, el cero trivialmente lo cumple.

6.2.

Polinomios y n´ umeros algebraicos

6.2.1. Definici´ on. Sea K/F una extensi´ on. Un elemento α ∈ K decimos que es algebraico sobre F si existe f ∈ F[X] tal que f 6= 0, pero f (α) = 0. 6.2.2. Teorema [Kronecker]. Sea F un cuerpo y f ∈ F[X] un polinomio no constante. Entonces existe una extensi´ on K/F donde f tiene una ra´ız. Demostraci´ on. Sea g un factor irreducible de f . Entonces F[X]/hgi = K es ηg un cuerpo. Claramente, la composici´on F ,→ F[X] −−−→ K es homomorfismo inyectivo de anillos con uno, donde k 7→ kX 0 7→ k + hgi. Hagamos α = X + hgi y notemos que la evaluaci´ on g(α) = ηg (g) = 0, por lo que α es una ra´ız de g y en consecuencia, de f . 6.2.3. Corolario. Si f ∈ F[X] entonces existe una extensi´ on K/F donde f tiene todas sus ra´ıces, que son, como sabemos, salvo multiplicidad, gr(f ).

CAP´ITULO 6. CUERPOS FINITOS

50

Demostraci´ on. Basta notar que se pueden ir construyendo K1 ⊂ K2 ⊂ · · · ⊂ Kn extensiones con el teorema de Kronecker, con α1 , . . . αn , las ra´ıces construidas en dicho resultado. El proceso se detiene cuando se llega, digamos, a Kn (con n ≤ gr(f )), el primero que tiene todas las ra´ıces. La factorizaci´on del polinomio por las ra´ıces hace el resto. En la situaci´ on anterior, si gr(f ) = n, se tiene que Kn = F (α1 , . . . , αn ). 6.2.4. Ejemplo. Hacemos F = Z2 , f = X 2 +X +1. Sea α tal que α2 +α+1 = 0. 3 Entonces α = 1. F4 = F(α) = a + bα | α2 + α + 1 = 0 ; a, b ∈ F es una extensi´ on de Z2 de cuatro elementos. Podemos hacer las tablas de sumar y multiplicar. 6.2.5. Definici´ on. Sea F un cuerpo y f ∈ F[X]. Un cuerpo de descomposici´ on de f sobre F es aqu´el generado por F y todas las ra´ıces de f . 6.2.6. Teorema. Sea K/F una extensi´ on y α ∈ K, algebraico sobre F. Entonces existe un polinomio mα = mα (X) = Irr(α, K) tal que: 1. mα tiene grado m´ınimo con la propiedad mα (α) = 0. 2. Si f (α) = 0 entonces mα | f . 3. mα puede elegirse m´ onico. 4. mα es irreducible. Demostraci´ on. Se considera Iα = {p ∈ F[X] | p(α) = 0}. Como F[X] es un ´ es DIP, se tiene que Iα es principal. Elegimos el u ´nico generador m´onico. Ese mα (X) y se tiene Iα = hmα i. Es inmediato comprobar que se cumplen las primeras tres condiciones. Para comprobar que es irreducible en F[X], recordemos α (X) que si mα (r) = 0, con r ∈ F, entonces m en vivir´ıa en Iα y tendr´ıa (X−r) tambi´ grado menor, lo cual es imposible. 6.2.7. Definici´ on. Sea F un cuerpo y α un elemento algebraico sobre F. Al polinomio mα se le llama polinomio m´ınimo de α sobre F. Las ra´ıces est´ an agrupadas en potencias del orden del cuerpo, como establece el siguiente resultado. 6.2.8. Proposici´ on. Sea K/F una extensi´ on y α ∈ K una ra´ız de f ∈ F[X]. Si |F| = q entonces αq es ra´ız de f . Demostraci´ on. Inmediata del Lema 6.1.17. 6.2.9. Definici´ on. Sea K/F una extensi´ on. Dos elementos de K decimos que son conjugados en F si sus polinomios m´ınimos sobre dichos cuerpos coinciden. 6.2.10. Teorema. Sea f ∈ Fq [X] irreducible de grado r > 1. Entonces 1. Si K es un cuerpo de descomposici´ on de f en F entonces [K : F] = r.

CAP´ITULO 6. CUERPOS FINITOS

51

2. Todas las ra´ıces de f son simples y dadas por los r elementos distintos ξ, ξ q , . . . , ξ q

r−1

donde ξ es cualquier ra´ız de f . 3. En consecuencia, cualquier ra´ız de f es elemento primitivo del cuerpo de escisi´ on donde pertenezca. Demostraci´ on. Sea, pues, ξ una ra´ız de f . 1. Consideremos el isomorfismo F(ξ) ∼ = F[X]/hf i inducido por la evaluaci´on. Es inmediato que dimF (F[X]/hf i) = r, as´ı que [F(ξ) : F] = r. s−1 s 2. Considero ξ, ξ q , . . . , ξ q con ξ q = ξ, el primero. Es inmediato que s ≤ r. Consideremos cualquier elemento primitivo ρ ∈ F(ξ). hay una escritura P P Entonces P s s ρ= ai ξ ki , con ai ∈ F y ki ≤ q s . Ahora, ρq = ai ξ ki ·q 0 ai ξ ki = ρ y por r−1 tanto r ≤ s. As´ı que s = r. Luego ξ, ξ q , . . . , ξ q son todos distintos y adem´as i ξ q ∈ F(ξ). 3. Inmediato de la demostraci´on del apartado (1 ). 6.2.11. Corolario. En la situaci´ on del Teorema 6.2.10, sea ξ ∈ K y mξ su polinomio m´ınimo sobre F. Entonces se tiene una descomposici´ on en K, mξ (X) =

s−1 Y

X − ξq

i



i=0 s

donde s es el primer natural tal que ξ q = ξ; que, de hecho, es el grado del polinomio m´ınimo. Demostraci´ on. Es inmediata. El siguiente resultado establece la relaci´on entre grado de una extensi´on y grado del polinomio m´ınimo de cualquier elemento primitivo. 6.2.12. Corolario. Sea K/F una extensi´ on de grado r y sea ξ un elemento primitivo de K, con polinomio m´ınimo mξ sobre F. Entonces r = gr (mξ ) Demostraci´ on. Inmediata de los Teoremas 6.2.6 y 6.2.10 Por ejemplo, F4 es el cuerpo de descomposici´on de X 2 + X + 1 = (X + α)(X + α2 )

6.3.

Existencia y unicidad.

En esta secci´ on vamos a demostrar la existencia y la unicidad de los cuerpos finitos. Lo haremos en dos partes. Primero probaremos el resultado para cuerpos de escisi´ on y luego lo aplicaremos a los cuerpos finitos en general. De hecho, veremos que todo cuerpo finito es un cuerpo de descomposici´on o escisi´on. Ya hemos probado su existencia. Vamos a probar la unicidad.

CAP´ITULO 6. CUERPOS FINITOS

52

6.3.1. Teorema [Unicidad del cuerpo de escisi´ on]. Sea F un cuerpo y f ∈ F[X]. Cualesquiera dos cuerpos de descomposici´ on de f sobre F son isomorfos. Demostraci´ on. Sea K = F (α1 , . . . , αn ), construido como en el Corolario 6.2.3. Recordemos que f se descompone en factores lineales en K[X]. Sea L/F una extensi´ on tal que posee una ra´ız de f , digamos l ∈ L. Se considera cualquier factor irreducible g de f tal que g(l) = 0. Por otra parte, existe αi ∈ K tal que g(αi ) = 0. Entonces, los subcuerpos F(αi ) y F(l) son isomorfos a F[X]/hgi y el isomorfismo compuesto entre ellos es la correspondencia αi 7→ l. A partir de ah´ı, si hay m´ as ra´ıces en L seguimos extendiendo hasta obtener K ,→ L. De aqu´ı el resultado es inmediato. 6.3.2. Notaci´ on. Dado un cuerpo F y un polinomio f ∈ K[X], podemos hablar de “el cuerpo de descomposici´ on de f sobre K”, salvo isomorfismo. 6.3.3. Lema. Sea F un cuerpo finito con q elementos y Fp su subcuerpo primo. Entonces, el polinomio X q − X ∈ Fp [X] se factoriza como Y Xq − X = (X − r) ; r∈F

es decir, todas las ra´ıces de X q − X viven en F cuando Car(F) = p y |F| = q. Demostraci´ on. Por el Lema 6.1.17, todos los elementos de F son ra´ıces, y como gr (X q − X) = q, ya tenemos todas las ra´ıces. 6.3.4. Observaci´ on. Recordemos que si un polinomio sobre cualquier cuerpo tiene ra´ıces m´ utiples entonces la derivada no puede ser constante distinta de cero. Ve´ amoslo. Supongamos que r ∈ F es dicha ra´ız. Si f = gh y f 0 = c ∈ F entonces g 0 h + gh0 = c, luego 0 = g 0 (r)h(r) + g(r)h0 (r) = c; contradicci´on. 6.3.5. Teorema [Existencia y unicidad de los cuerpos finitos]. Para cualquier primo, p y cualquier natural, t, existe un cuerpo finito con pt elementos. Cualquier cuerpo finito con q = pt elementos es isomorfo a un cuerpo de descomposici´ on (o escisi´ on) del polinomio X q − X sobre Fp . Demostraci´ on. Existencia: Consid´erese el polinomio X q − X ∈ Fp [X]. Como 0 la derivada (X q − X) = −1 entonces el polinomio no tiene ra´ıces m´ ultiples. As´ı que tiene exactamente q ra´ıces distintas (Corolario 6.2.3). Sea F el cuerpo de descomposici´on de X q − X en Fp y consideremos L = {α ∈ F | αq − α = 0}. Claramente, |L| = q y L es un subcuerpo de F (h´agase la cuenta si se quiere). As´ı que L es un cuerpo generado por todas las ra´ıces de X q − X. Pero esa es la definici´on de cuerpo de descomposici´on; as´ı que L = F. Unicidad: Inmediato del hecho de que todos los cuerpos finitos son cuerpos de descomposici´ on, junto con la unicidad de ´estos (Teorema 6.3.1). 6.3.6. Observaci´ on. Hemos probado entonces que todo cuerpo finito con q = pt elementos es el cuerpo de descomposici´on de X q − X en Fp . 6.3.7. Notaci´ on. Para q = pt , con p, primo, denotamos al cuerpo (salvo isomorfismo) con q elementos con Fq .

CAP´ITULO 6. CUERPOS FINITOS

53

6.3.8. Teorema. Sea p un n´ umero primo; t, r n´ umeros naturales, y Fpt y Fpr cuerpos finitos. Entonces Fpt es (isomorfo a) un subcuerpo de Fpr si y s´ olo si t|r. Demostraci´ on. Sea α un elemento primitivo de Fpr . Supongamos primero que t|r. Entonces, es sabido que (pt − 1)|(pr − 1) y por tanto F∗pr tiene un subgrupo de orden pt − 1, con el cual se forma un subcuerpo de la forma Fpt . Rec´ıprocamente, supongamos que tenemos un subcuerpo de Fpr de la forma Fpt . Entonces tambi´en se tiene que F∗pt es subgrupo de Fp∗r de donde (pt − 1)|(pr − 1) y por tanto t|r. As´ı que si tenemos un extensi´on cualquiera L/K, los resultados anteriores nos dicen que ha de ser de la forma Fqs /Fq con q = pt y s = r/t. Considero un elemento primitivo de Fqs , digamos ξ. Entonces o n s Fqs = 0, 1, ξ, . . . , ξ q −2 . Haciendo k =

q s −1 q−1

se tiene que n o Fq = 0, 1, ξ k , ξ 2k , . . . , ξ (q−1)k−1

y adem´ as Fqs = Fq (ξ) = Fp (ξ). De inmediato se desprende entonces que 6.3.9. Teorema. Toda extensi´ on L/K de cuerpos finitos es algebraica y simple. Demostraci´ on. Inmediato del hecho de que 1 + ξ + · · · + ξ q−1 = 0. As´ı que los cuerpos fintos est´an organizados en torres m´as o menos as´ı (con contenciones “´ unicas”) Fp4

Fp6

Fp9

* 6  * 6      Fp2 Fp3 ... YH H 6  * HH Fp

6.4.

Ejemplos

Comencemos con F2 = {0, 1}, y consideremos el polinomio
2 X 2 − X = X 4 − X = X (X + 1) X 2 + X + 1 . Aqu´ı, X 2 + X + 1 es el u ´nico irreducible de grado 2. Sea α una ra´ız de dicho polinomio. Entonces α2 + α + 1 = 0 y con ella construimos   F4 = a + bα | a, b ∈ F y α2 + α + 1 = 0 = 0, 1, α, α2 | α3 = 1 .

CAP´ITULO 6. CUERPOS FINITOS

54

Ahora vamos a extender F2 a F24 . Consideramos la factorizaci´on 4

X2 − X

=



X (X + 1) X 2 + X + 1 X 4 + X 3 + 1 ·

· X4 + X + 1 X4 + X3 + X2 + X + 1

en irreducibles en F2 [X]. Para construir una extensi´on de F2 , de grado 4, los polinomios de grado 1 y 2 no sirven. Vamos a los de grado 4. Seanβ una ra´ız cualquiera de alguno de los o 2 22 23 polinomios de grado 4. Las ra´ıces ser´an β, β , β , β . Ahora tenemos dos caminos: Primero. Hacemos,  
 2 3 X 4 + X 3 + 1 = (X + β) X + β 2 X + β 2 X + β2
= X 4 + β + β2 + β4 + β8 X 3 +
+ β 3 + β 5 + β 6 + β 9 + β 10 + β 12 X 2 +
β 7 + β 11 + β 13 + β 14 X + β 15 y a partir de aqu´ı construimos F24 . Es un poco rollo; o m´as bien mucho. Otra forma. Hacemos  F24 = a1 + a2 β + a3 β 2 + a4 β 3 | ai ∈ F2 ; β 4 + β 3 + 1 = 0 . o cualquier otra de las ecuaciones. Podemos hacer la tabla completa. Comenzamos con 0, 1, β, β 2 , β 3 y formamos, β4 β5 β6 β7 β8 β9 β 10 β 11 β 12 β 13 β 14 β 15

= = = = = = = = = = = =

1 + β3 β + β4 β + β2 + β4 β + β2 + β3 + β4 β + β2 + β3 β2 + β3 + β4 β + β3 β2 + β4 β + β3 + β4 β + β2 β2 + β3 β3 + β4

= = =

β + 1 + β3 β + β2 + 1 + β3 β + β2 + β3 + 1 + β3

= 1 + β + β3 = 1 + β + β2 + β3 = 1 + β + β2

=

β2 + β3 + 1 + β3

=

= =

β2 + 1 + β3 β + β3 + 1 + β3

= 1 + β2 + β3 = 1+β

=

1, como debe de ser.

1 + β2

Como hemos visto, podemos tambi´en pasar a F24 , extendiendo F22 en vez de F2 . Veamos.

CAP´ITULO 6. CUERPOS FINITOS

55

 Tenemos F22 = 0, 1, α, α2 , y q = 22 = 4. Sabemos que F24 es una extensi´on que se construir´ a con un irreducible de grado 2 = [F24 : F22 ]. Esos irreducibles 2 ser´ an divisores de X q − X o sea,


2 X 4 − X = X (X + 1) X 2 + X + 1 X 4 + X 3 + 1 X 4 + X + 1
X4 + X3 + X2 + X + 1 =

= X (X + 1) (X + α) X + α2 X 2 + αX + α


X 2 + α2 X + α2 X 2 + X + α X 2 + X + α2

X 2 + αX + 1 X 2 + α2 X + 1 . Ahora usamos cualquier irreducible de grado 2, como por ejemplo, la primera, X 2 + αX + α y consideramos una ra´ız (un s´ımbolo que verifica la ecuaci´on anterior), digamos β. Tenemos β 2 + αβ + α = 0 y α2 + α + 1 = 0. De aqu´ı sacaremos toda la tabla. Entonces F24 = {a + bβ | a, b ∈ F22 ; y las relaciones anteriores} Vamos a hacer tambi´en la tabla completa para construir todo otra vez como potencias de β. Tenemos 0, 1, β y adem´ as, β2 β3 β4 β5 β6 β7 β8 y as´ı... β9 β 10 β 11 β 12 β 13 β 14

6.5.

= = = = = = =

α + αβ ββ 2
2 β2 α αβ β2β5
2 β4

= · · · = α2 + β = ··· = α + β

= · · · = α2 + α2 β = · · · = 1 + αβ

= α2 + αβ = α2 = α2 β = 1+β = α + α2 β = 1 + α2 β

El anillo Fq [X]/(X n − 1)

El objetivo de esta secci´ on es describir el anillo cociente Rn = F[X]/hX n −1i y la relaci´ on con las ra´ıces de X n − 1. Los c´odigos c´ıclicos ser´an identificados como ideales de Rn . 6.5.1. Definici´ on. Sea n ∈ N, y consideremos el cuerpo Fq .

CAP´ITULO 6. CUERPOS FINITOS

56

1. Decimos que α ∈ Fq es ra´ız n-´esima de la unidad si αn = 1. 2. Decimos que ξ ∈ Fq es ra´ız primitiva de la unidad si ξ n = 1 y n es el primer natural (no cero) con la propiedad. 6.5.2. Proposici´ on. 1. Si ξ ∈ Fq es un elemento primitivo entonces ξ es una ra´ız (q − 1)-´esima primitiva de 1. 2. Fq tiene una ra´ız n-´esima primitiva de 1 si y s´ olo si n | (q − 1). Demostraci´ on. Inmediata del hecho de que F∗q es c´ıclico. 6.5.3. Definici´ on. Sea n ∈ N con mcd(q, n) = 1. Sea 0 ≤ s ≤ n. La clase q-ciclot´ omica de s m´ odulo n es:  Cs = s, sq, . . . , sq r−1 donde r = m´ın {t ∈ N | sq t ≡ s mod n}. Por ejemplo: M´ odulo Clases 2-ciclot´omicas 3 {0}, {1, 2} 5 {0}, {1, 2, 4, 3} 7 {0}, {1, 2, 4}, {3, 6, 5} 9 {0}, {1, 2, 4, 8, 7, 5}, {3, 6} 11 {0}, {1, 2, 4, 8, 5, 10, 9, 7, 3, 6} 13 {0}, {1, 2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7} 9 {0}, {1, 2, 4, 8}, {3, 6, 9, 12}, {5, 10}, {7, 14, 13, 11} 6.5.4. Observaciones.  1. Consid´erese G = q i i∈Z actuando en Zn , a trav´es de x 7→ xq i ∈ Zn . Los Cs son las ´ orbitas de esta acci´on y por tanto forman una partici´on de Zn . 2. Sean n, k n´ umeros naturales, tales que (n, q) = 1 y n | q k − 1. Entonces F∗qk posee un (´ unico) subgrupo c´ıclico de orden n, digamos, Ω. Sea ξ ∈ Ω cualquier generador; es decir, una ra´ız n-´ esima primitiva de la unidad. Entonces, si hacemos Ωs = ξ j | j ∈ Cs tendremos que {Ωs } es una partici´ on para Ω y cualesquiera dos elementos de un Ωi son conjugados.

q A´ un m´ as, como para todo f ∈ Fq [X] ocurre que f ξ iq = f ξ i entonces tambi´en ocurrir´ a que cada clase q-ciclot´omica corresponda con UN SOLO polinomio m´ınimo; es decir, 6.5.5. Teorema. Sea ξ ∈ Fqr una ra´ız n-´esima de 1 (entonces mcd(n, q) = 1). Entonces:

CAP´ITULO 6. CUERPOS FINITOS

57

1. Para cada 0 ≤ s ≤ n el polinomio m´ınimo de ξ s en Fq se factoriza en Fqr [X] como Y
mξs (X) = X − ξi i∈Cs

donde Cs es la clase q-ciclot´ omica de s m´ odulo n. 2. As´ı que la factorizaci´ on de X n − 1 en Fq [X] es Y Xn − 1 = mξs (X) s∈S

donde S es un juego completo de representantes de las clases q-ciclot´ omicas m´ odulo n. Demostraci´ on. Es consecuencia directa del Teorema 6.2.10. Veamos. Sea α = ξ s m−1 y supongamos que gr(mα ) = m. Por dicho teorema, α, . . . , αq son todas las ra´ıces de mα y adem´ as, por el argumento de la demostraci´ on, se cumple que  m αq = α y m es el primero con la propiedad. De ah´ı que Cs = s, sq, . . . , sq m−1 . N´ otes que gr(mα ) = |Cs |. Sea ξ una ra´ız n-´esima primitiva de 1. Se considera S un juego completo de representantes de las clases q-ciclot´ para cada s ∈ S, Q omicas. Claramente, n s ξ s esPra´ız de X n − 1 y por tanto m (X) | (X − 1). Finalmente, como ξ s∈S P n = s∈S |Cs | = s∈S gr (mξs ) se tiene la igualdad. 6.5.6. Observaciones. Ahora vamos a hacer una lista de hechos que sabemos o podemos probar muy f´ acilmente: 1. Si mcd(n, q) = 1 entonces X n − 1 no tiene ra´ıces m´ ultiples. 2. Sea Rn = Fq [X]/(X n − 1). Si I ≤ Rn , existe g ∈ Fq [X], m´onico, tal que ´nico.) g | (X n − 1) e I = hgi. (Este polinomio es u 3. Si g · h | X n − 1 entonces g y h son coprimos (no hay ra´ıces m´ ultiples) y por tanto existen a, b ∈ Fq [X] tales que 1 = ag + bh. 4. En Rn , si ocurre 1 = ag + bh, con gh = 0 entonces e = ag es idempotente, con bh = 1 − e. 5. Por tanto, Rn es semi simple y conmutativo. Por el Teorema de Wedderburn Rn es producto de cuerpos. (Esto tal vez no se conozca, pero lo veremos expl´ıcitamente.) 6.5.7. Definici´ on. Sea I un ideal de Rn . Al polinomio m´ onico g | X n − 1 de la Observaci´ on 6.5.6.2 se le conoce como polinomio generador de I. Vamos ahora a establecer la relaci´on entre los ideales del anillo Rn y las clases q-ciclot´ omicas de las ra´ıces n-´esimas de la unidad. Consideremos la situaci´ on de la Observaci´ on 6.5.4, donde k puede ser elegido de tal manera que sea precisamente el orden multiplicativo de q, m´odulo n.

CAP´ITULO 6. CUERPOS FINITOS

58

6.5.8. Definici´ on. En la situaci´ on del p´ arrafo anterior, sea I un ideal de Rn y ξ ∈ Fqk una ra´ız n-´esima primitiva de la unidad. 1. El conjunto de ceros de I es 
Zξ (I) = ξ i | p ξ i = 0, ∀ p ∈ I 2. El conjunto de no ceros de I son aquellos ξ j 6∈ Z(I). 6.5.9. Teorema. Sean q una potencia de un primo p; n, k n´ umeros naturales, tales que (n, q) = 1 y k es el orden multiplicativo de q, m´ odulo n. Sean {Ci } las clases q-ciclot´ omicas de q, m´ odulo n, y ξ ∈ Fqk una ra´ız n-´esima primitiva de la unidad. Entonces 1. Todo ideal I de Rn determina una u ´nica uni´ on de clases ciclot´ omicas D(I) = Ci1 ∪ · · · ∪ Cir , de tal manera que  Zξ = ξ j | j ∈ D(I) 2. Rec´ıprocamente, toda reuni´ on de clases q-ciclot´ omicas modulo n, D = Ci1 ∪ · · · ∪ Cir determina un u ´nico ideal I de Rn , dado por  I = p ∈ Rn | p(ξ j ) = 0, ∀ j ∈ D Demostraci´ on. Inmediata. 6.5.10. Teorema. Sean I, J ideales de Rn con polinomios generadores g, h, respectivamente. Entonces: 1. I ≤ J si y s´ olo si h | g. 2. Por tanto, los ideales maximales tienen generadores irreducibles y sus ceros forman una sola clase ciclot´ omica. 3. I ∩ J tiene polinomio generador, un asociado a mcm(g, h). 4. I + J tiene polinomio generador, un asociado a mcd(g, h). 5. I · J tiene polinomio generador, un asociado a mcd(gh, X n − 1). Demostraci´ on. Basta hacer las cuentas. Qs 6.5.11. Proposici´ on. Consid´erese la descomposici´ on X n − 1 = i=1 mi , donde los mi son los polinomios m´ınimos de las distintas clases q-ciclot´ omicas. n Hacemos ui = Xm−1 . Entonces i 1. Existen ai , bi tales que 1 = ai mi + bi ui . 2. Rn mi = Rn ai mi y Rn ui = Rn bi ui . 3. Rn mi es maximal y Rn ui es minimal.

CAP´ITULO 6. CUERPOS FINITOS

59

4. Rn ui ∼ = Rn /Rn mi ∼ = Fq [X]/(mi ) ∼ = Fqgr(mi ) . Demostraci´ on. Las tres primeras son inmediatas. Para la u ´ltima es el segundo teorema de isomorf´ıa; esto es, Rn /Rn mi ∼ = (Fq [X]/(X n − 1) / ((mi )/(X n − 1)). Sabemos que las identidades de Bezout vistas se pueden extender a m´as sumandos, as´ı que Qs 6.5.12. Teorema. Consid´erese la descomposici´ on X n −1 = i=1 mi , donde los mi son los polinomios m´ınimos de las distintas clases q-ciclot´ omicas. Hacemos n . Entonces ui = Xm−1 i 1. Rn = Rn u1 × · · · × Rn us . 2. Rn ui ∼ = Fqgr(mi ) . Demostraci´ on. Inmediata. Como gr(mi ) = |Ci | entonces se tiene 6.5.13. Corolario. Sean C1 , . . . , Cs las distintas clases q-ciclot´ omicas m´ odulo n. Entonces s Y F |Ci | . F[X]/(X n − 1) ∼ = q

i=1

6.5.14. Corolario. Si mcd(n, q) = 1 entonces Rn es un producto de cuerpos. 6.5.15. Ejemplo. Consideramos F2 y n = 7. Usando el Corolario las clases  6.5.13, calculamos  2-ciclot´omicas m´odulo 7. Son C0 = {0}, C1 = 1, 2, 22 , C3 = 3, 3 · 2, 3 · 22 . La estructura es: R7 = F2 [X]/(X 7 − 1) ∼ = F2 × F23 × F23 . Ahora viene la parte ardua que es calcular los idempotentes de la descomposici´ on. Lo primero que necesitamos es la factorizaci´on de X 7 − 1 en irreducibles. En principio, el Teorema 6.5.5 nos dice c´omo hacerlo expl´ıcitamente. Como hay tres clases 2-ciclot´ omicas, m´ odulo 7, hay tres factores irreducibles que se construyen, usando a ξ, una ra´ız s´eptima de 1, as´ı: 1. El de C0 , que es X + 1.


2. El de C1 que
es (X + ξ) X + ξ 2 X + ξ 4 = X 3 + ξ 4 + ξ 2 + ξ X 2 + ξ 6 + ξ 5 + ξ 3 X + 1.



3. El de C3 que
es X + ξ 3 X + ξ 6 X + ξ 5 = X 3 + ξ 3 + ξ 5 + ξ 6 X 2 + ξ + ξ 2 + ξ 4 X + 1.

CAP´ITULO 6. CUERPOS FINITOS

60

Nuevamente, el Teorema 6.5.5 nos dice que los coeficientes de los polinomios ξ 4 + ξ 2 + ξ y ξ 3 + ξ 5 + ξ 6 viven en F2 , luego son 0 o 1. Pero, desafortunadamente, no podemos saberlo con un m´etodo fijo; as´ı que descomponer polinomios sigue siendo igual de dif´ıcil que, por ejemplo, en la caracter´ıstica 0. Hay programas y tablas para calcular descomposiciones. Uno termina siempre echando mano de ellas. As´ı que, expresamos como producto de irreducibles X 7 − 1 = (X + 1)(X 3 + 2 X + 1)(X 3 + X + 1). Entonces m1 = X + 1 m2 = X 3 + X 2 + 1 m3 = X 3 + X + 1

u1 = X 6 + · · · + X 2 + X + 1 u2 = X 4 + X 3 + X 2 + 1 u3 = X 4 + X 2 + X + 1

De aqu´ı, todav´ıa faltar´ a hacer las identidades de Bezout para obtener los idempotentes.

6.6.

Automorfismos

6.6.1. Definici´ on. El grupo de Galois, como siempre, es Gal (F) el grupo de los automorfismos junto con la composici´ on. Si Fqs /Fq es una extensi´ on, denotamos con Gal (Fqs /Fq ) los automorfismos de Gal (Fqs ) que dejan fijo a Fq . Por la Definici´ on 6.1.14 se tiene 6.6.2. Observaci´ on. Un automorfismo de Frobenius es un elemento σp ∈ Gal (Fpr ) . N´ otese que σpr = σp ◦ .(r) . . ◦σp tiene sentido. Vamos a describir a Gal (Fq ). N´ otese que Gal (Fq ) = Gal (Fq /Fp ). 6.6.3. Teorema. Sea p un n´ umero primo y r ∈ N. Entonces, Gal (Fpr ) = hσp i. En consecuencia, es un grupo c´ıclico de orden r. Demostraci´ on. Hacemos q = p y consideramos ξ ∈ Fqr un elemento primitivo y mξ su polinomio m´ınimo en Fq . Sabemos que para cada σ ∈ Gal (Fq ), σ(ξ) r−1 es ra´ız de mξ y que esas ra´ıces son ξ, ξ q , . . . , ξ q , as´ı que no hay m´as que r-distintos automorfismos de hσp i = Gal (Fqr ). 6.6.4. Corolario. Sea q = pt y 0 ≤ n ≤ t. Entonces {x ∈ Fq | σpn (x) = x} = Fpmcd(n,t) . Demostraci´ on. Inmediato del hecho de que {x ∈ Fq | σpn (x) = x} es un subcuerpo.

Cap´ıtulo 7

C´ odigos c´ıclicos 7.1.

Conceptos b´ asicos

7.1.1. Definici´ on. Un [n, k]-c´ odigo lineal C sobre Fq se llama c´ odigo c´ıclico si cumple que es cerrado para permutaciones c´ıclicas; es decir, (x0 , . . . , xn−1 ) ∈ C ⇒ (xn−1 , . . . , xn−2 ) ∈ C. 7.1.2. Ejemplos. Vamos a ver algunos ejemplos muy simples 1. El total y el trivial. 2. El de repetici´ on. 3. El {(0000) , (1010) , (0101) , (1111)}, de dimensi´on 2. 4. El h{(1100) , (0110) , (0011)}i en F42 . 5. Sea P la matriz de permutaci´on c´ıclica; es decir,   0 I P = 1 0

 y X ⊆ Fnq un subconjunto arbitrario. Entonces XP i | i ∈ N ser´a un c´ odigo c´ıclico. 6. Un c´ odigo que NO es c´ıclico, {(0000) , (1100) , (0011) , (1111)}. N´otese que es cerrado para mover de dos en dos; de hecho, es permutaci´on equivalente a un c´ıclico. 7.1.3. Proposici´ on. Un c´ odigo lineal C ≤ Fnq es c´ıclico si y s´ olo si el ortogonal, ⊥ C es c´ odigo lineal c´ıclico. Demostraci´ on. Sea P la matriz de permutaci´on c´ıclica. Entonces y ∈ C ⊥ ⇔
t y · xP i = 0 para todo x ∈ C y para todo i ∈ N. Por la definici´ on, la matriz de permutaci´on es ortogonal; es decir, P P t = I.

t n Como P = I entonces (P i )t = P n−i . As´ı, 0 = yP i xt = y · xP n−i = 0. 61

´ CAP´ITULO 7. CODIGOS C´ICLICOS

7.2.

62

C´ odigos c´ıclicos y anillos de polinomios

Seguimos suponiendo que mcd(n, p) = 1. Consid´erese Fnq con la base can´onica En y Rn = Fnq /(X n − 1), como hemos estudiado, con su base can´onica  Xn = 1, X, X 2 , . . . , X n−1 (abusando de notaci´on, porque deber´ıan de tener barras). Sea φ : En → Xn tal que φ(ei ) = X i−1 , i = 1, . . . , n. Esta correspondencia induce un isomorfismo Ψ : Fnq −→ Rn que dejaremos en notaci´ on fija. 7.2.1. Proposici´ on. En la situaci´ on anterior (con Ψ fija), sea C ≤ Fnq un c´ odigo lineal. C es c´ıclico si y s´ olo si Ψ(C) es ideal en Rn . Demostraci´ on. Inmediato del siguiente diagrama conmutativo. Fnq 

Ψ Ψ

Rn

−1

·P

x· o ·x Ψ

? Fnq

-

 Ψ−1

? Rn

Como ejemplos de c´ odigos c´ıclicos tenemos los ideales obtenidos en el Ejemplo 6.5.15. Como hemos comentado, la definici´on de c´odigo c´ıclico nos impide ver al c´ odigo D = {(0000) , (1100) , (0011) , (1111)} como c´ıclico, a pesar de que sabemos que le operador que mueve dos veces las coordenadas los deja invariante. Si consideramos ϕ : F4q → R4 con ϕ (e1 ) = 1, ϕ (e2 ) = X 2 , ϕ (e3 ) = X, ϕ (e4 ) = X 3 se puede comprobar f´acilmente que ϕ(D) es ideal en Rn . A´ un m´ as, los u ´nicos isomorfismos entre Fnq y Rn que pueden interesar han de preservar pesos, luego han de ser biyecciones entre las bases can´onicas. De hecho, dos isomorfismos que preservan pesos restringen a una permutaci´on de las bases can´ onicas. 7.2.2. Proposici´ on. Un c´ odigo C ≤ Fnq lineal es equivalente a un c´ odigo c´ıclico si y s´ olo si existe un isomorfismo entre Fnq y Rn que restringe a una biyecci´ on de las bases can´ onicas y C se corresponde con un ideal. Demostraci´ on. Inmediata.

´ CAP´ITULO 7. CODIGOS C´ICLICOS

63

A partir de ahora, cuando digamos C es un c´odigo c´ıclico, entenderemos C ≤ Rn = Fnq , abusando de la notaci´on. 7.2.3. Observaci´ on. Repasemos lo que acabamos de ver sobre los ideales en Rn . Fijamos una ra´ız n-´esima primitiva de la unidad, digamos ξ, y consideramos las clases q-ciclot´ omicas m´ odulo n, Ci1 , . . . , Cis , con S = {i1 , . . . , is } un juego completo de representantes. Sean, como siempre, mj = mξji (X) los polinomios n

. Sabemos por el Teorema 6.5.12 que los Rn uj son todos los m´ınimos y uj = Xm−1 j ideales minimales y que cada Rn uj ∼ = Fqgr(mj ) = Fq|Cj | . Por tanto, dimF Rn uj = gr(mj ) = |Cj |. Sea ahora I ≤ Rn un c´odigo c´ıclico. Por la Observaci´on 6.5.6, existe un polinomio generador (m´ onico) g ∈ F[X] tal que I = hgi y g | X n − 1; por n eso abusamos de la notaci´ on y escribimos g en vez de g¯. Si h = X g−1 entnces Q existen Q S1 y S2 , una partici´on de S tal que (Teorema 6.5.5) g = j∈S1 mj y h = k∈S2 mk ; adem´ as, Y Y Y Rn uk ∼ Fqgr(mk ) ∼ Fq|Ck | . Rn g = = = k∈S2

k∈S2

k∈S2

P

De aqu´ı, dimF Rn g = n − gr(g) = k∈S2 |Ck |. 7.2.4. Proposici´ on. Sea C un c´ odigo c´ıclico en Rn con polinomio generador Pn−k g(X) = i=0 gi X i ; es decir, gr(g) = n − k. Entonces 1. dimFq C = k.  2. g(X), x · g(X), . . . , xk−1 · g(X) es base para C. 3. La matriz a continuaci´ on  g0 g1  0 g0  G=  0

es generadora de C, ··· ··· .. .

gn−k

0 gn−k

g0

···

··· ··· .. .

0

    

gn−k

k×n

Demostraci´ on. 1. Acabamos de verlo en la Observaci´on 7.2.3. P k−1 2. Es inmediato por el hecho de tener todos grados distintos. Si i=0 ri X i g(X) = n−1 0 entonces rk−1 gn−k X = 0, luego rk−1 = 0. Repitiendo el argumento se tiene r0 = · · · = rk−1 = 0. 3. Es la matriz generadora de la base anterior. Una vez que tenemos la matriz generadora queremos la matriz de control. 7.2.5. Definici´ on. Sea C un c´ odigo c´ıclico en Rn con polinomio generador g(X). Llamaremos polinomio de control de C a h(X) = es decir, gh = X n − 1 en Fq [X].

Xn − 1 g(X)

´ CAP´ITULO 7. CODIGOS C´ICLICOS

64

Usando h podemos dar una matriz de control muy f´acil. Pk 7.2.6. Teorema. Sea C ≤ Rn c´ odigo c´ıclico y h = i=0 hi X i su polinomio de control. Entonces la siguiente matriz es matriz de control para C,   hk hk−1 · · · h0 0 · · · 0 0  hk ··· h0 · · ·   H= ;  . . .. ..   0 hk · · · h0 n−k×n es decir,

H = (aij )n−k×n

  0 | aij = hk−(j−i)   0

si j − i < 0 si 0 ≤ j − i ≤ k si k < j − i

Demostraci´ on. Sea c = c(X) un elemento de C. Entonces c = gp, donde g es el generador, y g un polinomio en Rn con grado estrictamente menor que k, pues la suma de sus grados no puede pasar de n y g tiene grado n − k (esto siempre se puede conseguir con un representante adecuado, ya que si gp tiene grado mayor que n, hacemos gp = u(X n − 1) + r, pero g | (X n − 1), luego g | r y por tanto gp = g gr = g gr y tiene grado menor o igual a n). Entonces hc = hgp = (X n −1)p. Veamos que el polinomio (X n − 1) q tiene todos los coeficientes de los t´erminos Pk0 de grado k, . . . , n−1 cero. Supongamos que p = i=0 pi X i , con k 0 < k. Entonces Pk 0 Pk0 (X n −1)p = −p+X n p = − i=0 pi X i + i=0 pi X n+i , o sea, que X k , . . . , X n−1 tienen coeficientes 0. Es inmediato hacer la cuenta y ver que en el producto hc los coeficientes de los grados k, . . . , n − 1 son precisamente las entradas del producto   p0   H  ...  = 0 pn−1 por tanto H es matriz de control. Obs´ervese entonces que C ⊥ no necesariamente est´a generado por h. Pm 7.2.7. Definici´ on. Para un polinomio f (X) = i=0 ai X i , se define m m X X
f ? (X) = X m f X −1 = X m · ai X −i = ai X m−i i=0

i=0

7.2.8. Ejercicio. Probar que en la situaci´ on de la definici´ on anterior 1. Si f | g entonces g ? | f ? . 2. Si g | X n − 1 entonces g ? | X n − 1.

´ CAP´ITULO 7. CODIGOS C´ICLICOS

65

? ? Efectivamente. 1. Basta Pm Pmver quei f g = h implica que f g = h. Hacemos los dos i f = i=0 fi X y f = i=0gi X donde los  coeficientes de alguno de ellos pueden P2m P k ser 0. Entonces h = k=0 i+j=k fi gi X . Finalmente, se puede comprobar   P2m P 2m−k que f ? g ? = k=0 = h? . i+j=k fi gi X ?

2. Inmediato del hecho de que (X n − 1) = 1 − X n . 7.2.9. Corolario. Sea C un c´ odigo con polinomio de control h = 1 Entonces C ⊥ tiene polinomio generador h⊥ = h(0) h? .

7.3.

P

hi X i .

Ceros de un c´ odigo c´ıclico y matriz de control

Sea C un c´ odigo c´ıclico de orden n sobre Fq , con mcd(n, q) = 1, sea ξ una ra´ız n-´esima primitiva de 1, y sea S un juego completo de representantes de las clases q-ciclot´ omicas m´ odulo n. Sea g(X) el generador de C (Observaci´on 6.5.6). Como sabemos del Teorema 6.5.5 si g(X) | X n − 1 entonces Y g= mξt . t∈T ⊆S

7.3.1. Definici´ on. En la situaci´ on anterior. Definimos. 1. Los ceros de C son las ra´ıces de g; es decir, {ξ a | a ∈ Ct , t ∈ T } . 2. Los no ceros son las ra´ıces de h = 

X n −1 g ,

es decir el conjunto

ξ b | b ∈ Cs , s ∈ S \ T



.

7.3.2. Observaci´ on. Sea C un c´odigo c´ıclico. Entonces los ceros de C ⊥ son precisamente los inversos de los no ceros de C. La raz´on es la siguiente. Es inmediato comprobar que si ζ es ra´ız de un polinomio f (X) entonces ζ −1 es ra´ız de f ∗ (X); basta ver la definici´on (Definici´on 7.2.7). Usando los ceros de un c´ odigo c´ıclico podemos construir una matriz de control. Consideramos a C ≤ Rn sobre Fq , con mcd(n, q) = 1, con polinomio generador g y sea, usando la notaci´on de la definici´on anterior, T = {t1 , . . . , td }. Vamos a formar la matriz   1 ξ t1 ξ 2t1 . . . ξ (n−1)t1   .. L= (7.3.1)  . 1

ξ td

ξ 2td

...

ξ (n−1)td

|T |×n

´ CAP´ITULO 7. CODIGOS C´ICLICOS

66

Es muy claro que si c ∈ C, visto como coordenadas, Lct = 0, y viceversa. N´ otese que L no tiene entradas en Fq , as´ı que no es, en principio matriz de control; pero vamos a construir una a partir de L. Consideramos Fqr el cuerpo de escisi´on de g sobre Fq . Ahora, expresamos cada ξ tj como coordenadas de Fqr visto como espacio vectorial sobre Fq ; es decir, denotamos ξ tj las coordenadas de ξ tj . Ahora formamos  1  L=

ξ t1

1

ξ td

ξ 2t1 .. .

...

ξ 2td

...

ξ (n−1)t1

  

ξ (n−1)td

(7.3.2)

|T |·r×n

Vamos a ver que es matriz de control. Primero tenemos que Pr fijar una base. Sea {u1 , . . . , ur } una base para Fqr . supongamos que ξ mti = j=1 aji uj . Como Lct = 0 entonces   ! n−1 r r n−1 X X X X  0= aji uj  ci = uj aji ci i=0

j=1

j=1

i=0

y como los uj son linealmente independientes se tiene el resultado.

7.4.

Codificaci´ on y decodificaci´ on en c´ odigos c´ıclicos

Como hip´ otesis general, supongamos que tenemos un c´odigo c´ıclico C ≤ Rn tal que C = hgi, con g el polinomio generador, con gr(g) = r, as´ı que la dimensi´ on dim C = n − r. Comenzamos con la codificaci´on. Vamos a ver una decodificaci´on sistem´atica. Supongamos que queremos codificar la palabra a0 · · · an−r−1 . Pn−r−1 1. Hacemos a(X) = i=0 ai X n−i−1 2. Luego operamos a = tg + s, con gr(s) < r (n´otese que gr(tg) ≤ n). 3. Finalmente hacemos c = a − s = pg. Para decodificar, se puede proceder de la siguiente manera. 1. Se recibe un vector v ∈ Rn . 2. Se divide v = gt + s, con gr(s) < r. Si v = c + e, entonces c + e = gt + s y as´ı, c = gt + (s − e), con gr(s − e) < r. Pero c = gt0 , para alguna t0 , puesto que c ∈ C = hgi y la unicidad del algoritmo de la divisi´on nos dice que s = e; luego v − s es la palabra buscada.

´ CAP´ITULO 7. CODIGOS C´ICLICOS

67

Esta decodificaci´ on es en realidad una decodificaci´on por s´ındrome. Vamos a comprobar que existe una matriz de control cuyos s´ındromes son precisamente los restos obtenidos. Consid´erese para i = 0, . . . , n − 1, la expresi´on X r+i = gsi + ti , obtenidos con el algoritmo de la divisi´ on. Se puede comprobar f´acilmente que los X r+i − ti = gsi son una base para C. Por los grados de los t´erminos l´ıderes tenemos independencia lineal, y por el n´ umero de elementos tenemos Pr−1 que es base. Ahora, escribimos una matriz generadora. Si ti = j=0 ti,j X j 

−t0,0 −t1,0

  G=  −tn−r−1,0

··· ···

−t0,r−1 −t1,r−1

1 0 .. .

0 1

... ...

···

−tn−r−1,r−1

0

0

...

 0 0   = (−T | I)  1

´ Entonces la matriz de control es H = (I | T t ). Uno puede comprobar con un Pr Pn−r−1 c´ alculo directo que para un polinomio recibido u = j=0 X j + i=0 ur+i X r+i , se tiene que H(u0 , . . . , un−1 )t son justo los coeficientes del resto de la divisi´on u = gs + t.

Cap´ıtulo 8

C´ odigos cl´ asicos que se realizan como c´ odigos c´ıclicos 8.1.

C´ odigos de Hamming (de nuevo)

Recordemos la definici´ on de c´odigo de Hamming. Hq,r tiene matriz de control   de cada matriz de dimensi´on 1 de Fqr Hq,r = tomo un vector y lo pongo y sabemos que hay exactamente

q r −1 q−1 .

8.1.1. Observaci´ on. Sea H una matriz tal que   H = H1 · · · H qr −1 . r −1 q−1 [r× qq−1 ] Si las columnas son linealmente independientes 2 a 2 entonces H es la matriz h r i −1 q r −1 de control de un c´ odigo de Hamming, un qq−1 , q−1 − r, 3 -c´odigo. 8.1.2. Teorema. Todo c´ odigo de Hamming es c´ıclico r

−1 Demostraci´ on. Hacemos n = qq−1 . Vamos a ver primero que Fqr es el cuerpo n de escisi´ on de X − 1 sobre Fq . N´otese primero que n(q − 1) = q r − 1 y n = 1 + · · · + q r−1 , de donde n > q r−1 − 1. Ahora consid´erese una ra´ız de X n − 1, r digamos γ. Entonces γ n = 1, luego γ n(q−1) = 1, as´ı que γ q = γ, de donde Fqr contiene al cuerpo de escisi´ on, pero n > q r−1 − 1 as´ı que debe ser justo el cuerpo de escisi´ on. Ahora, sea ξ una ra´ız n-´esima primitiva de la unidad y consid´erese la matriz
L = 1 ξ · · · ξ (n−1)

68

´ ´ CAP´ITULO 8. CODIGOS CLASICOS

69

y expresemos esos elementos como se hizo en la Secci´on 7.3 de los ceros, viendo Fqr como Fq espacio vectorial,   H = 1 ξ · · · ξ (n−1) N´ otese que Frq tiene exactamente n-subespacios de dimensi´on 1 y como ´ese es precisamente el n´ umero de columnas de H, basta ver que cualesquiera dos columnas son l.i. para saber que H es matriz de c´odigo de Hamming. Supongamos que aξ i = ξ j , con 0 ≤ i, j < n. Entonces aξ (i−j) = 1, as´ı que
(i−j) (q−1) aξ = 1. Pero a ∈ Fq , luego aq−1 = 1, as´ı que ξ (i−j)(q−1) = 1, de donde n | (i − j)(q − 1); pero mcd(n, q − 1) = 1, luego i = j.

8.2.

C´ odigos BCH

El nombre viene de Bose, Ray-Chandhuri y Hocquengheim. En estos c´odigos c´ıclicos, se busca que tenga una longitud y distancia designada. 8.2.1. Definici´ on. Sea Fqr el cuerpo de escisi´ on de X n − 1 que contiene a Fq r y sea ξ ∈ Fq una ra´ız n-´esima primitiva de la unidad. Sean 2 ≤ δ ≤ n y b ≥ 0. Cambiando r, por ξ ∈ Fqr , tenemos cinco par´ ametros, (q, n, δ, ξ, b). Llamamos c´ odigo BCH de longitud n y distancia designada δ sobre Fq y lo denotamos Bq (n, δ, ξ, b) (el par´ ametro q sale del par´entesis) al c´ odigo c´ıclico generado por
g(X) = mcm mξb (X), mξb+1 (X), . . . , mξb+δ−2 (X) 1. En el caso b = 1, el c´ odigo se llama BCH en sentido restringido (narrow sense) y se omite el u ´ltimo par´ ametro, es decir, se escribe Bq (n, δ, ξ) 2. Si ξ es un elemento primitivo de Fqr , diremos entonces que el c´ odigo es BCH primitivo. N´ otese que esto ocurre si y s´ olo si n = q r − 1. Trivialmente, todo c´ odigo de Hamming es BCH (primitivo y restringido), con par´ ametros b = 1, δ = 2, d ≥ 2. 8.2.2. Proposici´ on. El c´ odigo Bq (n, δ, ξ, b) es el  c´ odigo c´ıclico de mayor dimensi´ on que contiene entre sus ceros al conjunto ξ b , ξ b+1 , . . . , ξ b+δ−2 . De hecho, el conjunto de sus ceros est´ a formado por los anteriores elementos y sus conjugados. Demostraci´ on. Es muy f´ acil. Sea g(X) como
en la definici´on de c´odigo BCH. Considero un polinomio f (X) tal que f ξ b+i = 0 para todo i = 0, . . . , δ − 2; entonces g | f , ya que mξb+i (X) | f (X). As´ı, g tiene grado m´ınimo y por tanto Bq (n, δ, ξ, b) tiene dimensi´ on m´axima. 8.2.3. Observaci´ on. En un c´odigo BCH restringido (b = 1), C generado por g, podemos asegurar que 1 no es ra´ız de g ya que δ < n implica que 1 + δ − 2 = δ − 1 = n − 1. Luego ξ i 6= 1 para todo i = 1, . . . , δ − 1.

´ ´ CAP´ITULO 8. CODIGOS CLASICOS

70

Adem´ as, el c´ odigo generado por (1 − X)g es el subc´odigo c´ıclico de las palabras de tipo par de C, que obviamente, ta,bi´en es un c´odigo BCH, de hecho, es Bq (n, δ + 1, ξ, 0). El siguiente resultado es un verdadero cl´asico de los c´odigos. 8.2.4. Teorema [Cota BCH]. Sea C un [n, k, d]-c´ odigo c´ıclico sobre Fq y sea n ξ una ra´ız n-´esima primitiva de la unidad en el cuerpo de escisi´ on de X − 1 i sobre Fq . Si existen b ≥ 0 y δ ≥ 1 tal que ξ | b ≤ i ≤ b + δ − 2 son ceros de C, entonces d ≥ δ.  Demostraci´ on. Sea Z = ξ i | b ≤ i ≤ b + δ − 2 un subconjunto de los ceros del c´ odigo, digamos ξ ij | j = 0, . . . , k . Si M es la matriz formada por los ceros (en la extensi´ on de Fq y p = (p0 , . . . , pn−1 ) es un vector de corficientes de un polinomio en el c´ odigo, se tiene que M p = 0; es decir     (ξ i0 )0 (ξ i0 ) ... (ξ i0 )n−1 0 ..          .     p0 b b n−1     (ξ b )0 (ξ ) . . . (ξ )   p1   ..      . ..   ..  =    .  .       (ξ b+δ−2 )0 (ξ b+δ−2 ) . . . (ξ b+δ−2 )n−1     pn−1      ..     . ik 0 ik ik n−1 0 (ξ ) (ξ ) ... (ξ ) Escogemos una palabra p ∈ C de modo que su peso sea m´ınimo; es decir, ω(p) = d. Elegimos un subconjunto {c1 , . . . , cd } del conjunto de columnas de las filas correspondientes a las entradas que comienzan con ξ b , . . . , ξ b+δ−2 y con eso formamos la matriz D.   (ξ b )c1 ... (ξ b )cd   .. D=  . (ξ b+δ−2 )c1

...

(ξ b+δ−2 )cd

Si p0 es el vector proyecci´on de p en los ´ındices de las columnas elegidas, podemos ejecutar el producto y obtenemos Dp0 = 0. Si ocurre que d ≤ δ − 1, podemos extraer la submatriz   (ξ b )c1 ... (ξ b )cd   .. ∆=  . (ξ b+d−1 )c1

...

(ξ b+d−1 )cd

cuyo determinante es no nulo. Luego ∆p0 = 0 implica p0 = 0, lo cual es imposible. 8.2.5. Corolario. d (Bq (n, δ, ξ, b)) ≥ δ, siempre. 8.2.6. Teorema. Sea C = Bq (n, δ, ξ, b) un c´ odigo BCH, donde On (q) = r; es decir, n | q r − 1 y r, el primero. Entonces dimFq C ≥ n − r(δ − 1).

´ ´ CAP´ITULO 8. CODIGOS CLASICOS

71

Demostraci´ on. Inmediato de la definici´on de c´odigo BCH y de (6.5.12 y 6.5.13). 8.2.7. Ejemplo. Consideremos los c´odigos BCH binarios y restringidos de orden 31; es decir, B2 (31, δ, ξ). Puede recorrer 2 ≤ δ ≤ 29. Para determinar los c´ odigos primero consideramos las clases 2-ciclot´omicas m´ odulo 31. Estas son: C0

=

{0}

C1

=

{1, 2, 4, 8, 16}

C3

=

{3, 6, 12, 24, 17}

C5

=

{5, 10, 20, 9, 18}

C7

=

{7, 14, 28, 25, 19}

C11

=

{11, 22, 13, 26, 21}

C15

=

{15, 30, 29, 27, 23}

Para calcular los datos se procede as´ı: 1. Se determina la distancia deseada. Por ejemplo, 9. 2. Se hace la lista {ξ, . . . , ξ 7 } que corresponde con b = 1 y δ = 9, y con esta lista se hacen las dos siguientes cosas. 3. Se determina g(X). 4. Se establecen las clases q-ciclot´omicas involucradas. En este caso son C1 , C3 , C5 y C7 P 5. Se establece la dimensi´on que es n − |Ci | involucrados. En este caso, 31 − 20 = 11. 6. El u ´ltimo c´ alculo de la tabla siguiente es “hecho a mano”. Tomando ξ una ra´ız 31-´esima primitiva de la unidad se tiene δ 1 3 5 7 9 y 11 13 y 15 17, . . . , 31

g(X) mξ 0 mξ mξ mξ3 mξ mξ3 mξ5 mξ mξ3 mξ5 mξ7 mξ mξ3 mξ5 mξ7 mξ9 X 31 − 1

Ci involucradas C0 C1 C1 , C3 C1 , C3 , C5 C1 , C3 , C5 , C7 C1 , C3 , C5 , C7 , C9 C1 , . . . , C15

dimF2 C 31 26 21 16 11 6 1

ω(C) 1 3 5 7 11 15 31

Como se puede apreciar, un c´odigo BCH puede interpretarse con distintos par´ ametros; de ah´ı la siguiente definici´on. 8.2.8. Definici´ on. Sea C = Bq (n, δ, ξ, b) un c´ odigo BCH. Se llama distancia de base de C al mayor δ tal que C = Bq (n, δ, ξ, b).

´ ´ CAP´ITULO 8. CODIGOS CLASICOS

8.3.

72

C´ odigos de Reed-Solomon

Son un caso particular de c´odigos BCH; de hecho, son un caso particular de c´ odigos BCH primitivos. 8.3.1. Definici´ on. Un c´ odigo de Reed-Solomon es un BCH sobre Fq , donde n = q − 1. 8.3.2. Observaciones. 1. Como n = q − 1 entonces Fq es cuerpo de escisi´on para X n − 1; as´ı que s´ olo hay factores lineales o, dicho en t´erminos de clases q-ciclot´omicas, todas las clases q ciclot´ omicas tienen orden 1. Qb+δ−2 2. Por lo anterior, si g es el polinomio generador entonces g = i=b (X−ξ i ) y por tanto dim C = n + 1 − δ. 3. Si C es un RS-c´ odigo entonces C ⊥ tambi´en lo es. Esto se desprende del hecho de que las clases ciclot´omicas s´olo tienen un elemento y no hay conjugados as que uno mismo. Esto significa que si los ceros de C contienen a  b b+1m´ ξ , ξ , . . . , ξ b+δ−2 entonces ya son todos. Luego los inversos de los no ceros  son ξ −(b+δ−1) , . . . , ξ −(b−1) que es otra vez una lista de potencias consecutivas (puestas de forma decreciente), m´odulo n. Se invierte la lista y punto. 4. Hemos visto que dim C = n + 1 − δ, luego δ = n + 1 − dim C; as´ı que d(C) ≥ δ = n+1−dim C, pero la cota de Singleton nos dice que d ≤ n+1−dim C, de donde se tiene la igualdad y por tanto es un c´odigo MDS.

Bibliograf´ıa [1] J. Ad´ amek, Foundations of Coding, Wiley, Chichester, 1991. [2] H. Fripertinger. Enumeration of the semilinear isometry classes of linear codes, en A. Kerber y A. Kohnert, ed., ALCOMA’05, Proceedings of the Conference on Algebraic Combinatorics and Applications, Designs and Codes, Thurnau, Germany, 2005. Bayreuth. Math. Schr., vol. 74, p. 100122, 2005. [3] W.C. Huffman y V. Pless, Fundamentals of Error Correcting Codes, Cambridge, 2003. [4] C. Munuera y J. Tena, Codificaci´ on de la Informaci´ on, Universidad de Valladolid, 1997. [5] V. Pless, Introduction to the Theory of Error-Correcting Codes, Wiley, 1982. [6] O. Pretzel, Codes and Finite Fields, Clarendon, 1992. [7] J. Rif´ a y Ll. Huguet, Comunicaci´ on Digital, Masson, 1991. [8] Derek J. S. Robinson, A Course in the Theory of Groups, Springer, Nueva York, 1996. [9] S. Roman, Coding and Information Theory, Springer, Nueva York, 1992. [10] S. Roman, Introduction to Coding and Information Theory, Springer, 1992. [11] J. H. van Lint, Introduction to Coding Theory, Springer, Nueva York, 1982.

73