Encabezado Facultad de Ciencias
Presentación

Ciencias de la Computación (plan 1994) 2014-1

Optativas, Teoría de Códigos

Grupo 7072, 40 lugares. 6 alumnos.
Profesor Zazil Santizo Huerta ma ju 17 a 18:30 P104
Ayudante Manuel Díaz Díaz lu mi 16 a 17 P104
Ayud. Lab. Víctor Genaro Aguilar Gonzaga ma 14 a 16 Taller de Ingeniería de Software

 
Forma de evaluación
El objetivo del curso es introducir al alumno a la teoría de códigos con un enfoque hacía la teoría de la información.
La forma de evaluación será mediante tres tareas-examen, las cuales constarán de dos partes, una parte teórica y otra práctica.
El alumno tendrá dos semanas para poder resolver y entregar las tareas.
Requisitos
El alumno deberá saber algún lenguaje de programación para poder resolver la parte práctica de la tarea.
Es deseable que se tenga noción de teoría de números y álgebra lineal. (El ayudante repasará estos temas)
Temario
1. El concepto de código
  • Cadenas de bits y operaciones binarias
  • La distancia de Hamming
  • Códigos binarios
  • Códigos correctores de errores en general
2. Codificación eficiente
  • Árbol de decodificación
  • Codificación de Shannon-Fano
  • Codificación de Huffman
  • Longitud promedio de un código
  • La eficiencia del esquema de Huffman
3. Información y entropía
  • Cantidad de información
  • Entropía de información
  • Propiedades de la entropía
  • Extensiones de una fuente
  • El primer teorema de Shannon
4. Codificación para detectar y corregir errores
  • Regla de decisión y canal de comunicación
  • Decodificación al vecino más cercano
  • Distancia mínima, capacidad de detección y corrección
  • Códigos maximales
  • Probabilidad de error al decodificar
  • Códigos de Hamming: idea e implementación
  • Esferas y códigos perfectos
  • Equivalencia de códigos
  • Tasa de transmisión y de corrección
  • El teorema de la codificación con ruido
  • Códigos de Golay: idea e implementación
5. Campos finitos
  • Campos
  • Anillo de polinomios
  • Estructura de los campos finitos
  • Polinomio mínimo
6. Códigos lineales
  • Definición, características
  • La matriz generadora
  • Corrección de errores
  • Probabilidad de decodificar correctamente
  • Complemento ortogonal, código dual
  • Decodificación de síndrome
  • Códigos de Hamming y Golay revisados
7. Códigos cíclicos
  • Definición, asociación con polinomios
  • Polinomio generador
  • Matriz generadora
  • Polinomios irreducibles y factorización
  • Polinomio y matriz de verificación de paridad
  • Codificación y decodificación
Bibliografía
  • Bierbrauer, J., Introduction to Coding Theory, Chapman and Hall, CRC, 2004
  • Van Lint, J. H., Introduction to Coding Theory, SpringerVerlag, GTM, 1998.
  • Ling S., Xing C. Coding theory (CUP, 2004)
  • Páez Osuna, O., Notas sobre Teoría de Códigos y Campos de Funciones,2012.
  • Galaviz Casas, J.,Introducción a la Teoría de Códigos y de la Información.

 


Hecho en México, todos los derechos reservados 2011-2016. Esta página puede ser reproducida con fines no lucrativos, siempre y cuando no se mutile, se cite la fuente completa y su dirección electrónica. De otra forma requiere permiso previo por escrito de la Institución.
Sitio web administrado por la Coordinación de los Servicios de Cómputo de la Facultad de Ciencias. ¿Dudas?, ¿comentarios?. Escribenos. Aviso de privacidad.