Saltar al contingut Menu
Mapa
  • Inici
  • Informació
  • Contacte
  • Mapa

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

Crèdits Dept. Tipus Requisits
7.5 (6.0 ECTS) MAT
  • Optativa per a l'EI
  • Optativa per a l'ETIG
  • Optativa per a l'ETIS
AL - Pre-requisit per la EI , ETIG , ETIS
MATD - Pre-requisit per la EI , ETIG , ETIS

Professors

Responsable:  (-)
Altres:(-)

Objectius Generals

L'assignatura té dues parts, que corresponen a dos objectius. En la primera, l'objectiu és familiaritzar-se amb la teoria de la informació de Shannon (bàsicament per a canals discrets sense memòria). A la segona part, l'objectiu és comprendre quins són els problemes bàsics de la codificació i adquirir les tècniques més usuals per a tractar-los.

Objectius Específics

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 l'abast dels teoremes de Shannon.
  2. Conèixer els paràmetres associats a un codi de blocs 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 (cossos de Galois), 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 (principalment als 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 blocs en casos senzills.
    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 a 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 per 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.

Continguts

Hores estimades de:

T P L Alt L Ext. Est A Ext.
Teoria Problemes Laboratori Altres activitats Laboratori extern Estudi Altres hores fora d'horari fixat

1. Informació i entropia
T      P      L      Alt    L Ext. Est    A Ext. Total 
3,0 4,0 0 0 0 7,0 0 14,0
Informació. Entropia i propietats. Informació mútua.

2. Codis de font i de canal.
T      P      L      Alt    L Ext. Est    A 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. Codis de bloc.
T      P      L      Alt    L Ext. Est    A 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. Codis lineals
T      P      L      Alt    L Ext. Est    A Ext. Total 
5,0 6,0 0 0 0 13,0 0 24,0
Cossos finits i espais vectorials sobre cossos finits. Codis lineals. Matrius generadora i de control. Correció per síndromes. Esborralls. Operacions amb codis lineals.
Codis perfectes. Codis de Hamming, de Golay binaris i de Golay ternaris.

5. Codis cíclics
T      P      L      Alt    L Ext. Est    A 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. Codis de Reed-Solomon
T      P      L      Alt    L Ext. Est    A 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. Codis BCH binaris
T      P      L      Alt    L Ext. Est    A Ext. Total 
6,0 8,0 0 0 0 14,0 0 28,0


Total per tipus T      P      L      Alt    L Ext. Est    A Ext. Total 
32,0 39,0 0 0 0 76,0 0 147,0
Hores addicionals dedicades a l'avaluació 6,0
Total hores de treball per l'estudiant 153,0

Metodologia docent

Amb materials específics que es posaran a la Web, la metodologia es base en els elements següents: presentacions de temes generals a l'aula per part del professor, resolució de problemes de les llistes distribuides, discussió de qüestions en grup (format taula rodona), redacció d'un treball (que inclourà l'implementació d'algun algorisme treballat durant el curs), i una "conferència" final per presentar els treballs.

Mètode d'avaluació

P1 (15%): Examen parcial sobre els objectius 1, 2 i 3 (teoria de la informació).

P2 (45%): Examen parcial sobre la resta d'objectius (codis correctors d'errors).

P (20%): Nota sobre la resolució de problemes a classe.

T (20%): Nota sobre el treball i la seva exposició.

P1+P2 (60%) es pot recuperar, o millorar, en un examen final.

Nota: P1 i P2 inclouen part de coneixements i d'habilitats, però amb més pes de les habilitats (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 complementària

  • 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.

Enllaços web

  1. http://www-ma2.upc.edu/sxd/Teaching/TIC12.html
    Teacher's VOX (a Virtual Office to ease and strengthen communication with students).


Capacitats prèvies

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.


Compartir

 
logo FIB © Facultat d'Informàtica de Barcelona - Contacte - RSS
Aquest web utilitza cookies pròpies per oferir una millor experiència i servei. En continuar amb la navegació entenem que acceptes la nostra política de cookies.
Versió clàssica Versió mòbil