9.2 Sorgente discreta con memoria
Passiamo ora ad affrontare il caso in cui i simboli emessi dalla sorgente non possano essere ritenuti statisticamente indipendenti. Indicando con
x = {x1, x2, …, xn} una sequenza di
n di simboli, la sua probabilità
congiunta si calcola ora come
dato che appunto la dipendenza statistica comporta l’uso delle probabilità condizionali. L’espressione dell’entropia si modifica dunque in
Hn = Ex{I(x)} = − 1n ⎲⎳.tutte le possibili sequenze x p(x) log2p(x) bit/simbolo
in cui
p(x) è la probabilità congiunta
(10.232) di una possibile sequenza di simboli
x, e la media di insieme è effettuata 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.
9.2.1 Sorgente Markoviana
Se oltre ad un certo valore nMax = M la sequenza Hn non decresce più la sorgente è detta a memoria finita o di Markov di ordine M, ed è 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à condizionate mostrate a lato, a cui corrisponde il
diagramma di transizione raffigurato. Essendo
M = 1, lo
stato della sorgente è determinato dal simbolo emesso per ultimo, che condiziona le probabilità di emissione del simbolo successivo: con i valori dell’esempio, si osserva come la sorgente
preferisca continuare ad emettere l’ultimo simbolo prodotto, piuttosto che l’altro.
In pratica è come se ora vi fossero
LM diverse sorgenti
Si (nel caso dell’esempio,
21 = 2), ognuna associata ad una diversa
storia passata rappresentata dagli ultimi
M simboli emessi (nell’esempio
M = 1), identificativi dello
stato, o
memoria, della sorgente. In questo caso l’entropia di sorgente può essere calcolata applicando la (
10.221) ad ognuno dei possibili stati, ottenendo in tal modo dei valori di
entropia condizionata H(x ⁄ Si), mentre l’entropia di sorgente
complessiva si ottiene 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 ⁄ S0) = − 0.9 log2 0.9 − 0.1 log2 0.1 = 0.47 H(x ⁄ S1) = − 0.4 log2 0.4 − 0.6 log2 0.6 = 0.97
bit/simbolo, mentre il valore della probabilità di trovarsi in uno dei due stati si ottiene risolvendo il sistema
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. Procedendo per sostituzione si ottiene
p(S0) = 0.8 e
p(S1) = 0.2, ossia gli stessi valori dell’esempio binario senza memoria di pag.
1 . Ma mentre in quel caso il valore dell’entropia risultava pari a
0.72 bit/simbolo, ora si ottiene
H = p(S0) H(x ⁄ S0) + p(S1) H(x ⁄ S1) = 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.
9.2.1.1 Autovettore della matrice di transizione
Come qualcuno avrà notato, le probabilità
p(S0) e
p(S1) corrispondono alla statistica di ordine zero (ossia la probabilità incondizionata, o marginale) dei simboli di sorgente
x0 = 0 ed
x1 = 1. I valori
p(Si) possono essere ottenuti (anziché impostando il sistema di equazioni di cui all’esempio precedente) come gli elementi dell’autovettore
vπ associato all’autovalore 1 della
matrice di transizione Π, i cui elementi
πi, j sono pari alle probabilità condizionate
p(xi ⁄ xj), potendo scrivere
Π ⋅ vπ = vπ. In pratica ogni riga di tale sistema di equazioni è l’estensione della prima delle
(10.233) a ciascuno stato della sorgente markoviana.
9.2.2 Codifica per sorgenti con memoria
La discussione svolta fin qui mostra come l’entropia delle sorgenti con memoria sia sempre
minore di quella relativa al caso di indipendenza statistica dei simboli emessi, e qualora le probabilità condizionate siano note al codificatore, possono essere usate per calcolare le probabilità per blocco
(10.232) e con queste individuare un codice di Huffman in grado di ridurre anche la velocità di codifica, a patto di accettare un maggior ritardo legato all’uso di codici a blocchi.
Ma la dimensione dei blocchi da prendere in considerazione può divenire 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.
9.2.2.1 Codifica run-length
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 elevata probabilità condizionata di rimanere nello stesso stato.
Le lunghe sequenze di bit tutti uguali vengono dette run (corse), e la codifica run-length consiste nel trasmettere parole di codice che indicano il numero (length) di questi bit uguali. In questo caso quindi la codeword è di lunghezza fissa (ad esempio n + 1 binit, il primo dei quali indica se il run è tutto di uni o di zeri), e rappresenta un numero variabile (da 0 a 2n − 1) di binit di sorgente. Se ad esempio n = 6 binit, questi 6+1 = 7 binit possono codificare fino a 64 (uguali) simboli di sorgente binaria: un bel risparmio!
9.2.2.2 Codifica predittiva
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̂ e quella effettiva x è una nuova sequenza indicata come errore di predizione e = x̂ − x che, se il predittore ci azzecca per la maggior parte del tempo, è quasi tutta nulla. Il predittore conserva uno stato interno che rappresenta gli ultimi bit di ingresso, in base ai quali determina la stima x̂, da cui ottenere l’errore e (frequentemente nullo) che viene sottoposto a codifica run-length, e trasmesso.
Ora avviene un trucco, dato che in realtà il predittore non conosce la sequenza xk − 1, ⋯xk − M da cui predire x̂k, ma viene invece alimentato con la sequenza di errore e, in modo che da questa possa determinare l’ultimo (vero) simbolo di ingresso come x = x̂ − e, ed aggiornare il proprio stato interno. Dal lato ricevente opera un predittore identico a quello di codifica, anch’esso alimentato dalla sequenza e in modo da generare un valore x̂ identico a quello del codificatore, a cui si applica la stessa relazione x = x̂ − e per ottenere il valore del simbolo x correttamente decodificato. Perché lo schema possa funzionare, occorre che i due predittori condividano il medesimo stato interno iniziale.
La fig.
9.6-a) esemplifica l’applicazione della tecnica al caso di sequenze binarie, per le quali l’operazione di differenza è realizzata tramite una somma modulo due
⊕, dato che scrivendo
e = x̂⊕x risulta
e ≠ 0 solamente quando
x̂ ≠ x. La parte destra della figura mostra quindi l’architettura interna del predittore del primo ordine adottato, che cioè tiene conto del solo simbolo
precedente xk − 1, e che semplicemente
scommette che sia uguale al successivo, ovvero
x̂k = xk − 1; il
vero simbolo precedente
xk − 1 è ottenuto come prima descritto, ovvero a partire dalla stima fornita in precedenza
x̂k − 1 ottenuta mediante un ritardo, e sommata al precedente errore
ek − 1, anch’esso ritardato rispetto alla sequenza di ingresso.
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.
9.2.3 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 potrebbe 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.
9.2.3.1 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 posizioni. Ogni carattere
c letto in ingresso viene accodato in una
stringa w, 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 l’indice 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 (nel senso di dipendenza statistica); 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 può essere 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.
9.2.3.2 Algoritmo Deflate
L’ultimo metodo di compressione senza perdite che esaminiamo è quello che è stato introdotto da Phil Katz con il 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 alla codeword già presente nel dizionario, 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.
scegli
