Teoria dell'Informazione e Crittografia 2011/2012

Orari del corso:

• lunedí I fascia, aula 5
• martedí I fascia, aula 5

Argomenti trattati a lezione

1. 26/09/2011. Presentazione del corso.

   PARTE 1

   Codici di sorgente: panoramica. Codici B-LV. Alberi di codice e univoca decodificabilità. Alberi e codici prefix-free (in breve, a prefisso).
2. 27/09/2011. Decodificabilità istantanea e non. Disuguaglianza di Kraft-McMillan. Sufficienza dei codici a prefisso. Probabilità di emissione; lunghezza media di un codice. Entropia.
3. 03/10/2011. Divergenza. I Teorema di Shannon. Codici di Shannon Fano, limitazione superiore di EL per i codici ottimi. Tasso del codice.
4. 04/10/2011. Entropia della distribuzione congiunta. Ottimalità asintotica dei codici di Shannon-Fano. Introduzione al codice di Huffman: geminazione e taglio. Teorema di preservazione ottimalità per geminazione (opportuna).
5. 10/10/2011. Il codice di Huffman. Entropia condizionata. Tipi. Dimensioni e numero dei tipi. Codice multinomiale. Lunghezza del prefisso. Lunghezza del suffisso. Ottimalità asintotica del codice multinomiale.
6. 11/10/2011. LV-B. Motivazioni e generalità. Famiglie esaurienti, a prefisso e complete. Generazione di famiglie complete. Relazioni tra tasso ed entropia. Alberi e Codici di Tunstall e cenni all'ottimalità degli stessi.
7. 17/10/2011. Non ottimalità dei codici di Tunstall al di fuori delle famiglie complete. Codici LV-LV. Codice universale di Ziv Lempel
8. 18/10/2011. Studio della compressione massima di Ziv Lempel. Codice universale di Lempel, Ziv e Welch. Codice universale di Burrows-Wheeler.
9. 24/11/2011. Brevi cenni alla codifica B-B e all'esistenza dei codici δ-tipici.

   PARTE 2

   Codifica di canale: generalità. Esempi: controllo parità unidimensionale e bidimensionale, codice a ripetizione. Il codice di Hadamard. Tasso di trasmissione e tasso di correzione.
10. 7/11/2011. 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 simmetrico binario.
11. 8/11/2011. Esercizio: Canale simmetrico q-ario e del canale con cancellazione. Decodifica di canale a massima verosimiglianza su CSB, CSQ: decodifica a minima distanza di Hamming. Distanza minima di un codice e relazioni con la capacità di correzione. Relazioni tra tasso di correzione la Probabilità di errore. Relazioni tra Tasso di trasmissione e Tasso di correzione, e loro relazioni nei codici. Cenni alle relazioni asintotiche denominate: limitazioni di Singleton e Plotkin. e Hamming, e Gilbert.
12. 14/11/2011. 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 (Qualche appunto). Matrice generatrice G (matrici equivalenti e in forma canonica). Peso minimo di un codice lineare.
13. 15/11/2011. Matrice di Controllo H dei codici algebrici. Sindrome. Decodifica usando la Tabella di Slepian. Codice di Hamming binario ed esteso.
14. 21/11/2011. Codici BCH. Introduzione. Codici BCH 2-correttori. Esempio.
15. 22/11/2011. Codici ciclici. Definizioni principali, polinomio generatore g, teorema principale. Esempi su matrice generatrice dei codici ciclici. (Qualche appunto).
16. 28/11/2011. Polinomio di controllo h e matrice H corrispondente Richiamo sulle radici primitive dell'unità nei campi finiti e relativi polinomi minimi. Uso dei polinomi minimi per determinare il polinomio generatore.
17. 29/11/2011. Progetto dei codici ciclici a partire dalle radici primitive dell'unità e relazioni con la distanza minima. Il codice di Reed e Solomon.
18. 05/12/2011. Codici convolutivi e l'algoritmo di Viterbi.

    PARTE 3

    Crittografia. Storia e terminologia. Cifrari a sostituzione monoalfabetica. Cifrari omofonici e nomenclatori. LUCIDI LEZIONE.
19. 06/12/2011. Cifrari polialfabetici. Tecniche per scoprire lunghezza della chiave e chiave. Esempio pratico di cifrazione Vigenere e sua decrittazione. LUCIDI LEZIONE. Programmino Prolog per l'automazione di quanto appena visto.
20. 12/12/2011. Cifrari polialfabetici "algebrici". One-time-pad. Perfezione del one-time-pad. Automazione della crittografia. Il rotore di Jefferson. L'Enigma, storia, funzionamento, debolezze. LUCIDI LEZIONE. Valutazione del corso.
21. 13/12/2011. Codici a trasposizione. Il Data Encryption Standard. Funzionamento e decrittazione. LUCIDI DES. L'Advanced Encryption Standard (AES). LUCIDI AES.
22. 19/12/2011. Richiami. Algoritmo di Euclide tradizionale ed esteso. Correttezza e complessità. Piccolo teorema di Fermat. Funzione e Teorema di Eulero. Esponenziale e logaritmo finito. (Qualche appunto).
23. 20/12/2011. Crittografia a chiave pubblica. Diffie e Hellman e il logaritmo finito. Diffie e Merkle e il cifrario del fusto. Rivest Shamir e Adlemann e il cifrario RSA. LUCIDI LEZIONE.