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

Orari del corso:

• martedí I fascia (5)
• Giovedí IV fascia (14:30 - aula H)

Argomenti trattati a lezione

1. 30 Settembre 2008. Presentazione del corso. Discussione sul concetto di informazione.
2. 1 Ottobre 2008. Codici di sorgente: panoramica. Codici B-LV. Alberi di codice e univoca decodificabilità. Decodificabilità istantanea e non. Disuguaglianza di Kraft-McMillan.
3. 7 Ottobre 2008. Sufficienza dei codici a prefisso. Probabilità di emissione; lunghezza media di un codice. Entropia. Divergenza. I Teorema di Shannon.
4. 9 Ottobre 2008. 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.
5. 15 Ottobre 2008. Introduzione al codice di Huffman: geminazione e taglio. Teorema di preservazione ottimalità per geminazione (opportuna). Esempio. Il codice di Huffman.
6. 17 Ottobre 2008. Entropia condizionata, mutua informazione. Tipi. Dimensioni e numero dei tipi. Codice multinomiale. Lunghezza del prefisso.
7. 21 Ottobre 2008. Ottimalità asintotica del codice multinomiale. Descrizione con variabili aleatorie di una sorgente di Informazione. LV-B. Motivazioni e generalità. Famiglie esaurienti, a prefisso e complete. Contro-disuguaglianza di Kraft.
8. 23 Ottobre 2008. Generazione di famiglie complete. 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. 15 Ottobre 2008. Non ottimalità dei codici di Tunstall al di fuori delle famiglie complete. Codice universale di Ziv Lempel. Cenni alla variante deflate.
10. 30 Ottobre 2008. Codice universale di Lempel, Ziv e Welch. Codice universale di Burrows-Wheeler.
11. 4 Novembre 2008. Codici LV-LV. Limiti e codici asintoticamente ottimi. 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 Ottobre 2008. Codici δ-tipici e Secondo Teorema di Shannon. Introduzione alla Complessità di Kolmogorov
13. 13 Novembre 2008. Complessità di Kolmogorov (incondizionata e condizionata). Indipendenza dal formalismo. Limiti superiori. Complessità di Kolmogorov di una stringa binaria. Complessità di una stringa binaria in un tipo. Confronti con codifica Shannoniana: Codice B-LV indotto dalla Complessità di Kolmogorov e sua ottimalità asintotica.
14. 18 Novembre 2008. Codifica di canale: generalità. Esempi: controllo parità unidimensionale e bidimensionale, codice a ripetizione. Il codice di Hadamard.
15. 20 Novembre 2008. 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).
16. 25 Novembre 2008. Significato della capacità del canale. Calcolo della capacità dei canali: inutile, senza rumore, deterministico. Entropia q-aria e capacità del Canale simmetrico q-ario (e di quello binario come caso particolare). Esercizio: capacità del canale binario con cancellazione.
17. 27 Novembre 2008. 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. Distanza minima di un codice e Tasso di correzione. Relazioni tra tasso di correzione la Probabilità di errore.
18. 1 Dicembre 2008. Limitazioni di Singleton e Plotkin. e Hamming, e Gilbert.
19. 3 Dicembre 2008. 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. Peso minimo di un codice lineare.
20. 16 Dicembre 2008. Matrice generatrice G (matrici equivalenti e in forma canonica). Matrice di Controllo H dei codici algebrici. Sindrome. Decodifica usando la Tabella di Slepian. Codice di Hamming binario ed esteso.
21. 18 Dicembre 2008. Codici BCH. Introduzione, principi generali ed esempio dettagliato di codice BCH binario 2-correttore. Codici di Reed-Müller: Rappresentazione algebrica di funzioni booleane, codifica e decodifica con correzione di errori.
22. 8 Gennaio 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. Esempio: codici di Hamming. Richiamo sulle radici primitive dell'unità nei campi finiti e relativi polinomi minimi.
23. 13 Gennaio 2008. Progetto dei codici ciclici a partire dalle radici primitive dell'unità e relazioni con la distanza minima. Il codice di Reed e Solomon. Valutazione del corso.
24. 15 Gennaio 2008. Codici convolutivi e l'algoritmo di Viterbi.