es ca en ca ca ca en pt es oc es es es en es es es ca es es en es es en lb gl es es es es es fr fr es fr es es es es es es es es es pt es es es es es es es es es es es es en en fr ia bn fr cs it es eo es eo es es cs es en en fr ia bn fr cs en en en en en en en en en ca cs es en en fr ia bn fr cs en en en en en en en en en ca ca cs es en en fr ia bn fr cs en en en en en en en en en ca ca cs es en en fr ia bn fr cs en en en en en en en en en es es cs es en en fr ia bn fr cs en en en en en en en en en ca cs es en en fr ia bn fr cs en en en en en en fr en fr ca da gl en en fr ia bn fr cs en en en en en en en en en es en en fr ia bn fr cs en en en en en en en en en es en es en es es es es es gl gl es es es en en en ca es en en en en en en en en es en pt es es es es es es pt es es es es pt es es es es es es es es es es es es es es es es es es es es es es es es en es en en es es
Asignaturas - Facultad de Informática de Barcelona - FIB - Universidad Politecnica de Cataluña - UPC - BarcelonaTech
Masters in Computer Science and Engineering
Grado en Ingeniería en informática
Versió en Català | English version
Teoría de la Información y la Codificación (TIC)
AL - Prerrequisito para la EI , ETIG , ETIS
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.
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.
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.
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).
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.
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.
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.
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.
Capacidad para resolver problemas aplicando los métodos de la ciencia y la ingeniería.
Capacidad para aplicar los conocimientos de matemáticas y lógica a la resolución de problemas.
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.
Capacidad para relacionar y estructurar información de varias fuentes, para integrar ideas y conocimientos.
Capacidad para transmitir ideas efectivamente de forma escrita.
Otras horas fuera del horario fijado
Informació. Entropia i propietats. Informació mútua.
Códigos de fuente y de canal.
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.
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.
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.
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.
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.
Horas adicionales dedicadas a la evaluación
Total horas de trabajo para el estudiante
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.
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 %).
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.
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.
(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.
Acceso a los estudios
Plan de estudios Grado
Trabajo de Fin de Grado
Ingeniería Técnica en Informática de Gestión
Ingeniería Técnica en Informática de Sistemas
Proyecto final de carrera
© 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