grado en matem aticas. curso 2013-2014 c odigos ... · cap itulo 1. informacion y c odigos 4...

Grado en matematicas. Curso 2013-2014

Codigos correctores de errores

Juan Jacobo Simon Pinero

21 de septiembre de 2013

Indice general

1. Informacion y codigos 31.1. La transmision de la informacion . . . . . . . . . . . . . . . . . . 3

1.1.1. Tipos de codigos . . . . . . . . . . . . . . . . . . . . . . . 51.2. Transmision de sımbolos a traves de un

canal con interferencias . . . . . . . . . . . . . . . . . . . . . . . 6

2. Generalidades sobre Codigos 112.1. Conceptos basicos . . . . . . . . . . . . . . . . . . . . . . . . . . 112.2. Equivalencia y automorfismos de codigos . . . . . . . . . . . . . . 192.3. Construccion de codigos a partir de otros . . . . . . . . . . . . . 19

3. Codigos lineales 223.1. Conceptos basicos . . . . . . . . . . . . . . . . . . . . . . . . . . 223.2. Codigos duales u ortogonales . . . . . . . . . . . . . . . . . . . . 263.3. Pesos y distancias . . . . . . . . . . . . . . . . . . . . . . . . . . 263.4. Codificacion y decodificacion en codigos

lineales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293.5. Construcciones con codigos lineales . . . . . . . . . . . . . . . . . 33

4. Cotas a los parametros 364.1. Generalidades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364.2. Cota de Hamming . . . . . . . . . . . . . . . . . . . . . . . . . . 384.3. Cota de Singleton y codigos MDS . . . . . . . . . . . . . . . . . . 384.4. Otras cotas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

5. Tipos especiales de codigos lineales 405.1. Codigos de Hamming y codigos simplex . . . . . . . . . . . . . . 405.2. Codigos de Golay . . . . . . . . . . . . . . . . . . . . . . . . . . . 425.3. Codigos de Reed-Muller (binarios) . . . . . . . . . . . . . . . . . 44

6. Cuerpos finitos 476.1. Suma y producto en cuerpos finitos . . . . . . . . . . . . . . . . . 476.2. Polinomios y numeros algebraicos . . . . . . . . . . . . . . . . . . 496.3. Existencia y unicidad. . . . . . . . . . . . . . . . . . . . . . . . . 51

1

INDICE GENERAL 2

6.4. Ejemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 536.5. El anillo Fq[X]/(Xn − 1) . . . . . . . . . . . . . . . . . . . . . . 556.6. Automorfismos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

7. Codigos cıclicos 617.1. Conceptos basicos . . . . . . . . . . . . . . . . . . . . . . . . . . 617.2. Codigos cıclicos y anillos de polinomios . . . . . . . . . . . . . . . 627.3. Ceros de un codigo cıclico y matriz

de control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 657.4. Codificacion y decodificacion en codigos

cıclicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

8. Codigos clasicos 688.1. Codigos de Hamming (de nuevo) . . . . . . . . . . . . . . . . . . 688.2. Codigos BCH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 698.3. Codigos de Reed-Solomon . . . . . . . . . . . . . . . . . . . . . . 72

Capıtulo 1

Informacion y codigos

1.1. La transmision de la informacion

La transmision de la informacion digital consiste en enviar mensajes, o ca-denas de “palabras” que son, a su vez, cadenas de elementos de un “alfabeto” oconjunto de sımbolos, donde incluimos tambien a las senales de cualquier tipo.Ası, los mensajes seran cadenas de sımbolos que separaremos en palabras (talvez una o tal vez, muchas).

Los sımbolos se envıan a traves de un canal. Un canal es cualquier mediode transmision, como puede ser el cable de telefono, la fibra optica, las ondasde radio, el empleado del supermercado que “teclea” en la caja el codigo debarras de un producto cuando ha fallado el lector, etcetera; aunque al finalsiempre trabajaremos con algunas restricciones. Desde el punto de vista de lafiabilidad de la transmision hay dos tipos fundamentales de canales; a saber,los canales con interferencia (o ruido) y los canales sin interferencia. Nosotrossolo nos ocuparemos del estudio de los canales con interferencia o ruido, que,obviamente, es el caso donde se pueden producir errores.

En este texto, ademas, solo nos ocuparemos de la parte cuantitativa de latransmision de la informacion y no del significado (si analizamos el contenidode los mensajes que normalmente se transmiten en el mundo, seguro que nosdesanimamos).

El siguiente cuadro refleja el proceso directo de la transmision de mensajes.

Figura 1.1.1: Esquema general

emisor - canal - receptor

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

3

CAPITULO 1. INFORMACION Y CODIGOS 4

determinadas reglas. Una de ellas es que cada palabra no pueda tener mas deuna correspondiente en el codigo; formalmente, la codificacion es una aplicacion.Vamos a verlo. Para cualquier alfabeto A, denotamos con Pal(A) el conjuntode todas sus palabras. A lo largo de todo el curso los alfabetos seran siempreconjuntos finitos.1.1.1. Definicion. Sean A,F alfabetos y sea M ⊆ Pal (A) un subconjuntofinito.

1. Una codificacion del alfabeto es una aplicacion inyectiva C : A → Pal(F).

2. Una codificacion de palabras de M es una aplicacion inyectiva C : M →Pal(F).

Llamamos codigo a la imagen de C y se llama palabra codigo o simplementepalabra a cada uno de sus elementos.1.1.2. Observacion. Sean A,F alfabetos y sea M ⊆ Pal (A) un subconjuntofinito. Supongamos que estamos transmitiendo informacion codificada a travesde un canal. El proceso de decodificacion lo realizaremos siempre en dos pasos;a saber:

1. Separaremos (de alguna forma) la lista de sımbolos en partes a las queasignaremos palabras del codigo.

2. A cada palabra de codigo le asignaremos su imagen inversa (que es unica)bajo C.

1.1.3. Ejemplo. Supongamos que somos un GPS para un punto que se va amover en un tablero. Partimos de una casilla “salida” y tenemos que mostrarle laruta a la casilla “meta”. Nuestro alfabeto y palabras seran A = ↑, ↓,←,→ =M .

Vamos a transmitir la ruta al punto de forma codificada; es decir, definiremosuna aplicacion C : M → Pal (F), para algun conjunto F. Luego se decodificara yentonces el punto seguira la ruta que aparece en el tablero.

s

m

Elegimos una ruta que se transmitira completa↓, ↓,→,→, ↓,→,→, ↓

Ahora codificamos. Lo haremos con tres codigos diferentes:

Codificacion 1: Hacemos F = Z2, y C (↑) = 0, C (↓) = 1, C (→) =10, C (←) = 01.

Entonces enviamos la cadena 111010110101 que se transmite sin errores yahora se tiene que decodificar. El problema es que, quien recibe la cadena tiene


mas posibilidades de decodificar que la contemplada por nosotros. Vamos a verdos opciones mas:

Una es: 1 1 1 01 01 10 10 1que se decodifica: ↓ ↓ ↓ ← ← → → ↓

Otra: 1 1 1 0 1 0 1 1 0 1 0 1que se decodifica: ↓ ↓ ↓ ↑ ↓ ↑ ↓ ↓ ↑ ↓ ↑ ↓

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.

Codificacion 2: Hacemos F = Z2∪], y C (↑) = 0], C (↓) = 1], C (→) =10], C (←) = 01] con tres sımbolos, pero si solo podemos enviar binariospodrıamos que hacer algo como F = Z2, y C (↑) = 01, C (↓) = 001, C (→) =0001, C (←) = 00001, o sea que el numero de cifras “0” nos indica la direccionde 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 decodificacion. A estetipo de codigos los llamaremos codigos de decodificacion unica.

Hay una tercera alternativa:

Codificacion 3: C (↑) = 00, C (↓) = 11, C (→) = 10, C (←) = 01Esta decodificacion no necesita sımbolo de separacion porque tiene una pro-

piedad permanente que de antemano sabra siempre el decodificador: que laspalabras tienen longitud fija; a saber, longitud 2. Ası que usa dos sımbolos y esde decodificacion unica.

Enviamos1111101011101011

y tiene solo una interpretacion, la que queremos.

1.1.1. Tipos de codigos

En general, el uso de los codigos abarca tres grandes objetivos en la trans-mision de la informacion:

1. Comprimir mensajes.

2. Detectar y corregir posibles errores.

3. Garantizar la privacidad.


En pocas palabras, hacer la transmision rapida, fiable y segura. La teorıaaborda por separado cada uno de estos objetivos, porque son, de hecho, inde-pendientes. Ası, tenemos tres tipos diferentes de codigos; a saber,

1. Los codigos compresores.

2. Los codigos correctores de errores.

3. Los codigos criptograficos o secretos.

Nosotros solo nos ocuparemos de los codigos correctores de errores. El pro-ceso de codificar, enviar y decodificar, modifica la Figura 1.1.1 a la Figura 1.1.2.

Figura 1.1.2: Transmision codificada

emisor - canal - receptor

codificador decodificador- 6 - 6

1.1.4. Definicion. Decimos que un codigo es de decodificacion unica si cadavez que recibimos una cadena de sımbolos, o mensaje, esta corresponde con unaunica lista de palabras.1.1.5. Definicion.

1. Decimos que una palabra tiene longitud n ∈ N si utiliza exactamente nsımbolos.

2. Decimos que un codigo es un codigo en bloques (o bloqueado) si existen ∈ N, tal que toda palabra es de longitud n.

Se tiene por supuesto la definicion, obvia, de codigo de longitud variable.Nosotros solo nos ocuparemos del estudio de los codigos en bloques. Un ejemplotıpico e importante de codigo de longitud variable es la Clave Morse. Uno debloques es el codigo de barras donde, ademas, todo mensaje tiene exactamenteuna palabra.1.1.6. Observacion. Es claro que todo codigo en bloques es de decodificacionunica.

1.2. Transmision de sımbolos a traves de uncanal con interferencias

Vamos a establecer el contexto que sera nuestra hipotesis de trabajo. Te-nemos un canal discreto y sin memoria, digamos C y un conjunto (finito) de


sımbolos de entrada al canal (el alfabeto), A, junto con una distribucion de pro-babilidades; la de que aparezcan al enviar mensajes. A la pareja del alfabeto yla distribucion de probabilidades se le llama una fuente de entrada. Por su par-te, tenemos tambien un conjunto de sımbolos de salida, F con una distribuciondada por p(F = v) =

∑A p(v|a)p(a = A), en la notacion habitual del calculo de

probabilidades.Para cada entrada a ∈ A hemos elegido un unico sımbolo sa ∈ F, que

llamaremos el sımbolo correspondiente o deseado para a. Diremos que se haproducido un error de transmision cuando habiendo enviado el sımbolo a, elsımbolo recibido no sea sa. Supondremos que la correspondencia es biyectiva.

Vamos a hacer algunos calculos suponiendo que la correspondencia nateriores biyectiva.

1. La probabilidad de cometer un error habiendo enviado el sımbolo a ∈ Aa traves de C, es

pe,C(a) =∑s∈S

p (s 6= sa|a) = 1− p (sa|a) . (1.2.1)

2. Entonces, la probabilidad de que se cometa un error al enviar algun sim-bolo es la media ponderada

Pe,C =∑a∈A

p(a)pe,C(a) =∑a∈A

p(a) (1− p (sa|a))

=∑a∈A

p(a)−∑a∈A

p(a ∩ sa) = 1−∑a∈A

p(a ∩ sa)

= 1−∑a∈A

p(a|sa)p(sa).

De la lista de igualdades anteriores uno usa la que convenga.1.2.1. Ejemplo. Supongamos que tenemos un cuerpo finito F como conjuntode sımbolos de entrada y salida, con distribuciones equiprobables en un canalC. Si p (x|x) = 1− p entonces peC(x) = p y Pe,C = p.

Correccion de errores de transmision. Esquemas y errores de decision

El objetivo de los codigos correctores de errores es anadir informacion (re-dundancia) al mensaje para poder recuperarlo aun cuando se hayan producido(no muchos) errores durante la transmision. Como veremos, la clave esta en lamanera como agregamos la informacion; es decir, como codificamos y tambiencomo descodificamos. Es ahı donde interviene la matematica.

Vamos a ver como afectan la interferencia y la correccion a la Figura 1.1.2.En la practica, para trabajar con codigos en bloques podemos sustituir,

respetando la distribucion de probabilidades, los sımbolos de entrada y salidapor un cuerpo finito F al que seguiremos llamando alfabeto. Haremos M =


Figura 1.2.1: Correccion de errores

emisorcanal coninterferencia receptor

codificador decodificador- 6

-

6

correccion deerrores

6

Palk(A) = Fk y la codificacion sera una aplicacion C : Fk → Fn y ası, nuestrocodigo en bloques sera ImC = C ⊆ Fn.

Consideremos Fn, el conjunto de las palabras de longitud n. Un esquema dedecision es una funcion parcial de Fn a las palabras del codigo; es decir, unarelacion donde no todo elemento del dominio tiene imagen (aquellas palabras,que no sepamos como corregir, no tendran imagen). Para cada c ∈ C, definimos

Bc = v ∈ Fn | f(v) = c . (1.2.2)

Como f es aplicacion parcial entonces los Bcc∈C son disjuntos aunque tal vezno sean una particion de Fn.

Considerese, pues, un esquema de decision f : Fn parcial−−−−−−→ C. Para unapalabra s ∈ Fn, si f(s) esta definido, entonces el esquema “decide” que lapalabra enviada fue f(s). Si f(s) no fue la palabra enviada decimos hemoscometido un error de decision.

A continuacion, vemos un grafico del proceso completo, donde denotamosFn C Fn la transmision a traves del canal C.

Fk codificacion−−−−−−−−→ C ⊆ Fn C Fn esquema−−−−−−→ C

decodificacion−−−−−−−−−−→ Fk

1.2.2. Observacion. Ya cuando estemos concentrados en los codigos, a estoserrores los llamaremos errores de decodificacion. La razon es que se considera ladecision o correccion como parte de la decodificacion.

Vamos a calcular la probabilidad de cometer un error de decision al “corre-gir” errores. Una vez fijado un codigo, C, tendremos que calcular la probabilidadde que una palabra c ∈ C sea enviada, y esto necesariamente determina una dis-tribucion de la fuente. Notese que esto no influye en la probabilidad de cometerun 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


de que aparezca en una decodificacion. Se calcula como p(v) =∑c∈C p(v|c)p(c).

Como el canal es sin memoria se tiene que, si c = c1 . . . cn y v = v1 . . . vn enton-ces p(v|c) =

∏ni=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 definicion, decimos que hemos cometido un error de decision cuando

habiendo enviado la palabra c ∈ C recibimos la palabra v 6∈ Bc; luego la proba-bilidad condicionada que elegimos usar es p(v|c), y la calcularemos de diversasmaneras. Ası, para una palabra c ∈ C enviada, la probabilidad es

pe(c) =∑v 6∈Bc

p(v|c) =

(1−

∑b∈Bc

p(b|c)

)

y la probabilidad total de error de decision es, en vista de que∑c∈C p(c) = 1

Pe(C) =∑c∈C

p(c)pe(c) =∑c∈C

p(c)

∑v 6∈Bc

p(v|c)

= 1−

∑c∈C

∑b∈Bc

p(c)p(b|c) = 1−∑v∈Fn

p(v ∩ f(v))

ya que, si b ∈ Bc entonces c = f(b) y ası p(c)p(b|c) = p(b ∩ f(v)). La suma secompleta a todo v ∈ Fn asumiendo que si v 6∈ ∪c∈CBc entonces p(v∩ f(v)) = 0,dado que f(v) no existe.

Para eliminar la suma doble quitamos la dependencia de que aparezca cadapalabra y tomamos el error maximo; es decir, definimos

Pmaxe (C) = max pe(c) | c ∈ C .

Claramente,Pe(C) ≤ Pmaxe (C)

Es tambien posible establecer la probabilidad de error en terminos de laotra probabilidad condicionada. Recordemos que, para v ∈ Fn, se tiene quep(v) =

∑c∈C p(v|c)p(c). entonces

Pe(C) = 1−∑v∈Fn

p (v ∩ f(v)) = 1−∑v∈Fn

p(v)p (f(v)|v)

=∑v∈Fn

p(v) (1− p (f(v)|v)) =∑v∈Fn

p(v)pe(v).

Entonces, para poder calcular la probabilidad total de error de decision ne-cesitamos tres ingredientes: el primero es la distribucion p(c) | c ∈ C, el se-gundo es la distribucion p(v|c) | (c, v) ∈ C × Fn y el otro es la familia Bc.1.2.3. Ejemplos. Vamos a ver algunos esquemas de decision. Transmitimosen un canal discreto y sin memoria con sımbolos de entrada y salida F. SeaC ⊂ An un codigo con |C| = M . Considerense los siguientes esquemas de

decision f : Fn parcial−−−−−−→ C,


