Docente
Prof. Agostino Dovier

Indirizzo e-mail
agostino.dovier@uniud.it

Indirizzo Pagina Web Personale
http://www.dimi.uniud.it/dovier

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.

********************************************************************************************

Aims

The course deals with the foundations of Information Theory, with particular emphasis on data compression, error correcting codes, and secret codes.

Program

The course is organized in three parts: Source Coding, Channel Coding, and Cryptography.

Source Coding. B-LV codes. Code trees. Uniquely Decodable and Istantaneous Decodable Codes. Kraft-McMillan Inequality. Discrete Probability and Expected Length of a code. Entropy, Divergence, and Shannon first Theorem. Shannon-Fano codes. Memoryless Information Sources. Rate and asymptotical optimality of Shannon-Fano codes. Fano and Huffman codes. Conditional Entropy, Mutual Information, Self Information. Universal (multinomial) Code and its optimality. LV-B codes. Exhaustive and Complete Families. Tunstall trees and coding and their optimality. B-B codes. Code value in error-free coding. Coding with error: delta typical sequences and the second Shannon Theorem. LV-LV codes. Asymptotically optimum codes. Ziv-Lempel, Ziv-Lempel-Welch, and Burrows-Wheeler Universal codes.

Channel Coding. Parity check, repetition, and Hadamard codes. Mathematical formalization of the channel. Channel's capacity: definition and computation on some channels. Shannon's channel coding Theorem. Maximum likelihood decoding. Minimum distance of a code, code rate and its relationships with error
probability. Singleton, Plotkin, Hamming, and Gilbert limitations. Error correcting codes: introduction to algebraic codes. Decoding using Slepian's table. Hamming codes. Perfect codes: main results. BCH codes and Reed-Muller codes. Cyclic codes: main definitions, generator and check matrixes, generator polynomial. Using primitive roots for the project of cyclic codes. Relationships with the minimum distances. Convolutional codes and Viterbi's algorithm.

Hystory of cryptography and main results of public key cryptography. Mono- and Poly-alphabetical substitution cyphers. Some techniques to retrieve key length, and, then, the key.
Examples. One-time-pad and its perfection. Automation of Cryptography. Jefferson rotor and the Enigma cypher machine. Transposition Cyphers. Data Encryption Standard. Some algebraic basics. Advanced Encryption Standard. Public Key Cryptography. Diffie, Hellman and the finite logarithm. Diffie, Merkle and the Knapsack cypher. Rivest Shamir e Adlemann and the RSA.

References

- Fabris F. Teoria dell'Informazione, codici, cifrari, Bollati-Boringhieri, Torino, 2001. (in Italian)

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

- Other textbooks, and teacher notes, are reported on the course website.

Exams

Oral Examination