Il corso affronta il problema di trasmettere efficacemente e fedelmente un messaggio. Introduce l'informazione come qualcosa di definito e misurabile e fornisce risposta a due quesiti fondamentali per qualsiasi sistema di informazione, ovvero quale è il massimo livello di compressione e quale è la massima velocità di trasmissione dei dati. Il corso fornisce poi elementi di codifica sia di sorgente che di canale, utilizzate per avvicinarsi ai limiti teorici definiti in precedenza.
T. M. Cover, J. A. Thomas: Elements of Information Theory. John Wiley & Sons, New York, 2nd ed 2006
N. Abramson: Information Theory and Coding. McGraw-Hill, New York, 1963.
K. Sayood: Introduction to data compression, Elsevier 4a ed., 2012
S. Benedetto, E. Biglieri, V. Castellani: Digital Transmission Theory, Prentice Hall, 1988.
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 affidabile dell'informazione su un canale di comunicazione con rumore, in particolare:
- Conoscenze dei concetti di base sulla rappresentazione dell'informazione.
- Conoscenza degli elementi fondamentali della codifica di sorgente e tecniche di codifica di sorgente.
- Conoscenza delle problematiche e caratterizzazione della trasmissione affidabile su canali rumorosi.
- Conoscenza dei principi della codifica di canale.
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
- saper applicare tecniche di compressione di sorgente.
- comprendere i principi 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
ll corso sarà costituito da:
Lezioni frontali
Modalità di verifica apprendimento
La verifica finale consta di una prova orale durante la quale verranno fatte domande teoriche e svolti esercizi.
Le domande teoriche hanno lo scopo di verificare
- la comprensione del concetto di informazione
- la comprensione della teoria che sta alla base della compressione e della codifica di canale
- la comprensione dei meccanismi e dei principi che permettono di costruire sia un codice di sorgente che di canale
- la comprensione delle caratteristiche dei codici di sorgente e di canale e le metriche di valutazione delle prestazioni
Gli esercizi hanno lo scopo di verificare
- la capacità di applicare i concetti teorici
- la capacità di applicare le tecniche di codifica analizzate
Programma del corso
PARTE I – SORGENTI E MISURA DELL'INFORMAZIONE
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.
PARTE II – CODIFICA DI SORGENTE
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. Codifica aritmetica. Codifica aritmetica con codice binario. Codifica di Lempel-Ziv.
PARTE III – SORGENTI CONTINUE E TEORIA DELLA RATE-DISTORTION
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 Lloyd-Max. Quantizzazione vettoriale. Cenni alla codifica di forma d'onda. Distorsione e sua misura. Teoria della Rate-Distortion: significato e proprietà della curva di rate-distortion di una sorgente. Equivocazione e irrilevanza. Calcolo della funzione di rate distortion per sorgenti Gaussiane. Estensione a sorgenti uniformi, Laplaciane e Gaussiane generalizzate. Applicazione dei principi della TRD alla codifica di immagini e video. Quantizzatori dipendenti e indipendenti. Codifica a bit-rate costante (CBR) per broadcasting e variabile (VBR) per streaming. Cenni sugli standard video e il loro funzionamento.
PARTE IV - CODIFICA DI CANALE
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.