11.1
Codifica di sorgente↓
Una fonte informativa (o sorgente) può essere
per sua natura di tipo discreto, come nel caso di un documento scritto,
o di tipo continuo, come nel caso di un segnale analogico, ad esempio
audio e video. In base a considerazioni di tipo statistico, la sorgente
può essere caratterizzata da una grandezza, l’entropia, che
indica il tasso di informazione (in bit/secondo) intrinseco per
i messaggi prodotti dalla sorgente; d’altra parte, la descrizione in
modo nativo dei messaggi prodotti può risultare in una velocità di
trasmissione ben superiore!
Lo scopo della codifica di sorgente è
quello di individuare rappresentazioni alternative per le informazioni
prodotte dalla sorgente, in modo da ridurre la quantità di bit/secondo
necessari alla trasmissione, a valori quanto più possibile prossimi a
quelli dell’entropia, sfruttando le caratteristiche della sorgente, del
processo di codifica, e del destinatario dei messaggi, ovvero
- la particolare distribuzione statistica dei simboli o dei valori
emessi dalla sorgente, che può permettere l’uso di un minor numero di
bit per rappresentare i simboli più frequenti di altri;
- la dipendenza statistica presente tra simboli successivi, ovvero la
presenza di un fenomeno di memoria intrinseco della sorgente, che
rende possibile entro certi limiti la predizione dei valori
futuri;
- l’introduzione di un ritardo di codifica, che permette di
analizzare un intero intervallo temporale del messaggio;
- nel caso di segnali multimediali, l’esistenza di fenomeni
percettivi legati alla fisiologia dell’apparato sensoriale, che
possono guidare il codificatore nella scelta delle componenti di
segnale da sopprimere, in quanto percettivamente non rilevanti.
Nel caso di sorgenti nativamente discrete, come
ad esempio documenti in formato elettronico, lo scopo della codifica di
sorgente è quello di permettere la ricostruzione integrale di
quanto trasmesso, che dunque viene detta senza perdita di
informazione. Nel caso invece di sorgenti continue, si ottiene una
sequenza numerica a seguito di un processo di campionamento e
quantizzazione, che determina l’insorgenza di una prima causa di distorsione
nel messaggio ricostruito, mentre la velocità binaria effettiva può
essere ulteriormente ridotta grazie allo sfruttamento dei fenomeni
percettivi: in tal caso il risultato della codifica viene detto con
perdita di informazione.
11.1.1
Codifica di sorgente discreta
Prendiamo in considerazione una sorgente
discreta e stazionaria, che emette una sequenza x(n)
composta di simboli xk
appartenenti ad un alfabeto di cardinalità L
(ossia con k = {1,
2, ⋯, L}), ognuno
contraddistinto dalla probabilità di emissione pk
= Pr(xk). Il termine senza memoria si
riferisce al fatto che, se indichiamo con xh,
xk una coppia di simboli emessi uno
dopo l’altro (ossia x(n) = xh, x(n + 1) = xk), la
probabilità del simbolo emesso per secondo non dipende dall’identità di
quello(i) emesso precedentemente, ossia p(xk ⁄ xh) = p(xk) = pk.
Misura
dell’informazione
↓↓
Definiamo informazione (espressa in
bit)
associata all’osservazione del simbolo
xk
il valore
Ik = I(xk) = log2(1)/(pk)
= − log2pk bit
che rappresenta il grado di incertezza a riguardo del verificarsi
dell’evento
xk
(prima che questo si verifichi), ovvero di quanto possiamo ritenerci
sorpresi nel venire a conoscenza dell’evento
xk,
di cui riteniamo di conoscere la probabilità
pk.
Osserviamo infatti che per come è fatta la funzione logaritmo, a bassi
valori di probabilità è associata una informazione elevata. La scelta di
usare il logaritmo in base 2 produce i seguenti risultati:
Come in termodinamica al concetto di entropia si associa il grado di
disordine in un sistema, così per una sorgente informativa
l’entropia misura il livello di
casualità dei simboli emessi.
Definiamo quindi
entropia (indicata con
H)
di una sorgente discreta
S, il
valore atteso della quantità di informazione apportata dalla conoscenza
dei simboli (scelti tra
L
possibilità) da essa generati
che pesando in probabilità il valore di informazione associato ai
diversi simboli, rappresenta il
tasso medio di informazione per
simbolo delle sequenze osservabili. Come mostrato nell’esercizio che
segue, risulta che:
- se i simboli sono equiprobabili (pk
= (1)/(L) con ∀k),
la sorgente è massimamente informativa, e la sua entropia è la
massima possibile per un alfabeto ad L
simboli, e pari a HsMax
= (1)/(L)∑Lk
= 1log2L = log2L
bit/simbolo;
- se i simboli non sono equiprobabili, allora Hs
< log2L;
- se la sorgente emette sempre e solo lo stesso simbolo, allora Hs = 0.
Da queste osservazioni discende l’espressione
riassuntiva
Per
dimostrare formalmente questo risultato, osserviamo innanzitutto che
Hs ≥ 0 in
quanto la (12.1↑)
comprende tutti termini positivi o nulli, essendo log2α
≥ 0 per α = 1⁄pk
≥ 1. Quindi, mostriamo che Hs
− log2L ≤ 0. Innanzitutto riscriviamo il
primo membro della diseguaglianza come
Hs − log2L
= ⎲⎳kpklog2(1)/(pk) − log2L⋅ ⎲⎳kpk
= ⎲⎳kpklog2(1)/(L⋅pk)
dato che ∑kpk
= 1. Quindi, esprimiamolo in termini dei logaritmi naturali,
tenendo conto che log2α = (lnα)/(ln2), e quindi
⎲⎳kpklog2(1)/(L⋅pk) = (1)/(ln2) ⎲⎳kpkln(1)/(L⋅pk)
A questo punto utilizziamo la relazione
lnα ≤ α − 1 mostrata in
figura, con l’uguaglianza valida solo se α
= 1, ottenendo così
Hs −
log2L
= (1)/(ln2) ⎲⎳kpkln(1)/(L⋅pk) ≤ (1)/(ln2) ⎲⎳kpk⎛⎝(1)/(L⋅pk) − 1⎞⎠
=
= (1)/(ln2)⎛⎝ ⎲⎳k(1)/(L) − ⎲⎳kpk⎞⎠
= (1)/(ln2)(1 − 1)
= 0
con il segno di uguale solo se (1)/(L⋅pk) = 1 ovvero pk
= (1)/(L⋅).
Entropia
di sorgente binaria
↓
Nel caso particolare delle sorgenti binarie, che
producono uno tra due simboli
{x0,
x1} con
probabilità rispettivamente
p0
= p,
p1 = q
= 1 − p, la formula dell’entropia fornisce l’espressione
il cui andamento è mostrato nella figura
11.3↓, in funzione di
p.
I due simboli
{x0,
x1} possono
essere rappresentati dalle 2 cifre binarie
{0, 1},
che in questo caso chiamiamo
binit, per non confonderli con la
misura dell’informazione (il bit). Osserviamo quindi che se
p
≠ .5 risulta
Hb(p) <
1, ossia la sorgente emette informazione con un tasso inferiore
a un bit/simbolo, mentre a prima vista non potremmo usare meno di un
binit per rappresentare ogni simbolo binario, introducendo una
ridondanza
↓
pari a
1 − Hb(p) (graficata)
.
Esempio Consideriamo
il caso di una sorgente con p0
= 0.8 e p1 = 0.2.
L’applicazione della (12.3↑)
fornisce un valore Hb(0.8) = .8log2(1)/(.8) + .2log2(1)/(.2) = 0.72 bit/simbolo,
minore del valore di 1 bit/simbolo che si sarebbe ottenuto nel caso di
equiprobabilità.
Entropia
di sorgente L-aria
L’applicazione della (
12.2↑) al caso di una sorgente che emette
simboli
non equiprobabili ed appartenenti ad un alfabeto di
cardinalità
L, determina per la
stessa un valore di entropia
HL
< log2L bit/simbolo: se i simboli sono
codificati utilizzando
⌈log2L⌉ binit/simbolo, otteniamo
una ridondanza pari a
⌈log2L⌉ − HL.
Esempio Consideriamo
il caso di una sorgente quaternaria con p0
= 0.5, p1 = 0.25,
p2 = 0.125, p3
= 0.125. L’applicazione della (12.1↑) fornisce H4
= 1.75 bit/simbolo, inferiore ai 2 bit/simbolo che si
sarebbero ottenuti nel caso di simboli equiprobabili.
11.1.1.2
Intensità informativa e codifica binaria ↓
Continuiamo a riferirci ad una sorgente discreta
e senza memoria, caratterizzata da una entropia
Hs
bit/simbolo, ed i cui simboli
xk
sono emessi ad una frequenza
fs
simboli/secondo: il
flusso informativo prodotto è dunque
caratterizzato da una
intensità o
velocità informativa
pari a
R = fs⋅Hs
bit/secondo
Volendo trasmettere tale informazione attraverso un
canale binario
(vedi §
11.2.1↓),
occorre che l’elemento indicato nella figura a lato come
codificatore
binario faccia corrispondere ad ogni simbolo
xk
una univoca sequenza di
Nk
bit (d’ora in poi indicata come
codeword↓ appartenente ad
un
codebook↓), scelti in uno dei modi
descritti nel seguito, producendo una
velocità di trasmissione
binaria di
fb binit⁄sec. Dal punto di
vista del canale, il messaggio è prodotto da una nuova sorgente, i cui
simboli binari hanno probabilità
p
e
1 − p, e dunque caratterizzata
da una entropia
Hb(p) bit⁄binit
≤ 1. Dato che l’intensità informativa in ingresso ed in uscita
dal codificatore deve essere la stessa, la
velocità binaria
fb
della nuova sorgente rispecchia il vincolo
fb ≥ fb⋅Hb(p) = fs⋅Hs
= R
Il rapporto
N =
(fb)/(fs) ≥ Hs
rappresenta il numero
medio di cifre binarie emesse per ciascun
simbolo della sorgente, e può essere valutato a partire dalle
probabilità
pk
dei simboli
xk,
come
N = ∑kpkNk.
Il primo teorema di Shannon
↓,
o della
codifica di sorgente, afferma che
esiste un modo
di scegliere gli
Nk
binit associati ai simboli
xk
tale che
con
ϵ piccolo a piacere, e che si
annulla in corrispondenza della codifica
ottima, per la quale
risulta
N = Hs.
Ma non dice come fare.
Rappresenta l’efficienza del processo di
codifica binaria, ed è definito come
η = (Hs)/(N) = (R)/(fb)
= Hb(p) ≤ 1
ovvero quanti bit di sorgente sono trasportati da ogni binit di codifica. D’altra parte, sappiamo già che se i binit
emessi a velocità
fb
assumono i valori 0 o 1 in modo equiprobabile, allora
Hb⎛⎝(1)/(2)⎞⎠ = 1,
ovvero
fb = R
e
N = Hs,
e dunque il problema di individuare un codice ottimo sembrerebbe quello
di trovare un insieme di
parole di codeword tali da rendere le
cifre binarie equiprobabili, con il vincolo di mantenere il codice
decifrabile,
ovvero tale da rispettare la
regola del prefisso. Ma andiamo con
ordine.
11.1.1.3
Codifica con lunghezza di parola variabile
Mostriamo mediante un esempio come scegliendo codeword
più lunghe
per rappresentare i simboli
meno probabili, e
più corte
per i simboli
più frequenti, si può subito ottenere un miglior
rendimento del codice. Consideriamo infatti una sorgente con alfabeto di
cardinalità
L = 4, ai cui simboli
competono le probabilità riportate alla seconda colonna della tabella.
In questo caso l’entropia vale
Hs
=
⎲⎳kpklog2(1)/(pk)
=
(1)/(2)log22 + (1)/(4)log24 + (2)/(8)log28 = (1)/(2) + (1)/(2) + (2)/(8)3 = 1.75
bit/simbolo
Se il codificatore di sorgente adotta le corrispondenze mostrate nella
terza colonna della tabella, a cui competono le lunghezze in binit
riportate quarta colonna, il numero
medio di binit/simbolo
prodotto dalla codifica binaria risulta pari a
N = E{L} = ⎲⎳kNkpk
= 1⋅(1)/(2) + 2⋅(1)/(4)
+ 3⋅(2)/(8) = 1.75
binit/simbolo
Il risultato ottenuto
Hs
= N, ovvero il migliore
possibile, non è per nulla scontato, e mostriamo appresso come dipenda
sia dalla particolare scelta fatta per le codeword, sia dal particolare
tipo delle
pk
dell’esempio, tutte potenze negative di due (essendo
0.5
= 2 − 1,
0.25 = 2 − 2,
0.125 = 2 − 3).
Perché un insieme di codewords possa costituire
un
codice di sorgente, esse devono poter essere riconosciute
come
distinte presso il ricevitore, e questo è possibile a patto
che nessuna di esse sia
uguale all’inizio di una codeword più
lunga. Si può mostrare che ciò è possibile purché le lunghezze
Nk
delle codeword soddisfino la
disuguaglianza di Kraft↓, espressa come
Esempio Nella tabella sono riportati quattro possibili codici
(A,B,C,D) per la sorgente quaternaria già discussa, assieme
al corrispettivo valore di N
e K.
Il codice A
corrisponde ad un codificatore particolarmente banale con Nk
= N per tutti i k, dunque la (12.5↑) diviene K
= L2 − N ≤
1 ed è soddisfatta a patto che N ≥ log2L:
nel nostro caso essendo L = 4
ed N = 2
si ottiene N
= log2L = 2 e quindi K
= 1, dunque il codice è decifrabile (anche perché a
lunghezza fissa), ma non particolarmente efficiente, in quanto (Hs)/(N) ≤ (Hs)/(log2L) e nel nostro caso,
anche se vale l’eguaglianza, si ottiene (Hs)/(N)
= 0, 875 < 1; in questo caso, o in generale quando Hs < log2L,
si può realizzare una efficienza migliore ricorrendo ad un codice
a lunghezza variabile.
Le
codeword del codice B producono un valore K
= 1.25 > 1, e dunque rappresentano un codice
ambiguo:
difatti violano sia la regola del prefisso, che il limite (12.5↑). Il codice C invece è
non ambiguo, essendo K < 1,
ma presenta una efficienza (Hs)/(N)
= 0, 93 < 1 e dunque
subottimale. Infine, il codice D è quello analizzato al
precedente paragrafo, ed effettivamente risulta una scelta ottima,
dato che (Hs)/(N) = 1 e le sue
codeword soddisfano la (12.5↑).
Indichiamo con questo termine un codice che soddisfa la regola del
prefisso, e per il quale
(Hs)/(N)=1: ciò equivale a dire che
i valori delle probabilità di simbolo
devono risultare potenze
negative di due, ovvero
pk
= 2 − Nk. In tal caso la
(12.5↑)
è verificata con il segno di uguale,
e scegliendo le lunghezze di codeword proprio pari a
Nk
= log2(1)/(pk),
possiamo verificare come l’espressione che calcola
N = ∑kpkNk
coincida con quella che fornisce
Hs
= ∑kpklog2(1)/(pk), ovvero ogni simbolo è
codificato con una codeword lunga tanti binit quanti sono i bit di
informazione che trasporta. Per individuare un codice che
si
avvicini a questa proprietà si può realizzare la tecnica di
Huffman
presentata appresso, mentre per
modificare le
pk
si ricorre alla
codifica per blocchi di simboli.
Si tratta di un algoritmo che permette di
realizzare un codice a lunghezza variabile che soddisfa la regola del
prefisso, adotta codeword più lunghe ai simboli meno probabili, ed
uniforma, per quanto possibile, la probabilità delle cifre binarie. Si
basa
sulla costruzione di un albero binario, i cui rami sono etichettati con
1 e 0, e può essere descritto come segue:
- crea una lista contenente
i simboli della sorgente, ordinati per valore di probabilità
decrescente, ed associa ad ognuno di essi un nodo-foglia
dell’albero;
- finché c’è più di un nodo
nella lista:
- rimuovi dalla lista i
due nodi con la probabilità più bassa;
- crea un nuovo nodo
interno all’albero con questi due nodi come figli, e con
probabilità pari alla somma delle loro probabilità;
- aggiungi il nuovo
nodo alla lista;
- il nodo rimanente è la
radice, e l’albero è completo;
- assegna cifre binarie
diverse ad ogni coppia di rami a partire dalla radice,
concatenando le quali ottieni le codeword per i simboli sulle
foglie
Si può dimostrare che il codice di Huffman
generato in questo modo è il migliore possibile nel caso in cui la
statistica dei simboli di sorgente sia nota a priori, nel senso che
produce una codifica con il minor numero possibile di binit/simbolo
medi. La codifica di Huffman è ampiamente utilizzata nel contesto di
altri metodi di compressione (metodo
deflate
di
pkzip, §
11.1.1.7↓) e di codec multimediali (
jpeg
e
mp3, cap.
12↓), in virtù della sua semplicità, velocità,
ed assenza di brevetti.
Ovviamente ci deve essere un accordo a priori tra
sorgente e destinatario a riguardo delle corrispondenze tra parole di
codice e simboli (o blocchi di simboli) della sorgente. Nel caso in cui
ciò non sia vero, oppure nel caso in cui la statistica dei simboli della
sorgente sia stimata a partire dal materiale da codificare, occorre
inviare all’inizio della comunicazione anche la tabella di
corrispondenza, eventualmente in forma a sua volta codificata.
Esempio una sorgente con L
= 8 simboli è caratterizzata dalle probabilità di simbolo
riportate in figura, a partire dalle quali si realizza un codice di
Huffman mediante la costruzione grafica riportata, in cui le
probabilità sono scritte sotto i rami ed accanto ai simboli,
mentre i binit sopra. Dopo aver ordinato i simboli in base
alle probabilità, si individuano i due nodi a prob. più bassa come a1 e a2,
che assommano prob. 0.09; dunque la coppia ora meno probabile è a3 con a5,
che cumulano prob. 0.126. Quindi, le due prob. minori divengono
quelle di a4 e
della coppia a1a2,
per un totale di 0.237, e poi è il turno di raggruppare a6
con a3a5,
per un totale di 0.273. Quest’ultimo nodo viene allora combinato con
a7 con
prob. complessiva 0.42, quindi è il turno di a8
con a1a2a4
che totalizzano 0.58, ed infine questo nodo è collegato con il (5).
A questo punto, partendo dalla radice a destra, si assegna un binit
pari a 0 o 1 ad ogni coppia di rami, ripetendo l’assegnazione per le
coppie discendenti, fino al risultato mostrato.
Questa variante permette di costruire e
modificare l’albero di codifica
man mano che i simboli sono trasmessi. In questo modo, se un carattere è
già presente nel codebook, viene trasmessa la codeword corrispondente,
mentre se non lo è, viene trasmesso il codice del carattere, ed
aggiornato il codebook. Lo stesso processo si svolge anche dal lato
ricevente, permettendo una codifica in tempo reale, e l’adattamento a
condizioni di variabilità nei dati. Ovviamente, il metodo inizia ad
essere efficiente solo dopo aver accumulato sufficienti informazioni
statistiche.
11.1.1.4
Codifica per blocchi↓
Riprendiamo la discussione iniziata a pag.
1↑ relativa al codice binario ottimo per una
sorgente
L − aria senza memoria
con simboli
ak a
probabilità
pk,
notando che se la lunghezza
Nk
delle codeword viene scelta in modo tale che
si può mostrare che la condizione
(12.5↑) è soddisfatta. Inoltre, moltiplicando i
membri di
(12.6↑)
per
pk e
sommando su
k si ottiene
Hs ≤ N
≤ Hs + 1
da cui si osserva che è possibile ottenere
(Hs)/(N)≃1 solo se
Hs≫1
oppure se
Nk≃log2(1)/(pk). Altrimenti, possiamo
ricorrere al
trucco di
trasformare la nostra sorgente ad
L simboli in una equivalente con
Ln simboli, ottenuti
concatenando
n simboli della
sorgente originaria. Dato che questi ultimi sono indipendenti, la nuova
sorgente esibisce una entropia
Hbloccos
= nHs, e la regola di codifica
(12.6↑) produce ora il risultato
nHs
≤ nN ≤ nHs
+ 1 in cui
nN
è il numero medio di binit per blocco. Dividendo per
n,
otteniamo infine
che rappresenta una diversa forma del teorema
(12.4↑) con
ϵ = (1)/(n), e che permette di
ottenere
N → Hs
se
n → ∞, avvicinandosi alle
condizioni di codifica ottima per qualsiasi distribuzione delle
pk.
Per applicare questo metodo ad un caso pratico, consideriamo una
sorgente binaria senza memoria con le pk
mostrate in tabella, e raggruppiamone i simboli a coppie, a cui
competono probabilità di emissione ottenute moltiplicando le probabilità
originarie,
e quindi codifichiamo i nuovi simboli quaternari con il codice a
lunghezza variabile già esaminato.
Mentre il valore dell’entropia della sorgente
binaria originale è ancora quello calcolato nel primo esempio a pag.
1↑
e pari a
Hb = 0.72
bit a simbolo, la lunghezza media del nuovo codice risulta ora
N = 1⋅0.64
+ 2⋅0.16 + 3⋅0.16 + 3⋅0.04 = 1.58 binit
ogni 2 simboli, ossia pari ad una media di 0.79 binit/simbolo binario,
effettivamente più vicina al valore di
Hb
= 0.72.
Compromesso
velocità-ritardo
↓
Come indicato dalla
(12.7↑), realizzando blocchi via via più lunghi
è possibile ridurre la velocità media di codifica
N (in binit/simbolo)
rendendola sempre più vicina all’entropia, ovvero
min[N] = Hs + ε
in cui ε
→ 0 se la lunghezza
del blocco tende ad infinito. D’altra parte, all’aumentare della
dimensione del blocco aumenta di egual misura il ritardo che
intercorre tra l’emissione di un simbolo e la sua codifica, e di
questo va tenuto conto, nel caso sussistano dei vincoli temporali
particolarmente stringenti sulla consegna del messaggio.
Qualora una sorgente discreta ad L
simboli esibisca un valore di entropia inferiore a log2L,
la velocità binaria in uscita dal codificatore di sorgente può essere
ridotta adottando una codifica a blocchi, e utilizzando per i nuovi
simboli un opportuno codice di Huffman.
Esercizio Si
ripeta il calcolo del numero medio di binit/simbolo, adottando lo
stesso codice a lunghezza variabile usato finora, per codificare i
simboli emessi dalla sorgente binaria Markoviana di primo ordine
analizzata all’esempio seguente, e mostrare come in questo caso si
riesca ad ottenere una velocità media pari a 0.72
bit/simbolo. Sperimentare quindi la costruzione di un codice di
Huffman basato sul raggruppamento di tre simboli di sorgente, per
verificare se ci si riesce ad avvicinare di più al valore limite
indicato dalla entropia, come vedremo pari a 0.58
bit/simbolo.
11.1.1.5
Sorgente con memoria↓
Rimuoviamo ora l’ipotesi di indipendenza
statistica tra i simboli emessi. In questo caso indichiamo con
x
= {x(1), x(2), …, x(N)} una
sequenza di
N di simboli, la cui
probabilità congiunta si calcola come
p(x) = p(x1)p(x2
⁄ x1)p(x3
⁄ x1, x2)…p(xN ⁄ x1,
x2, …xN − 1)
≠ N∏k = 1p(xk)
dato che appunto la dipendenza statistica comporta l’uso delle
probabilità condizionali. In questo caso, l’espressione dell’entropia si
modifica in
HN = Ex{I(x)} = − (1)/(N)
⎲⎳
per tutte le x p (
x )log2p(x) bit/simbolo
dove la sommatoria si intende replicata
N
volte, in modo da eseguire la media statistica su tutte le possibili
sequenze
x di lunghezza
N.
La grandezza
HN
prende il nome di
entropia a blocco↓,
e si dimostra che al crescere di
N
il suo valore è
non crescente, ossia
HN
+ 1 ≤ HN ≤ HN − 1,
mentre per
N → ∞,
HN tende ad un valore
H∞ ≤ Hs,
in cui l’uguaglianza è valida solo per sorgenti senza memoria.
Se oltre ad un certo valore NMax
= M la sequenza HN
non decresce più, allora la sorgente è detta a memoria finita o
di Markov di ordine M,
caratterizzata dal fatto che le probabilità condizionate dipendono solo
dagli ultimi M simboli emessi.
Esempio Analizziamo il caso di una sorgente binaria di
Markov del primo ordine, per la quale sono definite le probabilità mostrate a lato,
ed a cui
corrisponde il diagramma di transizione mostrato. In questo
caso, l’ultimo simbolo emesso determina lo stato della
sorgente, condizionando così i valori delle probabilità di
emissione di un nuovo simbolo: con i valori dell’esempio, si
osserva come la sorgente preferisca continuare ad
emettere l’ultimo simbolo prodotto, piuttosto che l’altro.
Sotto un certo punto di vista, è come se ora vi
fossero
LM
diverse sorgenti (nel caso dell’esempio,
21
= 2), ognuna con delle probabilità di emissione differenti in
base allo stato
Si
(o memoria) in cui si trova. Perciò, in questo caso l’entropia di
sorgente può essere calcolata applicando la (
12.3↑) ad ognuno dei possibili stati, ottenendo
dei valori di
entropia condizionata↓
H(x ⁄ Si), ed il valore dell’entropia di
sorgente può essere ottenuto come
valore atteso dell’entropia
condizionata rispetto alle probabilità di trovarsi in ognuno degli stati
del modello Markoviano.
Tornando
all’esempio, i valori di entropia condizionata risultano pari a
H(x
⁄ 0)
= − 0.9log20.9
− 0.1log20.1 = 0.47
H(x ⁄ 1)
= − 0.4log20.4 −
0.6log20.6 = 0.97
bit/simbolo, mentre il valore della probabilità di trovarsi in uno
dei due stati si ottiene risolvendo il sistema
⎧⎨⎩
p(0)
= p(0
⁄ 0)p(0) + p(0
⁄ 1)p(1)
1 = p(0) + p(1)
in cui la prima equazione asserisce che la probabilità di trovarsi
in S0 è pari alla
somma di quella di esserci già, per quella di emettere ancora zero,
più la probabilità di aver emesso uno, ed ora emettere zero.
Sostituendo i valori, si ottiene p(0) = 0.8
e p(1) = 0.2, ossia gli stessi valori
dell’esempio binario senza memoria. Ma mentre in quel caso il valore
dell’entropia risultava pari a 0.72
bit/simbolo, ora si ottiene
H = p(0)H(x
⁄ 0) + p(1)H(x
⁄ 1) = 0.58
bit/simbolo
mostrando come la presenza di memoria aumenti la predicibilità delle
sequenze emesse dalla sorgente.
Esercizio Si ripeta il calcolo dell’entropia per un modello di
Markov del primo ordine, caratterizzato dalle probabilità p(0) = p(1) = 0.5
e p(1 ⁄
0) = p(0
⁄ 1) = 0.01, mostrando che
in questo caso si ottiene una entropia di 0.08 bit/simbolo.
11.1.1.6
Codifica per sorgenti con memoria
La
discussione appena svolta ha evidenziato come nel caso di sorgenti con
memoria i valori di entropia si riducano ulteriormente, e
conseguentemente anche la velocità di codifica, a patto di accettare un
maggior ritardo legato all’uso di codici a blocchi. A volte però la
dimensione dei blocchi da prendere in considerazione può risultare
eccessiva, producendo spropositate tabelle di codeword. Inoltre si può
ritenere di
non conoscere la statistica della sorgente, e di non
desiderare effettuarne una stima, ed evitare di trasmettere la tabella
di codeword. In questi casi, può essere opportuno adottare tecniche
diverse dalle precedenti, come le due riportate appresso.
↓Prendendo
come esempio tipico il caso della trasmissione fax, in cui si ha a che
fare con un segnale di immagine in bianco e nero, scansionato per righe,
che è assimilabile ad una sorgente binaria che emetta uno zero per il
bianco, ed un uno per il nero: per la natura delle immagini scansionate,
tipicamente ci saranno lunghe sequenze di uni o di zeri, e dunque si può
assumere valido un modello di sorgente Markoviano di primo ordine, con
elevate probabilità condizionate di restare nello stesso stato.
Le lunghe sequenze di bit tutti uguali vengono
dette run (corse), e la codifica run-length consiste
effettivamente nel trasmettere una parola di codice che indica il numero
(length) di questi bit uguali. In questo caso quindi, la codeword
è di lunghezza fissa (ad esempio k + 1
binit, il primo dei quali indica se il run è tutto di uni o di zeri), e
rappresenta un numero variabile (da 0 a 2k − 1) di binit di
sorgente. Se ad esempio k = 6
binit, questi 6+1 = 7 binit possono codificare fino a 64 bit di
immagine: un bel risparmio!
Questa ulteriore tecnica si basa sul fatto che
un elevato grado di dipendenza statistica dei messaggi comporta la
possibilità di predire in qualche modo i simboli a venire, in
base all’identità di quelli già emessi. La differenza tra la sequenza
predetta x̃(n) e quella effettiva x(n)
è una nuova sequenza indicata come errore di predizione e(n) = x̃(n) − x(n)
che, se il predittore ci azzecca per la maggior parte del tempo,
è quasi tutta nulla.
Nella figura seguente mostriamo l’applicazione
della tecnica al caso di sequenze binarie, per le quali l’operazione di
differenza è realizzata tramite una somma modulo due
e(n) = x̃(n)⊕x(n),
in modo che nel caso di predizione corretta, l’errore sia nullo;
possiamo verificare l’effettiva invertibilità del processo di predizione
binaria confrontando lo schema mostrato con quello proposto per la
codifica differenziale al §
14.4↓.
Il predittore conserva uno stato interno
che rappresenta gli ultimi bit di ingresso, in base ai quali determina la stima x̃(n); l’errore e(n)
che è frequentemente nullo, e che viene sottoposto a codifica
run-length, è re-inserito anche nel predittore, in modo che questo possa
ri-determinare l’ultimo simbolo di ingresso x(n) = e(n)⊕x̃(n),
ed aggiornare il proprio stato interno. La medesima formula di
ricostruzione viene applicata anche in uscita del predittore di
ricezione, che condivide con quello di trasmissione la conoscenza dello
stato iniziale del segnale trasmesso, in modo da evolvere allo stesso
modo.
Notiamo come la codifica run-length non preveda
l’esistenza di un accordo a priori tra trasmettitore e ricevitore, a
parte il comune stato di partenza ad inizio messaggio, mentre la
codifica predittiva necessita solo di un accordo in merito alla
struttura del predittore. Per contro, in presenza di errori di
trasmissione i due predittori restano disallineati, finché non si inizia
a co-decodificare un nuovo messaggio. Ma lo stesso problema è comune
anche al caso di codifica a lunghezza di parola variabile, ed a quello
di Huffman dinamico.
11.1.1.7
Compressione basata su dizionario↓
Nella comune accezione del termine, un
dizionario è costituito da un array di stringhe, popolato con le
parole esistenti per un determinato linguaggio. Anziché operare
carattere per carattere, un codificatore di sorgente testuale può
ricercare la posizione nel dizionario delle parole del messaggio, e
quindi trasmettere l’indice della parola: per un dizionario di 25.000
termini bastano 15 bit di indirizzamento, ottenendo un rapporto di
compressione variabile, in funzione della lunghezza della parola
codificata.
Metodo
di Lempel-Ziv-Welsh
↓
Per evitare di dover condividere la conoscenza
dell’intero dizionario tra sorgente e destinatario, che tra l’altro
potrebbe essere assolutamente sovradimensionato rispetto alle
caratteristiche dei messaggi da trattare, il metodo lzw
prevede che il codificatore generi il dizionario in modo graduale, man
mano che analizza il testo, e che il decodificatore sia in grado di
replicare questa modalità di generazione. Inoltre, il dizionario non è
vincolato a contenere le reali parole del messaggio, ma
semplicemente ospita le sequenze di caratteri effettivamente osservati,
di lunghezza due, tre, quattro...
Operando su di un alfabeto ad
L
simboli, rappresentabili con
n = ⌈log2L⌉ bit, il dizionario iniziale conterrà
i simboli di sorgente alle prime
L
posizioni, e posti liberi
nelle restanti
2n − L −
1 posizioni.
Ogni carattere letto in ingresso viene accodato in una
stringa,
ed il risultato confrontato con le stringhe già presenti nel dizionario.
Nel caso non si verifichi nessuna corrispondenza, viene aggiunta una
nuova voce di dizionario, e quindi viene trasmesso il codice associato
alla sua parte iniziale, escludendo cioè il simbolo concatenato per
ultimo, e che ha prodotto l’occorrenza della nuova voce.
Nel caso invece
in cui la stringa sia già presente (e questo in particolare è vero per
la stringa di lunghezza uno corrispondente al primo simbolo analizzato)
non si emette nulla, ma si continuano a concatenare simboli fino ad
incontrare una stringa mai vista. Presso
Wikipedia
è presente un esempio di risultato della codifica.
La parte iniziale del testo, ovviamente, ha una
alta probabilità di contenere tutte coppie di caratteri mai viste prima,
e quindi in questa fase vengono semplicemente emessi i codici associati
ai simboli osservati. Con il progredire della scansione, aumenta la
probabilità di incontrare stringhe già osservate e sempre più lunghe.
Ogni volta che viene esaurito lo spazio residuo per i nuovi simboli,
viene aggiunto un bit alla lunghezza della codeword, ovvero viene
raddoppiata la dimensione del vocabolario. Man mano che viene analizzato
nuovo materiale, aumenta la lunghezza delle stringhe memorizzate nel
dizionario, che riflette l’effettiva composizione statistica del
documento in esame, ivi compresa la presenza di memoria; allo stesso
tempo, la dimensione del dizionario (e la lunghezza delle codeword)
resta sempre la minima indispensabile per descrivere il lessico
effettivamente in uso. Alla fine del processo, il dizionario ottenuto
viene aggiunto in testa al file compresso, seguito dalle
codeword risultanti dall’algoritmo.
L’algoritmo lzw
è usato nel programma di compressione Unix compress, per la
realizzazione di immagini gif e tiff, ed incorporato in altri software,
come ad esempio Adobe Acrobat.
L’ultimo metodo di compressione senza perdite
che esaminiamo è quello che è stato introdotto dal programma pkzip,
e quindi formalizzato nella rfc 1951,
e tuttora ampiamente utilizzato per le sue ottime prestazioni e
l’assenza di brevetti. Usa una variante dell’algoritmo lzw,
al cui risultato applica poi una codifica di Huffman. Deflate
opera su blocchi di dati con dimensione massima 64 Kbyte, ognuno dei
quali può essere replicato intatto (come nel caso in cui i bit siano già
sufficientemente impredicibili), oppure essere compresso con un codice
di Huffman statico, oppure ancora dinamico.
Per quanto riguarda la variante di lzw,
essa consiste nel non costruire esplicitamente il dizionario, ma
nell’usare invece dei puntatori all’indietro per specificare che
una determinata sotto-stringa di ingresso, è in realtà la ripetizione di
un’altra già osservata in precedenza. In questo caso, anziché emettere
il codice (di Huffman) associato al byte corrente, si emette (il codice
di Huffman del) la lunghezza della stringa da copiare, e la distanza
(nel passato) della stessa. Quindi in pratica, anziché usare una
codeword di lunghezza fissa per indicizzare gli elementi del dizionario
come per lzw, viene usato un puntatore
di lunghezza variabile, privilegiando le copie della sottostringa
corrente più prossime nel tempo, oppure quelle con un maggior numero di
caratteri uguali.
11.1.2
Codifica con perdite di sorgente continua↓
Come verrà mostrato ai §
11.2.3↓ e
11.2.4↓, un segnale
r(t)
di potenza
S ricevuto mediante un
canale alla cui uscita sia presente un filtro con banda
W
ed rumore
n(t) gaussiano bianco di potenza
N
non può convogliare un tasso di informazione
R
più elevato della
capacità di canale pari a
C
= Wlog2⎛⎝1 + (S)/(N)⎞⎠ bit
per secondo. Nel caso discreto e senza perdite trattato finora,
C
pone semplicemente un limite massimo al tasso di informazione che può
essere trasmesso. Viceversa, nel caso di una sorgente continua
x(t),
abbiamo due strade possibili: intraprendere un processo di campionamento
e quantizzazione per produrre un segnale numerico con velocità
R
≤ C, incorrendo così in una distorsione di
quantizzazione
D tanto minore
quanto maggiore è la
R consentita,
oppure effettuare una trasmissione analogica in cui
- il rumore al ricevitore può essere visto come una distorsione d(t) = n(t) = x(t) − r(t) di potenza D
= N
- l’entità della distorsione D
può essere ridotta aumentando (S)/(N) oppure W,
e quindi C, permettendo così
l’aumento del tasso di informazione R
trasferito.
Nel caso continuo pertanto, sia che la sorgente
sia quantizzata o che sia trasmessa come segnale analogico, sussiste un
legame diretto tra la distorsione ed il tasso informativo, di cui
discutiamo ora.
11.1.2.1
Curva velocità-distorsione↓
La valutazione della dipendenza tra
D
ed
R si avvale di una serie di
sviluppi teorici
che prendono come caso-tipo quello di una sorgente
x(t)
gaussiana, stazionaria, ergodica e bianca, con potenza
σ2x.
In tal caso si ottiene che la
minima distorsione conseguibile in
corrispondenza di una velocità di trasmissione (
rate) pari ad
R, assume un valore pari a
Questa espressione risulta poi essere
il più grande valore minimo
possibile per una potenza
σ2x
assegnata, dato che per sorgenti non gaussiane, oppure gaussiane ma non
bianche, si possono ottenere valori inferiori. D’altra parte, invertendo
la (
12.8↑)
si ottiene la curva
R(D)G, che descrive la
minima velocità
R necessaria per
trasmettere i campioni di una sorgente gaussiana con distorsione
D e potenza
σ2x
assegnate
R(D)G = ⎧⎨⎩
− (1)/(2)log2(D)/(σ2x)
se 0 ≤ D ≤ σ2x
0
se
D ≥ σ2x
la cui seconda riga può essere interpretata osservando che, se la
distorsione è superiore alla potenza di segnale, non occorre trasmettere
proprio nulla, dato che tanto il ricevitore può ri-generare un segnale
di errore, a partire da un rumore gaussiano di potenza
D
prodotto in loco.
Il valore
D(R)G
costituisce un
limite superiore per ciò che riguarda la
distorsione ottenibile ad una certa velocità
R,
utile per rapportare le prestazioni del codificatore della nostra
sorgente con quelle migliori ottenibili per la sorgente più
difficile,
ossia la gaussiana. Allo stesso tempo, è definito un
limite
inferiore D(R)L (ossia, la minima
distorsione sotto cui non si può scendere per un dato
R)
per sorgenti
non gaussiane e
senza memoria, in modo da
poter scrivere
in cui
Q è la
potenza
entropica (
12.12↓)
e risulta
Q < σ2x
per sorgenti non gaussiane.
In definitiva, per una determinata sorgente per la
quale sono disponibili diversi codificatori, potremmo ottenere una
famiglia di curve del tipo di quelle mostrate in figura.
11.1.2.2
Entropia di sorgente continua↓
Nel caso discreto abbiamo apprezzato come
l’entropia fornisca un potente strumento per valutare il tasso
informativo intrinseco di una sorgente, supportando così la ricerca di
metodi di riduzione della ridondanza al fine di avvicinare la velocità
di trasmissione alla entropia effettiva. Ci chiediamo allora se anche
nel caso continuo possa essere definita una entropia, e come questa
possa aiutarci nello stabilire dei limiti prestazionali. Estendendo
formalmente al caso continuo la definizione trovata per le sorgenti
discrete, si ottiene l’espressione
che è indicata con la
h minuscola
per distinguerla dal caso discreto, e che viene detta
entropia
differenziale↓
o
relativa perché il suo valore può risultare positivo, negativo
o nullo, in funzione della dinamica della variabile aleatoria
X.
Esempio Se
calcoliamo il valore di entropia differenziale per un processo i cui
valori sono descritti da una variabile aleatoria a distribuzione
uniforme px(x) = (1)/(A)rectA(x),
otteniamo il risultato h(X) = − (1)/(A)∫(A)/(2) − (A)/(2)log2⎛⎝(1)/(A)⎞⎠dx =
log2A il cui valore effettivo, appunto,
dipende dal valore di A.
Sebbene inadatta ad esprimere il contenuto
informativo
assoluto di una sorgente
continua, l’entropia differenziale può comunque essere utile per
confrontare tra loro due sorgenti con uguale varianza
σ2x;
in particolare, il massimo valore di
h(X)
per
σ2x assegnata è ottenuto
in corrispondenza di un processo gaussiano,
e risulta pari a
ed è per questo motivo che, a parità di velocità
R
e di potenza
σ2x,
il processo gaussiano incorre nella
massima distorsione minima (
12.8↑).
Associata alla definizione di entropia differenziale, sussiste quella di
potenza entropica↓
Q, scritta come
che per sorgenti gaussiane fornisce
QG
= σ2x,
mentre per altri tipi di statistiche, si ottiene un valore minore.
Applicando questa definizione alla (
12.9↑) osserviamo come il limite inferiore di
distorsione
D(R)L si riduce al
diminuire di
h(X).
11.1.2.3
Sorgente continua con memoria↓
Come per il caso di sorgenti discrete, anche per
quelle continue l’esistenza di una dipendenza statistica tra i valori
prodotti riduce la quantità di informazione emessa, al punto che a
parità di distorsione, questa può essere codificata a velocità ridotta;
oppure, a parità di velocità, può essere conseguita una distorsione
inferiore. Anche stavolta, la sorgente più
difficile (ossia a
cui compete la
massima distorsione minima) è quella gaussiana,
per la quale risulta che la minima distorsione per
σ2x
assegnata può esprimersi come
in cui
0 ≤ γ2x ≤ 1 rappresenta una
misura di
piattezza spettrale, che vale uno nel
caso senza memoria, ovvero di processo
bianco, e si riduce nel
caso di un segnale i cui valori sono correlati tra loro, ed a cui
corrisponde una densità spettrale
colorata.
Nel caso
non gaussiano, infine, la (
12.13↑) si riscrive sostituendo al posto di
σ2x la potenza entropica
Q espressa dalla (
12.12↑), ottenendo valori
D(R)
ancora inferiori.
L’applicazione dei principi relativi alla codifica
di sorgente al caso specifico dei messaggi multimediali (audio e video)
viene trattata al capitolo
12↓.