1. Supongamos que para cada c ∈ C y v ∈ Fn conocemos p(c|v). Con estosdatos definimos p (C|v) = p(c|v) | c ∈ C y podemos definir f(v) ∈ Ccomo el vector tal que p (f(v)|v) = max p (C|v). Este esquema se conocecomo error mınimo en la decodificacion de probabilidad a posteriori y tienela propiedad de que minimiza el error de decision 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 yf(v) como el vector tal que p (v|f(v)) = max p (v|C). Este esquema seconoce como maxima verosimilitud en la decodificacion de probabilidad aposteriori.

Capıtulo 2

Generalidades sobreCodigos

2.1. Conceptos basicos

Una vez que hemos fijado la intencion y el contexto del estudio de los codigoscorrectores de errores, vamos tambien a fijar un poco la notacion.2.1.1. Definicion. Sea A un alfabeto (finito), con |A| = q, y considerese An,como siempre. Llamamos codigo q-ario en bloques de longitud n a cualquiersubconjunto no vacıo de An. Al propio An lo llamamos el conjunto ambiente.

Sea M = |C|. Decimos que C tiene parametros (n,M), o que C es un (n,M)-codigo sobre A.

A los elementos de C les llamaramos palabras del codigo.2.1.2. Notacion. A los largo de todo el texto, nuestros alfabetos seran siemprecuerpos 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 codigo uncodigo corrector de errores definido en bloques. El conjunto ambiente sera Fn,a quien llamaremos el espacio ambiente.2.1.3. Ejemplo. [Codigos de repeticion] Consideremos a F2 y supongamos quesolo queremos enviar los mensajes “sı” y “no”. Vamos a suponer tambien quede alguna manera sabemos que el canal comete a lo mas dos errores cada 5emisiones. Usamos entonces 5 dıgitos como sigue.

sı 7→ 00000.

no 7→ 11111.

El codigo es entonces C = 00000, 11111.

Para crear este codigo hemos hecho posiblemente lo mas antiguo que se hacepara eliminar errores, REPETIR la palabra (5 veces). Este tipo de codigos sellaman codigos de repeticion.

11

CAPITULO 2. GENERALIDADES SOBRE CODIGOS 12

2.1.4. Ejemplo. El ISBN (International Standard Book Number) es un codigode 11 sımbolos; a saber, 0, 1, . . . , 9, X, y palabras de longitud 10 divididas en4 grupos de datos, que describimos a continuacion.

Todos los sımbolos, salvo posiblemente el ultimo, son numericos.

El primer grupo tiene un dıgito e indica el idioma en que esta escrito ellibro.

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 (numerico o X). El dıgito de control(check sum).

El dıgito de “control” es lo que nos interesa. Se calcula con la forma “com-pleta a 10”; es decir, si x1, . . . x9 son los dıgitos, hacemos

−10x10 ≡ x10 ≡9∑i=1

i · xi mod 11

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

10∑i=0

i · xi ≡ 0 mod 11.

La parte izquierda de la congruencia se llama suma de verificacion del pesadode x1 . . . , x10.

El problema aquı es que x10 = 10 es un valor posible y solo podemos escribirUN dıgito. Entonces, en ese caso hacemos x10 = X y a efectos de calculo yasabemos que numero asignar.

Por ejemplo, el codigo 0 − 19 − 859617 − 0 (los guiones se pueden ponerdonde uno quiera). El primer dıgito nos dice 0, que es ingles. Los dos siguientes19 son de Oxford University Press, el 859617 es el asignado por la Casa y∑9i=1 i · xi = 253 ≡ 0 mod 11.Vamos a ver los parametros de este codigo. El espacio ambiente es F10

11. Losdıgitos x1, . . . , x9 solo tienen restriccion en el alfabeto (no pueden ser 10 o X);ası que M = 109 segun la proposicion anterior, y el mınimo de las distanciasposibles es d(ISBN) = 2, ya que lo menos que difieren dos palabras ANTESdel dıgito de control es 1, pero luego van a diferir en el dıgito, ası que seran almenos 2.

Vamos a ver que si se comete un error entonces el codigo lo detecta. Seanx = 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). Notese que ni i0ni xi0 − yi0 son multiplos de 11, por lo que 11 - y.


Distancia mınima y correccion

Vamos a abordar un nuevo esquema de decision que tambien sera del tipode maxima verisimilitud. Esta nocion corresponde a la idea “mas cerca mientrasmenos errores se hayan cometido”, sin importar cuales fueron los dıgitos que secambiaron.

Vamos a formalizar un poco a este esquema de decision porque es el unicoque usaremos en el curso.2.1.5. Definicion. Sea F un cuerpo.

La distancia de Hamming entre dos vectores u, v ∈ Fn es el numero natural:

d(u, v) = |ı ∈ 1, . . . , n | u(ı) 6= v(ı)| .

La distancia mınima de un codigo, C ⊆ Fn es

d(C) = mın d(u, v) | u, v ∈ C .

La siguiente definicion es una variante util en algunos calculos, pero sobretodo lo sera cuando los codigos sean espacios vectoriales.2.1.6. Definicion. Sea F un cuerpo. Para un vector u ∈ Fn definimos el pesode u como

ω(u) = |supp(u)| = d(0, u).

2.1.7. Proposicion. Sea C un codigo sobre un alfabeto F. Entonces la distanciade Hamming cumple los axiomas de metrica; a saber,

1. d(u, v) = 0 si y solo si u = v.

2. d(u, v) = d(v, u).

3. d(v, u) ≤ d(u, z) + d(z, v).

2.1.8. Observacion. Es facil comprobar las siguientes afirmaciones sobre ladistancia 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 metrica, para determinar el esquema (vease la Ecua-cion 1.2.2) usaremos bolas cerradas de algun radio con centro en las palabrasdel codigo; 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 decision, lasbolas (cerradas) han de ser disjuntas dos a dos. Esto pone fuertes limitacionesal radio y nos hace detenernos en su estudio.


2.1.9. Lema. Sea C un codigo en Fn con distancia mınima d y sea r ∈ N. Lasbolas Br(c) | c ∈ C son disjuntas si y solo si r ≤ bd−1

2 c = t.

Demostracion. ⇒]. Supongamos que r > t. Notese primero que si r > d−12

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) ≤ bd− 12c+ bd− 1

2c ≤ d− 1 < d,

lo cual es imposible.

Por eso, al numero t = bd−12 c se le conoce tambien como radio de empaque-

tado; es facil ver que es el maximo de los radios que hacen a las bolas disjuntasdos a dos (vease [9, 10]). Como veremos un poco mas adelante, a t tambien sele conoce como la capacidad de correccion.2.1.10. Observacion. Entonces, para un codigo C ⊆ Fn, se tiene que si r ≤⌊d−1

2

⌋, el conjunto de bolas Br(c) | c ∈ C induce el esquema de decision

f : Fn parcial−−−−−−→ C tal que f(u) = c ⇔ d(u, c) ≤ r para c ∈ C y u ∈ Fn.De la definicion de nuestro esquema se puede deducir con facilidad la segunda

parte del siguiente resultado.2.1.11. Teorema. Sea C un codigo y d(C) la distancia mınima. Entonces

1. C puede detectar hasta d(C)− 1 errores.

2. C puede corregir hasta bd(C)−12 c errores.

Demostracion. (1) Sea c la palabra enviada y v la palabra recibida. Si v provinede 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 alo mas t = bd(C)−1

2 c errores entonces v ∈ Bt(c) y se corregira con exito.

2.1.12. Definicion. Para un codigo C, se define la capacidad de correccioncomo t = bd(C)−1

2 c.2.1.13. Definicion. Un (n,M, d)-codigo es un codigo de longitud n, que con-tiene M palabras y tiene distancia mınima d.


Errores de decision en el esquema de la distancia de Hamming

Vamos a calcular la probabilidad de cometer un error en este esquema dedecision. Sea F un cuerpo finito y C ⊆ Fn un codigo con distancia mınimad(C) = d y capacidad de correccion t = bd(C)−1

2 c. Ya sabemos que si se cometena lo mas t errores en la transmision no habra error de decision.

Vamos a calcular entonces la probabilidad de que se cometan mas de t erro-res. Eso depende de las probabilidades de cometer errores al enviar los sımbo-los. La probabilidad de que se cometa un error al enviar un sımbolo x ∈ Fq esp(Fq \ x|x) = p. Ası que la probabilidad de que se cometan k ≤ n errores enunas posiciones especıficas de una palabra es pk(1− p)(n−k).

Sea Sk(c) = s ∈ Fn | d(c, s) = k, con k ≤ t. Entonces Bt(c) =⋃tk=0 Sk(c)

(union disjunta). Claramente |Sk(c)| =(nk

)(q − 1)k, luego

1− pe(c) = p (≤ t errores) =∑

b∈Bt(c)

p(b|c)

=t∑

k=0

|Sk(c)| pk (1− p)n−k =t∑

k=0

