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 ${\displaystyle \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.

Nel descrivere la ridondanza dei dati grezzi, la velocità (attuale) di una fonte di informazione è l'entropia media per simbolo ${\displaystyle {\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:

${\displaystyle 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.

${\displaystyle 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:

${\displaystyle D=R-r,\,}$

La quantità ${\displaystyle {\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à ${\displaystyle {\frac {R}{r}}}$ fornisce il massimo rapporto di compressione ottenibile. Complementare al concetto di ridondanza relativa è l'efficienza, definita come ${\displaystyle {\frac {r}{R}}}$; si ha per definizione che ${\displaystyle {\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.

• (EN) Fazlollah M. Reza, An Introduction to Information Theory, New York, Dover , 1994 , ISBN 0-486-68210-2.
• (EN) Bruce Schneier, Applied Cryptography: Protocols, Algorithms, and Source Code in C, New York, John Wiley & Sons, Inc., 1996, ISBN 0-471-12845-7.
• (EN) B Auffarth, M. Lopez-Sanchez e J. Cerquides, Comparison of Redundancy and Relevance Measures for Feature Selection in Tissue Classification of CT images, in Advances in Data Mining. Applications and Theoretical Aspects, Springer, 2010, pp. 248–262.

• Codifica di ridondanza minima
• Codifica Huffman
• Compressione dati
• Negentropia
• Teorema del codice sorgente

• (EN) redundancy, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Eric W. Weisstein, Redundancy, su MathWorld, Wolfram Research.

Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica