Teoría de la Información y de la Codificación
Código: 104354 Créditos ECTS: 6| Titulación | Tipo | Curso | Semestre |
|---|---|---|---|
| 2503758 Ingeniería de Datos | OB | 2 | 2 |
Contacto
- Nombre:
- Joaquim Borges Ayats
- Correo electrónico:
- joaquim.borges@uab.cat
Uso de idiomas
- Lengua vehicular mayoritaria:
- catalán (cat)
- Algún grupo íntegramente en inglés:
- No
- Algún grupo íntegramente en catalán:
- Sí
- Algún grupo íntegramente en español:
- No
Equipo docente
- Joaquim Borges Ayats
- Joan Bartrina Rapesta
Prerequisitos
No hay prerequisitos. Sin embargo, los estudiantes deberían estar familiarizados con las cuestiones más básicas de álgebra lineal fundamental, análisis matemático y teoría de probabilidades.
Objetivos y contextualización
Estudiar la teoría matemática de la información, en el caso discreto, basada en las publicaciones de C.E. Shannon el año 1948. Estudiar las fuentes de datos, la codificación de la fuente, la compresión de datos y la codificación del canal. Estudiar códigos detectores y correctores de errores para una transmisión o almacenamiento eficiente de datos.
Competencias
- Generar propuestas innovadoras y competitivas en la actividad profesional y en la investigación.
- Que los estudiantes tengan la capacidad de reunir e interpretar datos relevantes (normalmente dentro de su área de estudio) para emitir juicios que incluyan una reflexión sobre temas relevantes de índole social, científica o ética.
- Trabajar cooperativamente, en entornos complejos o inciertos y con recursos limitados, en un contexto multidisciplinar, asumiendo y respetando el rol de los diferentes miembros del equipo.
- Transmitir los datos de forma eficiente, exacta y segura.
Resultados de aprendizaje
- Analizar y evaluar las ventajas e inconvenientes de una compresión con pérdida, sin pérdida y casi sin pérdida.
- Decidir cuál es el tipo de codificación más idónea, dependiendo de las características de la señal y del canal de transmisión.
- Formular métodos para la compresión de la información y codificación para la corrección de errores.
- Generar propuestas innovadoras y competitivas en la actividad profesional y en la investigación.
- Que los estudiantes tengan la capacidad de reunir e interpretar datos relevantes (normalmente dentro de su área de estudio) para emitir juicios que incluyan una reflexión sobre temas relevantes de índole social, científica o ética.
- Trabajar cooperativamente, en entornos complejos o inciertos y con recursos limitados, en un contexto multidisciplinar, asumiendo y respetando el rol de los diferentes miembros del equipo.
Contenido
1.- Conceptos básicos. Fuentes discretas sin memoria.
1.1.- Los problemas de la comunicación.
1.2.- Medida de la información.
1.3.- Modelo de Shannon de fuente discreta sin memoria.
1.4.- Función entropía.
1.5.- Información mutua.
1.6.- Canales discretos sin memoria. Capacidad.
2.- Codificación de la fuentee.
2.1.- Introducción y objectivos.
2.2.- Códigos de longitud constante.
2.3.- Códigos de longitud variable. Decodificación única.
2.4.- Cotas de Shannon.
2.5.- Construcción de códigos óptimos.
3.- Compresión de datos.
3.1.- Tipos de compresión. Medidas de compresión.
3.2.- Técnicas de compresión.
3.3.- Métodos estadísticos.
3.4.- Técnicas de diccionario.
3.5.- Compresión de sonido y de imágenes.
4.- Canales discretos sin memoria.
4.1.- Modelos de canales.
4.2.- Cálculo de la capacidad de un canal.
4.3.- Reglas de decodificación.
4.4.- El teorema fundamental.
5.- Teoría de la codificación I: códigos lineales.
5.1.- Códigos bloque. Decodificación a mínima distancia.
5.2.- Introducción a los cuerpos finitos.
5.3.- Códigos lineales. Matrices generadoras.
5.4.- Códigos equivalentes. Codificación sistemática.
5.5.- Códigos duales. Matrices de control.
5.6.- Decodificación. Tabla estándard y síndrome.
5.7.- Algunas familias de códigos lineales importantes.
6.- Teoría de la codificación II: códigos cíclicos.
6.1.- Códigos cíclicos como ideales de anillos de polinomios.
6.2.- Polinomios generadores y de control.
6.3.- Codificación sistemática con códigos cíclicos.
Metodología
Los contenidos teóricos se explicarán en clases magistrales, si bien se animará a los estudiantes a participar activamente en la resolución de ejemplos. En las clases de problemas, se irá resolviendo una lista de ejercicios. Se intentará que los estudiantes resuelvan los problemas anticipadamente y presenten sus soluciones en clase. En las sesiones de prácticas, se desarrollarán temas relacionados con los contenidos. En especial, compresión de datos y teoría de la codificación. El Campus Virtual se usará como medio de comunicación entre los profesores y los estudiantes (material, anuncios, etc.).
Nota: se reservarán 15 minutos de una clase dentro del calendario establecido por el centro o por la titulación para que el alumnado rellene las encuestas de evaluación de la actuación del profesorado y de evaluación de la asignatura o módulo.
Actividades
| Título | Horas | ECTS | Resultados de aprendizaje |
|---|---|---|---|
| Tipo: Dirigidas | |||
| Clases de problemas | 12 | 0,48 | 1, 2, 5 |
| Clases de teoría | 26 | 1,04 | 1, 2, 5 |
| Prácticas | 12 | 0,48 | 1, 2, 3, 4, 5, 6 |
| Tipo: Supervisadas | |||
| Tutorías y consultas | 17 | 0,68 | 1, 2, 3, 5 |
| Tipo: Autónomas | |||
| Preparación de problemas y prácticas | 25 | 1 | 1, 2, 3, 4, 5 |
| Preparación examen final | 25 | 1 | 1, 2, 3, 5 |
| Trabajo personal | 25 | 1 | 1, 2, 3, 4, 5 |
Evaluación
Las fechas de evaluación continua se publicarán en el Campus Virtual y pueden estar sujetas a cambios de programación por motivos de adaptación a posibles incidencias. Se informará siempre en el Campus Virtual sobre estos cambios ya que se entiende que ésta es la plataforma habitual de intercambio de información entre profesorado y alumnado.
La evaluación de la asignatura, sobre 10 puntos, se llevará a cabo de la forma siguiente:
- Dos pruebas parciaales individuales, 6 puntos (3 puntos cada una). La primera prueba se hará en horas de teoría y la segunda en la fecha especificada por la coordinación de la titulación. Estas pruebas individuales consistirán mayoritariamente en ejercicios al estilo de los que se han ido haciendo durante el curso; una parte menor consistirá en cuestiones más teóricas.
- Resolución de ejercicios, 1.5 puntos. Como parte de la evaluación continuada, deberán realizarse actividades o resolver ejercicios aplicando los métodos vistos.
- Prácticas obligatorias, 2.5 puntos. Como parte de la evaluación continuada, deberán realizarse implementaciones con ordenador. Habrá una fecha de recuperación para esta parte, en caso necesario.
- Examen final, 6 puntos. Quien no haya superado la asignatura tendrá la opción de presentarse al examen final para recuperar toda la materia de la asignatura. Por tanto, no hay recuperación de los parciales por separado, sinó que el examen es de todo el curso. Esta prueba individual consistirá mayoritariamente en ejercicios al estilo de los que se han ido haciendo durante el curso; una parte menor consistirá en cuestiones más teóricas.
Sin perjuicio de otras medidas disciplinarias que se estimen oportunas, y de acuerdo con la normativa académica vigente, las irregularidades cometidas por un estudiante que puedan conducir a uan variación de la calificación se calificarán con un cero (0). Las actividades de evaluación calificadas de esta forma y por este procedimiento no serán recuperables. Estas irregularidades incluyen, entre otras: la copia total o parcial de una práctica, informe o cualquier otra actividad de evaluación; dejar copìar; presentar un trabajo en grupo no realizado íntegramente por los miembros del grupo; presentar como propios materiales elaborados por un tercero, aunque sean traducciones o adaptaciones, y en general trabajos con elementos no originales y exclusivos del estudiante; tener dispositivos de comunicación (como teléfonos móbiles, smart watches, etc.) accesibles durante las pruebas de evaluación teórico-prácticas individuales (exámenes).
Para aprobar es necesario que la evaluación total supere los 5 puntos. No se otorgarà la calificación "no evaluable2 a quien haya participado en alguno de los dos exámenes parciales o bien en el examen final. No habrá tratamiento especial para los estudiantes repetidores, excepto que podrán convalidar la nota de prácticas del curso anterior.
Para obtener una MH, la nota final debe ser igual o superior a los 9 puntos. Puesto que el número de MH no puede superar el 5% del número de estudiantes matriculados, se concederán a quienes tengan las notas finales más elevadas.
En el caso de la resolución de ejercicios, se podrá pedir una revisión posterior. Para el resto de actividades de evaluación, se indicará lugar, fecha y hora de revisión, en la que el estudiante podrá revisar la actividad con el/la profesor/a. Si el estudiante no se presenta a esta revisión, ya no se revisará posteriormente esta actividad.
Se puede consultar la normativa académica de la UAB aprobada por el Consell de Govern de la UAB:
http://webs2002.uab.es/afers_academics/info_ac/0041.htm
Actividades de evaluación
| Título | Peso | Horas | ECTS | Resultados de aprendizaje |
|---|---|---|---|---|
| Examen final | 60% | 3 | 0,12 | 1, 2, 5 |
| Pruebas basadas en ejercicios en clase de problemas | 15% | 3 | 0,12 | 1, 2, 3, 5 |
| Pràcticas | 25% | 2 | 0,08 | 1, 2, 3, 4, 5, 6 |
Bibliografía
*L. Huguet i J. Rifà. Comunicación Digital. Ed. Masson, 1991.
*D. Salomon: Data compression - The Complete Reference, 4th Edition. Springer 2007.
*R.B. Ash. Information Theory. John Wiley and Sons Inc, 1965.
*G. Alvarez. Teoría matemática de la información. Ediciones ICE, 1981.
*T.C. Bell, J.G. Cleary i I.H. Witten. Text Compression. Prentice Hall, 1990.
*F.J. MacWilliams and N.J.A. Sloane. The theory of error-correcting codes. North-Holland, Amsterdam, 1977.
Software
Para la primera práctica se utilitzará el software development kit de Java de la casa Oracle, Apache ant, y software libre desarrollado por el equipo docente de la assignatura. Todo el software será de libre distribución.
Para la segunda práctica se utilizará SageMath. https://www.sagemath.org/ SageMath es un sistema de software matemático de código abierto con licencia GPL. Se basa en muchos paquetes de código abierto existentes: NumPy, SciPy, matplotlib, Sympy, Maxima, GAP, FLINT, R y muchos más. Se puede acceder a su potencial combinado a través de un lenguaje común basado en Python o directamente a través de interfaces. Desde la versión 9.0 lanzada en enero de 2020, SageMath está usando Python 3.