Teoria dell'Informazione e Crittografia 2013/2014

Orari del corso:

• lunedí II fascia, aula 1
• mercoledí I fascia, aula 2

Argomenti trattati a lezione

1. 30/09/2013. 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. 02/10/2013. Disuguaglianza di Kraft-McMillan. Sufficienza dei codici a prefisso. Probabilità di emissione; lunghezza media di un codice. Entropia.
3. 07/10/2013. Divergenza. I Teorema di Shannon. Codici di Shannon Fano, limitazione superiore di EL per i codici ottimi. Entropia della distribuzione congiunta. Tasso del codice. Ottimalità asintotica dei codici di Shannon-Fano.
4. 09/10/2013. Introduzione al codice di Huffman: geminazione e taglio. Teorema di preservazione ottimalità per geminazione (opportuna). Il codice di Huffman.
5. 14/10/2013. Entropia condizionata. Tipi. Dimensioni e numero dei tipi. Codice multinomiale. Lunghezza del prefisso. Lunghezza del suffisso.
6. 16/10/2013. Ottimalità asintotica del codice multinomiale. LV-B. Motivazioni e generalità. Famiglie esaurienti, a prefisso e complete. Generazione di famiglie complete.
7. 21/10/2013. Relazioni tra tasso ed entropia. Alberi e Codici di Tunstall. Ottimalità finita e asintotica del codice di Tunstall.
8. 23/10/2013. Non ottimalità dei codici di Tunstall al di fuori delle famiglie complete. Codici LV-LV: limiti teorici. Breve storia di LZ, LZW, BW. Codice universale di Ziv Lempel Studio della compressione massima di Ziv Lempel.
9. 30/10/2013. Codice universale di Lempel, Ziv e Welch. Codice universale di Burrows-Wheeler.
10. 04/11/2013. Codifica B-B senza e con errore, codici δ-tipici e loro ottimalità asintotica.
11. 06/11/2013.

    PARTE 2

    Codifica di canale: generalità. Esempi: controllo parità unidimensionale e bidimensionale, codice a ripetizione. Il codice di Hadamard.
12. 11/11/2013. Tasso di trasmissione e tasso di correzione. 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. Esercizio: Canale simmetrico q-ario.
13. 13/11/2013. 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 asintotiche: limitazioni di Singleton e Plotkin.
14. 18/11/2013. Limitazioni di Hamming e Gilbert. Codici Correttori di Errore: introduzione ai codici algebrici. Matrice generatrice G (matrici equivalenti e in forma canonica). Peso minimo di un codice lineare.
15. 20/11/2013. Matrice di Controllo H dei codici algebrici. Sindrome. Decodifica usando la Tabella di Slepian. Codice di Hamming binario, semplice ed esteso.
16. 25/11/2013. Campi finiti: con p elementi e con p^r elementi. Albegra dei polinomi per i campi finiti (Qualche appunto). Codici BCH. Introduzione. Codici BCH 2-correttori. Esempio.
17. 02/12/2013. 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.
18. 04/12/2013. 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.
19. 09/12/2013. La nozione di distinguibilità di stringhe e le relazioni con varie nozioni di distanza. Applicazioni alla teoria dei codici di canale.
    [Lezione in collaborazione con il prof. Andrea Sgarro]
20. 11/12/2012. Codici convolutivi e l'algoritmo di Viterbi.

    PARTE 3

    Crittografia. Storia e terminologia. Cifrari a sostituzione monoalfabetica. Cifrari omofonici e nomenclatori. LUCIDI LEZIONE. Cifrari polialfabetici. 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.
21. 16/12/2013. 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. Codici a trasposizione. Il Data Encryption Standard. Funzionamento e decrittazione. LUCIDI DES. Appunti della lezione (by A. Dovier)
22. 18/12/2013. L'Advanced Encryption Standard (AES). LUCIDI AES. Crittografia a chiave pubblica. Diffie e Merkle e il cifrario del fusto.
23. 08/01/2014. 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). Rivest Shamir e Adlemann e il cifrario RSA. LUCIDI LEZIONE.

    Conclusioni

24. 13/01/2014. Complessità di Kolmogorov. Definizioni e principali risultati.