Capitolo 11: Teoria dell’informazione e codifica Su  Capitolo 11: Teoria dell’informazione e codifica Sezione 11.2: Codifica di canale 

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
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

Sorgente senza memoria
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[431] [431] Per calcolare il logaritmo in base 2, si ricordi che log2α  = (log10α)/(log102)≃3.32log10α.
Ik = I(xk) = log2(1)/(pk)  =  − log2pkbit
misura dell'informazione
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:
Prob. Informazione Commento
pk   − log2pk
1 0 L’evento certo non fornisce informazione
0 L’evento impossibile dà informazione infinita
(1)/(2) 1 In caso di scelta binaria (es. testa o croce) occorre una cifra binaria (bit = binary digit) per indicare il risultato

11.1.1.1  Entropia

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
(12.1) Hs  = E{Ik} = Lk  = 1pkIk  = Lk = 1pklog2(1)/(pk)bit/simbolo
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:
Da queste osservazioni discende l’espressione riassuntiva
(12.2) 0 ≤ Hs  ≤ log2L
Esercizio
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 α = 1pk  ≥ 1. Quindi, mostriamo che Hs  − log2L ≤ 0. Innanzitutto riscriviamo il primo membro della diseguaglianza come
Hs − log2L  = kpklog2(1)/(pk) − log2Lkpk  = kpklog2(1)/(Lpk)
dato che kpk  = 1. Quindi, esprimiamolo in termini dei logaritmi naturali, tenendo conto che log2α = (lnα)/(ln2), e quindi
kpklog2(1)/(Lpk) = (1)/(ln2)kpkln(1)/(Lpk)
figure f17.1a.png
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)/(Lpk) ≤ (1)/(ln2)kpk(1)/(Lpk) − 1  =   =  (1)/(ln2)k(1)/(L) − kpk  = (1)/(ln2)(1 − 1)  = 0
con il segno di uguale solo se (1)/(Lpk) = 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
(12.3) Hb(p) =  − plog2p  − (1 − p)log2(1 − p)bit/simbolo
il cui andamento è mostrato nella figura 11.3↓, in funzione di p.
entropia di sorgente binaria figure f5.76.png
Figura 11.3 Entropia di sorgente binaria, e ridondanza associata
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)[432] [432] Si presti attenzione sulla differenza: la ridondanza della codifica di sorgente indica i binit/simbolo che eccedono il valore dell’entropia, mentre la ridondanza della codifica di canale indica il rapporto tra binit di protezione e quelli di effettivamente emessi dalla sorgente, come definito a pag. 1↑..
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[433]  [433] La notazione α indica l’intero superiore ad α: ad esempio, se α  = 3.7538, si ha α = 4., otteniamo una ridondanza pari a log2L − HL.
EsempioConsideriamo 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 = fsHs bit/secondo
Intensità informativa e codifica binaria
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)[434] [434] Mettere in corrispondenza i diversi simboli di sorgente con una loro codifica binaria è detta codifica per blocchi, discussa al § 11.1.1.4↓, dove si mostra anche la possibilità di emettere le codeword in corrispondenza di più di un simbolo di sorgente., scelti in uno dei modi descritti nel seguito, producendo una velocità di trasmissione binaria di fb binitsec. 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)bitbinit  ≤ 1. Dato che l’intensità informativa in ingresso ed in uscita dal codificatore deve essere la stessa[435] [435] Essendo la corrispondenza tra xk ed Nk univoca, non vi è perdita di informazione., la velocità binaria fb della nuova sorgente rispecchia il vincolo
fb ≥ fbHb(p) = fsHs  = 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[436] [436] http://it.wikipedia.org/wiki/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[437] [437] In effetti la (12.4↓) sussiste qualora il codificatore non operi indipendentemente su ogni simbolo di sorgente, ma più in generale possa emettere i binit in corrispondenza di sequenze di xk via via più lunghe.
(12.4) Hs  ≤ N  ≤ Hs + ϵ
con ϵ piccolo a piacere, e che si annulla in corrispondenza della codifica ottima, per la quale risulta N = Hs. Ma non dice come fare.
Rendimento del codice
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[438] [438] Ad esempio, un valore η = 0.33 indica che ogni binit trasporta solo 13 di bit.. 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.
Simbolo Prob. Codeword Nk
x1 .5 0 1
x2 .25 10 2
x3 .125 110 3
x4 .125 111 3
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).
Regola del prefisso
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[439]  [439] https://en.wikipedia.org/wiki/Kraft's_inequality, espressa come
(12.5) K = Lk  = 12  − Nk ≤ 1
EsempioNella tabella sono riportati quattro possibili codici (A,B,C,D) per la sorgente quaternaria già discussa, assieme al corrispettivo valore di N e K.
Simb. pk A B C D
x1 .5 00 0 0 0
x2 .25 01 1 01 10
x3 .125 10 10 011 110
x4 .125 11 11 0111 111
N 2.0 1.25 1.875 1.75
K 1.0 1.5 0.9375 1.0
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[440] [440] Ad esempio, la sequenza 10110010 potrebbe essere interpretata come x3x4x1x1x3 oppure x2x1x4x1x1x2x1 o x3x2x2x1x1x3: difatti violano sia la regola del prefisso, che il limite (12.5↑). Il codice C invece è non ambiguo[441] [441] Nonostante il codice C non soddisfi la regola del prefisso, non è ambiguo in quanto lo zero indica comunque l’inizio di una nuova codeword., 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↑).
Codice ottimo
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[442] [442] Infatti ora la (12.5↑) si scrive K = Lk = 12 − Nk  = Lk  = 1pk = 1., 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.
Codice di Huffman
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[443]  [443] Vedi http://en.wikipedia.org/wiki/Huffman_coding sulla costruzione di un albero binario, i cui rami sono etichettati con 1 e 0, e può essere descritto come segue:
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.
Esempiouna 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.
Simbolo pk Codeword
a1 0.027 1001
a2 0.063 1000
a3 0.063 0111
a4 0.147 101
a5 0.063 0110
a6 0.147 010
a7 0.147 00
a8 0.343 11
codice di Huffman


