Logo UAB

Teoria de la Informació i de la Codificació

Codi: 104354 Crèdits: 6
2024/2025
Titulació Tipus Curs
2503758 Enginyeria de Dades OB 2

Professor/a de contacte

Nom:
Joaquin Borges Ayats
Correu electrònic:
joaquim.borges@uab.cat

Equip docent

Joaquin Borges Ayats
Adrià Figuerola Torrell

Idiomes dels grups

Podeu consultar aquesta informació al final del document.


Prerequisits

No hi ha prerequisits. En tot cas és aconsellable que l'estudiant domini les qüestions més bàsiques d'àlgebra lineal fonamental, anàlisi matemàtica i teoria de probabilitats.


Objectius

Estudiar la teoria matemàtica de la informació, en el cas discret, basada en les publicacions de C.E. Shannon l'any 1948. Estudiar les fonts de dades, la codificació de la font, la compressió de dades i la codificació del canal. Estudiar codis detectors i correctors d'errors per a una transmissió o emmagatzematge eficient de dades.


Competències

  • Generar propostes innovadores i competitives en l'activitat professional i en la investigació.
  • Que els estudiants tinguin la capacitat de reunir i interpretar dades rellevants (normalment dins de la seva àrea d'estudi) per emetre judicis que incloguin una reflexió sobre temes destacats d'índole social, científica o ètica.
  • Transmetre les dades de forma eficient, exacta i segura.
  • Treballar cooperativament, en entorns complexos o incerts i amb recursos limitats, en un context multidisciplinari, assumint i respectant el rol dels diferents membres de l'equip.

Resultats d'aprenentatge

  1. Analitzar i avaluar els avantatges i els inconvenients d'una compressió amb pèrdua, sense pèrdua i gairebé sense pèrdua.
  2. Decidir quin és el tipus de codificació més idònia, depenent de les característiques del senyal i del canal de transmissió.
  3. Formular mètodes per a la compressió de la informació i la codificació per a la correcció d'errors.
  4. Generar propostes innovadores i competitives en l'activitat professional i en la investigació.
  5. Que els estudiants tinguin la capacitat de reunir i interpretar dades rellevants (normalment dins de la seva àrea d'estudi) per emetre judicis que incloguin una reflexió sobre temes destacats d'índole social, científica o ètica.
  6. Treballar cooperativament, en entorns complexos o incerts i amb recursos limitats, en un context multidisciplinari, assumint i respectant el rol dels diferents membres de l'equip.

Continguts

1.- Conceptes bàsics. Fonts discretes sense memòria.

1.1.- Els problemes de la comunicació.

1.2.- Mesura de la informació.

1.3.- Model de Shannon de font discreta sense memòria.

1.4.- Funció entropia.

1.5.- Informació mútua.

1.6.- Canals discrets sense memòria. Capacitat.

 

2.- Codificació de la font.

2.1.- Introducció i objectius.

2.2.- Codis de longitud constant.

2.3.- Codis de longitud variable. Descodificació única.

2.4.- Fites de Shannon.

2.5.- Construcció de codis òptims.

 

3.- Compressió de dades.

3.1.- Tipus de compressió. Mesures de compressió.

3.2.- Tècniques de compressió.

3.3.- Mètodes estadístics.

3.4.- Tècniques de diccionari.

3.5.- Compressió de so i d'imatges.

 

4.- Canals discrets sense memòria.

4.1.- Models de canals.

4.2.- Càlcul de la capacitat d'un canal.

4.3.- Regles de descodificació.

4.4.- El teorema fonamental.

 

5.- Teoria de la codificació I: codis lineals.

5.1.- Codis bloc. Descodificació a mínima distància.

5.2.- Introducció als cossos finits.

5.3.- Codis lineals. Matrius generadores.

5.4.- Codis equivalents. Codificació sistemàtica.

5.5.- Codis duals. Matrius de control.

5.6.- Descodificació. Taula estàndard i síndrome.

5.7.- Algunes famílies de codis lineals importants.

 

6.- Teoria de la codificació II: codis cíclics.

6.1.- Codis cíclics com a ideals d'anells de polinomis.

6.2.- Polinomis generadors i de control.

6.3.- Codificació sistemàtica amb codis cíclics.


Activitats formatives i Metodologia

Títol Hores ECTS Resultats d'aprenentatge
Tipus: Dirigides      
Classes de problemes 12 0,48 1, 2, 5
Classes de teoria 26 1,04 1, 2, 5
Pràctiques 12 0,48 1, 2, 3, 4, 5, 6
Tipus: Supervisades      
Tutories i consultes 17 0,68 1, 2, 3, 5
Tipus: Autònomes      
Preparació de problemes i pràctiques 25 1 1, 2, 3, 4, 5
Preparació examen final 25 1 1, 2, 3, 5
Treball personal 25 1 1, 2, 3, 4, 5

Els continguts teòrics s'explicaran en classes magistrals, si bé s'animarà als estudiants a participar activament en la resolució d'exemples. A les classes de problemes, s'anirà resolent una llista d'exercicis. S'intentarà que els estudiants resolguin els problemes anticipadament i presentin les seves solucions a classe. A les sessions de pràctiques, es desenvoluparan temes relacionats amb els continguts teòrics de l'assignatura. El Campus Virtual s'usarà com a mitjà de comunicació entre els professors i els estudiants (material, anuncis, etc.).

Nota: es reservaran 15 minuts d'una classe, dins del calendari establert pel centre/titulació, per a la complementació per part de l'alumnat de les enquestes d'avaluació de l'actuació del professorat i d'avaluació de l'assignatura/mòdul.


Avaluació

Activitats d'avaluació continuada

Títol Pes Hores ECTS Resultats d'aprenentatge
Examen final 60% 3 0,12 1, 2, 5
Proves basades en exercicis a classe de problemes 15% 3 0,12 1, 2, 3, 5
Pràctiques 25% 2 0,08 1, 2, 3, 4, 5, 6

Les dates d'avaluació continuada es publicaran al Campus Virtual i poden estar subjectes a canvis de programació per motius d'adaptació a possibles incidències. Sempre s'informarà al Campus Virtual sobre aquests canvis ja que s'entén que aquesta és la plataforma habitual d'intercanvi d'informació entre professorat i alumnat.

L'avaluació de l'assignatura, sobre 10 punts, es farà de la forma següent:

  • Dues proves parcials individuals, 6 punts (3 punts cadascuna). La primera prova es farà en hores de teoria i la segona en la data especificada per la coordinació. Aquestes proves individuals consistiran majoritàriament en exercicis a l'estil dels que s'han anat fent durant el curs; una part menor consistirà en qüestions mésteòriques.
  • Resolució d'exercicis, 1.5 punts. Com a part de l'avaluació continuada, s'hauran de realitzar activitats o resoldre exercicis aplicant els mètodes vistos.
  • Pràctiques obligatòries, 2.5 punts. Com a part de l'avaluació contínua, s'hauran de realitzar implementacions amb ordinador que seran objecte d'avaluació. En cas d'absentar-se d'una sessió sense una justificació prèviament presentada i adequada, el contingut d'aquesta sessió serà avaluat amb un 0
  • Examen final,6 punts. Qui no hagi superat l'assignatura arran de les proves parcials individuals tindrà l'opció de presentar-se a l'examen final per recuperar tota la matèria de l'assignatura. Per tant, no hi ha recuperació dels parcials per separat sinó que l'examen és de tot el curs. Aquesta prova individual consistirà majoritàriament en exercicis a l'estil dels que s'han anat fent durant el curs; una part menor consistirà en qüestions més teòriques.

En cadascuna de les proves parcials cal obtenir un mínim de 0.5 punts. No hi ha altres notes mínimes en cada part. Per aprovar cal que les diferents parts sumin almenys 5 punts. No s'ofereix avaluació única.

Sense perjudicid'altres mesures disciplinàries que s'estimin oportunes, i d'acord amb la normativa acadèmica vigent, les irregularitats comeses per un estudiant que puguin conduir a una variació de la qualificació es qualificaran amb un zero (0). Les activitats d'avaluació qualificades d'aquesta forma i per aquest procediment no seran recuperables. Aquestes irregularitats inclouen, entre d'altres: la còpia total o parcial d'una pràctica, informe, o qualsevol altra activitat d'avaluació; deixar copiar; presentar un treball de grup no fet íntegrament pels membres del grup; presentar com a propis materials elaborats per un tercer, encara que siguin traduccions o adaptacions, i en general treballs amb elements no originals i exclusius de l'estudiant; tenir dispositius de comunicació (com telèfons mòbils, smart watches, etc.) accessibles durant les proves d'avaluació teorico-pràctiques individuals (exàmens).

Per aprovar és necessari que l'avaluació total superi els 5 punts. No s'atorgarà la qualificació de "no avaluable" a qui hagi participat en algun dels dos exàmens parcials o bé a l'examen final. No hi haurà cap condició especial per als estudiants repetidors, excepte que podran convalidar la nota de pràctiques del curs anterior.

Per poder obtenir una MH, la nota final ha de ser igual o superior als 9 punts. Com que el nombre de MH no pot superar el 5% del nombre d'estudiants matriculats, es concediran a qui tingui les notes finals més altes.

En el cas de la resolució d'exercicis, es podrà demanar una revisió posterior. Per a la restad'activitats d'avaluació, s'indicarà un lloc, data i hora de revisió en la que l'estudiant podrà revisar l'activitat amb el/la professor/a. Si l'estudiant no es presenta a aquesta revisió, no es revisarà posteriorment aquesta activitat.


Podeu consultar la normativa acadèmica de la UAB aprovada pel Consell de Govern de la UAB:
http://webs2002.uab.es/afers_academics/info_ac/0041.htm


Bibliografia

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


Programari

Per a les pràctiques s'utilitzarà SageMath. https://www.sagemath.org/ SageMath és un sistema de programari matemàtic de codi obert amb llicència GPL. Es basa en diferents paquests de codi obert: NumPy, SciPy, matplotlib, Sympy, Maxima, GAP, FLINT, R i altres. Es pot accedir al seu potencial combinat a través d'un llenguatge comú basat en Python o directamente a través d'interfícies. Des de la versió 9.0 del gener de 2020, SageMath está usant Python 3.


Llista d'idiomes

Nom Grup Idioma Semestre Torn
(PAUL) Pràctiques d'aula 811 Català segon quadrimestre matí-mixt
(PAUL) Pràctiques d'aula 812 Català segon quadrimestre matí-mixt
(PLAB) Pràctiques de laboratori 811 Català segon quadrimestre matí-mixt
(PLAB) Pràctiques de laboratori 812 Català segon quadrimestre matí-mixt
(PLAB) Pràctiques de laboratori 813 Català segon quadrimestre matí-mixt
(TE) Teoria 81 Català segon quadrimestre matí-mixt