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
6CAPITOLO 1. TRASMISSIONE E COMPRESSIONE DELL’INFORMAZIONE
non viene fornita informazione in quanto non viene aggiunta conoscenza a quel che
già si sapeva. Al contrario, un messaggio contiene informazione quando comunica
qualcosa di nuovo e la sua quantificazione è appunto legata al grado di stupore che
il messaggio suscita nel chi lo riceve. L’informazione è quindi legata al grado di in-
certezza sulla conoscenza o sul contenuto, indipendentemente dal fatto che sia vera
o meno. Pertanto, la Teoria dell’Informazione tralascia gli aspetti semantici della
conoscenza: i messaggi che vengono scambiati non debbono avere necessariamente
un significato comprensibile, ne tanto meno utilità per un destinatario.
Si consideri, a titolo di esempio, l’esperimento del lancio di una moneta non
truccata. Come è ben noto, possono verificarsi solamente due eventi equiprobabili,
ovvero il presentarsi del simbolo della testa o della croce, ma a priori il lancio di una
moneta è incerto. L’incertezza viene risolta mediante l’esecuzione dell’esperimento
e il risultato, indipendentemente da quale esso sia
1
, porta nuova conoscenza espri-
mibile mediante una semplice risposta T o C, vero o falso, 0 o 1, rappresentabile
dunque in forma binaria da un singolo bit. Il destinatario del messaggio è in grado
di decodificare il bit ricevuto, determinando l’esito dell’esperimento ed eliminando
quindi l’incertezza iniziale associata al lancio della moneta.
Un altro esempio è il seguente. Si supponga di avere un dispositivo in grado di
generare cinque diversi simboli in maniera casuale ed equiprobabile: A, B, C, D e E.
Fintanto che si è in attesa di ricevere il prossimo simbolo generato dal dispositivo,
si permane in uno stato di incertezza, legato al fatto che non si conosce l’esito
della generazione. Non appena il simbolo viene prodotto, e arriva al destinatario,
questo riduce la propria incertezza poichè ha appreso quale dei cinque simboli è
stato effettivamente generato. Sotto quest’ottica, l’Informazione è una riduzione
dell’incertezza. In questo caso, per codificare uno dei cinque distinti simboli, sono
sufficienti 3 bit e si quantifica l’informazione appunto con 3 bit.
Dal confronto dei due esempi, appare chiaro come il risultato del secondo ti-
po di esperimento produca maggior Informazione, in quando porta ad una maggior
riduzione dell’incertezza iniziale. Nel primo caso, si era incerti solamente tra due
possibili risultati e l’esito non ha fatto altro che escludere uno dei due possibili;
nel secondo caso l’incertezza era tra cinque diversi valori e l’esecuzione dell’esperie-
mento ha ridotto l’incertezza eliminando quattro dei possibili esiti. Da ciò segue
che il secondo esperimento, quindi il messaggio dell’esito associato, è maggiormente
informativo.
Dalle considerazioni appena fatte, seppur intuitive, appare evidente come un
evento poco probabile sia altamente informativo poichè maggiormente riduce l’in-
certezza e come invece un evento assai probabile sia invece poco informativo, in
quando aggiunge poco a quanto già si sapeva. Pertanto, informazione e probabilità
di un certo evento sono legati indirettamente.
1.1.1 Misura dell’Informazione
Dato un generico evento E, è necessario definire in termini analitici il suo con-
tenuto informativo. Come già detto, tale quantità dipende dal grado di incertezza
che l’evento ha nel destinatario e in ultima analisi della sua probabilità.
1
Come già detto vengono tralasciati gli aspetti semantici.
1.1. INFORMAZIONE 7
SiaI(E) la funzione analitica che quantifica l’informazione contenuta nell’evento
(o messaggio) E. Come si è avuto modo di capire, il contenuto informativo di un
evento sarà funzione della sua probabilità:
I(E) =f(P (E)) (1.1)
Lafunzionef deveperòrispondereadeterminatirequisitiaffinchèrappresenticorret-
tamente il contenuto informativo di un evento
2
, proprio come discusso nel paragrafo
precedente:
1. Dalmomentochel’argomentodif èunaprobabilità, ilsuodominiodeveessere
compreso tra 0 e 1:
f : (0; 1] :! R
Si noti che P (E) = 0 non appartiene al dominio di f
2. L’evento certo non porta nessuna informazione:
f(1) = 0
3. L’evento impossibile contiene il massimo contenuto informativo, ovvero riduce
l’incertezza al massimo.
lim
P(E)!0
f(P (E)) = +1 (1.2)
4. f è una funzione continua nel suo dominio.
5. f è funzione monotona strettamente decrescente:
8E
1
;E
2
: P (E
1
);P (E
2
)2 (0; 1]; P (E
1
)<P (E
2
)
f(P (E
1
))>f(P (E
2
))
6. L’informazione è una grandezza estensiva (addittiva): dati due eventi indipen-
denti
3
E
1
e E
2
, il contenuto informativo dell’evento congiunto è somma dei
rispettivi contenuti informativi
I(E
1
\E
2
) =I(E
1
) +I(E
2
)
Sfruttando la definizione (1.1) e le proprietà degli eventi disgiunti, si ottiene
I(E
1
\E
2
) =f(P (E
1
\E
2
)) =f(P (E
1
) P (E
2
))
E quindi
I(E
1
\E
2
) =f(P (E
1
) P (E
2
)) =f(P (E
1
)) +f(P (E
2
)) (1.3)
2
Si indica genericamente con evento qualsiasi entità che contenga informazione, quindi si
comprende con il termine evento anche dato, messaggio, numero, file, etc...
3
Due eventi si dicono indipendenti quando il verificarsi di uno non modifica la probabilità di
verificarsi dell’altro, ovvero quando (AjB) =P (A) e (BjA) =P (B). Le due condizioni si possono
sintetizzare in
P (A\B) =P (A) P (B)
8CAPITOLO 1. TRASMISSIONE E COMPRESSIONE DELL’INFORMAZIONE
Figura 1.1: Grafico della funzione log
1
p
Claude Shannon, considerato il padre della Teoria dell’Informazione, propose
nel suo lavoro del 1948
4
una funzione analitica che rispondeva esattamente a tutti
i requisiti appena mostrati. Tale funzione è il logaritmo e in particolare Shannon
definì il contenuto informativo di un evento (o auto-informazione) come
I(E) = logP (E) =
1
logP (E)
(1.4)
Si noti che la (1.4) rispetti la proprietà (1.3), in virtù delle proprietà dei logaritmi
per cui log(a b) = loga + logb. Inoltre, Shannon dimostrò anche che la funzione
logaritmo è l’unica in grado di soddisfare tutte le prorpietà sopraccitate contempo-
raneamente. La Figura 1.1 mostra il grafico della funzione logaritmo in funzione di
1=P (E).
1.1.2 Entropia
Definito il contenuto informativo di un singolo evento E come logP (E), è
necessario esprimere il contenuto informativo medio della sorgente generatrice di
tali eventi. Si consideri una sorgente S, che generi una sequenza di n simboli
s
1
, s
2
, :::, s
n
. Ciascun evento s
i
ha un contenuto informativo pari a
I(s
i
) = logP (s
i
)
4
Una Teoria matematica della comunicazione, Claude Shannon, 1948
1.1. INFORMAZIONE 9
Il contenuto informativo medio della sorgente (Entropia della sorgente) è quindi
la media ponderata dei contenuti informativi dei singoli eventi che genera:
H(S) =
n
X
i=1
P (s
i
)I(s
i
)
= n
X
i=1
P (s
i
) logP (s
i
)
=
n
X
i=1
P (s
i
)
1
logP (s
i
)
(1.5)
Si noti che, dal momento che logx 08x2 (0; 1], risulta che
H(x) 08x2 (0; 1]
Le definizioni di Informazione e Entropia mostrate fanno uso della funzione logarit-
mo, senza che sia specificata una particolare base. Al variare della base scelta per il
logaritmo, cambia il valore numerico dell’entropia. Le principali basi utilizzate sono
riportate in Tabella 1.1
Base Unità di misura
2 bit
e nat
10 Hartley
Tabella 1.1: Unità di misura utilizzate e basi corrispondenti
Se X rappresenta un segnale aleatorio, la sua Entropia H(X) misura la quan-
tità di Informazione (o incertezza). Come si discuterà nel seguito, Shannon ha
dimostrato che l’entropia rappresenta la minima complessità descrittiva di tale va-
riabile aleatoria, ovvero il limite inferiore della compressione di dati senza perdita
di informazione.
QuandoX rappresentaunasorgentedisimboliappartenentiaduncertoalfabeto,
H(X) (con logaritmo in base 2) indica il numero medio di bit per ogni simbolo
dell’alfabeto. Pertanto, se H(X) = h, quando la sorgente X emette il simbolo
x
i
, ci si aspetta che venga codificato con h bit. Ovviamente, non tutti i simboli
dell’alfabeto verranno codificati esattamente conh bit: alcuni di essi ne necessitano
di meno, altri di più, proprio perchè H(X) è una media ponderata del contenuto
informativo di ciascun simbolo. Si ritornerà comunque su questi concetti quando si
discuterà della compressione.
Il concetto di Entropia analizzato dalla Teoria dell’Informazione ha un certo
legame con l’entropia fisica. Il fisico Leon Brillouin, nella sua opera Science and
Information Theory parla del legame tra entropia e informazione:
L’entropia è considerata in generale come espressione del disordine di un
sistema fisico. Più precisamente, si può dire che l’entropia misura la mancanza
di informazione sulla struttura effettiva del sistema. Questa mancanza di infor-
mazione implica la possibilità di una grande varietà di strutture microscopiche
diverse che sono, in pratica, impossibili da distinguere le une dalle altre. Poiché
una qualunque di queste strutture può esistere realmente a un istante dato, la
mancanza di informazione corrisponde ad un disordine reale.
10CAPITOLO1. TRASMISSIONEECOMPRESSIONEDELL’INFORMAZIONE
1.1.3 Sorgenti di Informazione
Nel paragrafo precedente è stata definita l’entropia di una sorgente di informa-
zione, mostrando una corrispondenza con il costo della rappresentazione con cifre
binarie. Con il termine sorgente ci si riferisce a qualunque cosa possa generare in-
formazione, come un file memorizzato su disco o proveniente da una fonte esterna
o, ad esempio, un insieme di caratteri generati da una tastiera.
Nel seguito verranno considerate solamente sorgenti discrete, che emettono suc-
cessioni di cifre. Una sorgente discreta emette messaggi m costituiti da concatena-
zioni di simboli di un certo alfabeto A. Ad esempio, una sorgente binaria è discreta
in quanto i messaggi che genera sono stringhe di 1 o 0. In realtà, sorgenti continue
nel tempo possono essere rese discrete mediante il campionamento, con degradazione
trascurabile se la frequenza di campionamento è scelta opportunamente
5
.
Allo stesso modo, sorgenti continue nelle ampiezze, ottenute campionando sor-
genti analogiche, vengono solitamente discretizzate mediante la quantizzazione. Si
tratta di un’operazione che introduce un errore, di entità facilmente prevedibile. Ad
ogni modo, si assumerà quindi che la sorgente sia già discreta nel tempo e nelle
ampiezze.
E’ possibile trattare analiticamente la sorgente S come una variabile aleatoria
X. In particolare X =fx
1
;x
2
;:::;x
n
g e la probabilità che si verifichi l’evento x è
data da
PfX =xg =p(x) ; x2X
Il contenuto informativo per tale evento è
IfX =xg = logp(x)
In maniera analoga a quanto già visto, il contenuto informativo della sorgenteX
è dato dal valore atteso della variabile aleatoria X ed è denominato Entropia di X.
Definizione 1.
H(X), X
x2X
p(x) logp(x) =
X
x2X
p(x)
1
logp(x)
(1.6)
Un’ulteriore supposizione riguardo la sorgente di informazione è la sua staziona-
rietà.
Definizione 2. Una sorgente di informazione X si dice stazionaria, se per ogni
simbolo x
i
2A, con A alfabeto di X, vale:
P
x
k
(x
i
) =p
i
8k
Pertanto, in ogni istante di tempo, la probabilità di emissione di un simbolo è la
medesima.
5
Il teorema di Nyuist-Shanon afferma che un segnale s(t) a banda limitata fm può essere uni-
vocamente ricostruito a partire dai suoi campioni s(nt);n 2 Z presi a frequenza fs =
1
t
, se
fs > 2fm.
1.1. INFORMAZIONE 11
1.1.3.1 Sorgenti senza memoria
Una prima famiglia di sorgenti è rappresentata dalle sorgenti di informazione
senza memoria (memoryless source o sorgenti a memoria zero) per le quali la pro-
babilità di emissione di un simbolo non dipende dal contesto, ovvero dai simboli
precedentemente emessi:
P (x
i
jx
j
) =P (x
i
) =p
i
8 i;j
Seinaggiunta, tuttiisimbolihannolastessaprobabilitàdiesseregenerati, allora
la sorgente gode della proprietà i.i.d. (independent and identically distribuited).
Le sorgenti senza memoria sono più semplici da trattare teoricamente e più
facili da codificare, ma molto rare nella realtà. Per una descrizione completa di una
sorgentesenzamemoriastazionaria,èsufficientefornireleprobabilitàdeimessaggix
i
tratti dall’alfabetoX. Come si è già avuto modo di vedere, l’informazione contenuta
nel singolo messaggio, I(x
i
) = logp
i
constribuisce all’entropia della sorgente in
proporzione alla sua probabilità di emissione
6
:
H(X) =E[I(x
i
)] = X
i
p
i
logp
i
A titolo di esempio, si consideri la variabile aleatoria X associata al lancio di
una moneta non truccata, ovvero una moneta che assume con egual probabilità i
due valori testa e croce. I due possibili esiti del lancio possono essere rappresentati
dallo 0 e dall’1:
X =f0; 1g : P (X = 0) =P (X = 1) = 1=2
L’esito di ogni lancio è imprevedibile e non vi sono ragioni per favorire un esito
anzichè un altro. Pertanto X può essere vista come sorgente binaria, discreta, sta-
zionaria e senza memoria, dal momento che l’esito di un lancio non condiziona i lanci
successivi.
L’entropia della variabile X vale:
H(X) = 1
X
i=0
P (X =i) log
2
P (X =i)
=P (X = 0) log
2
P (X = 0) P (X = 1) log
2
P (X = 1) = 1 bit
Il risultato ottenuto indica che, per risolvere l’incertezza sulla previsione è sufficiente
un1bito, inmanieraalternativa, ognisimboloprodottodaX ècodificabileinmedia
con 1 bit.
Il lancio di una moneta bilanciata è in realtà un caso particolare. Si può genera-
lizzare il concetto utilizzando una variabile binaria X tale per cui la probabilità di
generazione dei suoi due simboli non è simmetrica:
X =f0; 1g :
p(0) =P (X = 0) =p 0 x 1
p(1) =P (X = 1) = 1 p
6
Con pi si intende, vista la supposizione di stazionarietà della sorgente, P (xi).
12CAPITOLO1. TRASMISSIONEECOMPRESSIONEDELL’INFORMAZIONE
L’entropia di X vale:
H(X) =p logp (1 p) log(1 p) p2 [0; 1]
Per brevità, si lascia lo studio della funzione al lettore, ma se ne riporta il grafio in
Figura 1.2.
Figura 1.2: Studio della funzione H(p) (evento binario non bilanciato)
1.1.3.2 Proprietà dell’Entropia
Si noti come il caso in cui la moneta sia bilanciata, ovvero p = 1=2, rappresenti
la situazione per cui l’entropia è massima, ovvero viene fornito il massimo contenuto
informativo e quindi è necessario il maggior numero di bit per rappresentare i possi-
bili valori (due) di X. Gli estremi del dominio sono rappresentati da p = 0 e p = 1,
tali per cui l’entropia è minima: non si ha incertezza sull’esito del prossimo valore
della variabile binaria e quindi non viene fornita alcuna informazione.
Più in generale, vale il teorema seguente:
Teorema 1. L’entropia si una sorgente con alfabeto X costituito da M simboli
soddisfa la disuguaglianza
H(X ) logM (1.7)
L’uguaglianza della (1.7) è soddisfatta solo quando tutti i simboli dell’alfabeto
sono equiprobabili, cioè quando
P (x
i
) =p =
1
M
8 i
E dal momento che l’entropia è sempre maggiore di 0, la (1.7) può essere estesa
in
0 H(X ) logM
1.1. INFORMAZIONE 13
1.1.3.3 Entropia congiunta e condizionata
Nel paragrafo precedente è stata definita l’entropia di una singola variabile ca-
suale associata ad una sorgente di informazione stazionaria, discreta e a memoria
0. La definizione può essere al caso di due variabili casuali, introducendo l’entropia
congiunta.
Si considerino due variabili casuali
X =fx
1
;:::;x
n
g Y =fy
1
;:::;y
n
g
e si ponga
PfX =xg =p(x) PfY =yg =p(y)
La probabilità condizionata viene indicata come
PfX =x;Y =yg =p(x;y)
e rappresenta la probabilità che i due eventi X =x e Y =y si verifichino contem-
poraneamente. Dal momento che X e Y rappresentano sorgenti di informazione,
la probabilità congiunta rappresenta la probabilità che le due sorgenti emettano i
simboli x e y in contemporanea.
La probabilità condizionata è indicata come
PfX =xjY =yg =p(xjy)
e rappresenta la probabilità che la sorgente X emetta il simbolo x sapendo che la
sorgente Y ha emesso y. Si ricorda che la probabilità condizionata di un evento
rispetto ad un altro può essere espressa in termini della probabilità congiunta:
p(ajb) =
p(a;b)
p(b)
(1.8)
Fatte tali considerazioni è possibile definire l’entropia congiunta di due variabili
casuali.
Definizione 3. L’entropia congiunta H(X;Y ) di due variabili casuali X e Y è:
H(X;Y ) = X
x2X
X
y2Y
p(x;y) logp(x;y)
L’entropia condizionata rappresenta invece l’entropia di una sorgente sapendo
che un’altra sorgente ha emesso un certo simbolo:
H(XjY =y) X
x2X
p(xjy) logp(xjy)
A partire dall’entropia condizionata da un particolare evento Y = y, si definisce
l’entropia condizionata come valore atteso al variare di tutti gli eventi y
i
2Y.
14CAPITOLO1. TRASMISSIONEECOMPRESSIONEDELL’INFORMAZIONE
Definizione 4. L’entropia condizionata H(XjY ) di due variabili casuali X e Y è
H(XjY ) =
X
y2Y
H(XjY =y)
= X
y2Y
p(y)
X
x2X
p(xjy) logp(xjy)
= X
x2X
X
y2Y
p(x;y) logp(xjy)
L’ultimo passaggio è stato ottenuto sfruttando la definizione di probabilità condi-
zionata (1.8).
Esiste un legame tra entropia (marginale), condizionata e congiunta, espressa
dal seguente teorema.
Teorema 2 (Regola della catena).
H(X;Y ) =H(X) +H(YjX) =H(Y ) +H(XjY ): (1.9)
La dimostrazione richiede semplici passaggi algebrici
7
La regola della catena è
facilmente estendibile al caso di n variabili.
Teorema 3 (Regola della catena generalizzata).
H(X
1
;X
2
;:::;X
n
) =
n
X
i=1
H(X
i
jX
i
 1;X
i
 2;:::;X
1
) (1.10)
La dimostrazione sfrutta il principio di induzione ed esula gli scopi della presente
Tesi, in quanto non orientata ad una trattazione diffusa della Teoria dell’Informa-
zione.
La (1.9) può essere estesa inserendo un ulteriore condizionamento.
H(X;YjZ) =H(XjZ) +H(YjX;Z)
La dimostrazione è lasciata al lettore, dal momento che richiede passaggi già mo-
strati.
7
H(X;Y ) = X
x2X
X
y2Y
p(x;y) logp(x;y)
= X
x2X
X
y2Y
p(x;y) log[p(x)p(yjx)]
= X
x2X
X
y2Y
p(x;y) logp(x) X
x2X
X
y2Y
p(x;y) logp(yjx)
= X
x2X
p(x) logp(x) X
x2X
X
y2Y
p(x;y) logp(yjx)
=H(X) +H(YjX)
1.1. INFORMAZIONE 15
1.1.3.4 Sorgenti con memoria
In una sorgente di informazione con memoria, l’emissione di un certo simbolo
è condizionata dal contesto, ovvero da ciò che la sorgente ha generato precedente-
mente. Quindi, non è sufficiente fornire le proprabilità dei singoli messaggi, ma sono
necessarie anche le probabilità congiunte di generazione di un simbolo condizionate
dall’emissione di altri simboli.
L’entropia delle sorgenti con memoria è ragionevolmente minore dell’entropia
di una sorgente senza memoria. Infatti, i messaggi emessi dipendono in una certa
misura daquelli emessiprecedentemente, ilcheli rendepiù prevedibili equindi meno
informativi. Come esempio, si pensi ad una sorgente che emette i bit di bianco/nero
di un fax
8
. È chiaro che un bit di bianco sarà probabilmente preceduto da un altro
bit di bianco. Si potrebbe quindi pensare di codificare non un singolo bit ma ad
esempio coppie di bit. Per quanto detto in precedenza, le coppie di bit dello stesso
colore hanno una probabilità maggiore di presentarsi, da cui deriva una minore
entropia.
Siafx
k
g la successione di messaggi emessi da una sorgente stazionaria con me-
moria. Se la sorgente fosse priva di memoria, l’entropia verrebbe calcolata a partire
dalle probabilità marginali p
i
dei messaggi che genererebbe. Tuttavia, a causa della
memoria della sorgente, il messaggio x
k
all’istante k è maggiormente prevedibile di
quanto indicato dalle probabilità marginali P (x
k
) in quanto è già noto il messaggio
precedente x
k1
. L’entropia condizionata al messaggio precedente è
H(X
k
jx
k1
) H(x
k
) (1.11)
Se la memoria della sorgente si estende ad altri messaggi precedenti, la (1.11) può
essere estesa
H(X
k
jx
k1
;x
k2
) H(x
k1
);:::
L’entropia della sorgente H(X) è definita come limite di tale successione non
crescente di entropie condizionate, per osservazione tendente all’infinito. In gene-
rale, il calcolo non è semplice e spesso non è possibile misurare tutte le probabilità
condizionate che sono richieste.
Una definizione alternativa di entropia, equivalente alla precedente, è ottenuta
considerando blocchi di L messaggi e facendo tendere L a infinito:
H
L
(X) =
1
L
H(X
k
;X
k1
;:::;X
kL+1
) (1.12)
H(X) = lim
L!1
H
L
(X) (1.13)
Ricordando che il condizionamento non aumenta l’entropia, che la sorgente è stazio-
naria e sfruttando la (1.10), si ha:
H
L
(X) =
1
L
[H(X
k
L
+1
) +H(X
kL+2
jX
kL+1
) + +
+H(X
k
jX
k1
;:::;X
kL+1
] H(X
k
jx
k1
;:::;X
kL+1
) (1.14)
Pertanto la (1.12) tende a H(X
k
jx
k1
;:::;X
kL+1
). Anche nel caso di sor-
genti con memoria la lunghezza media di qualsiasi codice non può essere minore
dell’entropia, ma può avvicinarvisi quanto si vuole.
8
Si veda l’AppendiceC.
16CAPITOLO1. TRASMISSIONEECOMPRESSIONEDELL’INFORMAZIONE
1.2 Codifica di sorgente
Se si vuole trasmettere un messaggio attraverso un canale è necessario codifi-
carlo, ovvero offrirne una rappresentazione che permetta al ricevente la decodifica e
l’interpretazione del messaggio originario. Esistono diverse modalità per codificare
un insieme di simboli appartenenti ad un certo alfabeto, alcune molto convenien-
ti, altre meno. Il modello a cui si fa riferimento è rappresentato in Figura 1.3 e
presuppone la presenza di una sorgente di informazione che intende trasmettere un
certo insieme di messaggi ad un destinatario attraverso un canale, ovvero un mezzo
attraverso il quale propagare l’informazione. Ai fini della trattazione, si consideri un
canale di comunicazione completamente affidabile, non rumoroso, per il quale ogni
simbolo inviato giungerà al destinatario senza errore.
Figura 1.3: Sistema di comunicazione dotato di codificatore e decodificatore
La Figura 1.3 mostra la presenza di due blocchi particolari:
 Codificatore: trasforma la rappresentazione della sorgente in una forma
adatta ad essere trasmessa sul canale.
 Decodificatore: riceve il flusso dati codificato e si occupa di decodificarlo,
ovvero di riportarlo nella sua rappresentazione ridondante.
Generalmente, la sorgente trasmette informazione ridondante, quindi non rap-
presentatainmanieraefficiente. Lacodificasioccupadirendereefficientelatrasmis-
sione, riducendo la quantità di informazione inviata. In tal senso è anche possibile
aumentare la velocità di trasmissione o ridurre la dimensione della memorizzazione
dell’informazione.
In realtà, la codifica si occupa anche dell’affidabilità, non trattata vista la sup-
posizione di canale non rumoroso, ma che si cita a titolo di completezza. La codifica
rende la comunicazione affidabile introducendo informazione aggiuntiva che consente
di ricotruire l’informazione originale anche in presenza di errori.
Per migliorare l’efficienza la codifica mira alla riduzione della ridondanza, mentre
per ottenere una maggiore affidabilità si cerca di inserire informazione, quindi si
aumenta la ridondanza. Chiaramente, i due obiettivi sono contrastanti e la soluzione
migliore dipende dal particolare contesto applicativo.
1.2.1 Ridondanza
Si analizzerà ora solo l’obiettivo di eliminare la ridondanza al fine di comprime-
re l’informazione e rappresentarla in maniera efficiente e aumentare la velocità di
trasmissione.
Pertanto, un fattore molto importante quando si parla di codifica è la ridon-
danza, intesa come entità in grado di ridurre il potere informativo di un messaggio.
1.2. CODIFICA DI SORGENTE 17
Eliminare la ridondanza non comporta la perdita del contenuto informativo, ma por-
ta alla riduzione del numero di simboli (bit) necessario per codificare il messaggio
stesso.
La ridondanza dipende dalla tipologia dell’informazione e dal linguaggio con cui
è rappresentata. Pertanto, tipologie di informazione differenziate richiedono metodi
di compressione e quindi di riduzione della ridondanza differenti.
Come è già stato detto diverse volte, l’entropia di un certo insieme di simboli,
dipende dalla probabilità con cui questi si presentano e ha un massimo quando tutti
i simboli sono equiprobabili (vedi Teorema 1.7). Un esempio di ridondanza è quella
linguistica: ogni linguaggio, naturale o non, è di per sè ridondante. Ne segue che in
un certo linguaggio, vi sono simboli più frequenti di altri: ad esempio, nella lingua
italiana, la lettera ‘E’ si ripete con frequenza decisamente maggiore rispetto alla
lettera ‘Z’ e quindi fornisce un contributo più importante all’entropia. Questo com-
portamento statistico suggerisce di attribuire codici di lunghezza inferiore a simboli
molto probabili, come la ‘E’ e codici più lunghi ai simboli più improbabili.
Allo stesso modo, in una lingua determinate combinazioni di simboli sono assai
più probabili di altre. Sempre facendo riferimento alla lingua italiana, la lettera
‘q’ è sempre seguita dalla vocale ‘u’. In altre parole, alcuni digrammi o tigrammi
sono molto comuni nei linguaggi. Tale comportamento è noto come ridondanza
contestuale.
Un altra tipologia di ridondanza molto comune è quella spaziale e si ritrova facil-
mentenelleimmagini. Un’immaginedigitalevienerappresentatacomeunrettangolo
di pixel: osservando un certo punto del rettangolo si può notare come il colore di un
pixel sia uguale o simile ai pixel adiacenti. La ridondanza consiste quindi nel fatto
che non è necessario memorizzare tutti i pixel di un’immagine, in quando molti di
essi sono tra loro simili.
A questo punto è possibile fornire una misura della ridondanza di un certo dato.
La (1.7) mostra chiaramente un limite superiore dell’entropia di una sorgente di
informazione. La ridondanza riduce il contenuto informativo, in quanto inseriesce
informazione non necessaria: rimuovendo la ridondanza, l’informazione non cambia.
La ridondanza è analiticamente definita come
R = 1 H
H
max
(1.15)
dove H è l’entropia della sorgente e H
max
è invece la massima entropia possibile
della sorgente, ovveroH
max
= logn, conn cardinalità dell’alfabeto. La ridondanza è
ovviamentenullaquandoH =H
max
evisonoalcunicasiincuiciòpuòeffettivamente
verificarsi.
1.2.1.1 Ridondanza linguistica
Ogni linguaggio è di per sè ridondante. In ambito linguistico, la ridondanza
consiste nella costruzione di frasi e concetti utilizzando più informazione di quel-
la necessaria, ma che si ritiene necessaria per far comprendere meglio il proprio
messaggio.
Nella lingua parlata spesso si usa la ridondanza in maniera non voluta, ma frasi
ridondanti sono talvolta deliberatamente costruite al fine di enfatizzare un concetto
18CAPITOLO1. TRASMISSIONEECOMPRESSIONEDELL’INFORMAZIONE
e ridurre la possibilità che la frase venga fraintesa. La ridondanza prende spesso
la forma della tautologia, per cui le frasi ripetono un concetto sfruttando parole
semanticamente simili, come ad esempio “storia passata” o “piani futuri”.
La ridondanza nei linguaggi è osservabile anche a livello fonologico. In tal ca-
so viene utilizzata la ridondanza per facilitare l’interlocutore nella pronuncia delle
parolechecompongonoilmessaggiooperrisolvereproblemidiomonimiadeitermini.
Per meglio comprendere questi concetti e in particolare l’idea di ridondanza
nei linguaggi, è stata sviluppata insieme a questa Tesi un’applicazione in C# che si
occupadicompiereanalisistatistichesufiletestualiebinariingenerale,calcolandone
l’entropia e la ridondanza. Per la precisione, le considerazioni statistiche sono fatte
calacolando l’entropia di ordine 0, quindi considerando tutti i simboli dell’alfabeto
individualmente e indipendentemente dagli altri
9
.
L’applicazione ha un’interfaccia molto semplice e richiede come ingresso un file.
Nelle analisi effettuate sono stati utilizzati solamente file di testo, in particolare
presi dal Calgary Corpus e dal Canterbury Corpus, collezioni di files molto famose
in letteratura nell’ambito della compressione dei file.
La prima analisi è stata compiuta sul file “random.txt”, costituito da 100000
bytes generati casualmente da un alfabeto alfanumerico di dimensione 64.
(a) Frequenza dei 256 bytes (b) Frequenza dei caratteri alfabetici
Figura 1.4: Analisi statistica del file “random.txt”
La Figura 1.4(a) mostra la distribuzione dei 256 possibili valori di un byte conte-
nuti nel file. Si nota chiaramente come i vary byte siano effettivamente raggruppabili
in 3 gruppi: caratteri numerici, lettere maiuscole e lettere minuscole, più il byte 32
che corrisponde allo spazio. La Figura 1.4(b) analizza invece la distribuzione di pro-
babilità dei soli caratteri alfabetici, ignorando il fatto che una determinata lettera
sia maiuscola o minuscola.
Per avere una corrispondenza numerica con la figura, si osservi la Tabella 1.2
che riporta i valori delle frequenze di ciascun carattere alfabetico all’interno del file.
Dal momento che viene ignorato il fatto che una lettera sia maiuscola o minuscola,
con il simbolo “A” si intende sia la lettera maiuscola “A” che quella minuscola “a”.
Il calcolo dell’entropia del contenuto del file porta al valore numerico di 4:70
bit=simbolo, mentre la ridondanza percentuale calcolata usando la formula (1.15) è
dello 0:01%. Tali valori non dovrebbero ovviamente sorprendere poichè il teorema
(1.7) afferma chiaramente che l’entropia è sempre minore o uguale al valore logM,
dove M è la cardinalità dell’alfabeto. Inoltre, l’entropia assume il valore massimo
9
Ordini successivi di entropia tengono in considerazione la distribuzione di probabilità dei
digrammi, trigrammi e parole di lunghezza maggiore, in questo contesto non trattati.