Dynamic Huffman coding
Questa variante permette di costruire e modificare l’albero di codifica[444] [444] Presso Wikipedia si trova una descrizione dell’algoritmo di Vitter http://en.wikipedia.org/wiki/Adaptive_Huffman_coding 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
(12.6) log2(1)/(pk)  ≤ Nk ≤  log2(1)/(pk)  + 1
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
(12.7) Hs  ≤ N  ≤ Hs + (1)/(n)
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[445] [445] operazione resa possibile in conseguenza della indipendenza statistica tra i simboli binari, e quindi codifichiamo i nuovi simboli quaternari con il codice a lunghezza variabile già esaminato.
Simbolo Prob. Codeword
x1 .8 1
x2 .2 0
x1x1 .64 0
x1x2 .16 10
x2x1 .16 110
x2x2 .04 111
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.
Riassumendo
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.
EsercizioSi 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)  ≠ Nk = 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.
Sorgente Markoviana
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.
EsempioAnalizziamo il caso di una sorgente binaria di Markov del primo ordine, per la quale sono definite le probabilità mostrate a lato,
p(0  ⁄ 0)  = 0.9 p(1  ⁄ 0) = 0.1 p(0 ⁄ 1)  = 0.4 p(1  ⁄ 1)  = 0.6
sorgente Markoviana di primo ordine
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.
 
