TEORIA DELL'INFORMAZIONE
cod. 03551

Anno accademico 2011/12
1° anno di corso - Primo semestre
Docente
Settore scientifico disciplinare
Telecomunicazioni (ING-INF/03)
Field
Ingegneria delle telecomunicazioni
Tipologia attività formativa
Caratterizzante
48 ore
di attività frontali
6 crediti
sede:
insegnamento
in - - -

Obiettivi formativi

Finalità

Il corso si propone di presentare i principali risultati della teoria dell'informazione con approccio rigoroso e nella prospettiva dei sistemi di trasmissione, di elaborazione e di memorizzazione di segnali.

Prerequisiti

- - -

Contenuti dell'insegnamento

Introduzione alla teoria dell'informazione

Programma esteso

LEZIONE 1:
INTRODUZIONE:
Organizzazione del corso, obiettivi, testo (Cover Thomas II Ed), modalità esami. Descrizione panoramica del corso, motivazioni, applicazioni. Assegnata lettura cap 1 del testo. Giustificazione fisica e definizione di entropia. Esempi di calcolo di entropia. Fino a par 2.2 escluso.

LEZIONE 2:
Definizione di entropia congiunta, condizionata, esempio 2.2.1. Entropia relativa, informazione mutua, e loro relazione. Regole della catena per P e H, con dimostrazione.

LEZIONE 3:
Ripasso concetti precedenti, entropia relativa condizionata, Inf. mutua condizionata, regole della catena per I e D, con dim. Disuguaglianze per D, I , max di H, min di H, H(X|Y)<=H(X) e generalizzazione. Funzioni convesse, disuguaglianza di Jensen, esempio: media aritmetica >= media geometrica.

LEZIONE 4:
Prima ora: logsum inequality, convessità di D, concavità di H. Concavità di I in p(x) e convessità in p(y|x). Esercizio: mixing aumenta l'entropia. Seconda ora: Definizione di catena di Markov e prime proprietà per 3 RV X,Y,Z. Data processing inequality. Contresempio.

LEZIONE 5:
Prima ora: Statistiche sufficienti: definizione in termini di informazione mutua. Esempi: numero di successi in prove ripetute; media campione nella stima della media comune a un vettore di VA gaussiane indipendenti. Statistica sufficente e test delle ipotesi: teorema di fattorizzazione. Seconda ora: disuguaglianza di Fano. Esercizio 2.32 risolto in classe.

LEZIONE 6:
Esercitazione: risolti in classe esercizi 2.5, 2.4, 2.27, 2.30 (dopo breve introduzione al metodo dei moltiplicatori di Lagrange), 2.21.

LEZIONE 7:
Cap 3 AEP: introduzione. Richiami teoria probabilità: convergenza i.p., Disug. Chebychev, Weak law of large numbers, AEP. Insieme tipico e proprietà. Esempio con sequenze binarie.

LEZIONE 8:
Prima ora: relazione tra l'insieme tipico ed insiemi ad alta probabilità. Teorema 3.3.1 dimostrato in classe. Seconda ora: Esercitazione. Risolti in classe esercizi 3.8, 3.9. Cap4: entropy rates: introduzione. Definizione di processo stocastico tempo discreto e stazionarietà.

LEZIONE 9:
Prima ora: introduzione alle catene di markov (8 lucidi): matrice di transizione, legge di aggiornamento (chapman kolmogorov), distribuzione stazionaria. Esempio a due stati: digramma degli stati, evoluzione asintotica verso la distribuzione limite. Calcolo col bilanciamento dei flussi. Seconda ora: Entropy rate H e H'. H=H' per processi stazionari. Enunciato del AEP per sorgenti staz. ergodiche (Shannon/Breiman/McMillan). Calcolo esplicito H per DTMC. Esempi

LEZIONE 10:
Matrici doppio stocastiche e distribuzione di equilibrio uniforme. Connessioni con l'entropia definita in termodinamica statistica: DTMC sui microstati con matrice di transiz. doppio stocastica. L'entropia aumenta verso quella di equilibrio. Esempio 4 (eq 4.50-4.52). Hidden Markov models: entropy rate.

LEZIONE 11:
Esercitazione: Es. 4.1 mixing increases entropy. Condizioni affinche l'osservabile Y in un HMM sian una DTMC. Esempio in cui Y non è una DTMC. Iniziato punto a. Es. 4.18 Entropy Rate di Processo stazionario ma non ergodico.

LEZIONE 12:
Esercitazione: Prima ora: finito Es. 4.18 Entropy Rate di Processo stazionario ma non ergodico (punti b, c). Seconda ora: Es 4.10 entropy rate di un second order markov process: studio della catena nascosta. Accennato Es. 4.6.