(n

k

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

Pero esto ultimo ocurre con cada palabra; ası que la probabilidad de error(o acierto) en el codigo C es independiente de las palabras y podremos sacarlocomo factor comun. Ası,

Pe(C) ≤∑c∈C

p(c)

(1−

t∑k=0

(n

k

)(q − 1)kpk(1− p)n−k

)

=

(∑c∈C

p(c)

)(1−

t∑k=0

(n

k

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

)

= 1−t∑

k=0

(n

k

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

2.1.14. Ejemplo. Consideremos el codigo binario de repeticion, de longitud 3.

C =

000111

.

En este caso, la distancia mınima es d(C) = 3 y t = 1; luego las bolasson B1(000) = 000, 100, 010, 001, B2(111) = 111, 011, 101, 110. Notese queB1 ∪B2 = F3.

Aun mas, segun lo visto en el capıtulo anterior, si la probabilidad asociadaa C es uniforme, Pe(C) = 1−

∑1k=0

(3k

)pk (1− p)n−k = 3p2 − 2p3

2.1.15. Ejemplo. Volvamos al ejemplo en (1.1.3) del GPS. En ese caso, habıamos


definido el codigo

C1 =

↑ 7→ 00↓ 7→ 11→ 7→ 10← 7→ 01

C1 es un (2, 4, 1)-codigo binario y no detecta ni corrige error alguno.Ahora vamos a agregar redundancia

C2 =

↑ 7→ 00|0↓ 7→ 11|0→ 7→ 10|1← 7→ 01|1

C2 es un (3, 4, 2)-codigo binario y detecta 1 error, pero no puede corregir.Un codigo que solo detecta un error se llama codigo detector de un error.

Mientras mas redundancia agregamos, mejor para la correccion y peor parala tasa de trasmision. Si agregamos dos dıgitos mas,

C3 =

↑ 7→ 00|000↓ 7→ 11|011→ 7→ 10|110← 7→ 01|101

C3 es un (5, 4, 3)-codigo binario, tiene tasa 1/2, corrige un error y detecta 2,pero NO A LA VEZ. Por ejemplo, si recibimos la palabra 00001. Tenemos dosposibilidades:

1. Si asumimos que solo se puede cometer un error, entonces corregimos00001 7→ 00000.

2. Si asumimos que se puede cometer mas de un error entonces 00001 pue-de provenir de 01101 con dos errores o de 00000 con un error. Entoncesdetectamos 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. Observacion. Normalmente tenemos que decidir si un codigo es de-tector o corrector, aunque los codigos detectores no los estudiaremos aparte.2.1.17. Ejemplo. El codigo del ISBN (2.1.4), como vimos, tien distancia mıni-ma d(ISBN) = 2, entonces detecta un error y no corrige ninguno.


2.1.18. Ejemplo. Todo codigo q-ario de longitud n, de repeticion, es un (n, q, n)-codigo.

Codigos perfectos y radio de recubrimiento

Los codigos perfectos son aquellos para los cuales el esquema de decisioninducido por las bolas cerradas tiene una aplicacion o funcion (en el sentidohabitual) en vez de una funcion parcial. En [4] se llama codigo de decodificacionunica a aquellos que verifican que su esquema es una aplicacion.2.1.19. Definicion. Un codigo C sobre un alfabeto F se llama perfecto si ladistancia mınima es de la forma d = 2t+ 1 y

Fn =⋃x∈C

Bt(x)

es decir, si Fn es union de las bolas de radio d−12 ∈ N y centro en las palabras.

Vamos ahora a dar un criterio meramente aritmetico para determinar cuandoun codigo es perfecto.2.1.20. Lema. Sea Fq un cuerpo finito. En Fnq , una bola de radio r y centroen un punto v tiene exactamente

|Br(v)| =r∑j=0

(n

j

)(q − 1)j

elementos.

Demostracion. Ya hemos visto que para Sj(c) = s ∈ Fn | d(c, s) = j se tieneque |Sj(c)| =

(nj

)(q−1)j . El resultado se deduce entonces de la igualdad Bt(c) =⋃t

j=0 Sj(c) (union disjunta).

Ahora caracterizaremos a los codigos perfectos.2.1.21. Teorema. Un (n,M, d)-codigo q-ario es perfecto si y solo si

M ·t∑

j=0

(n

j

)(q − 1)j = qn, con t =

⌊d− 1

2

⌋.

Demostracion. Por hipotesis, las bolas son disjuntas, ası que∣∣∣∣∣ ⋃u∈C

Bt(u)

∣∣∣∣∣ = M · |Bt(x)| = M ·t∑

j=0

(n

j

)(q − 1)j

donde hemos fijado un x ∈ C cualquiera. De aquı, es inmediato el resultado.

2.1.22. Ejemplo. Para cualquier (5,M, 3)-codigo binario se tiene entonces queM(1 + 5) ≤ 25, luego M ≤ 5.


2.1.23. Ejemplos. Algunos codigos perfectos.

1. Todo codigo binario de repeticion de longitud impar es perfecto (vease2.1.14).

Efectivamente. Por la formula del binomio y el hecho de que

n∑k=n+1

2

(n

k

)=

n−12∑

k=0

(n

n− k

)

se tiene

2n = (1 + 1)n =n∑j=0

(n

j

)=

n−12∑j=0

(n

j

)+

n∑k=n+1

2

(n

k

)

=

n−12∑j=0

[(n

j

)+(

n

n− j

)]=

n−12∑j=0

2 ·(n

j

)= M

t∑j=0

(n

j

)(2− 1)j

2. El codigo total.

3. Los codigos binarios de longitud impar de la formac, 1 + c

.

Pero estos codigos son triviales. Un problema muy interesante es encontrarTODOS los codigos perfectos. Trataremos este problema mas adelante. Por lopronto solo mencionar que hay familias importantes de codigos perfectos comolos codigos de Hamming.

Cuando un codigo no es perfecto, nos interesa saber cuanto dista de serlo.Para ello usamos el siguiente concepto.2.1.24. Definicion. Sea C un (n,M, d)-codigo sobre F. El radio de recubri-miento de C es

ρ(C) = mın

r ∈ N | Fn =

⋃c∈C

Br(c)

.

Es decir, el menor natural tal que la familia de bolas con dicho numero cubreel espacio ambiente.2.1.25. Observacion. Equivalentemente se puede ver que

ρ(C) = maxv∈Fn

(mınc∈C

(d(v, c))).

2.1.26. Definicion. Sea C un (n,M, d)-codigo sobre F, con radio de empa-quetamiento (o capacidad de correccion) t. Decimos que C es cuasi perfecto siρ(C) = t+ 1.2.1.27. Ejemplo. El codigo C3 de (2.1.15) verifica bd−1

2 c = 1 y ρ (C3) = 2.Luego, C3 es quasi perfecto.


2.2. Equivalencia y automorfismos de codigos

La definicion tradicional de equivalencia de codigos es la siguiente (veanse,por ejemplo [4, 5, 9]).2.2.1. Definicion. Dos codigos C y D, q-arios decimos que son equivalentessi se puede obtener uno del otro a traves de una combinacion de operaciones delos siguientes tipos:

1. Permutacion de las posiciones.

2. Permutacion de los sımbolos de una posicion fija.

Como aplicacion, un resultado muy util a la hora de hacer calculos.2.2.2. Lema. Todo (n,M, d)-codigo sobre F es equivalente a un (n,M, d)-codi-go sobre F, que contiene al vector 0 ∈ Fn.

Demostracion. Inmediato del hecho de que las traslaciones son isometrıas.

A su vez, cada codigo tiene asociado su grupo de automorfismos o autoequi-valencias.2.2.3. Definicion. Sea F un cuerpo finito y C ⊆ Fn un codigo. El grupo deautomorfismos de C es

Aut(C) = x ∈ Isomn(F) | Cx = C .

De especial interes es el grupo de aquellos automorfismos que solo hacenpermutar a las coordenadas;2.2.4. Definicion. Dos codigos C,D ⊂ Fn, decimos que son permutacion equi-valentes si existe una permutacion σ ∈ Sn, tal que Cσ = D.2.2.5. Definicion. Sea F un cuerpo finito y C ⊆ Fn un codigo. El grupo deautomorfismos de permutacion es

PAut(C) = x ∈ Sn | Cx = C .

2.3. Construccion de codigos a partir de otros

Codigos pinchados

2.3.1. Definicion. Decimos que pinchamos un codigo C ⊂ Fnq , cuando elimi-namos una coordenada fija en todas las palabras; es decir, proyectamos sobre lasotras.

Una pregunta importante desde el punto de vista de la teorıa de codigoses que ocurre con los parametros. Es decir, si tenemos un (n,M, d)-codigo ydenotamos con C?i al codigo pinchado en la i-esima corrdenada ¿podemos dardirectamente los nuevos parametros?


2.3.2. Proposicion. Sea C un (n,M, d)-codigo sobre Fq y sea C?i el codigopinchado en la i-esima coordenada. Si d > 1 entonces C?i es un (n− 1,M, d?i )-codigo, donde

d?i =

d− 1 si existen u, v ∈ C, con d(u, v) = d y u(i) 6= v(i)d otro caso.

Demostracion. Si |C?i | < M = |C| entonces tendran que existir u, v ∈ C conu 6= v, pero v? = u? lo cual implica que d(u, v) = 1. Imposible. Luego, |C?i | = M .El calculo de d?i es inmediato.

Para los siguientes resultados, necesitamos el concepto de subgrupo de per-mutaciones transitivo.2.3.3. Definicion. Decimos que un subgrupo H ≤ Sn es transitivo si actuatransitivamente en 1, . . . , n; es decir, para cualesquier 1 ≤ i, j ≤ n, existeσ ∈ H tal que σ(i) = j (es decir, solo hay una orbita).2.3.4. Proposicion. Sea C un (n,M, d)-codigo. Si PAut(C) es transitivo en-tonces los n codigos obtenidos de pinchar C en cada coordenada son permutacionequivalentes.

Demostracion. Vamos a ver que C?1 es equivalente a C?j para j = 2, . . . , n.Sea a ∈ C tal que a = (a1, . . . , aj , . . . , an) y sea b = aσ1j ∈ C (por la tran-sitividad). Entonces b = (aj , a2, . . . , aj−1, a1, aj+1, . . . , an) y en consecuenciab?j = (aj , a2, . . . , aj−1, aj+1, . . . , an). Hacemos σ = σ12σ23 . . . σj−2j−1 y se tieneque b?j = (a2, . . . , aj , . . . , an) = a?1. Ası, (aσ1j)?jσ = a?1, pero aσ1j ∈ C, luegoC?j σ = C?1 .

2.3.5. Ejemplo. Sea C = 00000, 11000, 00111, 11111. Se puede construir C?1y C?5 , y comprobar que no son equivalentes.

Codigos extendidos

Esencialmente, extender codigos es agregar informacion, digamos en dos pa-sos. Hay muchas maneras (lineales) de hacerlo; una especial, es la que se llama“agragar el dıgito de control” (de paridad, parity check, en ingles). Se hace ası,2.3.6. Definicion. Sea C un (n,M, d)-codigo sobre Fq. Hacemos

C =

(v1, . . . , vn, vn+1) | (v1, . . . , vn) ∈ C y

n+1∑ı=1

vı = 0

Otra vez, queremos conocer los parametros por formula.2.3.7. Proposicion. Sea C un (n,M, d)-codigo sobre Fq. Entonces C es un[n+ 1,M, d

]-codigo, donde d = d o d+ 1.

Demostracion. Trivial.


2.3.8. Observacion. Obtener leyes para los codigos extendidos en el caso bi-nario es muy simple. Aquı, trivialmente, d = d+ 1 si d es impar y es d en casocontrario.

Concatenacion o suma directa

Es importante distinguir entre la suma directa del algebra lineal y la sumadirecta de codigos, que no coinciden.2.3.9. Definicion. Sean C1, C2 (n1,M1, d1) y (n2,M2.d2) codigos q-arios. Laconcatenacion o suma directa es el codigo

(u | v) | u ∈ C1, v ∈ C2

El estudio de los parametros aquı es muy sencillo y el propio lector puedecompletar la seccion.

La construccion de Plotkin

2.3.10. Definicion. Sean Ci dos (n,Mi, di)-codigos q-arios, con i = 1, 2, peron fijo. Formamos un nuevo codigo que llamamos la construccion de Plotkin.

C1 ⊕ C2 = (u | u+ v) | u ∈ C1, v ∈ C2

2.3.11. Proposicion. Sean Ci dos (n,Mi, di)-codigos q-arios, con i = 1, 2.Entonces C1 ⊕ C2 es un (2n,M1M2, d)-codigo, donde d = mın 2d1, d2.

Demostracion. 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ınimade C2 y u1 = u2.

Si v1 = v2 entonces d(x, y) = 2d (u1, u2) ≥ 2d1 y tambien hay palabras quela alcanzan. De aquı, se tiene de inmediato.

Capıtulo 3

Codigos lineales


Como hemos comentado antes, la idea subyacente de los codigos correctoresde errores es la redundancia en la informacion. En este capıtulo comentaremosla manera algebraica de controlar dicha redundancia, y de hecho, la codificaciony decodificacion.

Como viene ocurriendo, F siempre denotara un cuerpo finito. Cuando sequiera hacer enfasis en su cardinal, escribiremos Fq, donde q = |Fq|.

Por ejemplo, en el caso del codigo C1 = 00, 10, 01, 11 del GPS (1.1.3 y2.1.15) que vimos antes, lo ampliamos al codigo C2 = 000, 101, 011, 110. Esfacil ver que, la regla para ampliarlo es (x, y) 7→ (x, y, x + y) en terminos delalgebra lineal; es decir, la redundancia puede obtenerse mediante aplicacioneslineales. Vamos a identificarlo. Tenemos C1 = F2

2 y hacemos f : F22 → F3

2, tal quef(x, y) = (x, y, x+ y). Claramente C1

∼= C2. Llamaremos matriz de codificaciona la matriz asociada a la codificacion (en las bases canonicas, como escalaresopuestos). Se tiene, C2 =< M(f) >, la matriz en las bases canonicas. Masadelante, llamaremos a M(f) (una) matriz generadora 1.

Ahora hacemos δ : C2∼= F2

2 → 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 coor-

denadas (y dejando intacto el codigo original) nos produce matrices del tipoM(δ) = (Ik|A)

Vamos a formalizar la situacion.3.1.1. Definicion. Sea F un cuerpo finito. Un codigo lineal, C, es un subespaciodel espacio vectorial Fn. Escribimos [n, k, d]-codigo para un codigo lineal de Fn

1¿Generadora o generatriz? Las opiniones estan divididas (veanse [4, 7]). Segun el diccio-nario de la RAE, generadora es “que genera”, mientras que generatriz los reserva para fısicay geometrıa. En todo caso, ambas estan en el diccionario y aunque no estuvieran cada uno lasusarıa como quisiera. Aquı diremos generadora porque matriz generatriz, todo junto, no nosgusta.

22

CAPITULO 3. CODIGOS LINEALES 23

con dimF C = k y distancia mınima d. Escribiremos solo [n, k]-codigo cuandono nos interese hacer enfasis en la distancia mınima.3.1.2. Observacion. Un [n, k]-codigo sobre Fq tiene exactamente qk elementos.

Para la presentacion de los codigos 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. Definicion. Sea C un [n, k]-codigo sobre F. Una matriz generadora deC 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) lasubmatriz de M que proviene de la interseccion de las filas i1, . . . , ir y las co-lumnas j1, . . . , js. Abreviemos, M (1, . . . , n;X) = M(−;X) y M (X; 1, . . . , n) =M(X;−)3.1.4. Definicion. Sea C un [n, k]-codigo sobre F. Un conjunto de informaciono conjunto de posiciones de informacion, es un subconjunto I ⊂ 1, . . . , n talque, dada cualquier palabra del codigo, (c1, . . . , cn) ∈ C y cualquier posicion j =1, . . . , n existe un unico conjunto de coeficientes ai,ji∈I , tal que

∑i∈I ai,jci =

cj.Es decir, que el codigo C puede obtenerse conociendo los valores de las po-

siciones I.Por ejemplo, si se considera el codigo C = (x, y, z) | z = x+ y, entonces

I = 2, 3 es un conjunto de informacion. Vamos a comprobarlo. Sean (x, y, x+y)y (x′, y′, x′ + y′) tales que y = y′ y x+ y = x′ + y′. Claramente x = x′.3.1.5. Definicion. Sea C un [n, k]-codigo sobre F con un conjunto de in-formacion I. Se llama conjunto de redundancia o de posiciones de control a1, . . . , n \ I.

El ejemplo mas simple es la codificacion sistematica. Decimos que un codi-go es sistematico si al agregar la redundancia hemos mantenido las primerasfilas intactas. Ası, su matriz generadora sera de la forma G(C) = M(I|A). Lasprimeras columnas tienen la informacion y las siguientes la redundancia.

Un criterio sencillo y muy util para encontrar conjuntos de informacion setiene en el siguiente toerema.3.1.6. Teorema. Sea C un [n, k]-codigo sobre F con matriz generadora G. SiG tiene k columnas linealmente independientes entonces los ındices de dichascolumnas forman un conjunto de informacion. (Notese que al menos seguro unohay).

Recıprocamente, si I ⊂ 1, . . . , n es un conjunto de informacion enton-ces existe una matriz generadora G tal que las columnas con ındices en I sonlinealmente independientes.

Demostracion. Supongamos primero queG es una matriz generadora y que tieneciertas columnas con ındices i1, . . . , ik, que son linealmente independientes.Considerese la submatriz de las columnas i1, . . . , ik, sea G(i1, . . . , ik). Entoncesexiste una matriz de operaciones elementales por fila E tal que la submatrizEG(i1, . . . , ik) = I. Ademas, EG es matriz generadora, tambien. Sea c ∈ C


cualquier palabra. Entonces existe a ∈ Fk tal que aEG = c. Por la forma quetiene EG es claro que cij = aj y que, para cualquier l = 1, . . . , n, cl =

∑rjlaj =∑

rjlcij .Recıprocamente, supongamos que I = i1, . . . , ik es un conjunto de infor-

macion. Sea b1, . . . , bk una base para C y sean a1, . . . , ak las proyecciones de losbj en las coordenadas de I; es decir, aj = (bj(i1), . . . , bj(ik)).

Se afirma que a1, . . . , ak es linealmente independiente en Fk. Considereseuna combinacion lineal

∑rjaj = 0. Entonces, tomando cualquier componente,

se tiene∑rjbj(il) = 0, lo cual implica que rj = 0 para todo j = 1, . . . , k pues

I es conjunto de informacion y por tanto las expresiones son unicas.Finalmente, se considera la aplicacion inducida por la correspondencia aj 7→

bj . La matriz asociada a esta aplicacion en las bases aj y cualquier extensionde bj nos vale.

Sea ahora C un [n, k]-codigo sobre F con matriz generadora G. Sabemosque si las primeras k columnas de G forman un conjunto de informacion (osea, son linealmente independientes) entonces existe una matriz de operacioneselementales exclusivamente por filas, digamos E, tal que EG = (Ik|A). Es obvioque EG tambien es matriz generadora de C. Esta forma tiene nombre propio.3.1.7. Definicion. Sea C un [n, k]-codigo sobre F con matriz generadora G.Decimos que G esta en forma tıpica (estandar) si G = (Ik|A) para alguna matrizadecuada A.

3.1.8. Ahora consideremos la sucesion exacta 0→ Fk f−−→ Fn η−−→ Coker(f)→0. Entonces C = Im(f), el codigo nos da la sucesion 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 Hy se denota Nd(H). Tambien hay, claro, la nulidad a la izquierda. A la matrizH 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 deun [n, k]-codigo lineal entonces H = (−At|In−k) es una matriz de control de C.

Demostracion. Basta hacer las cuentas y luego considerar dimensiones.

El siguiente resultado nos muestra que esencialmente todo codigo puedesuponerse con matriz en forma tıpica.3.1.10. Teorema. Todo codigo lineal C es permutacion equivalente a un codigocuya matriz generadora esta en forma tıpica.

Demostracion. SeaG la matriz generadora. Por algebra lineal (metodo de Gauss-Jordan) sabemos que existen matrices invertibles (de operaciones elementales),E,F , tales que EGF = (Ik|A), donde Ik es la identidad y A alguna matriz


adecuada. Tambien sabemos que podemos elegir F como solo producto de per-mutacion de los pivotes (o cualquier permutacion que pusiera en las primerascolumnas un conjunto de informacion). Entonces EG genera el mismo codigoC y por tanto CF es permutacion equivalente y tiene la matriz de la formadeseada.

3.1.11. Ejemplos.

1. El codigo binario de repeticion F2f−−→ F5

2 que vimos en (2.1.3) tiene matrizde codificacion

M(f) =

1...1

5×1

y la matriz generadora es G = (1|1111),que esta en forma tıpica.

En este caso, el conjunto de informacion es 1 y la redundancia es 6. Lamatriz de control es

H =(At|I4

)=

−1...−1

I4

=

1...1

I4

porque estamos en F2.

2. Mas adelante, veremos con detalle un tipo de codigos llamados codigos deHamming. Por lo pronto llamaremos H3 al codigo con matriz generadora

G =

I4

0 1 11 0 11 1 01 1 1

y de control

H =

0 −1 −1 −1−1 0 −1 −1−1 −1 0 −1

I3

.

Este es un [7, 4]-codigo.

3. En el ejemplo del ISBN (2.1.4) tenemos C = F911 y agregamos la informa-

cion (dıgito de control de pesos) con la aplicacion lineal f : C → F1011 dada

por f (x1, . . . , x10) =(x1, . . . , x9,−

∑9i=1 ixi

). En este caso, la matriz

generadora es

G(ISBN) =

I9

−1...−9

.


3.2. Codigos duales u ortogonales

3.2.1. Sea F un cuerpo finito y C ≤ Fn un subespacio. Sabemos que

dimC⊥ + dimC = n.

3.2.2. Definicion. Sea C un codigo lineal con matriz de control H = H(C).El codigo 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]-codigo lineal si C es un [n, k]-codigo lineal. Aun mas,se puede probar facilmente que en la situacion de la definicion anterior, H =G(C⊥), la matriz generadora de C⊥.

3.2.3. Definicion. Un codigo lineal C se llama auto ortogonal si C ≤ C⊥ y sellama auto dual si la igualdad se verifica; es decir, C = C⊥

Claramente, para ser autodual, es condicion necesaria tener dimension n/2 ∈N.3.2.4. Ejemplos.

1. Considerese el codigoH3 en (3.1.11). Se puede probar haciendo las cuentasque el codigo extendido H3 es auto dual porque la matriz generadora esnilpotente de ındice 2 y tiene rango 4.

2. El [4, 2]-codigo ternario llamado tetracodigo tiene matriz

G =(

1 0 1 10 1 1 −1

).

Trivialmente, es autodual.

3.2.5. Teorema. Sea C un codigo lineal. Si I y R son las posiciones (ındices)de informacion y redundancia para C entonces R y I los son, respectivamente,para C⊥.

Demostracion. Si R = ∅ el caso es trivial. Supongamos que |I| = k. Sea Fla permutacion tal que F (I) = 1, . . . , k y F (R) = k + 1, . . . , n. Sabemosque existe un matriz E, producto de elementales tal que EGF = (Ik|A). Ha-cemos H = (−At|I)F−1. En este caso, puede elegirse como conjunto de infor-macion de H, I(H) = F−1 k + 1, . . . , n = R y el de redundancia R(H) =F−1 1, . . . , k = I.

3.3. Pesos y distancias

En el capıtulo anterior (2.1.5) vimos las nociones de distancia de Hammingy distancia mınima, ademas de la nocion de peso de un vector (2.1.6). En elcaso de los codigos lineales, la nocion de peso se usa de forma equivalente alde distancia de Hamming, pues es la “distancia al 0”. Vamos a ver entonces ladefinicion de peso mınimo.


3.3.1. Definicion. Para un codigo 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. Proposicion. Sea C un codigo lineal. Entonces ω(C) = d(C).

Peso mınimo y matriz de control

3.3.3. Teorema. Sea C un codigo lineal con matriz de control H. Para cadac ∈ C, las columnas de H correspondientes con las coordenadas no cero de cson linealmente dependientes.

Recıprocamente, si entre ciertas r columnas de H hay dependencia linealentonces existe c ∈ C tal que ω(c) = r y las r-coordenadas no cero de c tienenel mismo ındice que las r-columnas de H.

Demostracion. Inmediato de la definicion de matriz de control (3.1.8).

3.3.4. Corolario. Sea C un codigo lineal con matriz de control H. Entoncesω(C) = d si y solo si H tiene d-columnas linealmente dependientes, pero no tieneconjunto 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 quen − d + 1 ≥ k. Se puede probar algo mucho mas fuerte; a saber, que cualquiereleccion de al menos n − d + 1 columnas de la matriz generadora G, tiene unconjunto de informacion; o sea, tiene k-columnas linealmente independientes.3.3.5. Teorema. Sea C un [n, k, d]-codigo lineal con matriz generadora G.Entonces, todo conjunto de (n− d+ 1)-columnas de G contiene un conjunto deinformacion (o sea, k-columnas linealmente independientes).

Aun mas, d es el mayor numero con esta propiedad.

Demostracion. Consideremos cualquier eleccion de columnas de G, digamosi1, . . . , is y llamemos A a la matriz rsultante de dicha eleccion. Queremos verque, si s ≥ n − d + 1 entonces rg(A) ≥ k; o por contrapositiva, si rg(A) < kentonces s ≤ n− d.

Supongamos que rg(A) < k. Como A tiene k-filas entonces rg(A) es menorque el numero de filas de A, ası que existe r ∈ Fk tal que rA = 0. Considereseahora r · G = (r1, . . . , rn), donde al ser rA = 0, cada rij = 0, con j = 1, . . . , s.Obviamente, cG ∈ C, y ademas, ω (cG) ≤ n− s. Ası que d ≤ n− s y por tantos ≤ n− d.

Distribucion de peso o espectro de peso

3.3.6. Definicion. Sea C un codigo y sea

Ar(C) = |x ∈ C | ω(x) = r| .

A la lista A1, A2, . . . se le llama la distribucion de peso de C.


3.3.7. Ejemplo. Considerese el codigo binario con matriz generadora 1 1 0 0 0 00 1 1 0 0 01 1 1 1 1 1

.

El calculo de la distribucion de pesos se deja como ejercicio.Otro ejemplo que se puede comprobar facilmente es el calculo en un codigo

de repeticion.Vamos a ver algunas propiedades basicas.

3.3.8. Teorema. Sea C un [n, k, d]-codigo lineal sobre Fq. Entonces:

1.∑ni=0Ai(C) = qk.

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 yC⊥ tiene al (1, . . . , 1) (porque anula a todo C).

5. Si C es codigo ternario y auto ortogonal entonces el peso de cada palabraes divisible por 3.

Demostracion. Sea 1 = (1, . . . , 1). (1) y (2) son inmediatos. (3) Inmediato delhecho 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 unvector 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 subcodigo delas palabras de peso par.3.3.9. Teorema. Sea C, un [n, k]-codigo binario. Sea Ce el conjunto de todaslas palabras de peso par (en sentido llano). Entonces

1. Ce es un subcodigo lineal (subespacio) de C.

2. dimF2 (C/Ce) ≤ 1.

Demostracion. (1) Es obvio. (2) Se sigue directamente de (2.1.8)

Vamos a ver una generalizacion muy interesante de la nocion de palabra pare impar.3.3.10. Definicion. Decimos que un vector v ∈ Fnq es de tipo par (even-like)si∑ni=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. Definicion. Decimos que un codigo lineal es de tipo par si cada palabralo es. En caso contrario, decimos que es de tipo impar.


3.3.12. Observacion. Un codigo de tipo impar puede tener palabras de tipopar.3.3.13. Teorema. Sea C un [n, k, d]-codigo sobre Fq. Sea Ce el conjunto depalabras tipo par en C. Entonces Ce es subespacio de C y dimFq (C/Ce) ≤ 1.

Demostracion. La primera parte es trivial. Para la segunda parte, supongamosque existe u, v ∈ C tales que no son pares. Supongamos que u = (u1, . . . , un) yv = (v1, . . . , vn). Hacemos r =

∑vi/∑ui. Entonces

∑vi − r

∑ui = 0, ası que

v − ru ∈ Ce. De aquı es inmediato.

3.4. Codificacion y decodificacion en codigoslineales

Ya hemos comentado que para hacer la codificacion en codigos lineales usa-mos una aplicacion lineal que tiene que ser inyectiva (1.1.1); luego el espacio delas palabras de longitud k verifica Fk ∼= C. Cuando un codigo es muy grande,se aprecia con claridad la necesidad de codificar y descodificar por formula. Elproceso de codificacion es en general, mucho mas facil que el de decodificacion.La razon es que en la decodificacion hemos incluido la correccion de errores, lomas costoso.

Correccion de errores

Aunque hemos visto dos esquemas de decision en (1.2.3) ya hemos comentadoque nos centraremos en el esquema que proviene de la distancia mınima. Esimportante que tengamos claro que lo que vamos a desarrollar no es un esquemade decision (ese ya lo tenemos, el de d(C)) sino un algoritmo para la funcionparcial. Al final, comentaremos una variante para completar el dominio de lafuncion parcial y hacerla aplicacion. Comenzamos estableciendo la situacion.3.4.1. Tenemos un [n, k]-codigo C ≤ Fn, con matriz de control H y capacidadde correccion t. Hay una palabra enviada c ∈ C, un vector recibido v ∈ F y unvector “error”, que denotaremos e = v − c.

El vector error e contiene la informacion de los errores de transmision que secometieron ası como de las posiciones donde ocurrieron. Ademas, el peso ω(e)nos indica el numero de errores en la transmision. En principio, todo vectorpuede ser visto como un vector error de cualquier palabra, pero nosotros tenemospor hipotesis limitado el numero de errores que se van a cometer, luego, se puededecir que hay muchos vectores en Fn y en C, pero hay pocos vectores error masprobables; es decir, aquellos con peso menor que la capacidad de correccion.Uno por cada combinacion de errores y posiciones admisibles.

Los vectores error tienen, en vista de su definicion, su mejor representacioncomo elementos de clases de equivalencia e ∈ v + C y poseen, en ese sentido,una propiedad notable; a saber, Hv = He


3.4.2. Definicion. Sea C ≤ Fn un codigo lineal con matriz de control H.Para un vector v ∈ Fn, su sındrome es el vector Hv ∈ Fn/C (abusando de lanotacion).

¿Como se distribuyen los vectores error mas probables en las clases de equi-valencia? El siguiente resultado nos da la respuesta.3.4.3. Proposicion. Sea C ≤ Fn un codigo lineal con capacidad de correcciont y sea e ∈ Fn tal que ω(e) ≤ t. Entonces e tiene peso mınimo en e + C y esunico con la propiedad.

Demostracion. Supongamos que hay otro u = e+c distinto, i.e. c 6= 0, y verificaω(u) ≤ t. Entonces, por la desigualdad triangular y la definicion de capacidadde correccion

ω(c) = ω(u− e) ≤ ω(u) + ω(e) ≤ 2t ≤ d(C)− 1

lo cual es imposible. Luego e ∈ e+ C es unico.

Ası que ya sabemos como estan distribuidos los vectores error (mas proba-bles). Uno por clase.3.4.4. Definicion. Sea C ≤ Fn un codigo lineal. Un vector de peso mınimo enuna clase lateral v + C se llama lıder de la clase lateral.3.4.5. Observaciones.

1. Lo que nos dice la proposicion anterior es que los lıderes de peso menorque t son unicos.

2. Cuando la condicion del peso falla, los lıderes pueden no ser unicos.

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 00000, 11011, 10110, 01101 0000010000 10000, 01011, 00110, 11101 1000001000 01000, 10011, 11110, 00101 0100000100 00100, 11111, 10010, 01001 0010000010 00010, 11001, 10100, 01111 0001000001 00001, 11010, 10111, 01100 00001

Lıderes de peso mayor que t

11000 11000, 00011, 01110, 10101

1100000011

11100 11100, 00111, 01010, 10001

1000101010


El siguiente teorema nos dice que, cuando un vector recibido v ∈ Fn pertene-ce a una clase de equivalencia con lıder unico, digamos e, entonces v ∈ Bt(v−e)y por tanto el esquema decidira que la palabra enviada fue v − e ∈ C.3.4.7. Teorema. Sea C ≤ Fn un codigo lineal con capacidad de correccion t yv ∈ Fn. Son equivalentes:

1. Existe c ∈ C tal que d(v, c) ≤ t.

2. Existe un unico lıder, e, tal que Hv = He y ω(e) ≤ t.

En este caso, el esquema decidira que la palabra enviada es v − e.

Demostracion. [1 ⇒ 2] Hacemos e = v − c. Entonces ω(e) ≤ t y por (3.4.3)sera unico.

[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 loslıderes y sus sındromes. Es decir, que formaremos la tabla completa de lıderes(si queremos corregir siempre)

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

0 e01 = 0 0

e11 s11

1...

...e1n1 s1n1

......

...

et1 st1

t...

...etnt stnt


Peso mayor que tPeso lıder (eij) sındrome (Heij = sij)

et+1,1 st+1,1

t+ 1...

...et+1,nt+1 st+1,nt+1

......

...

e(t+p),1 s(t+p),1

t+ p...

...e(t+p),nt+p s(t+p),nt+p

donde t+ 1 < . . . < t+ p ≤ max d, n− k

Ası que, si recibimos un vector, calculamos su sındrome y habra un lıder(unico o no) cuyo sındrome sea igual al del vector.

1. Si el numero de errores no excediere la capacidad de correccion, el lıdercorrespondiente sera unico (y nos indicara los errores cometidos en lasposiciones). Ademas, se decidira la palabra enviada y corregiremos ade-cuadamente.

2. Si el numero de errores excediere la capacidad de correccion entonces,cuando los errores coincidan con un lıder, corregiremos (correctamente);si no, habremos cometido un error en la decision.

3. Uno puede optar por hacer la tabla mas pequena y, de ocurrir que nose encuentre lıder para un vector avisar la deteccion de un error. Si laprobabilidad de error es muy baja, incluso es conveniente.

3.4.9. Ejemplos.1. Continuamos con el ejemplo en (3.4.6).


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

0 0000 000

10000 11001000 101

1 00100 10000010 01000001 011

2 11000∗ 01110001∗ 111

(*) no unicos.

2. Sea C = 0000, 1110 binario. En este caso, hay 1 lıder de peso 0, 4 depeso 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ı quehay lıderes unicos de peso mayor que la capacidad de correccion, de hechotiene peso igual a la distancia mınima.

3.5. Construcciones con codigos lineales

Codigos pinchados

Ya hemos visto algunos resultados generales en (2.3.2). En el caso de los codi-gos lineales podemos mejorarlo. Vamos al caso cuando d = 1. La demostraciones trivial.3.5.1. Corolario. Sea C un [n, k, 1]-codigo sobre Fq y sea C?i el codigo pin-chado en la i-esima coordenada. Si C?i 6= 0 entonces es un [n−1, k?, d?]-codigo,donde,

1. k? = k si (0, . . . , 1i, 0 . . . , 0) 6∈ C.

2. Si k > 1, y no se cumple el apartado anterior sera un [n−1, k−1, 1]-codigo.

3.5.2. Sea C un codigo lineal sobre F. Sea C? el codigo pinchado en la ultimacoordenada y luego extendido (por definicion, tambien en la ultima). EntoncesC = C? si y solo si C es de tipo par.

Codigos extendidos

Tambien hemos visto ya los resultados generales en (2.3.7 y 2.3.8). Es muyfacil comprobar cualquiera de los siguientes hechos.


3.5.3. Observacion.

1. Extendido de lineal es lineal. Aun mas, si C es lineal y tiene parametros[n, k, d] entonces C tiene parametros

[n+ 1, k, d

], donde d = d, d+ 1.

2. Sean G,H las matrices generadora y de control de un codigo C. La exten-sion, siempre se puede interpretar

Fk ·G−−−→ Fn ·E−−−→ Fn+1

con

E =

In×n

−1...−1

y G = (gij)k×n .

Entonces

GE = G =

G

−∑j g1j

...−∑j gnj

.

Ahora, H ha de cumplir que H · Gt = 0, ası que H puede ser

H =

1 · · · 1 1

H

0...0

.

Esta es una construccion tıpica que llamaremos la matriz de control anadi-do

Vamos a mejorar el resultado que vimos en (2.3.8) en el caso de los codigoslineales.3.5.4. Proposicion. Sea C un codigo lineal, Ce y C0, las palabras tipo pary tipo impar, respectivamente (vease 3.3.10), y de = d (Ce) y d0 = d (C0),definidos de forma obvia. Entonces

d =

de si de ≤ d0

d0 + 1 otro caso

Demostracion. Inmediata. Notese que d(C) = mın de, d0

3.5.5. Ejemplo. Para ilustrar, podemos extender el codigo H32, con matriz

G =(

1 0 1 10 1 1 −1

)y H =

(−1 −1 1 0−1 1 0 1

)y calcular los parametros.


La construccion de Plotkin

Recordemos la definicion de la construccion de Plotkin en (2.3.10). Es inme-diato comprobar que cuando C1 y C2 son codigos lineales tambien C1 ⊕ C2 eslineal. Aun mas.3.5.6. Corolario. En la situacion de (2.3.10), si C1 y C2 tienen matrices gene-radoras y de control, respectivamente, G1, G2 y H1, H2, entonces C1 ⊕C2 tienematriz generadora y de control(

G1 G1

0 G2

)y(H1 0−H2 H2

)respectivamente.

Capıtulo 4

El problema principal de lateorıa de codigos. Cotas alos parametros

4.1. Generalidades

Sea C un (n,M, d)-codigo. Para ser un buen codigo debe:

Tener palabras, lo mas corto posible. Luego n debe de ser pequeno.

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 problemaprincipal de la teorıa de codigos.

Abordar el problema consiste en en optimizar uno de los parametros. Una delas versiones mas populares consiste en “encontrar el codigo con M mas grande(y los otros parametros fijos)”.4.1.1. Notacion. Denotamos con Aq(n, d) el mas grande valor de M , tal queexiste un (n,M, d)-codigo q-ario.

Empezamos con los casos triviales.4.1.2. Proposicion. Sea q = pi, con p primo.

1. Aq(n, 1) = qn.

2. Aq(n, n) = q.

Demostracion. (1) Si u 6= v ∈ Fnq entonces d(u, v) ≥ 1. De aquı se tiene deinmediato que Fnq es un (n, qn, 1)-codigo.

(2) Supongamos que C es un (n,M, n)-codigo q-ario. Si u, v ∈ C son distintosentonces d(u, v) ≥ n, pero C ⊂ Fnq . Ası que todas las coordenadas han de ser

36

CAPITULO 4. COTAS A LOS PARAMETROS 37

distintas; en particular, la primera. Luego M ≤ q. Por otra parte, el codigoq-ario de repeticion alcanza la cota.

4.1.3. Ejemplo. Vamos a determinar el valor de A2(5, 3). El codigo C3 de(2.1.15) es un (5, 4, 3)-codigo binario. Luego A2(5, 3) ≥ 4. Podemos ensayar alo bestia con todos los subconjuntos de 5 elementos de F5

2 a ver si la distanciamınima de alguno es 3. El problema es que son unos 200 000 conjuntos. Vamosentonces a trabajarlo con clases de equivalencia.

Supongamos que C tiene M ≥ 4 y que 00000 ∈ C. Claramente, solo puedehaber una palabra v con 4 o 5 valores 1; ya que si hubiese dos, digamos u y ventonces d(u, v) = 2 y ya no sirve.

Como 00000 ∈ C, no hay ninguna palabra con solo uno o dos valores1; ası que al menos hay dos palabras que tienen 3 valores 1. Reordenandolas posiciones podemos suponer que las siguientes palabras viven en el codi-go 00000, 11100, 00111. Ahora, basta mirar para darse cuenta de que solopodemos agregar 11011. No hay mas posibilidades. Por tanto M ≤ 4.

Es laborioso establecer cotas y existen muchos resultados generales paraayudar en los calculos, ademas de cotas especiales.4.1.4. Teorema. Sea d ∈ N impar. Entonces existe un (n,M, d)-codigo binariosi y solo si existe un (n+ 1,M, d+ 1)-codigo binario.

Demostracion. Por hipotesis, d es impar. Supongamos tenemos un (n,M, d)-codigo y que d = d(u, v), para algunos u, v ∈ C. Como d es impar, entonces elpeso de alguna de las dos palabras es impar (vease 2.1.8). Ası que, en el codigoextendido, d+ 1 = d (u, v).

Recıprocamente, supongamos que tenemos un codigo con parametros (n +1,M, d+ 1) para un numero 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) ypinchamos el codigo en esa entrada. Como d + 1 es par, las palabras varıan almenos en dos posiciones y por tanto no se pierde ninguna palabra. Ası que nosqueda el codigo pinchado de parametros (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 ante-rior, A2(6, 4) = 4.

En el caso q-ario se tiene la siguiente relacion.4.1.7. Teorema. Para n ≥ 2, se tiene

Aq(n, d) ≤ qAq(n− 1, d).

Demostracion. Sea C un codigo tal que M = Aq(n, d). Considerese la pri-mera posicion y para cada k ∈ F definimos Dk = u ∈ C | u(1) = k. Co-mo

⋃k∈F Dk = C entonces debe ocurrir que algun |Dk| ≥ M

q . Si pincha-mos en la primera coordenada, es claro que todo Dk va a sobrevivir. LuegoAq(n− 1, d) ≥M?

1 ≥ Mq = Aq(n,d)

q


Ahora vamos a ver algunas cotas especiales.

4.2. Cota de Hamming

Esta cota viene a completar el estudio de los codigos perfectos. Lo que hemosvisto en (2.1.20 y 2.1.21) nos indica facilmente la demostracion del siguienteresultado, que se conoce como cota de Hamming o del empaquetado esferico.4.2.1. Teorema.

Aq(n, d) ≤ qn∑tj=0

(nj

)(q − 1)j

con t = bd− 12c.

Entonces, un codigo perfecto es aquel que alcanza la cota de Hamming.

4.3. Cota de Singleton y codigos MDS

Esta cota es sencilla pero muy util y da lugar a los codigos de Reed Solomon,que veremos despues, y que se usan para la reproduccion de los CD.4.3.1. Teorema. Para d ≤ n se tiene que

Aq(n, d) ≤ qn−d+1.

Demostracion. Trivialmente, Aq(n, n) = q = qn−n+1 y vamos a hacer descenso.Sea d < n.

Aq(n, d) ≤ qAq(n− 1, d) ≤ · · · ≤ qn−dAq(d, d) = qn−d(q) = qn−d+1.

4.3.2. Observacion. En particular, para un [n, k, d]-codigo lineal q-ario, k ≤n− d+ 1.4.3.3. Definicion. Un codigo que verifica la igualdad en el teorema anterior seconoce como codigo separable de distancia maxima (maximum distance separableMDS).

La primera propiedad es obvia, aunque muy importante.4.3.4. Proposicion. Los codigos MDS son cerrados para isometrıas.

Luego un (n,M, d)-codigo MDS verifica que M = Aq(n, d). Ahora veremosalgunas propiedades interesantes de los codigos MDS lineales.4.3.5. Teorema. Sea C un [n, k]-codigo 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 informacion para C.

3. C⊥ es MDS.


4. Todo conjunto de (n − k)-posiciones es un conjunto de informacion paraC⊥.

Demostracion. [1⇒ 2] Aplicando (3.3.5 y 3.1.6) se tiene de inmediato del hechode que k = n− d+ 1, por hipotesis.

[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]-codigo con matriz generadora G. EntoncesC es codigo MDS si y solo si cualesquiera k columnas de G son linealmenteindependientes.

Demostracion. Inmediata.

4.4. Otras cotas

Existen otras cotas relevantes, como la cota de Plotkin o la cota de la Pro-gramacion lineal. Las limitaciones del curso no nos permiten verlas pero vamosa enunciar los resultados.4.4.1. Teorema [Cota de Plotkin]. Sea C un (n,M, d)-codigo sobre Fq, don-de q−1

q n < d. Hacemos r = q−1q . Entonces

1. M ≤ dd−rn o b d

d−rnc.

2. Si q = 2, M ≤ 2b d2d−nc.

4.4.2. Teorema [Cota de la programacion lineal]. Las siguientes cotasocurren.

1. Cuando q ≥ 2 se tiene que

Aq(n, d) ≤ max

n∑

w=0

Bw

donde el maximo esta tomado de los Bw que satisfacen:

a) B0 = 1 y Bw = 0 para 1 ≤ w ≤ d− 1.b) Bw ≥ 0, para d ≤ w ≤ n yc)∑nw=0BwK