EsercizioSi 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.
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 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![446] [446] In realtà, nel caso specifico del fax le cose non stanno esattamente in questi termini: infatti, anziché usare una parola di lunghezza fissa di k binit, l’ITU-T ha definito un apposito codebook http://www.itu.int/rec/T-REC-T.4-199904-S/en che rappresenta un codice di Huffman a lunghezza variabile, in modo da codificare le run length più frequenti con un numero ridotto di bit.
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 (n) e quella effettiva x(n) è una nuova sequenza indicata come errore di predizione e(n) = (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) = (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[447]  [447] Il lettore più curioso si chiederà a questo punto, come è fatto il predittore. Molto semplicemente, scommette sul prossimo simbolo più probabile, in base alla conoscenza di quelli osservati per ultimi, ed ai parametri del modello markoviano: se questo simbolo possiede una probabilità a priori > 0.5, allora la maggioranza delle volte la predizione sarà corretta, ed il metodo inizia a consentire una riduzione di velocità. Nel caso di sorgenti continue, troveremo invece alcune particolarità aggiuntive. la stima (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)(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[448] [448] Ad esempio con L=96 simboli si ha n=7 bit, ed un dizionario iniziale con 128 posizioni, di cui 96 occupate e 32 libere.. 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.
  w = NIL;
  while (read a char c) do
    if (wc exists in dictionary) then
      w = wc;
    else
      add wc to the dictionary;
      output the code for w;
      w = c;
    endif
  done
  output the code for w;
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[449]  [449] http://en.wikipedia.org/wiki/Lempel-Ziv-Welch è 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.
Algoritmo Deflate
L’ultimo metodo di compressione senza perdite che esaminiamo è quello che è stato introdotto dal programma pkzip, e quindi formalizzato nella rfc 1951[450]  [450] http://tools.ietf.org/html/rfc1951, 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  = Wlog21 + (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
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[451] [451] http://en.wikipedia.org/wiki/Rate-distortion_theory 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
(12.8) D(R)G  = 2 − 2Rσ2x
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.
 
curva distorsione-velocità curva velocità-distorsione
Valori limite
Il valore D(R)G costituisce un limite superiore per ciò che riguarda la
curva velocità-distorsione
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
(12.9) D(R)L  = 2 − 2RQ ≤ D(R) ≤ D(R)G = 2 − 2Rσ2x
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
(12.10) h(X)  = E{ − log2px(x)} =  − px(x)log2px(x)dx
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.
EsempioSe 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[452] [452]  In effetti esiste una misura di entropia assoluta per sorgenti continue, che però ha la sgradevole caratteristica di risultare sempre infinita. Infatti, approssimando la (12.10↑) come limite a cui tende una sommatoria, e suddividendo l’escursione dei valori di x in intervalli uguali Δx, possiamo scrivere
habs(x)  =  limΔx →  0ip(xi)Δxlog2(1)/(p(xi)Δx)  =  limΔx → 0ip(xi)Δxlog2(1)/(p(xi))  + p(xi)Δxlog2(1)/(Δx)  = h(x)  + h0
in cui h(x) è proprio la (12.10↑) mentre h0  =  − limΔx  → 0log2Δx  − ∞p(x)dx  =  − limΔx  → 0log2Δx  = ∞. D’altra parte, la differenza tra le entropie assolute di due sorgenti z e x risulta pari a habs(z) −  habs(x) = h(z) − h(x) + h0(z) − h0(x), in cui la seconda differenza tende a  − log2(Δz)/(Δx) che, se z ed x hanno la medesima dinamica, risulta pari a zero.
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[453]  [453] Questo risultato si ottiene massimizzando la (12.10↑) rispetto a p(x) mediante il metodo dei moltiplicatori di Lagrange http://it.wikipedia.org/wiki/Metodo_dei_moltiplicatori_di_Lagrange, in modo da tener conto dei vincoli espressi dalle condizioni px(x)dx  = 1 e x2px(x)dx  = σ2x. Notiamo esplicitamente la differenza rispetto al caso continuo, in cui la d.d.p. che rende massima l’entropia, è invece quella uniforme., e risulta pari a
(12.11) h(X)G  = (1)/(2)log2(2πeσ2x) > h(X)
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
(12.12) Q  = (1)/(2πe)22h(X)
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
(12.13) D(R)G  = 2 − 2Rγ2xσ2x
in cui 0 ≤ γ2x ≤ 1 rappresenta una misura di piattezza spettrale[454] [454] Si può mostrare che γ2x può essere interpretato come il rapporto tra la media aritmetica e la media geometrica della densità spettrale di potenza Px(f) del processo x(t): indicando con Sk = Px(fk), k  = 1, 2, ⋯, N, i campioni equispaziati della densità spettrale valutati a frequenze positive fk tra zero e la massima frequenza del processo, si ha
γ2x  = limN  → ∞((Nk = 1Sk)1N)/((1)/(N)Nk = 1Sk)
Nel caso di un processo bianco, per il quale i valori Sk sono tutti uguali, le due medie coincidono, e γ2x  = 1. Altrimenti, γ2x risulta tanto più piccolo quanto più i valori Sk si discostano dal loro valore medio.
, 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↓.
  Capitolo 11: Teoria dell’informazione e codifica Su  Capitolo 11: Teoria dell’informazione e codifica Sezione 11.2: Codifica di canale 
x Logo

Trasmissione dei Segnali e Sistemi di Telecomunicazione

http://infocom.uniroma1.it/alef/libro/

Un esperimento divenuto nel tempo un riferimento culturale. Scopri come effettuare il download, ricevere gli aggiornamenti, e contribuire!