Docente

Crediti

6 CFU

Finalità

Il corso si propone di introdurre lo studente ai temi della rappresentazione, codifica, e trasmissione pubblica e riservata dell'Informazione.
Nel corso si partira' da alcuni risultati matematici fondamentali quali i Teoremi di Shannon, per arrivare a definire i codici comunemente impiegati per la compressione dell'informazione (Huffman, Ziv-Lempel, LZW, Burrows-Wheeler), per la correzione degli errori di trasmissione spazio-temporale (Reed-Solomon, Viterbi), e per la crittografia (AES, RSA).

Programma

Parte I. Codici di sorgente.
Codici B-LV. Alberi di codice e univoca decodificabilita'. Alberi e codici prefix-free. Decodificabilità istantanea e non. Disuguaglianza di Kraft-McMillan. Sufficienza dei codici a prefisso. Probabilità di emissione; lunghezza media di un codice. Entropia. Divergenza. I Teorema di Shannon. Codici di Shannon Fano, limitazione superiore della lunghezza media per i codici ottimi. 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. Tipi. Dimensioni e numero dei tipi. Codice multinomiale. Lunghezza del prefisso. Lunghezza del suffisso. Ottimalità asintotica del codice multinomiale. Codici 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 ottimalità degli stessi. Non ottimalità dei codici di Tunstall al di fuori delle famiglie complete. Codici LV-LV. Codice universale di Ziv Lempel. Studio della compressione massima di Ziv Lempel. Codice universale di Lempel, Ziv e Welch. Codice universale di Burrows-Wheeler. Cenni alla codifica B-B e ai codici delta-tipici.

PARTE II. Codici di canale
Esempi: controllo parità, codice a ripetizione, codice di Hadamard.
Il modello del canale: matrice di canale, funzioni di codifica e decodifica, tasso di trasmissione e di coorezione, probabilità di errore. Esempi. Capacità di un canale e Teorema di Shannon di canale. Significato e calcolo della capacità del canale. Decodifica di canale a massima verosimiglianza su CSB: 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, Hamming, e Gilbert. 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. 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 ed esteso. Codici BCH. Introduzione. Resto del corso Codici BCH 2-correttori. Codici ciclici.
Definizioni principali, polinomio generatore, teorema principale. Esempi su matrice generatrice dei codici
ciclici. 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. Progetto dei codici ciclici a partire dalle radici primitive dell'unità e relazioni con la distanza minima. Il codice di Reed e Solomon. Codici convolutivi e l'algoritmo di Viterbi.

PARTE III. Crittografia.
Storia e terminologia. Cifrari a sostituzione monoalfabetica. Cifrari omofonici e nomenclatori.
Cifrari polialfabetici. Tecniche per scoprire lunghezza della chiave e chiave. Esempio pratico
di cifrazione Vigenere e sua decrittazione.
Cifrari polialfabetici "algebrici". One-time-pad. Perfezione del one-time-pad. Automazione della crittografia. Il rotore di Jefferson. L'Enigma, storia, funzionamento, debolezze. Codici a trasposizione.
Il Data Encryption Standard. Funzionamento e decrittazione. Richiami algebrici. Algoritmo di Euclide
tradizionale ed esteso. Correttezza e complessità. Piccolo teorema di Fermat. Funzione e Teorema di Eulero. Esponenziale e logaritmo finito. L'Advanced Encryption Standard
(AES). 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.

Bibliografia

- Testo principale: Francesco Fabris. Teoria dell'Informazione, codici, cifrari. Bollati Boringhieri, 2001.

- Wade Trappe, Lawrence C. Washington. Introduction to Cryptography with Coding Theory (2nd ed) Pearson, 2005

- Dal sito web del corso sono disponibili note, dispense, e presentazioni su varie parti del corso stesso.

Modalità d'esame

Orale, su appuntamento.