Entropia e Codifica di Sorgente

Prendiamo in considerazione una sorgente discreta, che emetta simboli x_k appartenenti ad un alfabeto di cardinalità L (ossia con k = $\left\{\vphantom{ 1,2,\cdots ,L}\right.$1, 2, ^... , L$\left.\vphantom{ 1,2,\cdots ,L}\right\}$), con probabilità p_k = Pr$\left(\vphantom{ k}\right.$k$\left.\vphantom{ k}\right)$. Definiamo l'informazione associata all'osservazione del simbolo x_k come^5.41

I_k = I$$\left(\vphantom{ x_{k}}\right.$$x_k$$\left.\vphantom{ x_{k}}\right)$$ = log₂$${\frac{1}{p_{k}}}$$ = - log₂p_k

La scelta fatta, conduce ai seguenti risultati:

Prob.	Informazione	Commento
pk	-log2pk
1	0	L'evento certo non fornisce informazione
0	$\infty$	L'evento impossibile dà informazione infinita
${\frac{1}{2}}$	1	In caso di scelta binaria (es. testa o croce) occorre una cifra binaria (bit = binary digit ) per indicare il risultato

<><>

L'informazione legata ad un evento è anche rappresentativa dell'incertezza a suo riguardo, prima che questo si verifichi.

Passiamo ora a definire Entropia (indicata con H) di una sorgente discreta S, il valore atteso dell'informazione apportata dalla conoscenza dei simboli da essa generati:

H_S = E$$\left\{\vphantom{ I_{k}}\right.$$I_k$$\left.\vphantom{ I_{k}}\right\}$$ = $$\sum_{k=1}^{L}$$p_kI_k = $$\sum_{k=1}^{L}$$p_klog₂$${\frac{1}{p_{k}}}$$

che costituisce una interessante applicazione dell'operatore di valore atteso da poco introdotto. H rappresenta l'informazione media di un generico simbolo emesso dalla sorgente, ottenuta pesando l'informazione di ogni possibile simbolo con la probabilità del simbolo stesso. Osserviamo ora che:

• Se i simboli sono equiprobabili ( p_k = ${\frac{1}{L}}$ con $\forall$k), la sorgente è massimamente informativa, e la sua entropia è la massima possibile per un alfabeto ad L simboli, e cioè H_SMax = ${\frac{1}{L}}$$\sum_{k=1}^{L}$log₂L = log₂L.
• Se i simboli non sono equiprobabili, allora H_S < log₂L.
• Se la sorgente emette sempre e solo lo stesso simbolo, allora H_S = 0. Questa circostanza, assieme alla precedente, consente di scrivere che 0 $\leq$ H_S $\leq$ log₂L.

Un caso particolare è quello delle sorgenti binarie, che producono uno tra due simboli $\left\{\vphantom{ x_{0},x_{1}}\right.$x₀, x₁$\left.\vphantom{ x_{0},x_{1}}\right\}$ con probabilità rispettivamente $\left\{\vphantom{ Pr\left( x_{0}\right) =p,\: Pr\left( x_{1}\right) =q=1-p}\right.$Pr$\left(\vphantom{ x_{0}}\right.$x₀$\left.\vphantom{ x_{0}}\right)$ = p, Pr$\left(\vphantom{ x_{1}}\right.$x₁$\left.\vphantom{ x_{1}}\right)$ = q = 1 - p$\left.\vphantom{ Pr\left( x_{0}\right) =p,\: Pr\left( x_{1}\right) =q=1-p}\right\}$, che inserite nella formula dell'Entropia, forniscono l'espressione

H_b$$\left(\vphantom{ p}\right.$$p$$\left.\vphantom{ p}\right)$$ = - $$\left(\vphantom{ p\log _{2}p+\left( 1-p\right) \log _{2}\left( 1-p\right) }\right.$$plog₂p + $$\left(\vphantom{ 1-p}\right.$$1 - p$$\left.\vphantom{ 1-p}\right)$$log₂$$\left(\vphantom{ 1-p}\right.$$1 - p$$\left.\vphantom{ 1-p}\right)$$ $$\left.\vphantom{ p\log _{2}p+\left( 1-p\right) \log _{2}\left( 1-p\right) }\right)$$

il cui andamento è mostrato nella figura seguente, in funzione di p.

Figura: Entropia di sorgente binaria, e ridondanza associata