n,qk (w) ≥ 0 para todo 1 ≤ k ≤ n.

2. Cuando d es par y q = 2,

A2(n, d) ≤ max

n∑

w=0

Bw

donde el maximo esta 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, yc)∑nw=0BwK

n,2k (w) ≥ 0 para todo 1 ≤ k ≤ bn/2c.

Capıtulo 5

Tipos especiales de codigoslineales

5.1. Codigos de Hamming y codigos simplex

Codigos de Hamming

La construccion de los codigos de Hamming y algunas de sus propiedadesen el caso binario las hemos visto en capıtulos anteriores. Vamos a extender ladefinicion.

Sea Fq un cuerpo finito cualquiera y consideremos Frq con r ≥ 2.Llamamos codigo de Hamming y denotamos Hq,r a todo aquel codigo cuya

matriz de control se construye de la siguiente manera. La denotamos con Hq,r.

1. Consideramos todos los distintos subespacios de dimension 1 de Frq. Sa-bemos que hay exactamente qr−1

q−1 (qr son todos, qr − 1, porque el < 0 >

tiene dimension 0, y qr−1q−1 porque los multiplos se absorben).

2. Denotamos con Hq,r al codigo que proviene de una matriz del tipo

Hq,r =(

de cada distinto subespacio tomoun 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) talque dimW = 1. Sea v3 ∈ W un generador de la diagonal. Entonces v3