LEZIONE 13:
Cap5: Compressione dei dati. Esempi di codici. Diseg. di Kraft. Ricerca di codici ottimi coi moltiplicatori di Lagrange. Noiseless coding theorem.

LEZIONE 14:
Commenti sul I teorema di Shannon: quando p non è diadica. Codici quasi-ottimi di Shannon. Super-codici di Shannon sono ottimi asintoticamente. Costo aggiuntivo sulla lunghezza ottima L quando si una PMF q diversa dalla vera p. Teorema di McMillan: ogni codice univocamente decodificabile soddisfa la disug di Kraft. Introduzione ai codici di Huffman: esempi 1, 2.

LEZIONE 15:
Codici di Huffman: esempio 3 (dummy symbols), esercizio 5.32, esempio 5.73 (set diversi di lunghezze ottime). Ottimalità competitiva dello shannon code. Dimostrazione dell'ottimalità degli Huffman codes.

LEZIONE 16:
Prima ora: Compressione ottima di sorgenti di Markov. Algoritmo Lempel Ziv di codifica universale: esempio di funzionamento. Seconda ora: Capacità di Canale: introduzione, definizione di canale discreto senza memoria, esempi di calcolo delle capacità: canale ideale, canale rumoroso a uscite separate, noisy typewriter.

LEZIONE 17:
Calcolo capacità BSC, BEC, canali simmetrici, debolmente simmetrici e simmetrici rispetto Gallager. Convessità della C su insieme delle PMF convesso; cenni a tecniche di calcolo del max I.

LEZIONE 18:
Introduzione alla dimostrazione del II teorema di Shannon. Codifica di canale, idee sulla decodifica per sequenze tipiche. Def. di insieme cong. tipico e dim. delle sue proprietà. Def. di prob. media, massima per parola, tasso raggiungibile, e capacità operativa di canale. Enunciato del II teorema di Shannon.

LEZIONE 19:
I ora: dimostrazione della parte diretta del II teorema di Shannon. II ora: dim. del converso del II teorema di Shannon.

LEZIONE 20:
Prima ora: teorema della codifica congiunta di sorgente e canale Seconda ora: Esercizi sulla capacità di canale: 7.8, 7.9 (Z channel) 7.3 (memory increases capacity) 7.12 (unused symbol). Assegnato 7.23.

LEZIONE 21:
Entropia differenziale (cap 9): definizione, esempi (uniforme, gauss); AEP, proprietà insieme tipico. 2^h=lato dell'insieme tipico. Entopia diff congiunta e condizionata. Es: Gaussiana multivariata. Entropia relativa e informazione mutua. Disuguaglianze. Hadamard. Traslazioni e cambio scala. Gauss multivariata massimiza l'entropia per matrice di covarianza assegnata.

LEZIONE 22:
Informazione mutua X discreta Y contnua. Esempio di calcolo per PAM con simboli equiprobabili su canale discrete-time memoryless additivo gaussiano (DTMAGC). Calcolo Capacità del DTMAG. Teorema del campionamento e formula di shannon. Rumore gaussiano è un caso peggiore per C.

LEZIONE 23:
Canali Gaussiani in Parallelo: calcolo Capacità. Canali additivi gaussiani tempo discreto (DTAGC) con memoria: def. di capacità. Matrici Toeplitz: Toeplitz distribution theorem (traccia della dimostrazione). Calcolo capacità del canale DTAGC con memoria (water-pouring).

LEZIONE 24:
Canale additivo Gaussiano Tempo-continuo con memoria (CTAGC): calcolo capacità con rumore equivalente di ingresso. Base di Karhunen-Loeve e Toeplitz distribution theorem nel continuo. Capacità del canale CTAGC. Esempi. Entropy rate di processi stazionari Gaussiani.

Bibliografia

Testo Seguito
[1] T. M. Cover, J. A. Thomas, "Elements of Information Theory". John Wiley and Sons, 1991.

Testi Complementari
[2] R. Blahut, "Principles and Practice of Information Theory". Addison-Wesley, 1988.
[3] J. Cioffi, "Ch. 8: Fundamental Limits of Coding and Sequences", http://www.stanford.edu/~cioffi

Metodi didattici

Lezioni frontali

Modalità verifica apprendimento

L'esame consiste in una prova orale da concordare col docente, con esercizi e domande teoriche.

Altre informazioni

Per aggiornamenti consultare:
http://www.tlc.unipr.it/bononi/didattica/TI/informazioni.html