Teoria dell'Informazione, A.A. 2009/2010

Orari del corso:

• lunedí II fascia (10:30 - 5)
• mercoledí IV fascia (14:30 - 5)

Argomenti trattati a lezione

1. 28 Settembre 2009. Presentazione del corso. Discussione sul concetto di informazione. Codici di sorgente: panoramica. Codici B-LV. Alberi di codice e univoca decodificabilità. Decodificabilità istantanea e non.
2. 30 Settembre 2009. (1 ora) Disuguaglianza di Kraft-McMillan.
3. 5 Ottobre 2009. Sufficienza dei codici a prefisso. Probabilità di emissione; lunghezza media di un codice. Entropia. Divergenza. I Teorema di Shannon.
4. 7 Ottobre 2009. Codici di Shannon Fano, limitazione superiore di EL per i codici ottimi. Tasso del codice. Entropia della distribuzione congiunta. Ottimalità asintotica dei codici di Shannon-Fano. Introduzione al codice di Huffman: geminazione e taglio.
5. 12 Ottobre 2009. Teorema di preservazione ottimalità per geminazione (opportuna). Esempio. Il codice di Huffman. Entropia condizionata, mutua informazione e loro relazioni.
6. 14 Ottobre 2009. Tipi. Dimensioni e numero dei tipi. Codice multinomiale. Lunghezza del prefisso. Ottimalità asintotica del codice multinomiale.
7. 19 Ottobre 2009. Descrizione con variabili aleatorie di una sorgente di Informazione. LV-B. Motivazioni e generalità. Famiglie esaurienti, a prefisso e complete. Contro-disuguaglianza di Kraft. Generazione di famiglie complete.
8. 21 Ottobre 2009. Relazioni tra tasso ed entropia. Alberi e Codici di Tunstall. Ottimalità degli stessi. Rapporti asintotici del tasso dei codici di Tunstall con l'entropia della sorgente.
9. 26 Ottobre 2009. Non ottimalità dei codici di Tunstall al di fuori delle famiglie complete. Codice universale di Ziv Lempel.
10. 28 Ottobre 2009 (1 ora). Cenni alla variante deflate di ziv-lempel come implementata nei compressori commerciali. Codice universale di Burrows-Wheeler.
11. 9 Novembre 2009. Codice universale di Lempel, Ziv e Welch. Codifica B-B. Valutazione del tasso in codifica priva di errore. Modelli con errore: ricerca di una famiglia ottima. Determinazione delle dimensioni di un tipo T con il metodo probabilistico.
12. 11 Novembre 2009. Codici δ-tipici e Secondo Teorema di Shannon. Codici LV-LV. Limiti e codici asintoticamente ottimi.
13. 16 Novembre 2009. Introduzione alla Complessità di Kolmogorov Complessità di Kolmogorov (incondizionata e condizionata). Indipendenza dal formalismo. Limiti superiori. Complessità di Kolmogorov di una stringa binaria.
14. 18 Novembre 2009. Complessità di una stringa binaria in un tipo. Confronti con codifica Shannoniana: Codice B-LV indotto dalla Complessità di Kolmogorov e sua ottimalità asintotica. Codifica di canale: generalità. Esempi: controllo parità unidimensionale e bidimensionale, codice a ripetizione. Il codice di Hadamard.
15. 23 Novembre 2009. Il modello del canale: matrice di canale, funzioni di codifica e decodifica, tasso e probabilità di errore. Esempi. Capacità di un canale e Teorema di Shannon di canale (no dim). Significato della capacità del canale. Calcolo della capacità dei canali: inutile, senza rumore, deterministico.
16. 25 Novembre 2009. Entropia q-aria e capacità del Canale simmetrico q-ario (e di quello binario come caso particolare). Esercizio: capacità del canale binario con cancellazione. Discriminazione di Ipotesi Statistiche: a massima verosimiglianza e a massima probabilità a posteriori. Decodifica di canale a massima verosimiglianza su CSB, CSQ: decodifica a minima distanza di Hamming.
17. 30 Novembre 2009. Distanza minima di un codice e Tasso di correzione. Relazioni tra tasso di correzione la Probabilità di errore. Limitazioni di Singleton e Plotkin. e Hamming, e Gilbert.
18. 2 Dicembre 2009. Studio asintotico delle limitazioni di Hamming e Gilbert. Codici Correttori di Errore: introduzione ai codici algebrici. Campi finiti: con p elementi e con p^r elementi. Albegra dei polinomi per i campi finiti.
19. 9 Dicembre 2009. Matrice generatrice G (matrici equivalenti e in forma canonica). Peso minimo di un codice lineare. Matrice di Controllo H dei codici algebrici. Sindrome. Decodifica usando la Tabella di Slepian.
20. 14 Dicembre 2009. Codice di Hamming binario ed esteso. Codici BCH. Introduzione, principi generali ed esempio dettagliato di codice BCH binario 2-correttore.
21. 16 Dicembre 2009. Codici di Reed-Müller: Rappresentazione algebrica di funzioni booleane, codifica e decodifica con correzione di errori.
22. 21 Dicembre 2009. Codici ciclici. Definizioni principali, polinomio generatore, teorema principale (no dim). Esempi su matrice generatrice dei codici ciclici. Polinomio di controllo h e matrice H corrispondente.
23. 11 Gennaio 2010. Richiamo sulle radici primitive dell'unità nei campi finiti e relativi polinomi minimi. Uso dei polinomi minimi per determinare il polinomio generatore. Valutazione del corso.
24. 13 Gennaio 2010. Progetto dei codici ciclici a partire dalle radici primitive dell'unità e relazioni con la distanza minima. Il codice di Reed e Solomon.
25. 18 Gennaio 2010. Codici convolutivi e l'algoritmo di Viterbi.