Sezione 9.4: Misure di informazione per una coppia di v.a. Su Capitolo 9: Teoria dell’informazione e codifica di sorgente Sezione 9.6: Appendici 

9.5 Codifica di sorgente con perdita di informazione

Si rende necessaria quando il canale trasmissivo non può trasportare un flusso informativo qualsiasi[484]  [484] Questo limite può essere causato da una insufficiente capacità di canale (§ 17.3), o da una limitata disponibilità di risorse, come ad es. nella archiviazione dei dati in memoria., ma esiste un limite RM alla massima velocità di codifica R, ovvero si impone che R ≤ RM. Ciò è possibile a patto di accettare una perdita di informazione che si traduce nell’insorgere di una distorsione D del messaggio, di cui vogliamo stabilire l’entità D(R), in funzione della velocità R. Siamo altresì interessati a stabilire il viceversa, ovvero quale sia la minima velocità di trasmissione R(D), qualora si accetti una distorsione D ≤ DM.
Messaggi di natura discreta
Quando la massima velocità RM è inferiore al tasso informativo (10.223) della sorgente, anche la codifica più efficiente sviluppa una velocità R eccessiva e dunque si è obbligati a scartare informazione, come ad esempio omettere la trasmissione di intere codeword, con la conseguenza di introdurre errori (o distorsione D) nel messaggio codificato[485]  [485] La perdita di informazione per messaggi discreti determina la corruzione del messaggio, come la mancanza di parti di testo, di un’immagine, o di un video. Ma nel caso di trasmissione dati si preferisce impiegare più tempo per la trasmissione, piuttosto che perdere informazione., in proporzione tanto maggiore quanto minore è RM.
Sorgenti continue
Qui abbiamo due strade possibili: o intraprendere un processo di campionamento e quantizzazione (§ 4.3) per produrre un segnale numerico con velocità R ≤ RM, ed incorrere in una distorsione di quantizzazione D tanto maggiore quanto minore è la RM consentita, oppure effettuare una trasmissione analogica del segnale x(t) con una potenza S, con le conseguenze
Nel caso continuo pertanto, sia che la sorgente venga quantizzata, sia che se ne effettui la trasmissione come segnale analogico, sussiste un legame inverso tra distorsione e velocità di trasmissione, il cui studio prende il nome di teoria velocità-distorsione, di cui discutiamo ora.

9.5.1 La distorsione di codifica

Per individuare la relazione R(D) tra la minima velocità R di trasmissione di una codifica (con perdite) di una sorgente informativa e la distorsione D che si ritiene
figure f17.veldist2.png
accettabile ci riferiamo alla figura a lato, in cui un simbolo (sorgente discreta) o valore (s. continua) x da trasmettere viene rappresentato mediante codeword c = f(x) di R binit, limitando dunque l’alfabeto a 2R elementi, a cui si associa in ricezione un nuovo valore  = g(f(x)) ≠ x. La corrispondenza tra x ed viene quindi espressa in termini probabilistici come p( ⁄ x), mentre indichiamo con d(x, ) la misura della distorsione corrispondente[487]  [487] Per sorgenti continue d(, x) può ad es. corrispondere ad un valore quadratico medio (o varianza, o potenza) dell’errore di quantizzazione dei suoi campioni (§ 4.1), mentre p( ⁄ x) dipende dalla caratteristica di quantizzazione f(x) (§ 4.3), e fornisce prob. pari ad uno al valore quantizzato k (o centroide) associato all’intervallo Ik in cui cade il campione x (vedi anche §§ 4.3.2 e 10.1.2.4). Prevedere anche per un valore probabilistico generalizza sia il concetto che la trattazione.. A questo punto è possibile definire la distorsione media Dx in cui si incorre nel rappresentare un generico valore (o simbolo) x mediante come un valore atteso, ossia
Dx = E, X{d(, x)} = p( ⁄ x)p(x)d(, x)ddx
la cui entità dipende sia dalla scelta della misura d(x, ) che dalla d.d.p. p( ⁄ x), risultato della scelta delle operazioni di codifica c = f(x) e restituzione  = g(c).

9.5.2 Funzione velocità-distorsione