es combinacion lineal de los otros, pero cualesquiera dos son linealmenteindependientes, luego (3.3.4) nos dice que ω (Hq,r) = 3.

40

CAPITULO 5. TIPOS ESPECIALES DE CODIGOS LINEALES 41

Ası que Hq,r es un[qr−1q−1 ,

qr−1q−1 − r, 3

]-codigo y cualesquiera dos codigos

construidos de esta manera y con estos datos seran permutacion equivalentes.Recıprocamente si H es la matriz de control de un codigo, tal que H es de

orden r× qr−1q−1 y tal que cada dos columnas existe una tercera que es combina-

cion lineal de las dos anteriores entonces trivialmente, H tiene en sus columnasa un generador de cada uno de los distintos subespacios de dimension 1; esdecir,hemos probado que.

5.1.1. Teorema. Todo[qr−1q−1 ,

qr−1q−1 − r, 3

]-codigo lineal sobre Fq es un codigo

de Hamming.Aun mas, cualesquiera dos codigos de Hamming con los mismos parametros

son permutacion equivalentes.

Codigos simplex

Son[qr−1q−1 , r

]-codigos lineales cuyos pesos de palabras tiene propiedades no-

tables. Por ejemplo, el codigo H⊥3 solo tiene palabras de peso 4 y el tetracodigo(3.2.4), que denotamos H3,2, es autodual, y tiene todas sus palabras de peso 3.5.1.2. Definicion. Los codigos simplex son aquellos que se realizan como dua-les de los codigos de Hamming

En general,5.1.3. Teorema. Las palabras no cero de un codigo simplex sobre Fq tienetodas peso qr−1.

Demostracion. El codigo ha de tener matriz generadora Hq,r de orden r ×(qr−1q−1

)y sabemos que rg (Hq,r) = r y que H⊥q,r = 〈Hq,r〉 =

xHq,r | x ∈ Frq

.

Notese que ω (xHq,r) = n− (columnas de Hq,r, digamos y, tal que xy = 0).Sabemos que dimx⊥ = r − 1, luego tiene qr−1−1

q−1 subespacios de dimension 1 ytodos ellos estan en las columnas de Hq,r. Por tanto,

ω (xHq,r) =qr − 1q − 1

− qr−1 − 1q − 1

= qr−1.

Construccion alternativa de codigos simplex binarios

Hacemos

G2 =(

0 1 11 0 1

).

Ahora, para r ≥ 3, definimos

Gr =

0 · · · 0 1 1 · · · 1

Gr−1 0 Gr−1


Se puede comprobar por construccion, que las columnas de Gr son la expan-sion de 1, 2, . . . , 2r − 1 (en binario, claro), ası que 〈Gr〉 = Sr es H⊥r .

Ahora vamos a verificar la propiedad de los pesos. Tenemos que ver es quetodas las filas de Gr tienen peso 2r−1.

Notese que G2 tiene 22 − 1, columnas ası que, por construccion, Gr tiene2r − 1 columnas. Vamos con el argumento sobre el peso. Es claro que todaslas 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 Grun simple argumento de induccion nos muestra que cada una de sus filas tienepeso 2r−1. Vamos ahora con las combinaciones lineales. Es muy importantetomar en cuenta que no es cierto que cualquier combinacion lineal de vectoresde peso 2r−1 tiene otra vez ese peso y ademas, es obvio. La propiedad provienede la forma como esta construida la matriz. Cualquier combinacion lineal de lasegunda fila en adelante cumple obviamente la propiedad por induccion y por laconstruccion de la matriz. Ası que basta comprobar que la combinacion linealentre la primera fila y cualquier combinacion lineal de las otras tiene el pesodeseado. Pero eso es facil de comprobar.

5.2. Codigos de Golay

Los codigos de Golay fueron propuestos por M. J. E. Golay en 1949. Haybinarios y ternarios. Los binarios se denotan G24, un [24, 12, 8]-lineal y G23, un[23, 12, 7] codigo. El segundo se obtiene pinchando el primero. Los ternarios sedenotan G12 y el G11.

Codigos de Golay binarios

Se construye la matriz G24 = (I12|A12×12) donde la matriz A tiene una lacaja inferior derecha de 11× 11 y se escribe en la primera fila, en la posicion iun 1 si i es cuadrado modulo 11 y un 0 en caso contrario. Despues se hace unrecorrido (shift) en direccion (←). Ası que el bloque tiene forma cıclica.

A =

0 1 1 1 1 1 1 1 1 1 1 1

1 1 1 0 1 1 1 0 0 0 1 01 1 0 1 1 1 0 0 0 1 0 11 0 1 1 1 0 0 0 1 0 1 11 1 1 1 0 0 0 1 0 1 1 01 1 1 0 0 0 1 0 1 1 0 11 1 0 0 0 1 0 1 1 0 1 11 0 0 0 1 0 1 1 0 1 1 11 0 0 1 0 1 1 0 1 1 1 01 0 1 0 1 1 0 1 1 1 0 01 1 0 1 1 0 1 1 1 0 0 01 0 1 1 0 1 1 1 0 0 0 1


Con esta matriz G24 genera un codigo que llamaremos codigo de Golay G24.Vamos a ver algunas de sus propiedades. Una propiedad importante es queG24G

t24 = 0, porque A es binaria, simetrica y con cada fila de peso par; luego es

nilpotente. Aun mas, lo anterior implica que (A|I) tambien es matriz generadorade 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 codigo auto ortogonal y tiene matriz generadora concada fila con peso divisible por 4 entonces toda palabra tiene peso divisible por4.

Demostracion. Basta analizar la Observacion 2.1.8 (3)

Toda palabra de G24 se puede escribir de la forma v = (a|b), con a, b ∈ F122 .

Ademas, si v = (a|b) es una palabra, tambien lo sera u = (b|a). Por el lemaanterior todas las palabras de G24 tienen peso multiplo de 4. Vamos a ver quees estrictamente mayor que 4. Tomemos un v = (a|b). Podemos suponer queω(a) ≤ ω(b). Hay tres casos.

Caso 1. Si ω(a) = 0, como G24 esta en forma tıpica y v = xG24 se tieneque a = 0 implica b = 0, luego v = 0.

Caso 2. Si ω(a) = 1 entonces v es una fila de G24, que tiene peso mayor oigual a 8.

Caso 3. Si ω(a) = 2 entonces v es combinacion lineal de dos filas de G24, yuna comprobacion a lo bestia nos da ω(v) = 8.

Ahora bien, si ω(a) ≥ 3 entonces ω(b) ≥ 3, por hipotesis, y como ha de sermultiplo de 4, ya es mayor o igual a 8.

Por tanto G24 es un [24, 12, 8]-codigo binario.

El codigo G23

Por (3.5.2) sabemos que si pinchamos G24 en la ultima coordenada (de he-cho en cualquiera) y extendemos (a la que pinchamos) entonces recuperamosel codigo original. Pinchando G24 obtenemos un [23, 12, 7]-codigo lineal, que lla-maremos G23.


Codigos de Golay ternarios

El codigo de Golay ternario G12 es el [12, 6]-codigo sobre F3 con matrizG12 = (I6|A), donde

A =

0 1 1 1 1 1

1 0 1 −1 −1 11 1 0 1 −1 −11 −1 1 0 1 −11 −1 −1 1 0 11 1 −1 −1 1 0

Se puede comprobar directamente cada una de las siguientes propiedades.

5.2.2. Proposicion. Las siguientes condiciones ocurren.

1. At = A y que A2 = −I. Luego G12 es autodual.

2. G12 es un [12, 6, 6]-codigo lineal.

3. El codigo ternario G11 que obtenemos de pinchar G12 en la ultima coorde-nada es un [11, 6, 5]-codigo lineal perfecto.

4. Si pinchamos en cualquier otra coordenada no salen codigos equivalentes.

5. Si pinchamos en cualquier coordenada y luego extendemos con el dıgito deparidad recuperamos un codigo equivalente a G12.

De hecho, incluso hay equivalencia con codigos que no sean lineales. Lademostracion del siguiente resultado excede el alcance de nuestro curso. Puedeconsultarse en [5, Theorem 95]5.2.3. Teorema. Todo codigo de parametros (12, 36, 6)-es equivalente a G12, ytodo codigo de parametros (11, 36, 5)-es equivalente a G11

5.3. Codigos de Reed-Muller (binarios)

Los propusieron por separado (en trabajos independientes) I. S. Redd y D.E. Muller en 1954. Existe tambien la definicion de codigo de Reed-Muller sobrecuerpos con otra caracterıstica.

Su distancia mınima es muy pequena pero se decodifican muy facilmente.Hay muchas maneras de construirlos. Una de ellas se basa en la construccion dePlotkin (2.3.10).

Construccion

Elegimos un natural m ∈ N \ 0 y 0 ≤ r ≤ m.Para cada m, vamos a definir m+ 1-codigos que denotaremos

R(0,m), . . . ,R(m,m).


Les llamaremos codigos RM de longitud 2m. Lo haremos por induccion:Primer paso: R(0,m) es el codigo de repeticion y R(m,m) = F2m

2 , el espaciocompleto.

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 construccion (u | u+ v), (2.3.10) la matriz sera,primero,

G(0,m) =(1 1 · · · 1

)y G(m,m) = I2m

y luego,

G(r,m) =

G(r,m− 1) G(r,m− 1)

0 G(r − 1,m− 1)

Una de las grandes ventajas de los codigos RM es que sus parametros se

calculan por formula.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 dimension es

dimF2 (R(r,m)) =r∑i=0

(m

i

).

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

Demostracion. (1) Inmediata por induccion. 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, dimR(0,m) = 1 =(m0

). Ahora, notese que

dimR(m,m) = 2m =m∑i=0

(m

i

)= (1 + 1)m .

Por (3.5.6) sabemos que dimR(j,m) = dimR(j,m−1)+dimR(j−1,m−1).Usando esta igualdad, la hipotesis de induccion, que es

dimR(j,m− 1) =j∑i=o

(m− 1i

)y dimR(j − 1,m− 1) =

j−1∑i=o

(m− 1i

)


y las igualdades de los coeficientes binomiales(m− 1

0

)=(m

0

)= 1 y

(m− 1i

)+(m− 1i− 1

)=(m

i

)nos dicen que

dimR(j,m) =j∑i=o

(m

i

).

(3) Sabemos por (2.3.10) que

d (R(r,m)) = mın 2d (R(r,m− 1)) , d (R(r,m)) .

Por induccion. Sid (R(r,m− 1)) = 2m−1−r

yd (R(r − 1,m− 1)) = 2m−1−(r−1) = 2m−r

