Transmissió i Codificació de la Informació

Esteu aquí

Crèdits
6
Tipus
Complementària d'especialitat (Tecnologies de la informació)
Requisits
  • Prerequisit: FM
  • Prerequisit: M1
  • Prerequisit: M2
Departament
MAT
Una introducció als conceptes i algorismes dels codis correctors d'errors.

Professorat

Responsable

  • Rafel Farré Cirera ( )

Hores setmanals

Teoria
3
Problemes
0
Laboratori
1
Aprenentatge dirigit
0
Aprenentatge autònom
6

Competències

Competències Tècniques de cada especialitat

Especialitat tecnologies de la informació

  • CTI1 - Definir, planificar i gestionar la instal·lació de la infraestructura TIC de l'organització.
    • CTI1.4 - Seleccionar, dissenyar, desplegar, integrar, avaluar, construir, gestionar, explotar i mantenir les tecnologies de hardware, software i xarxes, dintre dels paràmetres de cost i qualitat adequats.
  • CTI3 - Dissenyar solucions que integrin tecnologies de hardware, software i comunicacions (i capacitat de desenvolupar solucions específiques de software de sistemes) per a sistemes distribuïts i dispositius de computació ubiqua.
    • CTI3.3 - Dissenyar, implantar i configurar xarxes i serveis.

Competències Transversals

ús solvent dels recursos d'informació

  • G6 [Avaluable] - Gestionar l'adquisició, l'estructuració, l'anàlisi i la visualització de dades i d'informació de l'àmbit de l'enginyeria informàtica, i valorar de forma crítica els resultats d'aquesta gestió.
    • G6.3 - Planificar i utilitzar la informació necessària per a un treball acadèmic (per exemple, per al treball de final de grau) a partir d'una reflexió crítica sobre els recursos d'informació utilitzats. Gestionar la informació de manera competent, independent i autònoma. Avaluar la informació trobada i identificar-ne les llacunes.

Objectius

  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 de comunicació. Conèixer els conceptes de codificació de font (compressió de dades) i de codificació de canal (detecció i correcció) i els teoremes de Shannon.
    Competències relacionades: G6.3,
  2. Conèixer els conceptes bàsics dels codis de blocs: paràmetres associats i la seva relació amb la capacitat detectora i correctora del codi. Conèixer les aplicacions de l'aritmètica modular als codis detectors i correctors. Conèixer els protocols de detecció i correcció d'error emprats en xarxes de comunicació.
    Competències relacionades: CTI3.3, G6.3, CTI1.4,
  3. Conèixer l'estructura bàsica dels cossos finits, principalment els de característica 2. Conèixer els 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.
    Competències relacionades: G6.3,
  4. Conèixer l'estructura general dels codis cíclics i l'algorisme de correcció de Meggit. Conèixer els CRC: cocis cíclics emprats en la detecció d'errors i el seu ús en xarxes de comunicació. 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.
    Competències relacionades: CTI3.3, G6.3, CTI1.4,

Continguts

  1. Informació i entropia.
    Definició matemàtica de la quantitat d'informació. Entropia d'una distribució de probabilitat i informació mútua de dues variables aleatòries.
  2. Codificació de font i de canal
    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ó. Segon teorema de Shannon: codificació de canal amb soroll. El canal binari simètric. Esquema de decodificació per màxima versemblança.
  3. Detecció i correcció d'errors amb codis de bloc
    Distància de Hamming. Radis de tangència i de cobertura. Detecció i correcció d'errors. Protocols de detecció d'errors. El problema fonamental de la teoria de codis.
  4. Cossos finits
    Construcció de cossos finits, especialement els de característica 2. Propietats elementals i càlculs efectius en cossos finits.
  5. Codis lineals
    Espais vectorials sobre cossos finits. Codis lineals. Matrius generadora i de control. Correció per síndromes. Operacions amb codis lineals. Codis perfectes. Codis de Hamming, de Golay binaris i de Golay ternaris.
  6. Codis cíclics i CRC
    Polinomis sobre cossos finits. Codis polinomials. Polinomis generador i de control. Codificació sistemàtica. L'algorisme de correcció de Meggit. Codis cíclics emprats en la detecció d'errors: els CRC. El CRC d'Ethernet.
  7. Codis BCH binarios
    Arrels d'un codi cíclic: descripció d'un codi cíclic mitjançant les seves arrels. Codis BCH sobre un cos finit. Codis BCH binaris primitius i estrictes. L'equació clau. Decodificació per l'algorisme d'Euclides. Decodificació de Berlekamp-Massey.
  8. Codis de Reed-Solomon
    Els codis de Reed-Solomon com a codis cíclics. La transformada de Fourier finita. Algorisme de correcció d'errors. Aplicació: codificació del disc compacte d'àudio.

Activitats

Activitat Acte avaluatiu


Desenvolupament del tema "Informació i entropia"

Desenvolupament del tema "Informació i entropia". L'estudiant escolta, pren apunts, pregunta el que no entén i respon les preguntes del professor.
Objectius: 1
Continguts:
Teoria
3h
Problemes
0h
Laboratori
1h
Aprenentatge dirigit
0h
Aprenentatge autònom
5.5h

Desenvolupament del tema "Codificació de font i de canal"

