Redondance (théorie de l'information)

En théorie de l’information, la redondance correspond au nombre de bits nécessaires pour transmettre un message auquel on soustrait le nombre de bits correspondant aux informations réellement contenues dans ce même message. Officieusement, la redondance correspond à l’« espace » utilisé mais non occupé pour transmettre certaines données. La compression de données permet de réduire ou d’éliminer la redondance que l’utilisateur ne désire pas conserver, alors que les sommes de contrôle permettent d’ajouter une redondance souhaitée pour les besoins du code correcteur lorsque l’utilisateur communique sur un canal bruyant à capacité limitée.

Définition quantitative

Dans la description de la redondance de données brutes, le taux d’entropie d’une source d’informations correspond à son entropie moyenne par symbole. Pour les sources dites sans mémoire, ce taux correspond simplement à l’entropie de chaque symbole, tandis que, dans la plupart des cas généraux d’un processus stochastique, il correspond à

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

la limite, quand n tend vers l’infini, de l’entropie conjointe des premiers symboles n divisée par n. En théorie de l’information, on parle généralement de "taux" ou de l’"entropie" d’une langue. Cela s’applique, par exemple, lorsque la source d’informations est en prose anglaise. Le taux d’une source sans mémoire est simplement $H(M)$ , étant donné que, par définition, il n’existe aucune interdépendance entre les messages successifs d’une source sans mémoire.

Le taux absolu d’une langue ou d’une source correspond tout simplement au

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

logarithme de la cardinalité de l’espace du message, ou de l’alphabet utilisé. (Cette formule est parfois nommée Entropie de Hartley.) Il correspond au taux maximal possible d’informations qui peuvent être transmises grâce à cet alphabet. (Le logarithme doit être ramené à une base appropriée pour l’unité de mesure utilisée.) Le taux absolu équivaut au taux réel si la source est sans mémoire et suit une loi uniforme discrète.

La redondance absolue peut alors être définie comme étant

D=R-r,\,

la différence entre le taux et le taux absolu.

La quantité ${\frac {D}{R}}$ est appelée redondance relative et offre le taux de compression de données maximal possible, lorsqu’elle est exprimée comme étant le pourcentage par lequel la taille d’un fichier peut être réduite. (Lorsqu’elle est exprimée comme étant le ratio entre la taille du fichier original et celle du fichier compressé, la quantité $R:r$ donne le taux maximal de compression qui peut être atteint.) L’efficience est complémentaire au concept de redondance relative, et est définie par ${\frac {r}{R}},$ pour que ${\frac {r}{R}}+{\frac {D}{R}}=1$ . Une source sans mémoire obéissant à une loi discrète uniforme ne dispose d’aucune redondance (et donc d’une efficience de 100 %), et ne peut être compressée.

Autres notions de redondance

L’information mutuelle, ou une variante normalisée, permet de mesurer la redondance entre deux variables. La corrélation totale donne la mesure de la redondance entre plusieurs variables.

La redondance de données compressées correspond à la différence entre l’espérance mathématique de la longueur des données compressées de $n$ messages $L(M^{n})\,\!$ (ou le taux de données espéré $L(M^{n})/n\,\!$ ) et l’entropie $nr\,\!$ (ou le taux d’entropie $r\,\!$ ). (Nous supposons ici que les données sont ergodiques et stationnaires, comme une source sans mémoire.) Bien que la différence de taux $L(M^{n})/n-r\,\!$ peut être aussi arbitrairement faible que $n\,\!$ augmenté, cela ne s’applique pas à la différence de taux réelle $L(M^{n})-nr\,\!$ bien qu’elle puisse théoriquement être majorée de 1 dans le cas de sources sans mémoire à entropie finie.

Voir aussi

Références

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