E’ il nome dato alla relazione R(D) definita come la soluzione ad un problema di minimizzazione[488]  [488] Per gli amanti del rigore analitico, il processo logico-matematico che motiva tale definizione viene sviluppato ad esempio al cap. 13 del testo Elements of Information Theory di T.M. Cover e J.A. Thomas (1991, Wiley), reperibile ad es. presso  http://www.cs-114.org/wp-content/uploads/2015/01/Elements_of_Information_Theory_Elements.pdf, ossia come quella che rende minima l’informazione mutua media I(;x) tra x e al variare di p( ⁄ x) in tutti i modi possibili, in modo da mantenere Dx inferiore alla distorsione desiderata D:
(10.242) R(D) = minp( ⁄ x): Dx ≤ D I(;X)
Ricordando le osservazioni svolte al § 9.4.3 a proposito di I(;X), questa misura quanto la conoscenza di riduce l’incertezza a riguardo di x, incertezza che altrimenti[489]  [489] Per incognito, oppure statisticamente indipendente da x. sarebbe pari all’entropia H(X): intuitivamente si desidera che tale riduzione sia la massima possibile, e dunque la minimizzazione espressa dalla (10.242) va considerata congiuntamente al vincolo p( ⁄ x): Dx ≤ D, vincolo conseguibile purché I(;x) sia grande a sufficienza.

9.5.2.1 Shannon lower bound

Soluzioni generali per (10.242) sono difficili da ottenere[490]  [490] Benché esista un metodo iterativo di soluzione, vedi https://en.wikipedia.org/wiki/Blahut-Arimoto_algorithm, ma si può comunque mostrare che R(D) è continua, monotonicamente decrescente, e convessa (ossia ad U). Sussiste inoltre un limite inferiore valido per criteri di distorsione d(x, ) di tipo errore quadratico e per sorgenti qualsiasi e senza memoria, ma che ora illustriamo per il caso continuo, e che afferma
(10.243)
R(D) ≥ h(X) − h(D) = h(X) − 12 log2(2πeD)
dove h(X) è l’entropia differenziale della sorgente, e h(D) quella di una v.a. gaussiana con varianza D. Per dimostrare la (10.243) iniziamo osservando che in base alla relazione I(X;) = h(X) − h(X ⁄ )9.4.3) possiamo scrivere la (10.242) come
(10.244)
R(D)  = minDx ≤ D{I(X;)} = minDx ≤ D{h(X) − h(X ⁄ )} =   = h(X) − maxDx ≤ D{h(X ⁄ )}
in cui l’ultimo termine esprime l’incertezza residua su X una volta nota la sua codifica , incertezza pari a zero qualora  = X, e dunque abbiamo R(D)|D = 0 = h(X). Se invece D > 0 possiamo scrivere
(10.245)
maxDx ≤ D{h(X ⁄ )} = maxDx ≤ D{h(X −  ⁄ )} ≤  maxDx ≤ D{h(X − )}
in cui la prima eguaglianza significa che, dopo la conoscenza di , rimane la stessa incertezza sia a riguardo del valore vero X che a riguardo dell’errore X − [491]  [491] Ciò è conseguenza del fatto che, come osservato a pag. 1, l’entropia differenziale di una v.a. dipende dal suo valore medio, che in questo caso è .; la successiva diseguaglianza deriva invece dalla constatazione che aggiungendo informazione () l’entropia non può aumentare, e dunque h(X −  ⁄ ) ≤ h(X − ). Dato però che nella (10.244) l’ultimo termine compare con il segno meno, sostituendovi la (10.245) si ottiene
(10.246)
R(D) ≥ h(X) − maxDx ≤ D{h(X − )}
Per arrivare alla (10.243) è ora sufficiente osservare che una distorsione definita come D = E{(X − )2} è a tutti gli effetti una varianza σ2, dunque la condizione Dx ≤ D pone un limite σ2 ≤ D alla varianza dell’errore X − . Al §  9.3.2 si è mostrato che la sorgente che fornisce la massima entropia differenziale h per σ2 assegnata è gaussiana, con h = 1 2log2(2πeσ2), e dunque maxDx ≤ D{h(X − )} ≤ 12 log2(2πeD), che sostituita nella (10.246) fornisce la (10.243).

9.5.3 Curva velocità-distorsione per sorgente gaussiana