Desenvolupament del tema "Codificació de font i de canal". L'estudiant escolta, pren apunts, pregunta el que no entén i respon les preguntes del professor.
Objectius: 1
Continguts:
Teoria
3h
Problemes
0h
Laboratori
1h
Aprenentatge dirigit
0h
Aprenentatge autònom
14h

Examen parcial

Examen parcial sobre els continguts 1, 2 i 3
Objectius: 1 2
Setmana: 6
Tipus: examen de teoria
Teoria
2h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
7h

Desenvolupament del tema "Detecció i correcció d'errors amb codis de bloc"

Desenvolupament del tema "Detecció i correcció d'errors amb codis de bloc". L'estudiant escolta, pren apunts, pregunta el que no entén i respon les preguntes del professor.
Objectius: 2
Continguts:
Teoria
4h
Problemes
0h
Laboratori
1h
Aprenentatge dirigit
0h
Aprenentatge autònom
4h

Resolució de problemes 1

Al llarg del curs s'hauran de presentar per escrit un mínim de dos problemes completament resolts
Objectius: 1 2
Setmana: 8
Tipus: examen de laboratori
Teoria
0h
Problemes
0h
Laboratori
0.5h
Aprenentatge dirigit
0h
Aprenentatge autònom
2.2h

Desenvolupament del tema "Cossos finits"

Desenvolupament del tema "Cossos finits". L'estudiant escolta, pren apunts, pregunta el que no entén i respon les preguntes del professor.
Objectius: 3
Continguts:
Teoria
6h
Problemes
0h
Laboratori
2h
Aprenentatge dirigit
0h
Aprenentatge autònom
5h

Desenvolupament del tema "Codis lineals"

Desenvolupament del tema "Codis lineals". L'estudiant escolta, pren apunts, pregunta el que no entén i respon les preguntes del professor.
Objectius: 3
Continguts:
Teoria
5h
Problemes
0h
Laboratori
2h
Aprenentatge dirigit
0h
Aprenentatge autònom
6h

Desenvolupament del tema "Codis cíclics i CRC"

Desenvolupament del tema "Codis cíclics i CRC". L'estudiant escolta, pren apunts, pregunta el que no entén i respon les preguntes del professor.
Objectius: 4
Continguts:
Teoria
6h
Problemes
0h
Laboratori
3h
Aprenentatge dirigit
0h
Aprenentatge autònom
6h

Desenvolupament del tema "Codis BCH binaris"

Desenvolupament del tema "Codis BCH binaris". L'estudiant escolta, pren apunts, pregunta el que no entén i respon les preguntes del professor.
Objectius: 4
Continguts:
Teoria
6h
Problemes
0h
Laboratori
3h
Aprenentatge dirigit
0h
Aprenentatge autònom
7h

Desenvolupament del tema "Codis de Reed-Solomon"

Desenvolupament del tema "Codis de Reed-Solomon". L'estudiant escolta, pren apunts, pregunta el que no entén i respon les preguntes del professor.
Objectius: 4
Continguts:
Teoria
6h
Problemes
0h
Laboratori
1h
Aprenentatge dirigit
0h
Aprenentatge autònom
4h

Resolución de problemas 2

Al llarg del curs s'hauran de presentar per escrit un mínim de dos problemes completament resolts
Objectius: 3 4
Setmana: 13
Tipus: examen de laboratori
Teoria
0h
Problemes
0h
Laboratori
0.5h
Aprenentatge dirigit
0h
Aprenentatge autònom
2.3h

Treball sobre un tema de l'assignatura

Treball sobre un tema relacionat amb l'assignatura on, a més del contingut, també s'avaluarà l'ús solvent dels recursos d'informació.
Objectius: 1 2 3 4
Setmana: 14
Tipus: examen de teoria
Teoria
1h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
10h

Examen final

Examen final sobre els continguts 4 a 8
Objectius: 3 4
Setmana: 15 (Fora d'horari lectiu)
Tipus: examen de teoria
Teoria
3h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
17h

Metodologia docent

En les sessions de teoria el professor explica els temes teòrics amb exemples i problemes. Es combina tant la part magistral, en la qual el professor exposa, explica i exemplifica els conceptes de l'assignatura, com l'interacció amb els alumnes.

A les sessions de laboratori, i durant les hores d'estudi personal, els estudiants han d'intentar resoldre problemes d'una col lecció. El professor dona suport a l'estudiant amb les dificultats que se li plantegin. Es pretén que els estudiants prenguin la iniciativa en la resolució de problemes, avaluïn les seves solucions i aprenguin dels seus errors.

Mètode d'avaluació

Hi haurà dos examnes parcials.


La nota de curs es calcularà fent la mitjana dels dos examens.

Bibliografia

Bàsica:

Complementaria:

Web links

Capacitats prèvies

L'alumne hauria de:
(a) conéixer la funció logaritme i les seves propietats;
(b) propietats elementals de distribucions de probabilitat finites i variables aleatòries;
(c) conèixer els anells d'enters modulars i saber-ne fer càlculs;
(d) conèixer els conceptes bàsics d'espais vectorials: sistemes d'equacions lineals, dependència i independència lineal, base i dimensió, operacions amb matrius (sumes, productes) i calcular inverses;
(d) conèixer les propietats bàsiques dels polinomis i saber-ne operar amb ells.