Progetto e realizzazione tramite FPGA di un encoder/decoder basato sull’algoritmo di Huffman

Capitolo 1 Trasmissione e compressione dell’Informazione I sistemi di elaborazione hanno subito nel corso degli ultimi vent’anni sostanziali miglioramenti, presentando velocità e capacità sempre maggiori. A ciò si aggiunge una crescita del numero di dispositivi esistenti, di natura e tipologia diverse e quindi la necessità che questi interagiscano tra loro, scambiandosi appunto informazioni in una qualche maniera. Emerge quindi la necessità di rappresentare l’informazione in maniera ottimale, in modo tale che sfrutti al meglio le risorse a disposizione, sia che esse siano canali di comunicazione, sia che siano costituite da supporti di memorizzazione. In questo capitolo si discuterà appunto del problema della rappresentazione del- l’informazione, partendo innanzitutto dal definire che cosa si intende per Informazio- ne. Successivamente si esporrà il concetto di compressione delle informazioni, mo- strando alcune delle tecniche più importanti e maggiormente trattate in letteratura, per concludere con l’ultima parte del capitolo che approfondisce la compressione effettuata mediante l’algoritmo di Huffmann, oggetto appunto della presente Tesi e alla base del progetto realizzato su FPGA. 1.1 Informazione Nell’ambito della Computer Science si parla spesso di Informazione, senza però avere un’idea chiara e precisa di cosa essa sia. Intuitivamente si sa che cosa essa sia e si è consapevoli del fatto che costantemente si trasmette e si riceve informazione attraverso testi, immagini, suoni o altri mezzi di comunicazione, senza attribuire però al concetto di Informazione una qualche entità matematica misurabile. La Teoria dell’Informazione si prefigge il compito di definire con chiarezza il concetto di Informazione in termini matematici, mostrando come essa sia in effetti quantificabile. Pertanto, un certo dato, sia che esso sia un’immagine, un numero o un testo scritto, contiene una determinata quantità di Informazione, esprimibile mediante un numero e un’unità di misura. La quantificazione dell’Informazione è basata sull’osservazione che il contenu- to informativo di un messaggio equivale alla quantità di novità ad esso associata ([Sal04]). Se il messaggio contiene qualcosa che il destinatario già conosce, allora 5