Compressione dati con applicazioni alla codifica di segnali multimediali

Questo elaborato ha lo scopo di fornire un’introduzione al concetto di compressione dati andando ad illustrare i principali metodi di compressione. Per ogni metodo illustrato, verranno forniti esempi e un’analisi di massima delle prestazioni. In un primo momento vengono richiamati i concetti base della teoria dell’informazione. Successivamente verranno illustrati i principali metodi di codifica senza perdite, in particolar modo metodi di codifica entropica per sorgenti iid, partendo dalle codifiche di Shannon e di Huffman fino ad arrivare alla codifica aritmetica e al metodo ANS. Successivamente verranno accennati metodi di codifica per sorgenti non iid attraverso l’utilizzo di metodi di codifica ‘context based’ partendo da un’introduzione ai modelli di Markov per poi passare alle codifiche DMC e PPM. Successivamente verranno introdotti i così detti “compressori universali” di cui verranno analizzati gli algoritmi LZ77, LZ78, LZW (impiegati per lo più in compressori della famiglia ZIP) e LZ77-deflate per poi passare ad esempi di applicazione di codifica senza perdite quali GIF (primo formato per la codifica di immagini), UNIX-compress (antenato della famiglia ZIP) e il formato PNG (Successore di GIF e formato di maggior impiego nella codifica senza perdita di immagini). Successivamente verranno introdotti i principi base della codifica con perdite a partire dal concetto di quantizzazione per poi passare alle basi della rate distortion theory e del transform coding, in particolare ci si soffermerà sulle trasformate KLT e DCT. Per la codifica con perdite verrà preso in esame come esempio applicativo il formato JPEG. Successivamente viene accennato il metodo di “subband coding” e la trasformata MDCT per poi passare alle basi della codifica audio di cui verrà analizzato lo standard MPEG-1/2.