Informazione ed entropia

Quanto vale l'informazione

La teoria dell'informazione (Shannon, A mathematical theory of communication, 1948) vuole quantificare l'informazione di una sorgente. Una sorgente emette un evento $A$ (un simbolo) da un insieme $\mathcal A_x=\{a_1,\dots,a_M\}$, l'alfabeto, con probabilità $P(A)$. Si cerca una funzione $i(P(A))$ — l'informazione dell'evento — con quattro proprietà ragionevoli:

1. $i(A)>0$ (non esiste informazione negativa);
2. $i(\Omega)=0$ (un evento certo non dà informazione);
3. se $P(A)>P(B)$ allora $i(A)<i(B)$ (più è raro, più informa);
4. $i(A\cap B)=i(A)+i(B)$ se $A$ e $B$ sono indipendenti.

La funzione $g$ tale che $i=g(P)$ deve quindi essere positiva, nulla in 1, decrescente e con $g(ab)=g(a)+g(b)$: il logaritmo. Si pone $$i_x(A)=\log_M\frac1{P_A}=\log_2\frac1{P_A}\ \ [\text{bit}]\qquad(\text{base }e:\text{ nat}),$$ con base 2 se non detto altrimenti. Esempio: l'evento "testa" in un lancio di moneta ha $P=\frac12$ e $i=\log_22=1$ bit: è la quantità di informazione che serve per comunicare l'esito. Un evento di probabilità $\frac1{16}$ vale $4$ bit; un evento certo $0$ bit.

Entropia

