Teoria dell'Informazione, A.A. 2005/2006

Orari del corso:

• lunedí III fascia - anticipato alle 14:30 - (46),
• giovedí II fascia (46),
• venerdí I (42).

Argomenti trattati a lezione

1. 26 Settembre 2005. Presentazione del corso. Codici di sorgente: panoramica. Codici B-LV. Alberi di codice e univoca decodificabilità. Decodificabilità istantanea e non.
2. 29 Settembre 2004. Disuguaglianza di Kraft-McMillan. Sufficienza dei codici a prefisso. Probabilità di emissione; lunghezza media di un codice. Entropia. Divergenza. I Teorema di Shannon.
3. 10 Ottobre 2005. Codici di Shannon Fano, limitazione superiore di EL per i codici ottimi. Descrizione con variabili aleatorie di una sorgente di Informazione. Tasso del codice. Sorgenti stazionarie e senza memoria. Ottimalità asintotica dei codici di Shannon-Fano.
4. 13 Ottobre 2005. Introduzione al codice di Huffman: geminazione e taglio. Teorema di preservazione ottimalità per geminazione (opportuna). Esempio. Assemblea per il DDL Moratti.
5. 14 Ottobre 2005. Il codice di Huffman. Entropia condizionata, mutua informazione. Tipi.
6. 17 Ottobre 2005. Dimensioni e numero dei tipi. Codice multinomiale e sua asintotica ottimalità. Codici LV-B. Famiglie esaurienti, a prefisso e complete. Contro-disuguaglianza di Kraft. Generazione di famiglie complete.
7. 20 Ottobre 2005. 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.
8. 21 Ottobre 2005. Non ottimalità dei codici di Tunstall al di fuori delle famiglie complete. Codice universale di Ziv Lempel.
9. 24 Ottobre 2005. Codice universale di Lempel, Ziv e Welch. Codice universale di Burrows-Wheeler. Codifica B-B. Valutazione del tasso in codifica priva di errore. Modelli con errore: ricerca di una famiglia ottima.
10. 27 Ottobre 2005. Determinazione delle dimensioni di un tipo T con il metodo probabilistico. Codici δ-tipici.
11. 28 Ottobre 2005. Secondo Teorema di Shannon. Codici LV-LV. Limiti e codici asintoticamente ottimi.
12. 3 Novembre 2005. Complessità di Kolmogorov (incondizionata e condizionata). Limiti superiori. Esempi.
13. 4 Novembre 2005. Complessità di Kolmogorov di una stringa binaria in un "tipo". Confronti con codifica Shannoniana: Codice B-LV indotto dalla Complessità di Kolmogorov e sua ottimalità asintotica.
14. 7 Novembre 2005. Codifica di canale: generalità. Esempi: controllo parità, codice a ripetizione e codice di Hadamard. 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).
15. 10 Novembre 2005. Calcolo e significato della capacità su alcune tipologie di canale (inutile, senza errori, deterministico, CSB, CSQ). Confronti. Discriminazione di Ipotesi Statistiche: a massima verosimiglianza e a massima probabilità a posteriori.
16. 14 Novembre 2005. Decodifica di canale a massima verosimiglianza su CSB, CSQ: decodifica a minima distanza di Hamming. Distanza minima di un codice. tasso di correzione. Limitazioni di Singleton e Plotkin. Limitazioni di Hamming e Gilbert.
17. 17 Novemre 2005. Significato asintotico delle limitazioni di Hamming e Gilbert. Relazioni tra tasso di correzione la Probabilità di errore. Il problema del covering: esempio dei sistemi ridotti. Codici Correttori di Errore: introduzione ai codici algebrici.
18. 18 Novembre 2005: Campi finiti: con p elementi e con p^r elementi. Interpretazione polimoniale. Matrice generatrice G (matrici equivalenti e in forma canonica). Peso minimo di un codice lineare. Esempio: Bit di parità e Ripetizione come codici lineari.
19. 21 Novembre 2005. Matrice di Controllo H dei codici algebrici. Sindrome. Decodifica usando la Tabella di Slepian. Codice di Hamming: binario ed esteso.
20. 24 Novembre 2005: Codici BCH. Introduzione, principi generali ed esempio dettagliato di codice BCH binario 2-correttore.
21. 25 Novembre 2005. Codici di Reed-Müller: Rappresentazione algebrica di funzioni booleane, codifica e decodifica con correzione di errori.
22. 28 Novembre 2005. Codici ciclici. Definizioni principali, polinomio generatore, teorema principale (no dim). Matrice generatrice ed esempio. Valutazione del corso. 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. 1 Dicembre 2005. Progetto dei codici ciclici a partire dalle radici primitive dell'unità e relazioni con la distanza minima. Cenni ai codici di Reed e Solomon.
24. 2 Dicembre 2005. Codici convolutivi e l'algoritmo di Viterbi. Indicazioni sull'esame.