Qualora la v.a. continua x sia di tipo gaussiano, senza memoria e con varianza σ2x, inserendo l’espressione della corrispondente entropia differenziale (10.235) nella (10.243) si ottiene una funzione velocità-distorsione (10.242) pari a
RG(D) = 1 2 log2(2πeσ2x) − 1 2 log2(2πeD) = − 12 log2 Dσ2x
con il segno di uguale[492]  [492] Ciò deriva dal considerare x =  + e con ed e v.a. gaussiane statisticamente indipendenti, di varianza rispettivamente e σ2x − D e D: in tali condizioni si ottiene E{(X − )2} = D e I(X;) = 12log2σ2x D., ovvero la sorgente gaussiana consegue il limite inferiore (10.243). Osserviamo ora che per D = σ2x si ottiene R(D)|D = σ2x = 0 ovvero non occorre
figure f17.4.b.png
trasmettere nulla ( = 0), in modo che l’errore e = x −  = x abbia appunto potenza σ2x = D. Se poi D > σ2x ossia la distorsione è superiore alla potenza di segnale, è sufficiente generare un valore gaussiano, a media nulla, indipendente da x e di varianza D − σ2x per ottenere una distorsione E{(x − )2} = σ2x + D − σ2x = D.
L’espressione finale per questo caso risulta dunque
(10.247) RG(D) =   − 1 2 log2 D σ2x       se   0 ≤ D ≤ σ2x se   D ≥ σ2x
Sorgente non gaussiana e confronto prestazioni
In questo caso l’entropia h(X) è inferiore al caso gaussiano, e quindi il limite (10.243) fornisce un valore R(D)min
figure f17.4.c.png
più piccolo di (10.247), abbassando la curva mostrata sopra. Una volta stabilito un modello (anche sperimentale) della d.d.p. della nostra sorgente, e valutata (anche numericamente) la sua entropia, possiamo usare la (10.243) per tracciare la relativa curva R(D)min, e confrontare rispetto ad essa le prestazioni conseguite dal metodo di codifica che stiamo sviluppando, come esemplificato a lato.
Curva distorsione-velocità
Invertendo la relazione (10.247) si ottiene[493]  [493]  R = − 12 log2D σ2x ⟹  − 2R = log2D σ2x ⟹ 2 − 2R = D σ2xD = 2 − 2Rσ2x che la minima distorsione D conseguibile da una sorgente gaussiana in corrispondenza ad una
figure f17.4.a.png
velocità di R binit/campione risulta pari a
(10.248) DG(R) = 2 − 2Rσ2x
ovvero la distorsione per sorgenti gaussiane e con R fissato è proporzionale alla varianza σ2x, e decresce esponenzialmente con la velocità, come mostrato in figura.
Legame con l’SNR
Definendo il rapporto segnale-rumore in dB (§ 8.1) come 10 log10 σ2xD la (10.248) consente di ottenere
SNRdB = 10 log10 22R = 2R ⋅ 10 log10 2 = 6 ⋅ R dB
ossia un miglioramento di 6 dB per ogni binit in più utilizzato per la codifica di un campione, confermando in pieno il risultato già ricavato al § 4.3.1.1.
Valori limite
Il valore (10.248) rappresenta un limite superiore per la distorsione a velocità R per una sorgente non gaussiana, o gaussiana ma con memoria, per la quale si possono ottenere valori di distorsione inferiori; la (10.248) individua quindi il più grande valore della distorsione minima, per velocità R e potenza σ2x assegnate. D’altra parte è anche definito un limite inferiore DL(R) che individua 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
(10.249)
DL(R) = 2 − 2RQ  ≤  D(R)  ≤  DG(R) = 2 − 2Rσ2x
in cui Q è la...
Potenza entropica
Esprime una quantità direttamente legata all’entropia differenziale della sorgente, con valore
(10.250) Q = 12πe 22h(X)
che per sorgenti gaussiane fornisce QG = σ2x, mentre per altri tipi di v.a. si ottiene un valore inferiore[494]  [494] Ad esempio per una v.a. uniforme si ottiene QU = 0.703 ⋅ σ2x. Si può anche interpretare Q come la varianza di una sorgente gaussiana con la stessa entropia della sorgente in esame. Sostituendo (10.250) in (10.249) osserviamo come il limite inferiore di distorsione DL(R) si riduce al diminuire di h(X), ovvero sorgenti meno informative conseguono distorsioni minori a parità di velocità.

9.5.4 Sorgente continua con memoria

Come per il caso di sorgenti discrete anche per quelle continue la dipendenza statistica tra i campioni di segnale riduce la quantità di informazione emessa, cosicché a parità di distorsione la sorgente può essere codificata a velocità ridotta, oppure a parità di velocità si può conseguire una distorsione inferiore. Anche stavolta la sorgente più difficile (ossia a cui compete la massima distorsione minima) è quella gaussiana, per la quale si ottengono risultati la cui interpretazione è molto interessante; prima di esporli conviene però fare un piccolo passo indietro.

9.5.4.1 Entropia e potenza entropica di sorgente gaussiana con memoria