entonces2d (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.Como

(mi

)=(mm−i

)entonces

dimR(m− r − 1,m) =m−r−1∑j=0

(m

j

)=

m=(m−0)∑r+1=m−(m−r−1)

(m

j

).

Luego

dimR(r,m) + dimR(m− r − 1,m) =r∑0

(m

j

)+

m∑r+1

(m

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 hipotesis deinduccion ux = 0 = vx y por el apartado (1), v ∈ R(r,m − 1). Analogamente,uy = vy = 0 luego y ∈ R(m− r − 1,m− 1) tambien.

5.3.2. Observaciones.1. Como R(0,m) es el codigo de repeticion, R(m − 1,m) = R(0,m)⊥ es el

codigo de todos los vectores pares de F2m

2 .

2. Si m es impar, m = 2r + 1, entonces por los apartados (3) y (4), delteorema anterior se tiene que R(r,m) = R(m−1

2 ,m) es autodual con pesomınimo 2

m−12 .

Capıtulo 6

Cuerpos finitos

6.1. Suma y producto en cuerpos finitos

Damos por conocidos los conceptos de dominio euclıdeo, dominio de facto-rizacion unica, cuerpo, extension de un cuerpo y caracterıstica de un cuerpo K,que denotamos Car(K). Tambien damos por hecho que, para cualquier cuerpoF, el anillo de polinomios F[X] es un dominio euclıdeo, donde todo ideal esta ge-nerado por un polinomio (de grado mınimo), y si un elemento p ∈ F[X] tieneuna raız α ∈ F, entonces (X − α) | p.

Si un polinomio p ∈ F[X] es irreducible entonces el ideal que genera 〈p〉 ≤F[X] es maximal y por tanto, el cociente F[X]/〈p〉 es un cuerpo. Finalmente, siK/F es una extension y α ∈ K, recordemos que la correspondencia p(X) 7→ p(α)es un homomorfismo de anillos, F[X] Λα−−−→ K, que llamamos el homomorfismode evaluacion. Recordemos que a la imagen de Λα se le denota F(α) y es elsubcuerpo de K generado por F y el elemento α.

Sabemos que todo dominio finito es un cuerpo. El siguiente resultado esmenos conocido y las demostracion es demasiado larga como para reproducirlaaquı. La omitiremos porque no influye en el desarrollo del tema.6.1.1. Teorema [Wedderburn]. Todo anillo de division finito es un cuerpo.

Unas observaciones sobre la caracterıstica.6.1.2. Proposicion. Sea K un cuerpo. La correspondencia ϕ : Z → K tal que

ϕ(n) = 1+(n)· · · +1 es homomorfismo de anillos.

Demostracion. Trivial,

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

(1+

(n)· · · +1

)+

(m)· · · +

(1+

(n)· · · +1

)= ϕ(n)+

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

(1+

(m)· · · +1

)= ϕ(n)ϕ(m)

47

CAPITULO 6. CUERPOS FINITOS 48

6.1.3. Observacion. Para todo cuerpo K, Car (K) = mın n ∈ N | ϕ(n) = 0.6.1.4. Proposicion. Sea K un cuerpo finito. Entonces Car (K) es un numeroprimo.

Demostracion. Inmediato del hecho de que Z/ kerϕ → K. (Todo dominio finitoes un cuerpo.)

6.1.5. Corolario. Si F es un cuerpo tal que |F| = p, con p primo, entoncesF ∼= Zp.

Ası que podemos hablar de “el cuerpo con p elementos”.6.1.6. Notacion. Sea p un numero primo. Denotamos con Fp al cuerpo con pelementos.6.1.7. Observacion. Si F es un cuerpo de caracterıstica p entonces claramenteFp → F.6.1.8. Definicion. En la situacion anterior, a la imagen de Fp se le llama elsubcuerpo primo de F.

Mas adelante veremos que es unico.6.1.9. Definicion. Sea K/F una extension. El grado de la extension es la di-mension que tiene K como F-espacio vectorial. Se denota [K : F].6.1.10. Definicion. Una extension K/F decimos que es finita si el grado es unnumero 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).

Demostracion. Trivial; ademas, t = dimFp(F).

6.1.12. Notacion. A partir de ahora, p se reserva para un numero primo y q,para alguna potencia del primo p.6.1.13. Proposicion. Sea F un cuerpo con Car (F) = p. Entonces, para cua-lesquiera r, s ∈ F se tiene

(r + s)pt

= rpt

+ spt

.

Demostracion. Inmediato del binomio de Newton, pues(pt

i

)=

0 si i 6= 0, pt

1 otro caso.

en F.

Por la proposicion anterior, se tiene entonces que la correspondencia r 7→ rp

es un automorfismo.


6.1.14. Definicion. El automorfismo r 7→ rp de Fp se conoce como el auto-morfismo de Frobenius. Se denota σp.

Mas adelante veremos que todo automorfismo de un cuerpo finito es potenciadel automorfismo de Frobenius.6.1.15. Teorema. Para todo cuerpo F, el grupo multiplicativo F∗ = (F, ·) escıclico.

Demostracion. Suponemos que |F| = q > 3, si no, se hacen las cuentas.Sea h = q − 1 = pα1

1 · · · pαmm la descomposicion en factores primos. Recorde-mos que q − 1 = |F∗|.

Para cada 1 ≤ i ≤ m, consideremos el polinomio Xhpi − 1. Este polinomio

tiene a lo mas, hpi

-raıces en F. Como hpi< h, entonces que hay elementos en F

que no son raıces de Xhpi − 1. Sea ai uno de esos elementos.

Ahora, hacemos bi = a(h/p

αii )

i . Es claro que a(h/pαii )

i 6= 1; ademas, bpαiii = ah =

1; luego o (bi) | pαii . Por otra parte, para cualquier 0 ≤ β ≤ αi, a(h/p

(αi−βi)i )

i 6= 1,luego o (bi) = pαii . Hacemos b =

∏mi=1 bi. Finalmente, se puede comprobar de

forma directa que o(b) = h.

Curiosamente, se tiene entonces que para un cuerpo finito F, el grupo aditivoes elemental abeliano, mientras que el multiplicativo es cıclico.6.1.16. Definicion. A todo generador del grupo multiplicativo F∗ se le llamaelemento primitivo de Fq.6.1.17. Lema. Sea F un cuerpo con q = pt elementos. Entonces todo r ∈ Fverifica rq = r.

Demostracion. 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 numeros algebraicos

6.2.1. Definicion. Sea K/F una extension. Un elemento α ∈ K decimos quees 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 noconstante. Entonces existe una extension K/F donde f tiene una raız.

Demostracion. Sea g un factor irreducible de f . Entonces F[X]/〈g〉 = K esun cuerpo. Claramente, la composicion F → F[X]

ηg−−−→ K es homomorfismoinyectivo de anillos con uno, donde k 7→ kX0 7→ k + 〈g〉. Hagamos α = X + 〈g〉y notemos que la evaluacion g(α) = ηg(g) = 0, por lo que α es una raız de g yen consecuencia, de f .

6.2.3. Corolario. Si f ∈ F[X] entonces existe una extension K/F donde ftiene todas sus raıces, que son, como sabemos, salvo multiplicidad, gr(f).


Demostracion. Basta notar que se pueden ir construyendo K1 ⊂ K2 ⊂ · · · ⊂ Kn

extensiones con el teorema de Kronecker, con α1, . . . αn, las raıces construidasen dicho resultado. El proceso se detiene cuando se llega, digamos, a Kn (conn ≤ gr(f)), el primero que tiene todas las raıces. La factorizacion del polinomiopor las raıces hace el resto.

En la situacion anterior, si gr(f) = n, se tiene que Kn = F (α1, . . . , αn).6.2.4. Ejemplo. Hacemos F = Z2, f = X2+X+1. Sea α tal que α2+α+1 = 0.Entonces α3 = 1. F4 = F(α) =

a+ bα | α2 + α+ 1 = 0 ; a, b ∈ F

es una

extension de Z2 de cuatro elementos. Podemos hacer las tablas de sumar ymultiplicar.6.2.5. Definicion. Sea F un cuerpo y f ∈ F[X]. Un cuerpo de descomposicionde f sobre F es aquel generado por F y todas las raıces de f .6.2.6. Teorema. Sea K/F una extension y α ∈ K, algebraico sobre F. Entoncesexiste 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 monico.

4. mα es irreducible.

Demostracion. Se considera Iα = p ∈ F[X] | p(α) = 0. Como F[X] es unDIP, se tiene que Iα es principal. Elegimos el unico generador monico. Ese esmα(X) y se tiene Iα = 〈mα〉. Es inmediato comprobar que se cumplen las pri-meras tres condiciones. Para comprobar que es irreducible en F[X], recordemosque si mα(r) = 0, con r ∈ F, entonces mα(X)

(X−r) tambien vivirıa en Iα y tendrıagrado menor, lo cual es imposible.

6.2.7. Definicion. Sea F un cuerpo y α un elemento algebraico sobre F. Alpolinomio mα se le llama polinomio mınimo de α sobre F.

Las raıces estan agrupadas en potencias del orden del cuerpo, como estableceel siguiente resultado.6.2.8. Proposicion. Sea K/F una extension y α ∈ K una raız de f ∈ F[X]. Si|F| = q entonces αq es raız de f .

Demostracion. Inmediata del Lema 6.1.17.

6.2.9. Definicion. Sea K/F una extension. Dos elementos de K decimos queson 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 descomposicion de f en F entonces [K : F] = r.


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

ξ, ξq, . . . , ξqr−1

donde ξ es cualquier raız de f .

3. En consecuencia, cualquier raız de f es elemento primitivo del cuerpo deescision donde pertenezca.

Demostracion. Sea, pues, ξ una raız de f .1. Consideremos el isomorfismo F(ξ) ∼= F[X]/〈f〉 inducido por la evaluacion.

Es inmediato que dimF (F[X]/〈f〉) = r, ası que [F(ξ) : F] = r.2. Considero ξ, ξq, . . . , ξq

s−1con ξq

s

= ξ, el primero. Es inmediato que s ≤ r.Consideremos cualquier elemento primitivo ρ ∈ F(ξ). Entonces hay una escrituraρ =

∑aiξ

ki , con ai ∈ F y ki ≤ qs. Ahora, ρqs

=∑aiξ

ki·qs0∑aiξ

ki = ρ y portanto r ≤ s. Ası que s = r. Luego ξ, ξq, . . . , ξq

r−1son todos distintos y ademas

ξqi ∈ F(ξ).

3. Inmediato de la demostracion del apartado (1 ).

6.2.11. Corolario. En la situacion del Teorema 6.2.10, sea ξ ∈ K y mξ supolinomio mınimo sobre F. Entonces se tiene una descomposicion en K,

mξ(X) =s−1∏i=0

(X − ξq

i)

donde s es el primer natural tal que ξqs

= ξ; que, de hecho, es el grado delpolinomio mınimo.

Demostracion. Es inmediata.

El siguiente resultado establece la relacion entre grado de una extension ygrado del polinomio mınimo de cualquier elemento primitivo.6.2.12. Corolario. Sea K/F una extension de grado r y sea ξ un elementoprimitivo de K, con polinomio mınimo mξ sobre F. Entonces r = gr (mξ)

Demostracion. Inmediata de los Teoremas 6.2.6 y 6.2.10

Por ejemplo, F4 es el cuerpo de descomposicion de X2 + X + 1 = (X +α)(X + α2)

6.3. Existencia y unicidad.

En esta seccion vamos a demostrar la existencia y la unicidad de los cuerposfinitos. Lo haremos en dos partes. Primero probaremos el resultado para cuerposde escision y luego lo aplicaremos a los cuerpos finitos en general. De hecho,veremos que todo cuerpo finito es un cuerpo de descomposicion o escision. Yahemos probado su existencia. Vamos a probar la unicidad.


6.3.1. Teorema [Unicidad del cuerpo de escision]. Sea F un cuerpo y f ∈F[X]. Cualesquiera dos cuerpos de descomposicion de f sobre F son isomorfos.

Demostracion. 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 unaextension tal que posee una raız de f , digamos l ∈ L. Se considera cualquierfactor irreducible g de f tal que g(l) = 0. Por otra parte, existe αi ∈ K tal queg(αi) = 0. Entonces, los subcuerpos F(αi) y F(l) son isomorfos a F[X]/〈g〉 y elisomorfismo compuesto entre ellos es la correspondencia αi 7→ l. A partir de ahı,si hay mas raıces en L seguimos extendiendo hasta obtener K → L. De aquı elresultado es inmediato.

6.3.2. Notacion. Dado un cuerpo F y un polinomio f ∈ K[X], podemos hablarde “el cuerpo de descomposicion 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 Xq −X ∈ Fp[X] se factoriza como

Xq −X =∏r∈F

(X − r) ;

es decir, todas las raıces de Xq −X viven en F cuando Car(F) = p y |F| = q.

Demostracion. Por el Lema 6.1.17, todos los elementos de F son raıces, y comogr (Xq −X) = q, ya tenemos todas las raıces.

6.3.4. Observacion. Recordemos que si un polinomio sobre cualquier cuerpotiene raıces mutiples entonces la derivada no puede ser constante distinta decero. Veamoslo. Supongamos que r ∈ F es dicha raız. Si f = gh y f ′ = c ∈ Fentonces g′h+ gh′ = c, luego 0 = g′(r)h(r) + g(r)h′(r) = c; contradiccion.6.3.5. Teorema [Existencia y unicidad de los cuerpos finitos]. Para cual-quier 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 dedescomposicion (o escision) del polinomio Xq −X sobre Fp.

Demostracion. Existencia: Considerese el polinomio Xq −X ∈ Fp[X]. Comola derivada (Xq −X)′ = −1 entonces el polinomio no tiene raıces multiples.Ası que tiene exactamente q raıces distintas (Corolario 6.2.3).

Sea F el cuerpo de descomposicion de Xq − X en Fp y consideremos L =α ∈ F | αq − α = 0. Claramente, |L| = q y L es un subcuerpo de F (hagasela cuenta si se quiere). Ası que L es un cuerpo generado por todas las raıces deXq −X. Pero esa es la definicion de cuerpo de descomposicion; ası que L = F.

Unicidad: Inmediato del hecho de que todos los cuerpos finitos son cuerposde descomposicion, junto con la unicidad de estos (Teorema 6.3.1).

6.3.6. Observacion. Hemos probado entonces que todo cuerpo finito con q =pt elementos es el cuerpo de descomposicion de Xq −X en Fp.6.3.7. Notacion. Para q = pt, con p, primo, denotamos al cuerpo (salvo iso-morfismo) con q elementos con Fq.


6.3.8. Teorema. Sea p un numero primo; t, r numeros naturales, y Fpt y Fprcuerpos finitos. Entonces Fpt es (isomorfo a) un subcuerpo de Fpr si y solo sit|r.

Demostracion. Sea α un elemento primitivo de Fpr . Supongamos primero quet|r. Entonces, es sabido que (pt − 1)|(pr − 1) y por tanto F∗pr tiene un subgrupode 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 formaFpt . Entonces tambien se tiene que F∗pt es subgrupo de F ∗pr de donde (pt −1)|(pr − 1) y por tanto t|r.

Ası que si tenemos un extension cualquiera L/K, los resultados anterioresnos dicen que ha de ser de la forma Fqs/Fq con q = pt y s = r/t. Considero unelemento primitivo de Fqs , digamos ξ. Entonces

Fqs =

0, 1, ξ, . . . , ξqs−2.

Haciendo k = qs−1q−1 se tiene que

Fq =

0, 1, ξk, ξ2k, . . . , ξ(q−1)k−1

y ademas Fqs = Fq(ξ) = Fp(ξ). De inmediato se desprende entonces que6.3.9. Teorema. Toda extension L/K de cuerpos finitos es algebraica y simple.

Demostracion. Inmediato del hecho de que 1 + ξ + · · ·+ ξq−1 = 0.

Ası que los cuerpos fintos estan organizados en torres mas o menos ası (concontenciones “unicas”)

Fp

*

HHHHY 6

Fp2 Fp3 . . .

*6

*6

Fp4 Fp6 Fp9

. . .

6.4. Ejemplos

Comencemos con F2 = 0, 1, y consideremos el polinomio

X22−X = X4 −X = X (X + 1)

(X2 +X + 1

).

Aquı, X2 +X + 1 es el unico irreducible de grado 2. Sea α una raız de dichopolinomio. Entonces α2 + α+ 1 = 0 y con ella construimos

F4 =a+ bα | a, b ∈ F y α2 + α+ 1 = 0

=

0, 1, α, α2 | α3 = 1.


Ahora vamos a extender F2 a F24 . Consideramos la factorizacion

X24−X = X (X + 1)

(X2 +X + 1

) (X4 +X3 + 1

)·

·(X4 +X + 1

) (X4 +X3 +X2 +X + 1

)en irreducibles en F2[X].

Para construir una extension de F2, de grado 4, los polinomios de grado 1 y2 no sirven. Vamos a los de grado 4. Sea β una raız cualquiera de alguno de lospolinomios de grado 4. Las raıces seran

β, β2, β22

, β23

.Ahora tenemos dos caminos:Primero. Hacemos,

X4 +X3 + 1 = (X + β)(X + β2

) (X + β22

)(X + β23

)= X4 +

(β + β2 + β4 + β8

)X3 +

+(β3 + β5 + β6 + β9 + β10 + β12

)X2 +(

β7 + β11 + β13 + β14)X + β15

y a partir de aquı construimos F24 . Es un poco rollo; o mas 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 = 1 + β3

β5 = β + β4 = β + 1 + β3 = 1 + β + β3

β6 = β + β2 + β4 = β + β2 + 1 + β3 = 1 + β + β2 + β3

β7 = β + β2 + β3 + β4 = β + β2 + β3 + 1 + β3 = 1 + β + β2

β8 = β + β2 + β3

β9 = β2 + β3 + β4 = β2 + β3 + 1 + β3 = 1 + β2

β10 = β + β3

β11 = β2 + β4 = β2 + 1 + β3 = 1 + β2 + β3

β12 = β + β3 + β4 = β + β3 + 1 + β3 = 1 + ββ13 = β + β2

β14 = β2 + β3

β15 = β3 + β4 = 1, como debe de ser.

Como hemos visto, podemos tambien pasar a F24 , extendiendo F22 en vezde F2. Veamos.


Tenemos F22 =

0, 1, α, α2

, y q = 22 = 4. Sabemos que F24 es una extensionque se construira con un irreducible de grado 2 = [F24 : F22 ]. Esos irreduciblesseran divisores de Xq2 −X o sea,

X42−X = X (X + 1)

(X2 +X + 1

) (X4 +X3 + 1

) (X4 +X + 1

)(X4 +X3 +X2 +X + 1

)=

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

) (X2 + αX + α

)(X2 + α2X + α2

) (X2 +X + α

) (X2 +X + α2

)(X2 + αX + 1

) (X2 + α2X + 1

).

