Teoria de la Informació i la Codificació (TIC)

L'assignatura té dues parts que corresponen a dos objectius.
En la primera l'objectiu es posar a l'abast de l'estudiant la teoria matemàtica de la informació de Shannon per a canals discrets sense memòria.
En la segona l'objectiu és fer conscient a l'estudiant de quins són els problemes bàsics de la codificació i posar al seu abast les tecniques més usuals per a dissenyar codis detectors i correctors d'errors.

Coneixements

1. Conèixer els conceptes d'informació d'un esdeveniment i d'entropia d'una distribució de probabilitats. Conèixer el concepte de font d'informació, de canal d'informació i els teoremes de Shannon.
2. Conèixer els paràmetres associats a un codi de bloc i la seva relació amb la capacitat detectora i correctora del codi. Conèixer les aplicacions de l'aritmètica modular als codis detectors/correctors usuals.
3. Conèixer l'estructura bàsica dels cossos finits, principalment de característica 2, i dels espais vectorials de dimensió finita sobre un cos finit. Conèixer les formes de donar un codi lineal, determinar els seus paràmetres i l'algorisme de correcció per síndromes.
   Conèixer codis lineals concrets, en especial els perfectes, i els algorismes de correcció corresponents.
4. Conèixer l'estructura general dels codis cíclics i l'algorisme de correcció de Meggit. Conèixer els codis BCH binaris i els algoritmes de correcció d'errors associats. Conèixer els codis de Reed-Solomon i les seves aplicacions al discs compactes.

Habilitats

1. Saber calcular incerteses d'esdeveniments, entropies de distribucions i informacions mútues de variables aleatòries. Saber construir codis de Huffman. Saber calcular capacitats de canal per a matrius de canal suficientment simples.
2. Saber calcular paràmetres de codis de bloc en situacions suficientment simples.
   Saber emprar l'aritmètica modular en la detecció i correcció de codis construïts sobre Z_n.
3. Saber expressar els codis lineals en termes de les matrius generadora i de control i saber passar d'una a l'altra. Saber usar l'algorisme de correcció per síndromes.
   Saber emprar l'algorisme de correcció per codis de Hamming, i de Golay binaris i ternaris.
4. Saber relacionar les matrius generadora i de control d'un codi cíclic amb els polinomis generador i de control.
   Saber aplicar l'algorisme de correcció Meggit. Saber construir codis BCH binaris i corregir errors.
   Saber construir i corregir codis de Reed-solomon.

Competències

1. Capacitat de resoldre problemes aplicant els mètodes de la ciència i l'enginyeria
2. Capacitat d'aplicar els coneixements de matemàtiques i lògica a la resolució de problemes.
3. Saber aplicar el cicle de resolució de problemes típic de la ciència i l'enginyeria: especificació, generació d'idees i alternatives, disseny d'una estratègia de solució, execució de l'estratègia, validació, interpretació i avaluació dels resultats. Capacitat d'analitzar el procés un cop acabat.
4. Capacitat per relacionar i estructurar informació de diverses fonts, per integrar idees i coneixements.
5. Capacitat per transmetre idees efectivament de forma escrita.

(-)

Un primer examen parcial amb un valor del 25% que inclou els objectius 1, 2 i 3 (teoria de la informació).

Un segon examen parcial amb un valor del 75% que inclou la resta d'objectius (codis correctors d'errors).

Ambdós parcials són eliminatoris (no cal presentar-se al final si s'aprova fent mitjana dels parcials).

Un examen final (100%) recuperatori si es suspen l'assignatura aplicant la fórmula anterior.

Els dos exàmens inclouen part de coneixements i d'habilitats, però amb més pes d'habilitats (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.

1. http://www-ma2.upc.es/~brunat/iic.html
   Pàgina associada al primer llibre de la bibliografia bàsica. Hi ha problemes resolts, algorismes implementats, bibliografia, etc.

L'alumne hauria de:
(a) conéixer els anells de classes mòdul un enter i saber-ne fer càlculs.
(b) Ha de saber construir i fer operacions en cossos finits.
(c) Ha de conéixer els conceptes de dependència i independència lineal, base i dimensió, i ha de saber operar amb matrius (sumes, productes) i calcular inverses.
(d) Ha de conéixer la funció logaritme i les seves propietats.

AL i MATD haurien de ser prerequisits.