Il termine entropia scelto da Shannon per stimare l'efficienza massima di un sistema di codifica è utilizzato anche in termodinamica col significato di "misura del grado di ordine (o di disordine) presenti in un sistema fisico". Il concetto di entropia in termodinamica è piuttosto complesso e può essere adeguatamente affrontato solo con una trattazione matematica che va ben oltre i nostri scopi.

Tuttavia possiamo dare un'idea del significato con qualche esempio. Si considerino per esempio i tre sistemi mostrati in figura, ciascuno composto da 24 quadratini di due colori diversi:

Nel sistema (a) l'ordine è massimo e l'entropia è minima: il sistema infatti risulta molto ordinato. Il sistema (c) è quello con l'entropia maggiore cioè quello maggiormente disordinato.

Non è difficile vedere che esiste una semplice relazione fra l'ordine in un sistema e la quantità di informazioni necessarie per descriverlo. Per esempio le informazioni necessarie per descrivere (a) sono molto semplici: tutti i quadratini blu scuro occupano le due colonne di sinistra, mentre i quadratini chiari occupano le due colonne di destra. Le informazioni necessarie per descrivere (b) (sistema con entropia "intermedia") sono maggiori ("tutti i quadratini scuri occupano le due colonne di sinistra e tutti i quadratini chiari occupano le due colonne di destra tranne che il quadratino in colonna 2 e riga 5 è chiaro mentre il quadratino in colonna 3 e riga 5 è scuro"). Ancora maggiori sono le informazioni necessarie per descrivere lo stato di (c) (occorre in pratica specificare il colore di ogni singolo quadratino presente in ogni singola posizione).