Ahora usamos cualquier irreducible de grado 2, como por ejemplo, la primera,X2 + αX + α y consideramos una raız (un sımbolo que verifica la ecuacionanterior), digamos β.

Tenemosβ2 + αβ + α = 0 y α2 + α+ 1 = 0.

De aquı sacaremos toda la tabla.Entonces F24 = a+ bβ | a, b ∈ F22 ; y las relaciones anterioresVamos a hacer tambien la tabla completa para construir todo otra vez como

potencias de β.Tenemos

0, 1, β

y ademas,β2 = α+ αββ3 = ββ2 = · · · = α2 + β

β4 =(β2)2 = · · · = α+ β

β5 = αβ6 = αββ7 = β2β5 = · · · = α2 + α2β

β8 =(β4)2 = · · · = 1 + αβ

y ası...β9 = α2 + αββ10 = α2

β11 = α2ββ12 = 1 + ββ13 = α+ α2ββ14 = 1 + α2β

6.5. El anillo Fq[X]/(Xn − 1)

El objetivo de esta seccion es describir el anillo cociente Rn = F[X]/〈Xn−1〉y la relacion con las raıces de Xn − 1. Los codigos cıclicos seran identificadoscomo ideales de Rn.6.5.1. Definicion. Sea n ∈ N, y consideremos el cuerpo Fq.


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 elprimer natural (no cero) con la propiedad.

6.5.2. Proposicion.

1. Si ξ ∈ Fq es un elemento primitivo entonces ξ es una raız (q − 1)-esimaprimitiva de 1.

2. Fq tiene una raız n-esima primitiva de 1 si y solo si n | (q − 1).

Demostracion. Inmediata del hecho de que F∗q es cıclico.

6.5.3. Definicion. Sea n ∈ N con mcd(q, n) = 1. Sea 0 ≤ s ≤ n. La claseq-ciclotomica de s modulo n es:

Cs =s, sq, . . . , sqr−1

donde r = mın t ∈ N | sqt ≡ s mod n.

Por ejemplo:Modulo Clases 2-ciclotomicas

3 0, 1, 25 0, 1, 2, 4, 37 0, 1, 2, 4, 3, 6, 59 0, 1, 2, 4, 8, 7, 5, 3, 611 0, 1, 2, 4, 8, 5, 10, 9, 7, 3, 613 0, 1, 2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 79 0, 1, 2, 4, 8, 3, 6, 9, 12, 5, 10, 7, 14, 13, 11

6.5.4. Observaciones.

1. Considerese G =qii∈Z actuando en Zn, a traves de x 7→ xqi ∈ Zn. Los

Cs son las orbitas de esta accion y por tanto forman una particion de Zn.

2. Sean n, k numeros naturales, tales que (n, q) = 1 y n | qk − 1. EntoncesF∗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

particion para Ω y cualesquiera dos elementos de un Ωi son conjugados.

Aun mas, como para todo f ∈ Fq[X] ocurre que f(ξiq)

= f(ξi)q enton-

ces tambien ocurrira que cada clase q-ciclotomica corresponda con UN SOLOpolinomio mınimo; es decir,6.5.5. Teorema. Sea ξ ∈ Fqr una raız n-esima de 1 (entonces mcd(n, q) = 1).Entonces:


1. Para cada 0 ≤ s ≤ n el polinomio mınimo de ξs en Fq se factoriza enFqr [X] como

mξs(X) =∏i∈Cs

(X − ξi

)donde Cs es la clase q-ciclotomica de s modulo n.

2. Ası que la factorizacion de Xn − 1 en Fq[X] es

Xn − 1 =∏s∈S

mξs(X)

donde S es un juego completo de representantes de las clases q-ciclotomi-cas modulo n.

Demostracion. Es consecuencia directa del Teorema 6.2.10. Veamos. Sea α = ξs

y supongamos que gr(mα) = m. Por dicho teorema, α, . . . , αqm−1

son todas lasraıces de mα y ademas, por el argumento de la demostracion, se cumple queαq

m

= α ym es el primero con la propiedad. De ahı que Cs =s, sq, . . . , sqm−1

.

Notes 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-ciclotomicas. Claramente, para cada s ∈ S,ξs es raız de Xn − 1 y por tanto

∏s∈S mξs(X) | (Xn − 1). Finalmente, como

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 sabemoso podemos probar muy facilmente:

1. Si mcd(n, q) = 1 entonces Xn − 1 no tiene raıces multiples.

2. Sea Rn = Fq[X]/(Xn − 1). Si I ≤ Rn, existe g ∈ Fq[X], monico, tal queg | (Xn − 1) e I = 〈g〉. (Este polinomio es unico.)

3. Si g · h | Xn − 1 entonces g y h son coprimos (no hay raıces multiples) ypor 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 Wed-derburn Rn es producto de cuerpos. (Esto tal vez no se conozca, pero loveremos explıcitamente.)

6.5.7. Definicion. Sea I un ideal de Rn. Al polinomio monico g | Xn − 1 dela Observacion 6.5.6.2 se le conoce como polinomio generador de I.

Vamos ahora a establecer la relacion entre los ideales del anillo Rn y lasclases q-ciclotomicas de las raıces n-esimas de la unidad. Consideremos la situa-cion de la Observacion 6.5.4, donde k puede ser elegido de tal manera que seaprecisamente el orden multiplicativo de q, modulo n.


6.5.8. Definicion. En la situacion del parrafo anterior, sea I un ideal de Rny ξ ∈ 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 numeros naturales,tales que (n, q) = 1 y k es el orden multiplicativo de q, modulo n. Sean Ci lasclases q-ciclotomicas de q, modulo n, y ξ ∈ Fqk una raız n-esima primitiva dela unidad. Entonces

1. Todo ideal I de Rn determina una unica union de clases ciclotomicasD(I) = Ci1 ∪ · · · ∪ Cir , de tal manera que

Zξ =ξj | j ∈ D(I)

2. Recıprocamente, toda reunion de clases q-ciclotomicas modulo n, D =

Ci1 ∪ · · · ∪ Cir determina un unico ideal I de Rn, dado por

I =p ∈ Rn | p(ξj) = 0, ∀ j ∈ D


6.5.10. Teorema. Sean I, J ideales de Rn con polinomios generadores g, h,respectivamente. Entonces:

1. I ≤ J si y solo si h | g.

2. Por tanto, los ideales maximales tienen generadores irreducibles y sus cerosforman una sola clase ciclotomica.

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,Xn − 1).

Demostracion. Basta hacer las cuentas.

6.5.11. Proposicion. Considerese la descomposicion Xn− 1 =∏si=1mi, don-

de los mi son los polinomios mınimos de las distintas clases q-ciclotomicas.Hacemos ui = Xn−1

mi. Entonces

1. Existen ai, bi tales que 1 = aimi + biui.

2. Rnmi = Rnaimi y Rnui = Rnbiui.

3. Rnmi es maximal y Rnui es minimal.


4. Rnui ∼= Rn/Rnmi∼= Fq[X]/(mi) ∼= Fqgr(mi) .

Demostracion. Las tres primeras son inmediatas. Para la ultima es el segundoteorema de isomorfıa; esto es, Rn/Rnmi