I due simboli $\left\{\vphantom{ x_{0},x_{1}}\right.$x₀, x₁$\left.\vphantom{ x_{0},x_{1}}\right\}$ possono essere rappresentati dalle 2 cifre binarie $\left\{\vphantom{ 0,1}\right.$0, 1$\left.\vphantom{ 0,1}\right\}$, che in questo caso chiamiamo binit, per non confonderli con la misura dell'informazione (il bit), ed allora se p $\neq$ .5, usiamo 1 binit/simbolo per rappresentare un messaggio con solo H_b < 1 bit/simbolo di informazione, dunque la nostra codifica ha una ridondanza pari a 1 - H_b$\left(\vphantom{ p}\right.$p$\left.\vphantom{ p}\right)$ (graficata )^5.42.

Lo stesso concetto, si applica ad una sorgente ad L livelli, con Entropia H_S = log₂L, i cui simboli sono codificati con $\left\lceil\vphantom{ \log _{2}L}\right.$log₂L$\left.\vphantom{ \log _{2}L}\right\rceil$ binit/simbolo^5.43, con ridondanza $\left\lceil\vphantom{ \log _{2}L}\right.$log₂L$\left.\vphantom{ \log _{2}L}\right\rceil$ - H_S. Ci chiediamo allora: è possibile trasmettere tanti binit quanti ne servono, e non di più? La risposta è sí, ricorrendo ad una CODIFICA DI SORGENTE, di cui appresso forniamo un esempio.

Codifica di Huffmann e codifica entropica a lunghezza variabile

Consiste nell'usare CODEWORDS (parole di codice) di lunghezza variabile, ed usare le più lunghe per i simboli meno probabili. Consideriamo ad esempio una sorgente con alfabeto di cardinalità L = 4, ai cui simboli compete la probabilità riportata nella tabella che segue. In questo caso l'Entropia vale

$$\sum_{k}^{}$$p_klog₂$${\frac{1}{p_{k}}}$$ = $${\textstyle\frac{1}{2}}$$log₂2 + $${\textstyle\frac{1}{4}}$$log₂4 + $${\textstyle\frac{2}{8}}$$log₂8 = $${\textstyle\frac{1}{2}}$$ + $${\textstyle\frac{1}{2}}$$ + $${\textstyle\frac{2}{8}}$$3 = 1.75 bit/simbolo

mentre il numero medio di binit/simbolo usati è pari a

$$\overline{N} \left\{\vphantom{ \hbox {Lunghezza}}\right. \left.\vphantom{ \hbox {Lunghezza}}\right\} \sum_{k}^{} \left(\vphantom{ k}\right. \left.\vphantom{ k}\right)$$ =

$${\textstyle\frac{1}{2}} {\textstyle\frac{1}{4}} {\textstyle\frac{2}{8}}$$ =

Simbolo	Prob.	Codeword
x1	.5	1
x2	.25	01
x3	.125	001
x4	.125	000

<><>

Osserviamo che:

• le codewords a lunghezza variabile non si confondono tra loro in quanto soddisfano la regola del prefisso, ovvero nessuna codeword è uguale all'inizio di una codeword più lunga: se cosí non fosse, non riusciremmo ad isolarle nel flusso numerico.
• I due risultati (entropia e lunghezza media) coincidono, in virtú del fatto che i valori di probabilità sono potenze non negative di 2.

Nel caso generale (valori di probabilità di emissione qualsiasi), si introduce un ritardo di codifica, in modo da raggruppare più simboli di sorgente, ed effettuare cosí una cosiddetta codifica a blocchi: per fissare le idee, consideriamo una sorgente binaria, della quale si raggruppino coppie di bit simulando cosí una sorgente a quattro valori. Con i risultati riportati in tabella che segue, si può verificare che si ottiene una Entropia di sorgente

H_s = .8log₂$${\frac{1}{.8}}$$ + .2log₂$${\frac{1}{.2}}$$ = 0.72

bit/simbolo, mentre adottando una codifica con 1 binit per ogni simbolo generato, si ottiene ovviamente una lunghezza media di 1 binit/simbolo. Al contrario, la lunghezza media ottenibile raggruppando coppie di simboli risulta pari a

$$\overline{N}$$ = 1 ^. .64 + 2 ^. .16 + 3 ^. .16 + 3 ^. .04 = 1.5792

binit/2 simboli, ossia pari a 0.7896 bit/simbolo.

 

Simbolo	Prob.	Codeword
x1	.8	1
x2	.2	0
x1x1	.64	1
x1x2	.16	01
x2x1	.16	001
x2x2	.04	000

<><>

 

In generale, prendendo blocchi via via più lunghi, è possibile ridurre la velocità di codifica R (in binit/simbolo) rendendola sempre più simile all'Entropia, ovvero

min$$\left[\vphantom{ R}\right.$$R$$\left.\vphantom{ R}\right]$$ = H_S + $$\varepsilon$$      con  $$\varepsilon$$ $$\rightarrow$$ 0

se la lunghezza del blocco tende ad infinito (Teorema di Shannon sulla codifica di sorgente).