Teoria dell'Informazione e Crittografia 2012/2013

Orari del corso:

• lunedí II fascia, aula 5
• mercoledí I fascia, aula 46

Argomenti trattati a lezione

1. 01/10/2012 [8:30-10:15]. 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). Decodificabilità istantanea e non.
2. 03/10/2012. [8:30-10:15] Disuguaglianza di Kraft-McMillan. Sufficienza dei codici a prefisso. Probabilità di emissione; lunghezza media di un codice. Entropia.
3. 08/10/2012. Divergenza. I Teorema di Shannon. Codici di Shannon Fano, limitazione superiore di EL per i codici ottimi. Entropia della distribuzione congiunta.
4. 10/10/2012. Tasso del codice. Ottimalità asintotica dei codici di Shannon-Fano. Introduzione al codice di Huffman: geminazione e taglio. Teorema di preservazione ottimalità per geminazione (opportuna). Il codice di Huffman.
5. 15/10/2012. Entropia condizionata. Tipi. Dimensioni e numero dei tipi. Codice multinomiale. Lunghezza del prefisso. Lunghezza del suffisso. Ottimalità asintotica del codice multinomiale.
6. 17/10/2012. 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.
7. 22/10/2012. Ottimalità finita e asintotica del codice di Tunstall. Non ottimalità dei codici di Tunstall al di fuori delle famiglie complete. Codice universale di Ziv Lempel Studio della compressione massima di Ziv Lempel.
8. 24/10/2012. Codici LV-LV: limiti teorici. Codice universale di Lempel, Ziv e Welch. Codice universale di Burrows-Wheeler.
9. 29/10/2012. Codifica B-B senza e con errore, codici δ-tipici e loro ottimalità asintotica.
10. 31/10/2012.

    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. Il modello del canale: matrice di canale, funzioni di codifica e decodifica, tasso e probabilità di errore.
11. 05/11/2012. 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 e di quello con cancellazione. 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.
12. 07/11/2012. 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. Relazioni asintotiche: limitazioni di Singleton e Plotkin. Hamming, e Gilbert.
13. 12/11/2012. 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).
14. 14/11/2012. Matrice generatrice G (matrici equivalenti e in forma canonica). Peso minimo di un codice lineare. Matrice di Controllo H dei codici algebrici. Sindrome. Decodifica usando la Tabella di Slepian. Codice di Hamming binario, semplice ed esteso.
15. 21/11/2011. Codici BCH. Introduzione. Codici BCH 2-correttori. Esempio.
16. 26/11/2012. Codici ciclici. Definizioni principali, polinomio generatore g, teorema principale. Esempi su matrice generatrice dei codici ciclici. (Qualche appunto). Polinomio di controllo h e matrice H corrispondente Richiamo sulle radici primitive dell'unità nei campi finiti e relativi polinomi minimi.
17. 28/11/2012. Uso dei polinomi minimi per determinare il polinomio generatore. Progetto dei codici ciclici a partire dalle radici primitive dell'unità e relazioni con la distanza minima. Il codice di Reed e Solomon.
18. 03/12/2012. Codici convolutivi e l'algoritmo di Viterbi.
19. 05/12/2012.

    PARTE 3

    Crittografia. Storia e terminologia. Cifrari a sostituzione monoalfabetica. Cifrari omofonici e nomenclatori. LUCIDI LEZIONE. Cifrari polialfabetici.
20. 10/12/2012. Tecniche per scoprire lunghezza della chiave e chiave. Esempio pratico di cifrazione Vigenere e sua decrittazione. LUCIDI LEZIONE. Codici sorgenti in quattro linguaggi per l'automazione di quanto appena visto. Cifrari polialfabetici "algebrici". One-time-pad. Perfezione del one-time-pad. Automazione della crittografia. Il rotore di Jefferson.
21. 12/12/2012. L'Enigma, storia, funzionamento, debolezze. LUCIDI LEZIONE. Codici a trasposizione. Il Data Encryption Standard. Funzionamento e decrittazione. LUCIDI DES. Appunti della lezione (by A. Dovier)
22. 14/12/2012. L'Advanced Encryption Standard (AES). LUCIDI AES. Richiami. Algoritmo di Euclide tradizionale ed esteso. Correttezza e complessità. Piccolo teorema di Fermat. Funzione e Teorema di Eulero.
23. 17/12/2012. Esponenziale e logaritmo finito. (Qualche appunto). 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.

    Conclusioni

24. 19/12/2012. Complessità di Kolmogorov. Definizioni e principali risultati.