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

Orari del corso:

• lunedí II fascia (44)
• martedí II fascia (47)
• venerdí II fascia (42)

Argomenti trattati a lezione

1. 24 Settembre 2007. Presentazione del corso. Discussione sul concetto di informazione.
2. 25 Settembre 2007. Codici di sorgente: panoramica. Codici B-LV. Alberi di codice e univoca decodificabilità. Decodificabilità istantanea e non. Disuguaglianza di Kraft-McMillan. Sufficienza dei codici a prefisso.
3. 01 Ottobre 2007. Probabilità di emissione; lunghezza media di un codice. Entropia. Divergenza. I Teorema di Shannon.
4. 02 Ottobre 2007. 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. 5 Ottobre 2007. Introduzione al codice di Huffman: geminazione e taglio. Teorema di preservazione ottimalità per geminazione (opportuna). Esempio. Il codice di Huffman.
6. 8 Ottobre 2007. Entropia condizionata, mutua informazione. Tipi. Dimensioni e numero dei tipi. Codice multinomiale. Lunghezza del prefisso.
7. 9 Ottobre 2007. 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. 12 Ottobre 2006. Generazione di famiglie complete. Relazioni tra tasso ed entropia. Alberi e Codici di Tunstall. Ottimalità degli stessi.
9. 15 Ottobre 2007. Rapporti asintotici del tasso dei codici di Tunstall con l'entropia della sorgente. Non ottimalità dei codici di Tunstall al di fuori delle famiglie complete. Codice universale di Ziv Lempel.
10. 16 Ottobre 2007. Codice universale di Lempel, Ziv e Welch. Codice universale di Burrows-Wheeler.
11. 19 Ottobre 2007. 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. 22 Ottobre 2007. Codici δ-tipici e Secondo Teorema di Shannon. Codici LV-LV. Limiti e codici asintoticamente ottimi.
13. 26 Ottobre 2007. Complessità di Kolmogorov (incondizionata e condizionata). Indipendenza dal formalismo. Limiti superiori. Complessità di Kolmogorov di una stringa binaria.
14. 29 Ottobre 2007. 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à, codice a ripetizione.
15. 30 Ottobre 2007. Il 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). Significato della capacità del canale. Calcolo della capacità del canale senza rumore.
16. 05 Novembre 2007. Calcolo della capacità sul canale simmetrico binario, con cancellazione e loro confronti. Entropia q-aria e Canale simmetrico q-ario. 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. 6 Novembre 2007. 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.
18. 9 Novembre 2006. Limitazione di Gilbert e significato 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.
19. 12 Novembre 2007. Albegra dei polinomi per i campi finiti. Matrice generatrice G (matrici equivalenti e in forma canonica). Matrice di Controllo H dei codici algebrici. Peso minimo di un codice lineare. Sindrome. Decodifica usando la Tabella di Slepian. Codice di Hamming binario.
20. 13 Novembre 2007. Codice di Hamming q-ario ed esteso. Codici BCH. Introduzione, principi generali ed esempio dettagliato di codice BCH binario 2-correttore.
21. 16 Novembre 2007. Codici di Reed-Müller: Rappresentazione algebrica di funzioni booleane, codifica e decodifica con correzione di errori. Codici ciclici. Definizioni principali, polinomio generatore, teorema principale (no dim).
22. 19 Novembre 2007. 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. 20 Novembre 2007. Progetto dei codici ciclici a partire dalle radici primitive dell'unità e relazioni con la distanza minima. Cenni ai codici di Reed e Solomon. Valutazione del corso.
24. 23 Novembre 2007. Codici convolutivi e l'algoritmo di Viterbi.