3Des

´
´
INTRODUCCION A LA TEOR´ DE CODIGOS
IA
AUTOCORRECTORES
´
RICARDO A. PODESTA
Resumen. En estas notas se presenta una introducci´n a la teor´ de los c´digos autocorrectores
o
ıa
o
a trav´s del estudio de una clase particular muy importante es ´stos, los llamados c´digos
e
e
o
lineales. Se introducen algunos conceptos y resultados b´sicos de la teor´ y se estudian en
a
ıa
mayordetalle algunas familias famosas de tales c´digos.
o

´
Indice
Introducci´n
o
1. Generalidades sobre C´digos
o
1.1. Definiciones b´sicas
a
1.2. Distancia de Hamming y peso
1.3. C´digos lineales
o
1.4. Canales y decodificaci´n
o
1.5. Equivalencia de c´digos
o
1.6. Esferas y c´digos perfectos
o
1.7. Detecci´n y correcci´n de errores
o
o
1.8. Construcciones
2. C´digos Linealeso
2.1. Matriz generadora
2.2. C´digo dual y matriz de control de paridad
o
2.3. Distancia de un c´digo lineal y algunas cotas
o
2.4. Decodificaci´n por s´
o
ındrome
2.5. Enumeradores de peso y la identidad de MacWilliams
3. Algunos C´digos Lineales Famosos
o
3.1. C´digos de Hamming
o
3.2. C´digos de Golay
o
3.3. C´digos de Reed-Muller
o
4. C´digos C´
o
ıclicos
4.1. Polinomiogenerador
4.2. Polinomio de chequeo
4.3. Codificaci´n y decodificaci´n de c´digos c´
o
o
o
ıclicos
4.4. Ceros de polinomios y c´digos c´
o
ıclicos famosos
Ap´ndice A: Status Tecnol´gico de C´digos
e
o
o
Ap´ndice B: El c´digo ISBN
e
o
Ejercicios
Referencias
Date : 6 de junio de 2006 (6/6/6).
1991 Mathematics Subject Classification. 94-01, 94-06, 94B05, 94B15.
CONICET y SecytUNC.
4142
45
45
46
48
49
50
51
54
55
59
59
61
63
65
68
69
69
71
74
76
76
82
83
85
86
87
88
90

´
RICARDO A. PODESTA

42

´
Introduccion
Como el t´
ıtulo indica, estas notas tratan sobre C´digos Autocorrectores. ¿Contienen alguna
o
revelaci´n sobre el C´digo Da Vinci ? ¿Tienen algo que ver con los “c´digos del f´tbol”? No,
o
o
o
u
en absoluto. Por otraparte, existen ciertos tipos de c´digos como los lenguajes naturales, la
o
notaci´n musical y las se˜ales de tr´nsito, que no son c´digos en el sentido matem´tico que nos
o
n
a
o
a
interesa. Por ejemplo, los lenguajes naturales son c´digos (t´cnicamente hablando, no-lineales
o
e
y de longitud variable) aunque con muy malas propiedades en cuanto a detecci´n y correcci´n
o
o
de errores.Casi siempre, por sintaxis o contexto, podemos detectar un error, pero es muy
dif´ corregirlo. Como ejemplo, un hombre va a buscar a su amada a la habitaci´n y solo
ıcil
o
encuentra una escueta notita que dice “Xo te amo”. El hombre detecta el error, pero duda
entre interpretar el texto como “Yo te amo” o interpretarlo como “No te amo”. En ingl´s, el
e
ejemplo se torna m´s dram´tico, ya queel hombre encuentra la nota “I love Xou”, con las
a
a
posibles interpretaciones “I love You” o “I love Lou” (quien adem´s podr´ ser su amigo. . . )
a
ıa
Para despejar estas dudas, en este apunte explicamos a que cosa nos referimos por c´digo y
o
qu´ quiere decir que ´ste sea autocorrector. Trataremos tambi´n de mostrar para qu´ sirven y
e
e
e
e
cu´l es el inter´s en ellos. El objetivodel curso que presentamos, es dar una breve introducci´n a
a
e
o
la teor´ de los c´digos autocorrectores, a trav´s de numerosos ejemplos y de una clase particular
ıa
o
e
muy rica de c´digos, los c´digos lineales. La escasez de tiempo y espacio han hecho que muchos
o
o
temas queden sin tratar. Algunos, como los c´digos perfectos o los enumeradores de peso y
o
la identidad deMacWilliams son tratados, aunque no en el detalle que estos se merecen. He
preferido incluir un poco de informaci´n extra, a costa de dejar algunos hechos sin demostraci´n.
o
o
La frase “ejercicio para el lector” ser´, por lo tanto, frecuentemente utilizada.
a
La situaci´n general es, grosso modo, la siguiente. Supongamos que queremos enviar un
o
´
mensaje. Este es enviado por un canal de...