Transmissió i Codificació de la Informació

• Professorat
• Hores setmanals
• Competències
• Objectius
• Continguts
• Activitats
• Metodologia docent
• Mètode d'avaluació
• Bibliografia
• Web links
• Capacitats prèvies

Professorat

Responsable

• Francesc Tiñena Salvañà ( )

Altres

• Rafel Farré Cirera ( )

Hores setmanals

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: G6.3, CTI1.4, CTI3.3,
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

Metodologia docent

Mètode d'avaluació

Bibliografia

Bàsica:

• Apunts de Teoria de la Informació i Codificació - Farré, Rafel, 2003.
  
• Informació i codis - Brunat Blay, Josep M; Ventura Capell, Enric, Edicions UPC, 2001. ISBN: 8483015285
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991002316969706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• A Course in algebraic error-correcting codes - Ball, Simeon, Birkhäuser, [2020]. ISBN: 9783030411527
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991004198669706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Introduction to coding theory - Bierbrauer, Jürgen, CRC Press, 2017.
  http://cataleg.upc.edu/record=99100492344570671~S1*cat

Complementaria:

• A first course in coding theory - Hill, R, Clarendon Press , 1988. ISBN: 0198538030
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991000254769706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Reed-Solomon codes and their applications - Wicker, Stephen B.; Bhargava, Vijay K. (editores), IEEE Press , 1994. ISBN: 078031025X
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991001296739706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Foundations of coding: theory and applications of error-correcting codes, with an introduction to cryptography and information theory - Adámek, J, Wiley , 1991. ISBN: 0471621870
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991000948639706711&context=L&vid=34CSUC_UPC:VU1&lang=ca

Web links

• http://www.sagemath.org

Capacitats prèvies