"Qual è il numero minimo di bit che servono per memorizzare in media il messaggio di una sorgente?" (vedi Wikipedia).
Nota: si vuole cioè stabilire qual è la quantità minima di bit che si devono trasmettere per comunicare un dato messaggio.
Ricordiamo che nel post "L'Entropia dell'Informazione" abbiamo così definito l'entropia H(x) di una sorgente discreta (cioè con un numero finito di elementi):
In particolare se P(x) è la stessa per tutti i simboli (cioè P(x)=1/N) risulta:
Poiché in generale risulta <I(x)>≤I(x) 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:
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:
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:
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:
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:
Supponiamo che le probabilità di emissione dei simboli sia diversa:
Si noti che se la probabilità di emissione fosse la stessa (cioè P(x)=1/4) avremmo:
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:
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):
In effetti se avessimo usato la codifica precedente, con lo stesso numero di bit per ogni simbolo, avremmo ottenuto un valore più alto:
Infine si osservi che per questo particolare esempio risulta (vedi sopra):
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 la misura dell'informazione non riguarda il significato semantico 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.