venerdì 7 febbraio 2020

Informazione, codici e bit!

Ricordiamo che è grazie all'entropia informazionale (già trattata nel post "L'Entropia dell'informazione") che si può rispondere ad una fondamentale questione relativa alla memorizzazione e trasmissione di un messaggio:
"Qual è il numero minimo di bit che servono per memorizzare in media il messaggio di una sorgente?" (vedi Wikipedia).
Nota: si vuole cioè stabilire la quantità minima di bit che si devono trasmettere per comunicare un dato messaggio.

Ricordiamo che nel post "L'Entropia dell'Informazione" abbiamo definito l'entropia H(x) di una sorgente discreta (con un numero finito di elementi):
H(x)=<I(x)>
dove <I(x)> è il contenuto medio di informazione della sorgente: 
<I(x)>=∑P(xi)ln(1/P(xi))
mentre P(xi) definisce la probabilità che ogni simbolo xi venga trasmesso.

In particolare se P(x) è la stessa per tutti i simboli (cioè P(x)=1/N) risulta:
<I(x)>=ln(1/P(x))=I(x).
Nota: se P(x)=1/N si ha <I(x)>=lnN∑P(xi)=lnN=I(x) essendo P(xi)=1.

Si dimostra in generale che <I(x)>≤I(x) quindi l'entropia è sempre minore (o al massimo uguale) del contenuto di informazione* di una sorgente che trasmette simboli equiprobabili, cioè risulta: H(x)I(x).

Ora nella trasmissione di dati si sceglie quasi sempre la codifica binaria** indicata dai simboli 0 e 1 — sia per semplicità (perché è costituita da soli due simboli) ma soprattutto per affidabilità (poiché è difficile confondere fisicamente i due simboli) — la cui unità di informazione è detta bit.

Il contenuto di informazione I(x), per questo tipo di sorgente a due valori, viene definito in base-2:
I(x)=log2(1/P(x))
e se l'emissione dei due simboli è equiprobabile (cioè P(x)=1/2) si ha:
I(x)=log2(1/P(x))=1 bit
che è l'unità minima di informazione binaria.
Nota: per cambiare unità di misura e passare da bit a nat (cioè da log2 a ln) basta porre lnx=log2x/log2e≈log2x/1,4 (per le proprietà dei logaritmi).

In particolare con soli due simboli è possibile creare stringhe (cioè sequenze di 0 e 1) la cui lunghezza n determina 2n messaggi distinti; per esempio con stringhe composte da 3 bit possiamo codificare 23=8 messaggi diversi:
000 001 011 111 110 100 101 010
a cui possiamo far corrispondere altrettanti simboli.
Nota: ad esempio possiamo far corrispondere i numeri da 1 a 8 oppure i giorni della settimana (in questo caso sfrutteremmo solo 7 codici).

Ma vediamo un esempio legato all'alfabeto inglese composto da 26 lettere: se ogni lettera fosse trasmessa in modo equiprobabile (P(x)=1/26) il contenuto di informazione per ogni simbolo sarebbe:
I(x)=log2(1/P(x))=log2264,7 bit.
Quindi dovremmo utilizzare esattamente 5 bit per comporre messaggi con l'alfabeto inglese e codificarli in binario***.
Nota: essendo 25=32 sono disponibili sufficienti combinazioni binarie per codificare tutte le 26 lettere dell'alfabeto inglese.

Tuttavia sappiamo che ogni lettera dell'alfabeto viene usata con frequenze diverse (non solo nella lingua inglese) e quindi è opportuno calcolare il contenuto medio di informazione o entropia della sorgente:
H(x)=∑P(xi)ln(1/P(xi))
dove le P(xi) sono le probabilità di ogni lettera calcolate empiricamente.
Nota: un recente studio ha stabilito statisticamente il contenuto medio di informazione dell'alfabeto inglese pari a <I(x)>4,1 bit/simbolo.

Consideriamo ad esempio una sorgente S con soli quattro simboli:
S{A, B, C, D} 
che possiamo codificare utilizzando una sorgente binaria:
A=00, B=01, C=10 e D=11.

Supponiamo che le probabilità di emissione dei simboli sia diversa:
P(A)=1/2, P(B)=1/4 e P(C)=P(D)=1/8
possiamo quindi calcolare l'entropia della sorgente in base-2:
H(x)=∑P(xi)log2(1/P(xi))=(1/2)*1+(1/4)*2+2*(1/8)*3=1,75 bit/simbolo.

Si noti che se la probabilità di emissione fosse la stessa (cioè P(x)=1/4) avremmo:
H(x)=log2(1/P(x))=2 bit/simbolo
poiché l'entropia è in generale maggiore se i simboli sono equiprobabili e in effetti l'entropia è massima per quelle sorgenti completamente casuali.

Ora però ci chiediamo (data la diversa frequenza dei simboli) se non sia possibile ottimizzare il codice, in modo da utilizzare il minor numero possibile di bit nella trasmissione di messaggi.

Proponiamo quindi il seguente abbinamento simbolo-codice:
A=0, B=10, C=110 e D=111.
Nota: coerentemente ai simboli con maggior frequenza facciamo corrispondere meno bit e viceversa (come accade nel codice Morse).

Calcoliamo quindi il numero medio <N(x)> di bit usati per ogni simbolo (calcoliamo cioè la media pesata del numero di bit usati per ogni simbolo):
<N(x)>=∑N(xi)P(xi)=1*(1/2)+2*(1/4)+2*3*(1/8)=1,75 bit/simbolo
dove N(xi) è il numero di bit dell'i-esimo simbolo.

Tuttavia se avessimo usato la codifica precedente, con lo stesso numero di bit per ogni simbolo, avremmo ottenuto un valore più alto:
<N(x)>=∑N(xi)P(xi)=2*(1/2)+2*(1/4)+2*2*(1/8)=2 bit/simbolo
confermando che in generale risulta: H(x)<N(x)>.

Infine si osservi che per questo particolare esempio risulta (vedi sopra):
<N(x)>=H(x)=1,75 bit/simbolo
poiché le probabilità di emissione dei simboli sono diverse.

Ma il fatto che H(x)=<N(x)> è notevole poiché ciò significa, secondo il primo teorema di Shannon, che questa è la migliore codifica possibile(!)
Nota: il teorema è valido per una sorgente senza memoria, cioè quando ogni simbolo viene trasmesso in modo indipendente dal precedente.

(*) Si osservi che il contenuto o meglio la misura dell'informazione non riguarda il significato di un messaggio ma la sua composizione in simboli.
(**) In quasi tutti gli elaboratori elettronici si usa la logica binaria, rappresentata fisicamente da due diversi livelli di tensione elettrica.
(***) Calcoliamo ad esempio il contenuto minimo di informazione necessario per esprimere un orario in forma digitale: 00:00:00.
In totale gli stati dell'orario sono: 24 (ore) x 60 (min.) x 60 (sec.) = 86.400 stati, quindi I(x)=log286.400=16,4 bit cioè servono 17 bit.
Ma possiamo anche scrivere: I(ore)+I(min.)+I(sec.) dove I(ore)=log224=4,6 bit e I(min.)=I(sec.)=log260=5,9 bit per un totale di 5+6+6=17 bit.