∼= (Fq[X]/(Xn − 1) / ((mi)/(Xn − 1)).

Sabemos que las identidades de Bezout vistas se pueden extender a massumandos, ası que6.5.12. Teorema. Considerese la descomposicion Xn−1 =

∏si=1mi, donde los

mi son los polinomios mınimos de las distintas clases q-ciclotomicas. Hacemosui = Xn−1

mi. Entonces

1. Rn = Rnu1 × · · · ×Rnus.

2. Rnui ∼= Fqgr(mi) .


Como gr(mi) = |Ci| entonces se tiene6.5.13. Corolario. Sean C1, . . . , Cs las distintas clases q-ciclotomicas modulon. Entonces

F[X]/(Xn − 1) ∼=s∏i=1

Fq|Ci| .

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 6.5.13, calculamos las clases 2-ciclotomicas modulo 7.Son C0 = 0, C1 =

1, 2, 22

, C3 =

3, 3 · 2, 3 · 22

. La estructura es:

R7 = F2[X]/(X7 − 1) ∼= F2 × F23 × F23 .

Ahora viene la parte ardua que es calcular los idempotentes de la descom-posicion.

Lo primero que necesitamos es la factorizacion de X7−1 en irreducibles. Enprincipio, el Teorema 6.5.5 nos dice como hacerlo explıcitamente. Como hay tresclases 2-ciclotomicas, modulo 7, hay tres factores irreducibles que se construyen,usando a ξ, una raız septima de 1, ası:

1. El de C0, que es X + 1.

2. El de C1 que es (X + ξ)(X + ξ2

) (X + ξ4

)= X3 +

(ξ4 + ξ2 + ξ

)X2 +(

ξ6 + ξ5 + ξ3)X + 1.

3. El de C3 que es(X + ξ3

) (X + ξ6

) (X + ξ5

)= X3 +

(ξ3 + ξ5 + ξ6

)X2 +(

ξ + ξ2 + ξ4)X + 1.


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 metodo fijo; ası que descomponer polinomios siguesiendo igual de difıcil que, por ejemplo, en la caracterıstica 0.

Hay programas y tablas para calcular descomposiciones. Uno termina siem-pre echando mano de ellas.

Ası que, expresamos como producto de irreducibles X7 − 1 = (X + 1)(X3 +X2 + 1)(X3 +X + 1). Entonces

m1 = X + 1 u1 = X6 + · · ·+X2 +X + 1m2 = X3 +X2 + 1 u2 = X4 +X3 +X2 + 1m3 = X3 +X + 1 u3 = X4 +X2 +X + 1

De aquı, todavıa faltara hacer las identidades de Bezout para obtener losidempotentes.

6.6. Automorfismos

6.6.1. Definicion. El grupo de Galois, como siempre, es Gal (F) el grupo delos automorfismos junto con la composicion.

Si Fqs/Fq es una extension, denotamos con Gal (Fqs/Fq) los automorfismosde Gal (Fqs) que dejan fijo a Fq.

Por la Definicion 6.1.14 se tiene6.6.2. Observacion. Un automorfismo de Frobenius es un elemento

σp ∈ Gal (Fpr ) .

Notese que σpr = σp (r). . . σp tiene sentido.Vamos a describir a Gal (Fq).Notese que Gal (Fq) = Gal (Fq/Fp).

6.6.3. Teorema. Sea p un numero primo y r ∈ N. Entonces, Gal (Fpr ) = 〈σp〉.En consecuencia, es un grupo cıclico de orden r.

Demostracion. Hacemos q = p y consideramos ξ ∈ Fqr un elemento primitivoy mξ su polinomio mınimo en Fq. Sabemos que para cada σ ∈ Gal (Fq), σ(ξ)es raız de mξ y que esas raıces son ξ, ξq, . . . , ξq

r−1, ası que no hay mas que

r-distintos automorfismos de 〈σp〉 = Gal (Fqr ).

6.6.4. Corolario. Sea q = pt y 0 ≤ n ≤ t. Entonces x ∈ Fq | σpn(x) = x =Fpmcd(n,t) .

Demostracion. Inmediato del hecho de que x ∈ Fq | σpn(x) = x es un sub-cuerpo.

Capıtulo 7

Codigos cıclicos


7.1.1. Definicion. Un [n, k]-codigo lineal C sobre Fq se llama codigo cıclicosi 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 repeticion.

3. El (0000) , (1010) , (0101) , (1111), de dimension 2.

4. El 〈(1100) , (0110) , (0011)〉 en F42.

5. Sea P la matriz de permutacion cıclica; es decir,

P =(

0 I1 0

)y X ⊆ Fnq un subconjunto arbitrario. Entonces

⟨XP i | i ∈ N

⟩sera un

codigo cıclico.

6. Un codigo que NO es cıclico, (0000) , (1100) , (0011) , (1111). Notese quees cerrado para mover de dos en dos; de hecho, es permutacion equivalentea un cıclico.

7.1.3. Proposicion. Un codigo lineal C ≤ Fnq es cıclico si y solo si el ortogonal,C⊥ es codigo lineal cıclico.

Demostracion. Sea P la matriz de permutacion cıclica. Entonces y ∈ C⊥ ⇔y ·(xP i

)t = 0 para todo x ∈ C y para todo i ∈ N.Por la definicion, la matriz de permutacion es ortogonal; es decir, PP t = I.

Como Pn = I entonces (P i)t = Pn−i. Ası, 0 =(yP i

)xt = y ·

(xPn−i

)t = 0.

61

CAPITULO 7. CODIGOS CICLICOS 62

7.2. Codigos cıclicos y anillos de polinomios

Seguimos suponiendo que mcd(n, p) = 1. Considerese Fnq con la base canoni-ca En y Rn = Fnq /(Xn − 1), como hemos estudiado, con su base canonicaXn =

1, X,X2, . . . , Xn−1

(abusando de notacion, porque deberıan de tener

barras).Sea φ : En → Xn tal que φ(ei) = Xi−1, i = 1, . . . , n. Esta correspondencia

induce un isomorfismoΨ : Fnq −→ Rn

que dejaremos en notacion fija.7.2.1. Proposicion. En la situacion anterior (con Ψ fija), sea C ≤ Fnq uncodigo lineal. C es cıclico si y solo si Ψ(C) es ideal en Rn.

Demostracion. Inmediato del siguiente diagrama conmutativo.

Fnq Rn

Fnq Rn

? ?

-

-

·P x· o ·x

Ψ

Ψ−1

Ψ

Ψ−1

Como ejemplos de codigos cıclicos tenemos los ideales obtenidos en el Ejem-plo 6.5.15.

Como hemos comentado, la definicion de codigo cıclico nos impide ver alcodigo

D = (0000) , (1100) , (0011) , (1111)

como cıclico, a pesar de que sabemos que le operador que mueve dos veces lascoordenadas los deja invariante.

Si consideramos ϕ : F4q → R4 con ϕ (e1) = 1, ϕ (e2) = X2, ϕ (e3) =

X, ϕ (e4) = X3 se puede comprobar facilmente que ϕ(D) es ideal en Rn.Aun mas, los unicos isomorfismos entre Fnq y Rn que pueden interesar han

de preservar pesos, luego han de ser biyecciones entre las bases canonicas. Dehecho, dos isomorfismos que preservan pesos restringen a una permutacion delas bases canonicas.7.2.2. Proposicion. Un codigo C ≤ Fnq lineal es equivalente a un codigo cıclicosi y solo si existe un isomorfismo entre Fnq y Rn que restringe a una biyeccionde las bases canonicas y C se corresponde con un ideal.



A partir de ahora, cuando digamos C es un codigo cıclico, entenderemosC ≤ Rn = Fnq , abusando de la notacion.7.2.3. Observacion. Repasemos lo que acabamos de ver sobre los ideales enRn. Fijamos una raız n-esima primitiva de la unidad, digamos ξ, y consideramoslas clases q-ciclotomicas modulo n, Ci1 , . . . , Cis , con S = i1, . . . , is un juegocompleto de representantes. Sean, como siempre, mj = mξij

(X) los polinomios

mınimos y uj = Xn−1mj

. Sabemos por el Teorema 6.5.12 que losRnuj son todos losideales minimales y que cada Rnuj ∼= F

qgr(mj)= F

q|Cj |. Por tanto, dimF Rnuj =

gr(mj) = |Cj |.Sea ahora I ≤ Rn un codigo cıclico. Por la Observacion 6.5.6, existe un

polinomio generador (monico) g ∈ F[X] tal que I = 〈g〉 y g | Xn − 1; poreso abusamos de la notacion y escribimos g en vez de g. Si h = Xn−1

g entncesexisten S1 y S2, una particion de S tal que (Teorema 6.5.5) g =

∏j∈S1 mj y

h =∏k∈S2 mk; ademas,

Rng =∏k∈S2

Rnuk ∼=∏k∈S2

Fqgr(mk) ∼=∏k∈S2

Fq|Ck| .

De aquı, dimF Rng = n− gr(g) =∑k∈S2 |Ck|.

7.2.4. Proposicion. Sea C un codigo cıclico en Rn con polinomio generadorg(X) =

∑n−ki=0 giX

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 continuacion es generadora de C,

G =

g0 g1 · · · gn−k 0 · · · 00 g0 · · · gn−k · · ·

. . . . . .0 g0 · · · gn−k

k×n

Demostracion. 1. Acabamos de verlo en la Observacion 7.2.3.2. Es inmediato por el hecho de tener todos grados distintos. Si

∑k−1i=0 riX

ig(X) =0 entonces rk−1gn−kX

n−1 = 0, luego rk−1 = 0. Repitiendo el argumento se tiener0 = · · · = 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. Definicion. Sea C un codigo cıclico en Rn con polinomio generadorg(X). Llamaremos polinomio de control de C a

h(X) =Xn − 1g(X)

es decir, gh = Xn − 1 en Fq[X].


Usando h podemos dar una matriz de control muy facil.7.2.6. Teorema. Sea C ≤ Rn codigo cıclico y h =

∑ki=0 hiX

i su polinomio decontrol. Entonces la siguiente matriz es matriz de control para C,

H =

hk hk−1 · · · h0 0 · · · 00 hk · · · h0 · · ·

. . . . . .0 hk · · · h0

n−k×n

;

es decir,

H = (aij)n−k×n | aij =

0 si j − i < 0hk−(j−i) si 0 ≤ j − i ≤ k0 si k < j − i

Demostracion. Sea c = c(X) un elemento de C. Entonces c = gp, donde g es elgenerador, y g un polinomio en Rn con grado estrictamente menor que k, puesla suma de sus grados no puede pasar de n y g tiene grado n−k (esto siempre sepuede conseguir con un representante adecuado, ya que si gp tiene grado mayorque n, hacemos gp = u(Xn − 1) + r, pero g | (Xn − 1), luego g | r y por tantogp = g rg = g rg y tiene grado menor o igual a n). Entonces hc = hgp = (Xn−1)p.Veamos que el polinomio (Xn − 1) q tiene todos los coeficientes de los terminosde grado k, . . . , n−1 cero. Supongamos que p =

∑k′

i=0 piXi, con k′ < k. Entonces

(Xn−1)p = −p+Xnp = −∑k′

i=0 piXi+∑k′

i=0 piXn+i, o sea, que Xk, . . . , Xn−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

H

p0

...pn−1

= 0

por tanto H es matriz de control.

Observese entonces que C⊥ no necesariamente esta generado por h.7.2.7. Definicion. Para un polinomio f(X) =

∑mi=0 aiX

i, se define

f?(X) = Xmf(X−1

)= Xm ·

m∑i=0

aiX−i =

m∑i=0

aiXm−i

7.2.8. Ejercicio. Probar que en la situacion de la definicion anterior

1. Si f | g entonces g? | f?.

2. Si g | Xn − 1 entonces g? | Xn − 1.


Efectivamente. 1. Basta ver que fg = h implica que f?g? = h. Hacemos los dosf =

∑mi=0 fiX

i y f =∑mi=0 giX

i donde los coeficientes de alguno de ellos pueden

ser 0. Entonces h =∑2mk=0

(∑i+j=k figi

)Xk. Finalmente, se puede comprobar

que f?g? =∑2mk=0

(∑i+j=k figi

)X2m−k = h?.

2. Inmediato del hecho de que (Xn − 1)? = 1−Xn.

7.2.9. Corolario. Sea C un codigo con polinomio de control h =∑hiX

i.Entonces C⊥ tiene polinomio generador h⊥ = 1

h(0)h?.

7.3. Ceros de un codigo cıclico y matrizde control

Sea C un codigo cıclico de orden n sobre Fq, con mcd(n, q) = 1, sea ξ unaraız n-esima primitiva de 1, y sea S un juego completo de representantes de lasclases q-ciclotomicas modulo n. Sea g(X) el generador de C (Observacion 6.5.6).Como sabemos del Teorema 6.5.5 si g(X) | Xn − 1 entonces

g =∏

t∈T ⊆S

mξt .

7.3.1. Definicion. En la situacion 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 = Xn−1g , es decir el conjunto

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

7.3.2. Observacion. Sea C un codigo cıclico. Entonces los ceros de C⊥ sonprecisamente los inversos de los no ceros de C. La razon es la siguiente. Esinmediato comprobar que si ζ es raız de un polinomio f(X) entonces ζ−1 es raızde f∗(X); basta ver la definicion (Definicion 7.2.7).

Usando los ceros de un codigo cıclico podemos construir una matriz de con-trol.

Consideramos a C ≤ Rn sobre Fq, con mcd(n, q) = 1, con polinomio gene-rador g y sea, usando la notacion de la definicion anterior, T = t1, . . . , td.

Vamos a formar la matriz

L =

1 ξt1 ξ2t1 . . . ξ(n−1)t1

...1 ξtd ξ2td . . . ξ(n−1)td

|T |×n

(7.3.1)


Es muy claro que si c ∈ C, visto como coordenadas, Lct = 0, y viceversa.Notese 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 escision de g sobre Fq. Ahora, expresamos

cada ξtj como coordenadas de Fqr visto como espacio vectorial sobre Fq; esdecir, denotamos ξtj las coordenadas de ξtj . Ahora formamos

L =

1 ξt1 ξ2t1 . . . ξ(n−1)t1

...1 ξtd ξ2td . . . ξ(n−1)td

|T |·r×n

(7.3.2)

Vamos a ver que es matriz de control. Primero tenemos que fijar una base.Sea u1, . . . , ur una base para Fqr . supongamos que ξmti =

∑rj=1 ajiuj . Como

Lct = 0 entonces

0 =n−1∑i=0

r∑j=1

ajiuj

ci =r∑j=1

uj

(n−1∑i=0

ajici

)

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

7.4. Codificacion y decodificacion en codigoscıclicos

Como hipotesis general, supongamos que tenemos un codigo cıclico C ≤Rn tal que C = 〈g〉, con g el polinomio generador, con gr(g) = r, ası que ladimension dimC = n− r.

Comenzamos con la codificacion. Vamos a ver una decodificacion sistematica.Supongamos que queremos codificar la palabra a0 · · · an−r−1.

1. Hacemos a(X) =∑n−r−1i=0 aiX

n−i−1

2. Luego operamos a = tg + s, con gr(s) < r (notese 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+ sy ası, c = gt + (s − e), con gr(s − e) < r. Pero c = gt′, para alguna t′,puesto que c ∈ C = 〈g〉 y la unicidad del algoritmo de la division nos diceque s = e; luego v − s es la palabra buscada.


Esta decodificacion es en realidad una decodificacion por sındrome. Vamos acomprobar que existe una matriz de control cuyos sındromes son precisamentelos restos obtenidos.

Considerese para i = 0, . . . , n − 1, la expresion Xr+i = gsi + ti, obtenidoscon el algoritmo de la division. Se puede comprobar facilmente que los Xr+i −ti = gsi son una base para C. Por los grados de los terminos lıderes tenemosindependencia lineal, y por el numero de elementos tenemos que es base.

Ahora, escribimos una matriz generadora. Si ti =∑r−1j=0 ti,jX

j

G =

−t0,0 · · · −t0,r−1 1 0 . . . 0−t1,0 · · · −t1,r−1 0 1 . . . 0

...−tn−r−1,0 · · · −tn−r−1,r−1 0 0 . . . 1

= (−T | I)

Entonces la matriz de control es H = (I | T t). Uno puede comprobar con uncalculo directo que para un polinomio recibido u =

∑rj=0X

j+∑n−r−1i=0 ur+iX

r+i,se tiene que H(u0, . . . , un−1)t son justo los coeficientes del resto de la divisionu = gs+ t.

Capıtulo 8

Codigos clasicos que serealizan como codigoscıclicos

8.1. Codigos de Hamming (de nuevo)

Recordemos la definicion de codigo de Hamming.Hq,r tiene matriz de control

Hq,r =(

de cada matriz de dimension 1 de Fqrtomo un vector y lo pongo

)y sabemos que hay exactamente qr−1

q−1 .8.1.1. Observacion. Sea H una matriz tal que

H =(H1 · · ·H qr−1

q−1

)[r× qr−1

q−1 ].

Si las columnas son linealmente independientes 2 a 2 entonces H es la matrizde control de un codigo de Hamming, un

[qr−1q−1 ,

qr−1q−1 − r, 3

]-codigo.

8.1.2. Teorema. Todo codigo de Hamming es cıclico

Demostracion. Hacemos n = qr−1q−1 . Vamos a ver primero que Fqr es el cuerpo

de escision de Xn − 1 sobre Fq. Notese primero que n(q − 1) = qr − 1 y n =1 + · · · + qr−1, de donde n > qr−1 − 1. Ahora considerese una raız de Xn − 1,digamos γ. Entonces γn = 1, luego γn(q−1) = 1, ası que γq

r

= γ, de donde Fqrcontiene al cuerpo de escision, pero n > qr−1−1 ası que debe ser justo el cuerpode escision.

Ahora, sea ξ una raız n-esima primitiva de la unidad y considerese la matriz

L =(1 ξ · · · ξ(n−1)

)68

CAPITULO 8. CODIGOS CLASICOS 69

y expresemos esos elementos como se hizo en la Seccion 7.3 de los ceros, viendoFqr como Fq espacio vectorial,

H =(

1 ξ · · · ξ(n−1)

)Notese que Frq tiene exactamente n-subespacios de dimension 1 y como ese

es precisamente el numero de columnas de H, basta ver que cualesquiera doscolumnas son l.i. para saber que H es matriz de codigo de Hamming.

Supongamos que aξi = ξj , con 0 ≤ i, j < n. Entonces aξ(i−j) = 1, ası que(aξ(i−j))(q−1)

= 1. Pero a ∈ Fq, luego aq−1 = 1, ası que ξ(i−j)(q−1) = 1, dedonde n | (i− j)(q − 1); pero mcd(n, q − 1) = 1, luego i = j.

8.2. Codigos BCH

El nombre viene de Bose, Ray-Chandhuri y Hocquengheim. En estos codigoscıclicos, se busca que tenga una longitud y distancia designada.8.2.1. Definicion. Sea Fqr el cuerpo de escision de Xn − 1 que contiene a Fqy sea ξ ∈ Fqr una raız n-esima primitiva de la unidad. Sean 2 ≤ δ ≤ n y b ≥ 0.Cambiando r, por ξ ∈ Fqr , tenemos cinco parametros, (q, n, δ, ξ, b).

Llamamos codigo BCH de longitud n y distancia designada δ sobre Fq ylo denotamos Bq(n, δ, ξ, b) (el parametro q sale del parentesis) al codigo cıclicogenerado por

g(X) = mcm(mξb(X), mξb+1(X), . . . ,mξb+δ−2(X)

)1. En el caso b = 1, el codigo se llama BCH en sentido restringido (narrow

sense) y se omite el ultimo parametro, es decir, se escribe Bq(n, δ, ξ)

2. Si ξ es un elemento primitivo de Fqr , diremos entonces que el codigo esBCH primitivo. Notese que esto ocurre si y solo si n = qr − 1.

Trivialmente, todo codigo de Hamming es BCH (primitivo y restringido),con parametros b = 1, δ = 2, d ≥ 2.8.2.2. Proposicion. El codigo Bq (n, δ, ξ, b) es el codigo cıclico de mayor di-mension que contiene entre sus ceros al conjunto

ξb, ξb+1, . . . , ξb+δ−2

. De

hecho, el conjunto de sus ceros esta formado por los anteriores elementos y susconjugados.

Demostracion. Es muy facil. Sea g(X) como en la definicion de codigo 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 tantoBq (n, δ, ξ, b) tiene dimension maxima.

8.2.3. Observacion. En un codigo BCH restringido (b = 1), C generado porg, 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.


Ademas, el codigo generado por (1 −X)g es el subcodigo cıclico de las pa-labras de tipo par de C, que obviamente, ta,bien es un codigo BCH, de hecho,es Bq(n, δ + 1, ξ, 0).

El siguiente resultado es un verdadero clasico de los codigos.8.2.4. Teorema [Cota BCH]. Sea C un [n, k, d]-codigo cıclico sobre Fq y seaξ una raız n-esima primitiva de la unidad en el cuerpo de escision de Xn − 1sobre Fq. Si existen b ≥ 0 y δ ≥ 1 tal que

ξi | b ≤ i ≤ b+ δ − 2

son ceros de

C, entonces d ≥ δ.

Demostracion. Sea Z =ξi | b ≤ i ≤ b+ δ − 2

un subconjunto de los ceros

del codigo, digamosξij | j = 0, . . . , k

. Si M es la matriz formada por los

ceros (en la extension de Fq y p = (p0, . . . , pn−1) es un vector de corficientes deun polinomio en el codigo, se tiene que Mp = 0; es decir

(ξi0)0 (ξi0) . . . (ξi0)n−1

...(ξb)0 (ξb) . . . (ξb)n−1

...(ξb+δ−2)0 (ξb+δ−2) . . . (ξb+δ−2)n−1

...(ξik)0 (ξik) . . . (ξik)n−1

p0

p1

...pn−1

=

0

...

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 delas filas correspondientes a las entradas que comienzan con ξb, . . . , ξb+δ−2 y coneso formamos la matriz D.

D =

(ξb)c1 . . . (ξb)cd...

(ξb+δ−2)c1 . . . (ξb+δ−2)cd

Si p′ es el vector proyeccion de p en los ındices de las columnas elegidas,

podemos ejecutar el producto y obtenemos Dp′ = 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 ∆p′ = 0 implica p′ = 0, lo cual es imposible.

8.2.5. Corolario. d (Bq (n, δ, ξ, b)) ≥ δ, siempre.8.2.6. Teorema. Sea C = Bq (n, δ, ξ, b) un codigo BCH, donde On(q) = r; esdecir, n | qr − 1 y r, el primero. Entonces dimFq C ≥ n− r(δ − 1).


Demostracion. Inmediato de la definicion de codigo BCH y de (6.5.12 y 6.5.13).

8.2.7. Ejemplo. Consideremos los codigos BCH binarios y restringidos de or-den 31; es decir, B2(31, δ, ξ). Puede recorrer 2 ≤ δ ≤ 29.

Para determinar los codigos primero consideramos las clases 2-ciclotomicasmodulo 31. Estas son:

C0 = 0C1 = 1, 2, 4, 8, 16C3 = 3, 6, 12, 24, 17C5 = 5, 10, 20, 9, 18C7 = 7, 14, 28, 25, 19C11 = 11, 22, 13, 26, 21C15 = 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 estalista se hacen las dos siguientes cosas.

3. Se determina g(X).

4. Se establecen las clases q-ciclotomicas involucradas. En este caso son C1,C3, C5 y C7

5. Se establece la dimension que es n −∑|Ci| involucrados. En este caso,

31− 20 = 11.

6. El ultimo calculo de la tabla siguiente es “hecho a mano”.

Tomando ξ una raız 31-esima primitiva de la unidad se tiene

δ g(X) Ci involucradas dimF2 C ω(C)1 mξ0 C0 31 13 mξ C1 26 35 mξmξ3 C1, C3 21 57 mξmξ3mξ5 C1, C3, C5 16 79 y 11 mξmξ3mξ5mξ7 C1, C3, C5, C7 11 1113 y 15 mξmξ3mξ5mξ7mξ9 C1, C3, C5, C7, C9 6 1517, . . . , 31 X31 − 1 C1, . . . , C15 1 31

Como se puede apreciar, un codigo BCH puede interpretarse con distintosparametros; de ahı la siguiente definicion.8.2.8. Definicion. Sea C = Bq (n, δ, ξ, b) un codigo BCH. Se llama distanciade base de C al mayor δ tal que C = Bq (n, δ, ξ, b).


8.3. Codigos de Reed-Solomon

Son un caso particular de codigos BCH; de hecho, son un caso particular decodigos BCH primitivos.8.3.1. Definicion. Un codigo de Reed-Solomon es un BCH sobre Fq, donden = q − 1.8.3.2. Observaciones.

1. Como n = q − 1 entonces Fq es cuerpo de escision para Xn − 1; ası quesolo hay factores lineales o, dicho en terminos de clases q-ciclotomicas, todas lasclases q ciclotomicas tienen orden 1.

2. Por lo anterior, si g es el polinomio generador entonces g =∏b+δ−2i=b (X−ξi)

y por tantodimC = n+ 1− δ.

3. Si C es un RS-codigo entonces C⊥ tambien lo es. Esto se desprende delhecho de que las clases ciclotomicas solo tienen un elemento y no hay con-jugados mas que uno mismo. Esto significa que si los ceros de C contienen aξb, ξb+1, . . . , ξ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), modulo n. Se invierte la lista y punto.4. Hemos visto que dimC = n + 1 − δ, luego δ = n + 1 − dimC; ası que

d(C) ≥ δ = n+1−dimC, pero la cota de Singleton nos dice que d ≤ n+1−dimC,de donde se tiene la igualdad y por tanto es un codigo MDS.

Bibliografıa

[1] J. Adamek, Foundations of Coding, Wiley, Chichester, 1991.

[2] H. Fripertinger. Enumeration of the semilinear isometry classes of linearcodes, en A. Kerber y A. Kohnert, ed., ALCOMA’05, Proceedings of theConference on Algebraic Combinatorics and Applications, Designs andCodes, Thurnau, Germany, 2005. Bayreuth. Math. Schr., vol. 74, p. 100-122, 2005.

[3] W.C. Huffman y V. Pless, Fundamentals of Error Correcting Codes, Cam-bridge, 2003.

[4] C. Munuera y J. Tena, Codificacion de la Informacion, Universidad deValladolid, 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. Rifa y Ll. Huguet, Comunicacion Digital, Masson, 1991.

[8] Derek J. S. Robinson, A Course in the Theory of Groups, Springer, NuevaYork, 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

grado en matem aticas. curso 2013-2014 c odigos ... · cap itulo 1. informacion y c odigos 4...

Documents