Politecnico di Torino
Politecnico di Torino
   
Login  
en
Politecnico di Torino
Anno Accademico 2010/11
01NMONG
Teoria dell'informazione e dei codici
Corso di Laurea Magistrale in Ingegneria Matematica - Torino
Docente Qualifica Settore Lez Es Lab Tut Anni incarico
Benedetto Sergio       80 40 0 0 1
SSD CFU Attivita' formative Ambiti disciplinari
ING-INF/03
MAT/05
6
6
D - A scelta dello studente
D - A scelta dello studente
A scelta dello studente
A scelta dello studente
Presentazione
Il modulo si propone di introdurre i concetti e le tecniche fondamentali della teoria dell'Informazione e dei Codici. La teoria dell'informazione tratta due questioni fondamentali: quanto si possano comprimere dei dati e con quale velocità si possano trasmettere attraverso un canale disturbato mantenendo la fedeltà ad un certo livello prefissato. Essa rappresenta non soltanto uno strumento teorico imprescindibile per l'Ingegneria delle comunicazioni, ma anche una branca molto feconda della probabilità con molteplici applicazioni alla statistica, all'informatica e alla finanza. La teoria dei codici si innesta sulla questione della trasmissione su canale e offre strumenti concreti per raggiungere i limiti teorici previsti dalla teoria dell'informazione. Due sono le questioni fondamentali: la costruzione del codice ed il problema della decodifica. La costruzione di codici con alte prestazioni avviene utilizzando sofisticati strumenti algebrici e di matematica discreta e pone problemi teorici riformulabili come problemi combinatorici e di teoria dei grafi. Decodificare invece vuol dire risolvere un complesso problema di statistica inferenziale; le tecniche più moderne di decodifica utilizzano algoritmi distribuiti su grafi con importanti connessioni con l'ottimizzazione combinatorica e la meccanica statistica.
Risultati di apprendimento attesi
In questo modulo lo studente apprende una serie di concetti fondamentali della teoria dell'informazioni e tecniche efficienti per la costruzione e la decodifica di codici di canale. In primis viene introdotto il concetto di entropia che offre la possibilità di quantificare l'informazione presente in un certo dato e di affrontare il problema della compressione dei dati per il quale vengono poi proposti alcuni algoritmi classici. Collegati al concetto di entropia, ve ne sono altri quali l'entropia relativa e la mutua informazione. Essi permettono di quantificare l'informazione che un dato possiede su di un altro, ad esempio l'informazione che l'uscita di un canale disturbato ha sul corrispondente segnale di ingresso. Essi permettono così di definire il concetto di capacità di un canale e di presentare i risultati teorici di Shannon sulla ridondanza necessaria per trasmettere con fedeltà attraverso i canali disturbati. Nella teoria dei codici lo studente apprende una serie di tecniche matematiche per costruire codici di canale con alte prestazioni e per una loro efficiente valutazione. Queste tecniche mischiano insieme idee algebriche (teoria dei campi finiti), combinatoriche (teoria dei grafi) e fanno uso del cosiddetto metodo probabilistico (media su ensemble) mettendo così insieme concetti che provengono da vari altri corsi e sviluppandoli ulteriormente. Rilevante parte nel corso è costituita dagli algoritmi, in particolare da quelli utilizzati per decodificare un dato trasmesso; in questo modo lo studente si confronta anche con questione cruciali come complessità e con i problemi dell'implementazione numerica.
Prerequisiti / Conoscenze pregresse
Calcolo differenziale in una variabile. Teoria dei campi finiti. Elementi di combinatoria e di probabilità (variabili aleatorie discrete e continue). Elementi di teoria dei processi casuali discreti.
Programma
' Elementi di teoria dell'informazione: entropia e mutua informazione.
' Entropia di sorgenti stazionarie; codifica di sorgente: gli algoritmi di Huffman e di Lempel-Ziv.
' Canali di trasmissione discreti: informazione mutua e capacità.
' Il teorema (diretto e inverso) della codifica di canale di Shannon.
' Codici a blocco lineari. Codificatori, sindromi. Distanza minima e suoi bound. Analisi delle prestazioni.
' Codici convoluzionali. Rappresentazioni di stato e a traliccio.
' Codici concatenati (i 'turbo' codici) e codici a bassa densità. Analisi delle prestazioni attraverso la media su 'ensemble'
' Tecniche di decodifica 'soft' di codici a traliccio. L'algoritmo di Viterbi. L'algoritmo BCJR.
' La decodifica iterativa di codici concatenati e a bassa densità.
Organizzazione dell'insegnamento
All'incirca 1/3 del corso sarà dedicato ad esercitazioni in aula. Verranno anche assegnati dei compiti a casa che saranno corretti.
Testi richiesti o raccomandati: letture, dispense, altro materiale didattico
I testi, scelti tra quelli elencati, saranno comunicati a lezione dal docente titolare dell'insegnamento
S. Benedetto, E. Biglieri, Principles of digital transmission with wireless applications
T. M. Cover, J. A. Thomas, Elements of Information theory
T. Richardson, R. Urbanke, Modern coding theory

Saranno anche disponibili dispense in rete su parti degli argomenti del corso.
Criteri, regole e procedure per l'esame
Homeworks e prova orale
Orario delle lezioni
Statistiche superamento esami

Programma provvisorio per l'A.A.2010/11
Indietro



© Politecnico di Torino
Corso Duca degli Abruzzi, 24 - 10129 Torino, ITALY
WCAG 2.0 (Level AA)
Contatti