Analogamente al caso discreto (§ 9.2), per una sequenza (o vettore colonna) x = (x1, x2⋯, xn)T di n v.a. con ampiezza continua, descritte da una d.d.p. congiunta p(x), si definisce una entropia differenziale a blocco come
(10.251)
hn(X) = − 1 n x1x2xn p(x) log2 p(x) dx
la cui valutazione è generalmente intrattabile. Se consideriamo un processo gaussiano x(t) limitato in banda, a media nulla, stazionario e con densità di potenza Px(f) colorata, i suoi campioni xk = x(kTc) (cap. 4) hanno d.d.p. congiunta (§ 6.5)
pX(x) = 1 (2π)ndet(Rxx) exp− 12 xR− 1xxx
dove Rxx = E{xx} è la matrice di correlazione, simmetrica e con elementi diagonali uguali tra loro e pari a Rxx(i, i) = E{x2} = σ2x. In tal caso la (10.251) fornisce[495]  [495] La dimostrazione penso sia simile a quella del § 9.3.2, con le complicazioni della notazione matriciale.
hn(X) = 1 2 log2 (2πe(det(Rxx))1n)
da cui, dopo aver definito l’entropia differenziale per simbolo come h(X) = limn → ∞ hn(X), ricaviamo la potenza entropica per questo caso, pari a[496]  [496] Infatti limn → ∞hn(X) = 12 log2(2πelimn → ∞( det(Rx))1n)  ⇒ 
.  ⇒  2h(X) = log2(2πelimn → ∞( det(Rx))1n)  ⇒  22h(X) = 2πelimn → ∞( det(Rx))1n  ⇒ 
.  ⇒  22h(X) 2π e = Q = limn → ∞( det(Rx))1n. Per la seconda uguaglianza della (10.252), si veda il § 9.6.3.
(10.252)
QG, mem = limn → ∞(det(Rxx))1n = γ2xσ2x
(vedi § 9.6.3) dove 0 ≤ γ2x ≤ 1 è una misura di piattezza spettrale[497]  [497] Vedi https://en.wikipedia.org/wiki/Spectral_flatness, o meglio N.S. Jayant, P. Noll, Digital Coding of Waveforms, 1984 Prentice Hall. Si può mostrare che γ2x può essere interpretato come il rapporto tra la media geometrica e la media aritmetica della densità spettrale di potenza Px(f) del processo x(t) limitato in banda ± W: 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 , si ha
γ2x = limN → ∞ (Nk = 1Sk)1N 1 N Nk = 1Sk = exp1 2W W − Wln Px(f)df 1 2W W − WPx(f)df
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 per un processo bianco o senza memoria, tornando così all’espressione Q = σ2x valida in tal caso. Viceversa Q si riduce (γ2x < 1) per un processo gaussiano a valori correlati, e quindi con una densità spettrale colorata ed una maggiore predicibilità dei suoi valori, e dunque una minore entropia.

9.5.4.2 Funzione distorsione-velocità per sorgente gaussiana con memoria

