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

Orari del corso:

• lunedí II fascia (46)
• mercoledí II fascia (49)
• giovedí I fascia (44)

Argomenti trattati a lezione

1. 28 Settembre 2006. Presentazione del corso. Codici di sorgente: panoramica. Codici B-LV. Alberi di codice e univoca decodificabilità. Decodificabilità istantanea e non.
2. 2 Ottobre 2006. Disuguaglianza di Kraft-McMillan. Sufficienza dei codici a prefisso. Probabilità di emissione; lunghezza media di un codice. Entropia. Divergenza.
3. 4 Ottobre 2006. I Teorema di Shannon. 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. 9 Ottobre 2006. Introduzione al codice di Huffman: geminazione e taglio. Teorema di preservazione ottimalità per geminazione (opportuna). Esempio. Il codice di Huffman. Entropia condizionata, mutua informazione.
5. 12 Ottobre 2006. Tipi. Dimensioni e numero dei tipi. Codice multinomiale e sua asintotica ottimalità. Codici LV-B. Motivazioni e generalità.
6. 16 Ottobre 2006. Famiglie esaurienti, a prefisso e complete. Contro-disuguaglianza di Kraft. Generazione di famiglie complete. Generazione di famiglie complete. Relazioni tra tasso ed entropia.
7. 18 Ottobre 2006. Alberi e Codici di Tunstall. Ottimalità degli stessi. 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.
8. 19 Ottobre 2006. Codice universale di Ziv Lempel. Codice universale di Lempel, Ziv e Welch. Codice universale di Burrows-Wheeler.
9. 23 Ottobre 2006. 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.
10. 25 Ottobre 2006. Codici δ-tipici.
11. 28 Ottobre 2005. Secondo Teorema di Shannon. Codici LV-LV. Limiti e codici asintoticamente ottimi.
12. 26 Ottobre 2006. Complessità di Kolmogorov (incondizionata e condizionata). Indipendenza dal formalismo. Limiti superiori. Complessità di Kolmogorov di una stringa binaria in un "tipo".
13. 30 Ottobre 2006. 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 e codice di Hadamard.
14. 02 Novembre 2006. 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). Calcolo e significato della capacità su alcune tipologie di canale CSB.
15. 06 Novembre 2006. Calcolo dell acapacità sul canale con cancellazione e confronti con il CSB. 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.
16. 8 Novembre 2006. Limitazioni di Singleton e Plotkin. Limitazioni di Hamming e Gilbert.
17. 9 Novembre 2006. Significato asintotico delle limitazioni di Hamming e Gilbert. Il problema del covering: esempio dei sistemi ridotti. Codici Correttori di Errore: introduzione ai codici algebrici. Campi finiti: con p elementi e con p^r elementi. Interpretazione polimoniale. Matrice generatrice G (matrici equivalenti e in forma canonica).
18. 13 Novembre 2006. Matrice di Controllo H dei codici algebrici. Peso minimo di un codice lineare. Esempio: Bit di parità e Ripetizione come codici lineari. Sindrome. Decodifica usando la Tabella di Slepian. Codice di Hamming binario.
19. 15 Novembre 2006. Codice di Hamming q-ario ed esteso. Codici BCH. Introduzione, principi generali ed esempio dettagliato di codice BCH binario 2-correttore.
20. 16 Novembre 2006. Codici di Reed-Müller: Rappresentazione algebrica di funzioni booleane, codifica e decodifica con correzione di errori. Valutazione del corso.
21. 19 Novembre 2006. Codici ciclici. Definizioni principali, polinomio generatore, teorema principale (no dim). Matrice generatrice ed esempio. 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.
22. 21 Novembre 2006. Progetto dei codici ciclici a partire dalle radici primitive dell'unità e relazioni con la distanza minima. Cenni ai codici di Reed e Solomon.
23. 22 Novembre 2006. Codici convolutivi e l'algoritmo di Viterbi.
24. 26 Novembre 2006. Esercitazione in vista dell'esame.