Teoria dell'Informazione, A.A. 2002/2003

Orari del corso:

• lunedí 16:05-17:45 (51),
• giovedí 14:15-16:00 (51),
• venerdí 9:00-10:40 (3).

Argomenti trattati a lezione

1. 13 Gennaio 2003. Presentazione del corso. Codici di sorgente: panoramica. Codici B-LV. Alberi di codice e univoca decodificabilità.
2. 16 Gennaio 2003. Decodificabilità istantanea e non. Disuguaglianza di Kraft-McMillan. Sufficienza dei codici a prefisso. Probabilità di emissione; lunghezza media di un codice. Entropia e Divergenza.
3. 17 Gennaio 2003. 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.
4. 27 Gennaio 2003. Ottimalità asintotica dei codici di Shannon-Fano. Il codice di Fano. Geminazione, Taglio e codice di Huffman.
5. 30 Gennaio 2003. Entropia condizionata, mutua informazione, autoinformazione. Relazioni tra queste grandezze. Codice multinomiale e sua asintotica ottimalità.
6. 31 Gennaio 2003. Codici LV-B. Famiglie esaurienti, a prefisso e complete. Generazione di famiglie complete. Relazioni tra tasso ed entropia.
7. 6 Febbraio 2003. Alberi e Codici di Tunstall. Ottimalità degli stessi e rapporti asintotici con l'entropia della sorgente. Non ottimalità dei codici di Tunstall al di fuori delle famiglie complete.
8. 7 Febbraio 2003: Codice universale di Ziv Lempel. Codici B-B. Valutazione del tasso in codifica priva di errore. Modelli con errore: ricerca di una famiglia ottima.
9. 10 Febbraio 2003: Codici δ-tipici e Secondo Teorema di Shannon.
10. 13 Febbraio 2003: Codici LV-LV. Limiti e codici asintoticamente ottimi. Il codice universale di Burrows Wheeler.
11. 14 Febbraio 2004: 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.
12. 17 Febbraio 2003: Esempi. Capacità di un canale e Teorema di Shannon di canale (no dim). Calcolo e significato della capacità su alcune tipologie di canale (inutile, senza errori, deterministico, CSB).
13. 20 Febbraio 2003: Calcolo e significato della capacità su CSQ e canale binario con cancellazione. Confronti. Discriminazione di Ipotesi Statistiche: a massima verosimiglianza e a massima probabilità a posteriori.
14. 21 Febbraio 2003: Decodifica di canale a massima verosimiglianza sul canale binario con cancellazione. Decodifica di canale a massima verosimiglianza su CSB, CSQ: decodifica a minima distanza di Hamming. Distanza minima di un codice, tasso di correzione e relazioni con la Probabilità di errore.
15. 24 Febbraio 2003: Limitazioni di Singleton, Plotkin, Hamming e Gilbert.
16. 27 Febbraio 2003: Forma asintotica delle limitazioni di Hamming e Gilbert e considerazioni generali. Codici Correttori di Errore: introduzione ai codici algebrici.
17. 28 Febbraio 2003: Matrice generatrice G (matrici equivalenti e in forma canonica) e Matrice di Controllo H. Peso minimo di un codice. Sindrome. Decodifica usando la Tabella di Slepian.
18. 3 Marzo 2003: Codici di Hamming: binario, q-ario ed esteso. Perfezione del codice di Hamming.
19. 6 Marzo 2003: Codici Perfetti: definizioni e risultati principali. Cenni ai codici isolati di Golay. Introduzione ai codici BCH.
20. 7 Marzo 2003: Operazioni su campi finiti: polinomio irriducibile, somme, moltiplicazioni, calcolo dell'inversa, del cubo, e risoluzione di equazioni di secondo grado. Esempio dettagliato di codice BCH binario 2-correttore.
21. 7 Marzo 2003: Codici di Reed-Müller: Rappresentazione algebrica di funzioni booleane, codifica e decodifica con correzione di errori.
22. 10 Marzo 2003: Codici ciclici. Definizioni principali, polinomio generatore, matrice generatrice e di controllo. Esempio: codici di Hamming. Scelta di g e h usando le radici primitive dell'unità.
23. 13 Marzo 2003: Progetto dei codici ciclici a partire dalle radici primitive dell'unità e relazioni con la distanza minima. Codici convolutivi e l'algoritmo di Viterbi.
24. 14 Marzo 2003: Codici segreti. Breve storia della crittografia e principali risultati della crittografia a chiave pubblica.

Qualche link interessante:

• L'articolo originale di Claude Shannon
• Il sito del corso di Teoria di Informazione di Francesco Fabris (con elenco riferimenti utili)
• Uso dei codici di Ziv Lempel e Huffman in gzip.
• Codice di Burrows Wheeler usato in bzip2
• The Error Correcting Codes (ECC) Site
• Codifica dei dati negli SMS (SOB).
• Algoritmo di Viterbi per i Codici Convoluzionali
• Un po' di storia della crittografia e le frequenze di alcune lingue.