Il valore di Q (10.252) consente il calcolo del limite inferiore definito alla (10.249):
(10.253)
DL, G, mem(R) = 2 − 2RQG, mem = 2 − 2Rγ2xσ2x
Mostriamo ora in quale caso la distorsione effettiva consegue il limite ossia DG, mem(R) = DL, G, mem(R), e quale sia il valore DG, mem(R) > DL, G, mem(R) in caso contrario.
Il water-filling
Le funzioni (10.247) e (10.248) nel caso di sorgente gaussiana con memoria, i cui campioni sono descritti da uno spettro di densità di potenza Sxx(e jω) colorato, devono essere espresse in forma parametrica come[498]  [498] Di questo non viene fornita dimostrazione, di cui trovo indicazione essere presente in T. Berger, Rate distortion theory, Prentice-Hall 1971, che non trovo pubblicamente disponibile in rete.
(10.254) DG, mem(φ)  = 12π π − πmin ω [φ, Sxx(e jω)]dω (10.255) RG, mem(φ)  = 12π π − πmax ω 0, 1 2 log2 Sxx(e jω) φdω
in cui all’aumentare di φ, D aumenta ed R diminuisce,
figure waterfill.png
Figure 9.13 Bande di frequenza individuate dal parametro φ,
ed aree che concorrono ai valori D ed R
come andiamo a spiegare con l’aiuto della figura 9.13.
Le regioni indicate con B, in cui φ > Sxx(e jω), non contribuiscono al valore di R, dato che nella (10.254) il log è negativo, mentre contribuiscono al valore di D (eq. (10.254)) solamente per l’area ombreggiata in verde, ossia nelle regioni B la distorsione D ha densità di potenza colorata come Sxx. Quando invece Sxx(e jω) > φ (regioni A) il contributo a D non dipende dal valore di Sxx(e jω) ed assume l’aspetto (aree ocra) di un rumore bianco; viceversa (sempre in A) il contributo ad R è legato (con legge logaritmica) al valore delle aree lilla (indicate con C).
Questa interpretazione grafica delle (10.254) e (10.254) viene denominata a riempimento d’acqua perché simula un recipiente con la forma di Sxx(e jω) per il quale le regioni A fungono da vasi comunicanti riempiti di acqua fino al livello φ. Da tale discussione traiamo i risultati
Osserviamo ora che ponendo φ > max{Sxx(e jω)} la sagoma di Sxx(e jω) si riempie completamente d’acqua, la (10.254) fornisce D = σ2x, mentre la (10.254) restituisce R = 0; viceversa nel caso in cui φ < min{Sxx(e jω)} ci si trova nelle condizioni di bassa distorsione per le quali D consegue il suo valore limite inferiore espresso dalla (10.253), ovvero
(10.256)
DG, mem, low − dist(R) = 2 − 2Rγ2xσ2x
dove 0 ≤ γ2x ≤ 1 è la misura di piattezza spettrale già introdotta nella (10.252). Qualora Sxx(e jω) sia costante risulta γ2x = 1, ri-ottenendo così il risultato (10.248) trovato per il caso senza memoria.
Esempio Consideriamo la sequenza di tipo autoregressivo x(n) = z(n) + αx(n − 1) presente all’uscita di un filtro passa basso numerico iir del primo ordine (§ 5.3.2.2) con h(n) = αn (per n ≥ 0 ed 0 < α < 1), al cui ingresso è presente una sequenza z(n) di campioni di un processo gaussiano, a media nulla, varianza σ2z ed a valori indipendenti ed incorrelati da quelli di x. Anche x(n) sarà dunque gaussiano, ma con autocorrelazione[499]  [499] I risultati indicati sono derivati al § 9.6.4 Rxx(k) = α|k|σ2x, varianza σ2x = σ2z1 − α2, piattezza spettrale γ2x = 1 − α2 e densità di potenza colorata pari a
Sxx( e jω) = σ2z ⋅ |Hxx(e jω)|2 = σ2x1 − α2 1 + α2 − 2αcosω
All’aumentare di α la misura di piattezza γ2x si riduce, x(n) diviene più predicibile, e la distorsione D = 2 − 2R(1 − α2)σ2x (10.253) diminuisce. Il minimo valore di Sxx( e jω) si ottiene per ω = π (vedi fig. 4.28 ), ed è pari a
(10.257)
min ω {Sxx(e jω)} =  σ2x 1 − α2 1 + α2 − 2αcosω||ω = π = σ2x 1 − α2 (1 + α)2 = σ2x 1 − α 1 + α
Ponendo (ad esempio)
figure f17.veldist4.png
α = 0.95, la (10.257) fornisce 6 ⋅ σ2x: pertanto la regione a bassa distorsione in questo caso è definita come Dσ2x ≤ 0.0256, o R ≥ log2(1 + α) = 0.964[500]  [500] Infatti la (10.257) può essere riarrangiata come Dσ2x = 1 − α 1 + α mentre dalla (10.256) si ottiene Dσ2x = 2 − 2R(1 − α2); dunque 1 − α 1 + α = 2 − 2R(1 − α2)  ⇒  2 − 2R = 1 − α 1 + α 1 1 − α2 = 1 (1 + α)2 e quindi infine R = − 12 log21 (1 + α)2 = log2(1 + α)2 = log2(1 + α), ed in tale regione è lecito applicare la (10.256) ossia
D(R) = 2 − 2R(1 − α2)σ2x = 0.0975 ⋅ 2 − 2Rσ2x
avendovi sostituito i valori per γ2x ed α. Il risultato è la retta parallela a quella per una sorgente gaussiana senza memoria mostrata alla figura a lato, su di una scala logaritmica per le distorsioni. Per valori Dσ2x > 0.0256 la distorsione D aumenta più rapidamente ed il suo valore va determinato applicando la (10.254), per raggiungere (ad R = 0) il valore σ2x, come avviene per il caso senza memoria.

9.5.4.3 Sorgente non gaussiana

In questo caso la (10.256) si riscrive sostituendo al posto di σ2x la potenza entropica Q espressa dalla (10.250) in cui il valore di entropia differenziale è ora quello della sorgente con memoria, inferiore al caso senza memoria, ottenendo così 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 10, mentre l’applicazione dei concetti di informazione mutua media e di entropia condizionale al calcolo della capacità di canale è sviluppata al capitolo 17.
 Sezione 9.4: Misure di informazione per una coppia di v.a. Su Capitolo 9: Teoria dell’informazione e codifica di sorgente Sezione 9.6: Appendici