Sorgenti di informazione. Entropia di sorgente. Codifica di sorgente e teorema di Shannon sulla codifica reversibile. Elementi di teoria della Rate-Distortion. Canali per la trasmissione di informazione. Capacità di canale, teorema di Shannon sulla codifica di canale. Codici blocco. Codici ciclici. Codici convoluzionali.
N. Abramson: Information Theory and Coding. McGraw-Hill, New York, 1963.
S. Benedetto, E. Biglieri, V. Castellani: Digital Transmission Theory, Prentice Hall, 1988.
T. M. Cover, J. A. Thomas: Elements of Information Theory. John Wiley & Sons, New York, 1991.
S. Lin, D. J. Costello Jr.: Error Control Coding: Fundamentals and Applications. Prentice-Hall, 1983.
J. G. Proakis: Digital Communications. McGraw-Hill, 4a Ed., 2001.
A. Papoulis, S.U. Pillai, Probability, Random Variables, and Stochastic Processes, 4th ed., McGraw-Hill, 2002.
Obiettivi Formativi
Il corso ha lo scopo di fornire le conoscenze di base per la rappresentazione in forma compatta dell’informazione e la trasmissione sicura su un canale di comunicazione con rumore.
Al termine del corso, lo studente avrà acquisito la capacità di: comprendere i principi alla base degli standard correnti per la compressione di dati, audio, immagini e video e quelli alla base delle tecniche di protezione di un segnale trasmesso su un canale con rumore.
Prerequisiti
Si presuppone una conoscenza di base di: teoria dei segnali; teoria delle probabilità; variabili e processi aleatori e loro caratterizzazione nel dominio temporale e della frequenza; calcolo vettoriale e matriciale.
Metodi Didattici
Lezioni frontali
Modalità di verifica apprendimento
Esame orale
Programma del corso
Sorgenti di informazione. Sorgenti senza memoria. Misura della quantità di informazione. Entropia di una sorgente. Entropia congiunta e condizionale. Sorgente estesa. Entropia di una sorgente estesa. Sorgenti di informazione con memoria (sorgenti di Markov). Modello a stati finiti. Entropia di stato. Entropia di sorgenti di Markov. Sorgente aggiunta. Estensione di sorgenti con memoria e calcolo della loro entropia. [Abramson, Capitolo 1, Capitolo 2, sezioni da 2.1 a 2.7], [Cover&Thomas, Capitolo 2, sezioni da 2.1 a 2.5].
Introduzione alla codifica di sorgente: codici non singolari, univocamente decodificabili, istantanei. Disuguaglianze di Kraft e di McMillan. Lunghezza media di un codice. Primo teorema di Shannon, sulla codifica di sorgente reversibile (caso di sorgente senza memoria e di sorgente con memoria). Codifica di sorgenti estese. Codici compatti. Codifica di Huffman. [Abramson, Capitoli 3 e 4].
Codifica aritmetica. Codifica aritmetica con codice binario. Codifica di Lempel-Ziv. [Cover&Thomas, Capitolo 13, sezioni 13.3 e 13.4], [Proakis, Capitolo 3, sezione 3.3.3].
Entropia di sorgenti continue: entropia differenziale. Entropia differenziale di vettore di variabili aleatorie congiuntamente Gaussiane. Entropia relativa. Informazione mutua. Quantizzazione. Quantizzazione uniforme e non uniforme. Algoritmo di Max-Lloyd. Cenni alla quantizzazione vettoriale. Cenni alla codifica di forma d'onda. Distorsione e sua misura. Teoria della Rate-Distortion: significato della curva di rate-distortion di una sorgente. Funzione di rate distortion per variabili Gaussiane, uniformi, Laplaciane. [Cover&Thomas, Capitolo 8, sezione 8.1, sezioni da 8.3 a 8.6, capitolo 10, sezioni da 10.1 a 10.3],[Proakis, Capitolo 3, sezione 3.4].
Introduzione alla codifica di canale. Modelli di canale per la trasmissione di informazione: canale binario simmetrico (BSC), canale discreto senza memoria, canale a forma d'onda (canale Gaussiano). Matrice di canale. Entropia a priori e a posteriori. Equivocazione di canale. Capacità di canale. Canali senza rumore. Canali deterministici. Capacità del BSC. Canali in cascata. Regole di decisione. Equivocazione di canale. Probabilità di errore. Disuguaglianza di Fano. Codici a ripetizione. Distanza di Hamming. Secondo teorema di Shannon, sulla trasmissione affidabile di informazione su canali rumorosi. Capacità di un canale Gaussiano. Limite di Shannon e regione di comunicazione affidabile. [Abramson, capitolo 5, sezioni da 5.1 a 5.8, sezione 5.13, capitolo 6, sezioni da 6.1 a 6.6]. [Benedetto-Biglieri-Castellani, capitolo 3].
Codifica a controllo d'errore. Rivelazione e correzione di errori. Codici blocco. Codici lineari. Matrice generatrice del codice. Matrice di controllo di parità. Decodifica hard di codici lineari: calcolo della sindrome. Standard array. Codici ciclici. Polinomio generatore. Polinomio di parità. Calcolo della matrice generatrice di un codice ciclico in forma sistematica. Decodifica di codici ciclici. Codici BCH. Codici Reed-Solomon. Codici concatenati. Tecniche di interleaving. Codici convoluzionali. Decodifica dei codici convoluzionali: algoritmo di Viterbi. Decodifica soft. Guadagno di un codice di canale. [Benedetto-Biglieri-Castellani, capitolo 9].