Questo breve cenno ci permette di intuire che la definizione di entropia H di Shannon (basata sull'informazione associata a ogni simbolo e sulla rispettiva probabilità) e la definizione di entropia usata in fisica sono in realtà molto simili. Si può dire che l'entropia fornisce una misura dell'imprevedibilità di un sistema: un sistema a entropia minima è molto prevedibile (occorrono poche informazioni per descriverlo), mentre un sistema a entropia massima è molto imprevedibile (occorrono molte informazioni per descriverlo).

Per esempio il lancio di una moneta non truccata (in cui le probabilità del risultato "testa" e del risultato "croce" sono uguali a 0,5) è un sistema ad entropia elevata, in quanto il risultato del lancio è del tutto imprevedibile. Infatti, come abbiamo già visto, l'entropia calcolata con la formula di Shannon è:

H = p_testa^.I_testa + p_croce^.I_croce = 0,5 x log₂(1/0,5) +  0,5 x log₂(1/0,5) = 1 bit/carattere

Si tratta di un sistema "molto disordinato" nel senso della termodinamica. Viceversa, se la moneta fosse truccata, cioè se per esempio p_testa = 0,8 e p_croce = 0,2, il sistema sarebbe molto più prevedibile e ordinata. Infatti l'entropia calcolata con la formula di Shannon sarebbe

H = p_testa^.I_testa + p_croce^.I_croce = 0,8 x log₂(1/0,8) +  0,2 x log₂(1/0,2) = 0,72 bit/carattere

Nel caso di una moneta totalmente prevedibile, cioè che fornisca per esempio sempre "testa" (ad esempio una moneta truccata con entrambe le facce uguali), l'entropia assume il valore minimo teoricamente possibile:

H = p_testa^.I_testa + p_croce^.I_croce = 1 x log₂(1/1)  = 0 bit/carattere

Dunque il valore minimo di entropia è zero e corrisponde a un sistema completamente ordinato, in cui è possibile un solo stato con probabilità 1. Viceversa il massimo dell'entropia si ottiene quando tutte le configurazioni hanno la stessa probabilità (come nel caso della moneta non truccata). In generale per un sistema con k simboli tutti equiprobabili l'entropia vale:

Per esempio nel caso di un alfabeto composto da 26 lettere, l'entropia massima si verifica quando tutti i simboli hanno la stessa probabilità 1/26 di comparire:

E_max = log₂(26) = 4,7 bit/carattere

Ciò è consistente col fatto che, per rappresentare 26 simboli equiprobabili, occorrono 5 bit.

Dunque in generale, per un qualsiasi sistema di k simboli, l'entropia può assumere valori compresi fra:

0 ≤ E ≤  log₂(k)

Nelle telecomunicazioni la misura dell'entropia di un dato codice è importante poiché fornisce una stima della massima compressione possibile che è possibile effettuare sul codice stesso. Tornando all'esempio delle 26 lettere dell'alfabeto inglese, si è detto che il codice ASCII è molto inefficiente in quanto usa ben 8 bit per rappresentare ogni carattere. Invece il codice Huffman ne usa 4,31 mentre il limite teorico calcolato con la formula dell'entropia di Shannon è 4,19. Questo valore significa che con quel dato insieme di simboli e data quella distribuzione di probabilità, non è possibile in nessun caso ottenere una codifica più efficiente di 4,19 bit per carattere.

Per essere ancora più chiari, torniamo ancora all'esempio della codifica della parola di 28 caratteri

ANTIDISESTABLISHMENTARIANISM

usando il codice ASCII occorrono 224 bit, mentre usando il codice Huffman ne occorrono 120. In nessun caso sarebbe possibile scendere al di sotto di 28 x 4,19 = 117 caratteri, poiché questo è il limite imposto dal calcolo dell'entropia di Shannon.

Si definisce ridondanza il numero di bit in eccesso usati per codificare un dato messaggio rispetto al minimo teorico di Shannon. Per esempio nel nostro caso il codice ASCII presenta una ridondanza pari a 224 - 117 = 107 bit, mentre la ridondanza del codice Huffman è di soli 3 bit. Eliminando la ridondanza presente in un messaggio è possibile comprimerlo, cioè ridurre le sue dimensioni

Occorre a questo punto fare però alcune precisazioni. Il calcolo dell'entropia sull'alfabeto inglese che abbiamo fatto prende in considerazione solo i singoli caratteri e la loro probabilità, supponendo che la probabilità di ogni carattere sia indipendente da tutti quelli che l'hanno preceduto. Ma questo non è evidentemente vero. Per esempio dopo la lettera 'Q' il carattere successivo è, con assoluta certezza, la lettera U. Alcune combinazioni di lettere, viceversa, sono impossibili, come ad es. HH, per cui dopo aver ricevuto una H sappiamo con assoluta certezza che il carattere successivo non può essere un'altra H.

Considerando coppie di caratteri, invece di caratteri singoli, è possibile calcolare quella che Shannon chiama entropia di secondo ordine. Con questa scelta l'alfabeto non è composto più da 26 simboli ma da 26² = 678 coppie diverse di due simboli (es. AA, AB, AC, AD, ... fino a ZZ). Anche in questo caso è possibile stimare la probabilità associata a ogni coppia di simboli e dunque calcolare l'entropia associata, che risulta (secondo i calcoli dello stesso Shannon, che differiscono dai nostri in quanto lui considerava anche lo spazio come simbolo) pari a 4,03 bit/carattere.

Considerando invece di coppie, triplette di caratteri con la relativa probabilità si ottiene la cosiddetta entropia di terzo ordine, ancora più bassa della precedente. Per gruppi di 4 caratteri l'entropia di quarto ordine, secondo Shannon, è pari a 2,8 bit/carattere. Ciò significa che considerando gruppi di 4 caratteri e le relative 26⁴ = 456976 probabilità, un messaggio di 28 caratteri potrebbe essere compresso fino a occupare solo 28 x 2,8 = 78 bit circa.

Aumentando ulteriormente la dimensione dei blocchi di caratteri considerati l'entropia a un certo punto si stabilizza su un valore che, nel caso della lingua inglese, fu calcolato da Shannon in circa 1,3 bit/carattere. In altre parole usando la miglior codifica possibile per la lingua inglese sarebbero sufficienti meno di due bit (in media!) per codificare ogni carattere.

Ai tempi di Shannon tutte queste considerazioni erano piuttosto teoriche poiché i calcolatori dell'epoca non avevano la potenza di calcolo necessaria per gestire algoritmi di compressione così complessi (soprattutto per il calcolo e la generazione dei corrispondenti codici di Huffman). Oggi tuttavia gli algoritmi di compressione usati per comprimere testi, immagini, suoni e video (si pensi al formato zip o jpeg o mp3) fanno uso di queste tecniche e di altre ancora per spingere la compressione dei file molto vicino al limite teorico dell'entropia calcolato da Shannon.

 

precedente - successiva

Sito realizzato in base al template offerto da

http://www.graphixmania.it

Segui @ElePrograMania