Ridondanza (teoria dell'informazione)

Nella teoria dell'informazione la ridondanza misura la differenza tra l'entropia H(X) di un insieme X e il suo valore massimo possibile $\log(|{\mathcal {A}}_{X}|)$ .^[1]^[2] Concettualmente indica la quantità di spazio usato in eccesso rispetto al contenuto informativo, ossia misura tutto quanto non è strettamente necessario per ricavare l'informazione utile netta (perché per esempio non aggiunge informazione o trasporta contenuti di altro tipo) e che quindi peggiora l'efficienza della trasmissione. La compressione dei dati o il ricorso a opportuni algoritmi di codifica sono alcuni dei sistemi pratici utilizzati per ridurre o eliminare la ridondanza. Altre tecniche trasmissive invece introducono apposta una ridondanza in quantità nota e limitata, per consentire una maggiore robustezza nella trasmissione o per trasportare sullo stesso canale informazioni ausiliarie per il monitoraggio e controllo del traffico: esempi del primo caso sono gli algoritmi di checksum e di Forward Error Correction impiegati per il rilevamento e la correzione degli errori quando si comunica su un canale rumoroso; esempi del secondo caso sono gli overhead associati alle strutture trasmissive come ad esempio i pacchetti o le trame dati utilizzate in tecnologie quali SDH e OTN.

Definizione formale

Nel descrivere la ridondanza dei dati grezzi, la velocità (attuale) di una fonte di informazione è l'entropia media per simbolo ${\overline {H(M)}}$ . Per le sorgenti senza memoria questa coincide con l'entropia di ciascun simbolo, mentre, nel caso più generale di un processo stocastico, è data da:

r=\lim _{n\to \infty }{\frac {1}{n}}H(M_{1},M_{2},\dots M_{n}),

cioè il limite, per n tendente all'infinito, dell'entropia congiunta dei primi n simboli diviso per n.

La velocità assoluta di una fonte è data dal logaritmo della cardinalità dello spazio del messaggio, o alfabeto.

R=\log |\mathbb {M} |,\,

Questa formula è talvolta chiamata funzione di Hartley.^[3] Essa indica la quantità massima possibile di informazione per unità di tempo che può essere trasmessa con quell'alfabeto. La velocità assoluta è uguale alla velocità effettiva se la sorgente è priva di memoria e ha una distribuzione uniforme.

La ridondanza assoluta può quindi essere definita come la differenza tra la velocità assoluta e quella attuale:

D=R-r,\,

La quantità ${\frac {D}{R}}$ è chiamata ridondanza relativa e fornisce il massimo rapporto possibile di compressione dei dati, espresso come la percentuale di riduzione della dimensione di un insieme di dati. Quando invece viene espresso come rapporto tra la dimensione originale e la dimensione compressa, la quantità ${\frac {R}{r}}$ fornisce il massimo rapporto di compressione ottenibile. Complementare al concetto di ridondanza relativa è l'efficienza, definita come ${\frac {r}{R}}$ ; si ha per definizione che ${\frac {r}{R}}+{\frac {D}{R}}=1$ . Una sorgente senza memoria con una distribuzione uniforme ha ridondanza zero (e quindi efficienza del 100%) e non può essere compressa.

Note

^ Qui si assume che ${\mathcal {A}}_{X}$ siano gli insiemi nei quali sono definite le distribuzioni di probabilità.
^ (EN) David J.C. MacKay, 2.4 Definition of entropy and related functions, in Information Theory, Inference, and Learning Algorithms, Cambridge University Press, 2003, p. 33, ISBN 0-521-64298-1.
«The redundancy measures the fractional difference between $H(X)$ and its maximum possible value, $|\log(|{\mathcal {A}}_{X}|)$ »
^ (EN) Hartley, R. V. L., Transmission of Information, in Bell System Technical Journal, luglio 1928.