Saltar al contingut Menu
Mapa
  • Inicio
  • Información
  • Contacto
  • Mapa

Teoría de la Información y la Codificación (TIC)

Créditos Dept. Tipo Requisitos
7.5 (6.0 ECTS) MAT
  • Optativa para la EI
  • Optativa para la ETIG
  • Optativa para la ETIS
AL - Prerequisito para la EI , ETIG , ETIS
MATD - Prerequisito para la EI , ETIG , ETIS

Profesores

Responsable:  (-)
Otros:(-)

Objectivos Generales

La asignatura tiene dos partes, con sendos objetivos. En la primera, el propósito es familiarizarse con la teoría de la información de Shannon (básicamente para canales discretos sin memoria). En la segunda parte, el objetivo es comprender cuáles son los problemas básicos de la codificación y adquirir las técnicas más usuales para tratarlos.

Objectivos Específicos

Conocimientos

  1. Conocer los conceptos de información de un acontecimiento y de entropía de una distribución de probabilidades. Conocer el concepto de fuente de informació, de canal e información y el alcance de los teoremas de Shannon.
  2. Conocer los parámetros asociados a un código de bloques y su relación con la capacidad detectora y correctora del código. Conocer las aplicaciones de la aritmética modular en los códigos detectores/correctores usuales.
  3. Conocer la estructura básica de los cuerpos finitos, principalmente los de característica 2, y de los espacios vectoriales de dimensión finita sobre un cuerpo finito. Conocer las formas de definir un código lineal, determinar sus parámetros y el algoritmo de corrección por síndromes.

    Conocer códigos lineales concretos, en especial los perfectos, y los algoritmos de corrección correspondientes.
  4. Conocer la estructura general de los códigos cíclicos y el algoritmo de corrección de Meggit. Conocer los códigos BCH binarios y los algoritmos de corrección asociados. Conocer los códigos de Reed-Solomon y sus aplicaciones (principalmente a los discos compactos).

Habilidades

  1. Saber calcular incertidumbres de acontecimientos, entropías de distribuciones y informaciones mutuas de variables aleatorias. Saber construir códigos de Huffman. Saber calcular la capacidad canales suficientemente simples.
  2. Saber calcular parámetros de códigos de bloques en casos sencillos. Saber usar la aritmética modular en la detección y corrección de códigos construidos sobre Z_n.
  3. Saber expresar códigos lineales en términos de las matrices generadora y de control y saber pasar de una a la otra. Saber usar el algoritmo de corrección por síndromes. Saber usar el algoritmo de corrección de los códigos de Hamming, y de Golay binarios y ternarios.
  4. Saber relacionar las matrices generadora y de control de un código cíclico con los polinomios generador y de control.Saber aplicar el algoritmo de corrección Meggit. Saber construir códigos binarios BCH y corregir errors con ellos. Saber construir códigos de Reed-Solomon i corregir errores con ellos.

Competencias

  1. Capacidad para resolver problemas aplicando los métodos de la ciencia y la ingeniería.
  2. Capacidad para aplicar los conocimientos de matemáticas y lógica a la resolución de problemas.
  3. Saber aplicar el ciclo de resolución de problemas típico de la ciencia y la ingeniería: especificación, generación de ideas y alternativas, diseño de una estrategia de solución, ejecución de la estrategia, validación, interpretación y evaluación de los resultados. Capacidad para analizar el proceso una vez ha acabado.
  4. Capacidad para relacionar y estructurar información de varias fuentes, para integrar ideas y conocimientos.
  5. Capacidad para transmitir ideas efectivamente de forma escrita.

Contenidos

Horas estimadas de:

T P L Alt L Ext. Est O. Ext.
Teoria Problemas Laboratorio Otras actividades Laboratorio externo Estudio Otras horas fuera del horario fijado

1. Información y entropía
T      P      L      Alt    L Ext. Est    O. Ext. Total 
3,0 4,0 0 0 0 7,0 0 14,0
Informació. Entropia i propietats. Informació mútua.

2. Códigos de fuente y de canal.
T      P      L      Alt    L Ext. Est    O. Ext. Total 
3,0 4,0 0 0 0 7,0 0 14,0
Codis de longitud variable. Desigualtat de Kraft. Codis de Huffman. Extensions d'una font. Primer teorema de Shannon.
Capacitat d'un canal. Esquemes de decisió. Teorema de la codificació amb soroll.

3. Códigos de bloque.
T      P      L      Alt    L Ext. Est    O. Ext. Total 
3,0 4,0 0 0 0 7,0 0 14,0
Distància de Hamming. Radis de tangència i de cobertura. Detecció i correcció d'errors. El problema fonamental de la teoria de codis.
Els codis ISBN, DNI, EAN, etc. Codi decimal corrector de dos errors.

