Teoria de la Informació i de la Codificació
Codi: 104354 Crèdits: 6| Titulació | Tipus | Curs | Semestre |
|---|---|---|---|
| 2503758 Enginyeria de Dades | OB | 2 | 2 |
Professor/a de contacte
- Nom:
- Joaquim Borges Ayats
- Correu electrònic:
- Joaquim.Borges@uab.cat
Utilització d'idiomes a l'assignatura
- Llengua vehicular majoritària:
- català (cat)
- Grup íntegre en anglès:
- No
- Grup íntegre en català:
- Sí
- Grup íntegre en espanyol:
- No
Equip docent
- Joaquim Borges Ayats
- Joan Bartrina Rapesta
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
- Analitzar i avaluar els avantatges i els inconvenients d'una compressió amb pèrdua, sense pèrdua i gairebé sense pèrdua.
- Decidir quin és el tipus de codificació més idònia, depenent de les característiques del senyal i del canal de transmissió.
- Formular mètodes per a la compressió de la informació i la codificació per a la correcció d'errors.
- 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.
- 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.
Metodologia
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. En especial, compressió de dades i teoria de la codificació. 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.
Activitats formatives
| 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 |
Avaluació
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ó continuada, s'hauran de fer implementacions amb ordinador. Hi haurà una data de recuperació per a aquesta part, si és necessari.
- 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.
Sense perjudici d'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 resta d'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
Activitats d'avaluació
| 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 |
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 la primera pràctica s’utilitzarà el software development kit de Java de la casa Oracle, Apache ant, i programari lliure desenvolupat per l’equip docent de l’assignatura. Tot el software serà de lliure distribució.
Per a la segona pràctica 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.