L'entropia è l'informazione media della sorgente: $$\boxed{H(x)=E\left[i_x(x)\right]=\sum_{a\in\mathcal A_x}P(x=a)\,\log_2\frac1{P(x=a)}.}$$ Rappresenta il grado di casualità (l'incertezza) dell'uscita. (In termodinamica si usa un'espressione simile, $S=k_B\ln\Omega$.) Per i termini con $P=0$ si pone $0\log\frac10=0$.

Esempio (variabile di Bernoulli). $P(x=1)=p$: $H=-p\log_2p-(1-p)\log_2(1-p)$. Si cerca il massimo con la derivata: $\frac{dH}{dp}=-\log_2p+\log_2(1-p)=0\Rightarrow p=\frac12$, dove $H=1$ bit. Agli estremi $H\to0$ per $p\to0$ e per $p\to1$.

Due proprietà (la seconda dalla disuguaglianza di Jensenper una funzione concava il valore medio della funzione è al più la funzione del valore medio per funzioni concave, Disuguaglianze di Markov, Chebyshev e JensenMarkov: per X ≥ 0, P(X ≥ a) ≤ E[X]/a; Chebyshev: P(|X − μ| ≥ ε) ≤ Var(X)/ε²; Jensen: per φ convessa, φ(E[X]) ≤ E[φ(X)]. Stimano probabilità e medie conoscendo solo media e varianza.Disuguaglianze di Markov, Chebyshev e Jensen →):

• Proposizione 1. $0\le H(x)\le\log_2M$. Se la sorgente è "quasi costante" (un simbolo ha probabilità 1) $H=0$; altrimenti $H>0$.
• Proposizione 2. $H(x)=\log_2M$ se e solo se i simboli sono equiprobabili; altrimenti $H<\log_2M$.

Esempio. Probabilità $0{,}35,\ 0{,}22,\ 0{,}20,\ 0{,}13,\ 0{,}10$: $H=0{,}35\log_2\frac1{0{,}35}+0{,}22\log_2\frac1{0{,}22}+\dots=2{,}19$ bit, contro $\log_2 5=2{,}32$ bit del caso equiprobabile.

Vettori di simboli, entropia congiunta e condizionata

Una sorgente emette una sequenza; si considerano parole (vettori) $\mathbf x=[x_1,\dots,x_N]$ con $N$ simboli, in un dizionario $\mathcal A_{\mathbf x}=\mathcal A_x^N$ (prodotto cartesiano degli alfabeti). L'entropia congiunta di $x,y$ è $$H(x,y)=\sum_a\sum_bP_{x,y}(a,b)\log_2\frac1{P_{x,y}(a,b)}\qquad\Rightarrow\qquad0\le H(\mathbf x)\le N\log_2M.$$

• Proposizione 3. Se $y$ è funzione di $x$, $H(x,y)=H(x)$ (conoscere $y$ non aggiunge incertezza); altrimenti $H(x,y)>H(x)$.
• Proposizione 4. Se $x$ e $y$ sono indipendenti, $H(x,y)=H(x)+H(y)$. In generale $$\max\{H(x),H(y)\}\le H(x,y)\le H(x)+H(y).$$

Informazione e entropia condizionata. $i_{x|y}(a|b)=\log_2\frac1{P_{x|y}(a|b)}$ e $H(x|y)=E\left[i_{x|y}\right]$. Vale $i_{x|y}(a|b)=i_{x,y}(a,b)-i_y(b)$ (dal rapporto $P_{x|y}=\frac{P_{x,y}}{P_y}$), quindi $$H(x|y)=H(x,y)-H(y),$$ e $H(x|y)=H(x)$ se e solo se $x$ e $y$ sono indipendenti: in questo caso sapere $y$ non riduce l'incertezza su $x$.

Esempio (il meteorologo). Il tempo di domani $y$ e la previsione $x$ hanno distribuzione congiunta ($S$ = sole, $P$ = pioggia): $P_{x,y}(S,S)=\frac9{16}$, $(S,P)=\frac3{16}$, $(P,S)=\frac3{16}$, $(P,P)=\frac1{16}$. La probabilità di indovinare è $\frac9{16}+\frac1{16}=\frac{10}{16}$. L'incertezza residua: $H(x,y)=\frac9{16}\log_2\frac{16}9+\frac6{16}\log_2\frac{16}3+\frac1{16}\log_24=1{,}62$ bit; le marginali sono $P(S)=\frac34$, $P(P)=\frac14$ per entrambe, quindi $H(y)=0{,}81$ bit e $$H(y|x)=H(x,y)-H(x)=1{,}62-0{,}81=0{,}81\ \text{bit}=H(y):$$ la previsione non riduce l'incertezza, perché è indipendente dal tempo ($P_{x,y}=P_xP_y$). Il meteorologo "non dà informazione".

Entropia per simbolo, rate ed efficienza

L'entropia media per simbolo della parola di $N$ simboli è $H_s(\mathbf x)=\frac{H(\mathbf x)}N\le\log_2M$. Se la sorgente (o il quantizzatore) emette $F_s$ simboli al secondo:

Si ha sempre $R\le F_s\log_2M$. Se i simboli non sono equiprobabili o hanno memoria, si possono risparmiare bit per migliorare l'efficienza: è la codifica di sorgente (Codifica di sorgente - codici a prefisso e teorema di ShannonLa codifica di sorgente riduce il numero di bit mappando le parole della sorgente in parole di lunghezza variabile (più corte per le più probabili), senza perdere informazione. Il codice deve essere decodificabile; i codici a prefisso (nessuna parola è prefisso di un'altra) lo sono. Kraft-McMillan: se il codice è decodificabile $\sum M_y^{-L(b)}\le1$. Teorema di Shannon: $L_y\ge\frac{H(x)}{\log_2M_y}$ e esiste un codice a prefisso con $L_y\le\frac{H(x)}{\log_2M_y}+1$; l'efficienza è $\eta=\frac{H(x)}{L_y\log_2M_y}$.Codifica di sorgente - codici a prefisso e teorema di Shannon →).

Esempio (rate con e senza codifica). Un quantizzatore a 4 bit ha rate nominale $\frac{4\ \text{bit}}{T_s}$. Una sorgente a $5$ simboli con le probabilità dell'esempio precedente ($H=2{,}19$ bit) che emette $F_s=100$ simboli al secondo richiede senza codifica $3$ bit per simbolo, cioè $300$ bit/s, mentre l'informazione prodotta è $100\cdot2{,}19=219$ bit/s.

Esempio (sorgente con memoria). $x_n$ è una sequenza illimitata di bit indipendenti equiprobabili e $y_n=x_n-x_{n-1}$. Alfabeto di $y_0$: $\{0,1,-1\}$ con probabilità $\frac12,\frac14,\frac14$: $H(y_0)=1{,}5$ bit. Per $[y_{-1},y_0,y_1]$ ci sono 15 sequenze distinte: la sequenza nulla ($x$ costante, due casi su 16) ha probabilità $\frac18$ e le altre 14 hanno $\frac1{16}$, per cui $H=\frac18\cdot3+14\cdot\frac1{16}\cdot4=3{,}875$ bit. In generale per $2N+1$ campioni $H=2N+2-\frac1{2^{2N+1}}$ e l'entropiainformazione media di una sorgente, in bit per simbolo per simbolo tende a $H_s=1$ bit ($\frac{2N+2}{2N+1}\to1$): $\eta=\frac{1}{\log_23}=0{,}63$ (alfabetoinsieme dei valori che un simbolo può assumere di 3 valori).

Esempio (quantizzatore su un segnale laplaciano). $x$ a campioni indipendenti con densità $\frac1{2A}e^{-\lvert a\rvert/A}$, quantizzato mid-riser con $L=6$ livelli e $\Delta=\frac A2$: i livelli sono $\pm\frac\Delta2,\pm\frac{3\Delta}2,\pm\frac{5\Delta}2$ con probabilità (calcolate integrando la densità) $0{,}197,\ 0{,}119,\ 0{,}184$ (per ciascun segno): $H=2{,}55$ bit; con $F_s=8$ kHz il rate di informazionebit di informazione prodotti al secondo è $R=20{,}4$ kbit/s, contro il rate nominale $8000\cdot\log_2 6\approx20{,}7$ kbit/s (con 3 bit interi: $24$ kbit/s). Questo tipo di calcolo è alla base degli esercizi sui quantizzatori (Esercizio 5 · quantizzatore a 60 dB per un segnale laplaciano e codice di Huffman (tema d'esame febbraio 2026)).

Errori comuni

• Dimenticare che l'entropia dipende solo dalle probabilità, non dai valori dei simboli: una trasformazione biunivoca ($b=2a-1$) non la cambia, mentre una non biunivoca (come $c=a^2+1$ che fonde $\pm1$) la diminuisce.
• Scrivere $H(x,y)=H(x)+H(y)$ senza verificare l'indipendenza.
• Confondere $\log_2M$ (massimo) con l'entropia effettiva.
• Calcolare l'efficienza con $\log_2M$ e non con la lunghezza reale delle parole (Codici di Shannon-Fano e di HuffmanIn un codice ottimo le parole più probabili non sono più lunghe di quelle meno probabili e le due parole più lunghe differiscono solo per l'ultimo simbolo. Shannon-Fano costruisce l'albero dall'alto dividendo ripetutamente i simboli in due gruppi di probabilità quasi uguali; Huffman lo costruisce dal basso unendo ogni volta i due simboli meno probabili ed è sempre ottimo tra i codici a prefisso. La lunghezza media $L_y$ è la somma delle probabilità dei nodi uniti, l'efficienza è $\eta=\frac{H}{L_y}$.Codici di Shannon-Fano e di Huffman →: lì conta $L_y\log_2M_y$).