4. Códigos lineales
T      P      L      Alt    L Ext. Est    O. Ext. Total 
5,0 6,0 0 0 0 13,0 0 24,0
Cuerpos finitos y espacios vectoriales sobre cuerpos finitos. Códigos lineales. Matriz generadora y matriz de control. Correción por síndromes. Borrones. Operaciones con códigos lineales.
Codis perfectes. Codis de Hamming, de Golay binaris i de Golay ternaris.

5. Códigos cíclicos
T      P      L      Alt    L Ext. Est    O. Ext. Total 
7,0 8,0 0 0 0 18,0 0 33,0
Ideals en anells de polinomis sobre cossos finits. Polinomis generador i de control. Codificació. Exemples de codis cíclics. Correcció. El mètode de Meggit.

6. Códigos de Reed-Solomon
T      P      L      Alt    L Ext. Est    O. Ext. Total 
5,0 5,0 0 0 0 10,0 0 20,0
Versió original dels codis de Reed-Solomon. La transformada de Fourier finita. Correcció. Codis de Reed-Solomon retallats. Descens de cos. Aplicació al disc compacte.

7. Códigos BCH binarios
T      P      L      Alt    L Ext. Est    O. Ext. Total 
6,0 8,0 0 0 0 14,0 0 28,0


Total por tipo T      P      L      Alt    L Ext. Est    O. Ext. Total 
32,0 39,0 0 0 0 76,0 0 147,0
Horas adicionales dedicadas a la evaluación 6,0
Total horas de trabajo para el estudiante 153,0

Metodología docente

Con materiales específicos que se pondrán en la Web, la metodología se basa en los elementos seguientes: presentaciones de temas generales en el aula por el professor, resolución de problemas de las listas distribuidas, discussión de cuestiones en grupo (formato mesa redonda), redacción de un trabajo (que incluirá la implementación de algún algoritmo estudiado durante el curso), y una "conferencia" final para presentar los treballs.

Método de evaluación

P1 (15%): Examen parcial sobre los objectivos 1, 2 y 3 (teoría de la información).

P2 (45%): Examen parcial sobre los demás objectivos (códigos correctores de errores).

P (20%): Nota sobre la resolución de problemas en clase.

T (20%): Nota sobre el trebajo escrito y su exposición.

P1+P2 (60%) se puede recuperar, o mejorar, en un examen final.

Nota: P1 y P2 incluyen parte de los conocimientos y habilidades, pero con mayor peso de las habilidades (60-70 %).


Bibliografía básica

  • Raymond Hill A First course in coding theory, Clarendon Press, 1986.
  • Sweeney, Peter Error control coding : an introduction, Prentice Hall, 1991.
  • Shu Lin, Daniel J. Costello Error control coding : fundamentals and applications, Pearson Prentice-Hall, 2004.
  • Josep M. Brunat Blay, Enric Ventura Capell Informació i codis , Edicions UPC, 2001.

Bibliografía complementaria

  • Steven Roman Coding and information theory, Springer-Verlag,, 1992.
  • F. J. MacWilliams, N. J. A. Sloane The Theory of error correcting codes, North-Holland, 1977.
  • Vera Pless Introduction to the theory of error-correcting codes, John Wiley & Sons, 1998.
  • Robert J. Mc Eliece The Theory of information and coding, Addison-Wesley Publ. Co., 1982.
  • Justesen, Jrn A Course in error-correcting codes, European Mathematical Society, 2004.
  • Stephen B. Wicker, Vijay K. Bhargava editores Reed-Solomon codes and their applications, IEEE Press, 1994.
  • Jirí Adámek Foundations of coding : theory and applications of error-correcting codes, with an introduction to cryptography and information theory, Wiley, 1991.
  • Sebastià Xambó-Descamps Block error-correcting codes : a computational primer, Springer,, 2003.

Enlaces web

  1. http://www-ma2.upc.edu/sxd/Teaching/TIC12.html


Capacidades previas

El alumno debe:
(a) conocer los anillos de clases módulo un entero y saber hacer cálculos.
(b) Debe saber construir y hacer operaciones en cuerpos finitos.
(c) Debe conocer los conceptos de dependencia e independencia lineal, base y dimensión, y debe saber operar con matrices (sumas, productos) y calcular inversas.
(d) Debe conocer la función logaritmo y sus propiedades.



AL y MATD deberían ser prerrequisitos.


Compartir

 
logo FIB © Facultad de Informática de Barcelona - Contacto - RSS
Esta web utiliza cookies propias para ofrecerle una mejor experiencia y servicio. Si continúa la navegación, entendemos que acepta nuestra política de cookies. Versión clássica Versión móvil