Ridondanza (teoria dell'informazione)
Nella [[teoria dell'informazione]] la '''ridondanza''' misura la differenza tra l'[[Entropia (teoria dell'informazione)|entropia]] H(X) di un insieme X e il suo valore massimo possibile <math>\log(|\mathcal{A}_X|)</math>.<ref>Qui si assume che <math>{\mathcal A}_X</math> siano gli insiemi nei quali sono definite le distribuzioni di probabilità.</ref><ref>{{Cita libro|lingua=en|autore=MacKay|nome=David J.C.|wkautore=David J.C. MacKay|titolo=Information Theory, Inference, and Learning Algorithms|url=http://www.inference.phy.cam.ac.uk/mackay/itila/book.html|anno=2003|editore=[[Cambridge University Press]]|p=33|capitolo=2.4 Definition of entropy and related functions|citazione=The ''redundancy'' measures the fractional difference between <math>H(X)</math> and its maximum possible value, <math>|\log(|{\mathcal A}_X|)</math>|ISBN=0-521-64298-1}}</ref> 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 [[Codice (teoria dell'informazione)|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 [[Rilevazione e correzione d'errore|rilevamento e la correzione degli errori]] quando si comunica su un [[Canale (telecomunicazioni)|canale]] rumoroso; esempi del secondo caso sono gli [[overhead]] associati alle strutture trasmissive come ad esempio i [[pacchetto (reti)|pacchetti]] o le trame dati utilizzate in tecnologie quali [[Synchronous Digital Hierarchy|SDH]] e [[Optical Transport Network|OTN]].

== Definizione formale==

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

: <math>r = \lim_{n \to \infty} \frac{1}{n} H(M_1, M_2, \dots M_n),</math>

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.

: <math>R = \log |\mathbb M| ,\,</math>

Questa formula è talvolta chiamata funzione di Hartley.<ref>{{cita pubblicazione|lingua=en|autore=Hartley, R. V. L.|titolo=Transmission of Information|pubblicazione=Bell System Technical Journal|data=luglio 1928}}</ref> 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 discreta uniforme|distribuzione uniforme]].

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

: <math> D = R - r ,\,</math>

La quantità <math>\frac D R</math> è 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à <math>\frac R r</math> fornisce il massimo rapporto di compressione ottenibile. Complementare al concetto di ridondanza relativa è l''''efficienza''', definita come <math>\frac r R </math>; si ha per definizione che <math>\frac r R + \frac D R = 1</math>. Una sorgente senza memoria con una distribuzione uniforme ha ridondanza zero (e quindi efficienza del 100%) e non può essere compressa.

== Note ==
<references />

==Bibliografia==
* {{Cita libro|lingua=en|autore=Reza|nome=Fazlollah M.|titolo=An Introduction to Information Theory|annooriginale=1961|anno=1994|editore=Dover [McGraw-Hill]|città=New York|ISBN=0-486-68210-2}}
* {{Cita libro|lingua=en|autore=Schneier|nome=Bruce|wkautore=Bruce Schneier|titolo=Applied Cryptography: Protocols, Algorithms, and Source Code in C|url=https://archive.org/details/Applied_Cryptography_2nd_ed._B._Schneier|anno=1996|editore=John Wiley & Sons, Inc.|città=New York|ISBN=0-471-12845-7}}
* {{Cita libro|lingua=en|autore=Auffarth|nome=B|autore2=Lopez-Sanchez|nome2=M.|nome3=J.|autore3=Cerquides|titolo=Advances in Data Mining. Applications and Theoretical Aspects|url=https://archive.org/details/advancesdatamini00pern_504|anno=2010|editore=Springer|pp=[https://archive.org/details/advancesdatamini00pern_504/page/n259 248]–262|capitolo=Comparison of Redundancy and Relevance Measures for Feature Selection in Tissue Classification of CT images}}

== Voci correlate ==
* [[Codificazione entropica|Codifica di ridondanza minima]]
* [[Codifica di Huffman|Codifica Huffman]]
* [[Compressione dei dati|Compressione dati]]
* [[Neghentropia|Negentropia]]
* [[Primo teorema di Shannon|Teorema del codice sorgente]]

== Collegamenti esterni ==
* {{Collegamenti esterni}}

{{portale|informatica}}

[[Categoria:Teoria dell'informazione]]