entropie

Rédaction : Boucherit
Programmation: Castelbou
Recherche : Hassani

Introduction

Comment quantifier l'information transmise sur un canal donné ? Sur une ligne téléphonique par exemple, sur un réseau informatique ou par ondes radio ? c'est la question que s'est posé l'ingénieur Claude Shannon (1916-2001) alors ingénieur en génie électrique au Laboratoire Bell.

En 1948 il formalise cette théorie, alors conçue pour quantifier l'information perdue sur les lignes téléphoniques . Depuis l'entropie occupe une place importante dans nombre de domaines liés à la théorie de l'information . Des lignes téléphoniques à nos réseaux wifi regardons ensemble comment l'entropie nous permet d'optimiser le flux d'information transmis .

Dans cet article nous verrons tout d'abord, le concept d'entropie dans les grandes lignes, puis sa formalisation mathématique et enfin comment encoder une information et un programme permettant de calculer l'entropie d'un texte .

1) Présentation du concept d'entropie

L'entropie d'une source d'information peut se résumer par la quantité d'information transmise par cette source, on doit sa théorisation et sa formalisation à l'ingénieur Claude Shannon (1916-2001) .

Que ce soit un texte, un signal ou un code lorsqu'un système reçoit une information il existe possiblement une incertitude quant à la prochaine information qu'il recevra. Dans le cas d'un code binaire par exemple, après avoir reçu un '0' le système ne peut pas déterminer s'il recevra encore un '0' ou bien un '1', on dit alors que l'entropie est positive ou non nulle. À l'inverse pour une source qui émet toujours la même information, par exemple une suite continue de '0',ont dit que l'entropie est nulle. Car il n'y a pas d'incertitude sur la nature du prochain bit d'information.

2) Formalisation de l'entropie

-Définition : Pour une source, qui est une variable aléatoire  discrète X comportant n symboles, chaque symbole xi ayant une probabilité Pi d'apparaître, l'entropie H de la source X est définie comme :

Formule :

{\displaystyle H_{b}(X)=-\mathbb {E} [\log _{b}{P(X)}]=\sum _{i=1}^{n}P_{i}\log _{b}\left({\frac {1}{P_{i}}}\right)=-\sum _{i=1}^{n}P_{i}\log _{b}P_{i}.\,\!}
E: désigne l'espérance mathématique
log : c'est le logarithme en base b
P(X) : c'est la probabilité que la variable X apparaisse

Lorsqu’on utilise le concept d'entropie de Shannon en informatique pour coder de l'information, on utilise le logarithme en base 2 car on souhaite coder en binaire. L'entropie que l'on obtient suite à ce calcul indique le nombre moyen de bits pour coder chaque élément de la source d'information. Par exemple soit un texte composé d'une chaîne de lettres et d'espaces, soit 27 caractères. Si ces caractères sont équiprobables alors l'entropie associée à chaque caractère est log(27) = 4.75 et des poussières, ce qui signifie donc qu'il faut entre 4 et 5 bits pour coder un caractère.

Prenons un second exemple, nous avons un texte composé uniquement de a, de b, de c et de d, dont la longueur est 8. Si 'a' apparaît 4 fois, 'b' deux fois, 'c' et 'd' une fois alors l'entropie de ce texte vaut1.75, il faut donc entre 1 et 2 bits pour coder chaque caractère.

-Exemple avec une source binaire :

La courbe ci-dessus est celle de la fonction f(x) = -(x*(log(x)/log(2)-(1-x)(log(1-x)/(log(2)).
Ici x représente la probabilité pour une source binaire d'émettre 0 (donc pour émettre1 on a une probabilité de 1-x). C'est donc la courbe de l'entropie des sources binaires émettant 0 avec une probabilité x et 1 avec une probabilité 1-x.

3) Codage de l'information et entropie du texte

1-codage de l'information:

Pour encoder une information (un son, une image), on procède à trois étape.

-l'échantillonnage, qui ramène des données (hauteur d'une note, couleur d'un pixel) à une valeur discrète

-suivi du codage, qui convertit ses valeurs discrètes en nombre binaire de longueur la plus courte possible dans le but de les compresser ou de les transmettre sur un canal de transmission

-et enfin le codage correcteur d'erreurs, qui permet de vérifier une erreur lors de la transmission des données ainsi obtenues

exemple : codage d'une image

On considère l'image ci-dessous en teinte de gris allant de noir (0) à blanc (3)

source : http://images.math.cnrs.fr/Claude-Shannon-et-la-compression-des-donnees.html

On se retrouve donc en mettant bout à bout les valeurs du tableau ci-dessus (pour les 25 pixels sélectionnés) avec cette suite de valeurs discrètes:
(0,1,3,2,0,3,2,2,1,2,2,1,1,2,2,2,1,1,2,2,1,1,2,1).

On doit à présent coder cette suite. Une façon de la coder est tout simplement de convertir chaque nombre en binaire ce qui nous donne :

000111100011101001101001011010100101101001011001

Cependant un codage efficace doit être le plus compact possible. ici chaque valeur peut être encodé sur 2 bit car sa longueur dépend de log2(n), soit n le nombre de valeur . Nous avons donc 25 valeurs d'une longueur de 2 bit ce qui nous fait 50 bit . Cela semble correct mais on peut faire mieux !
C'est ici qu'intervient la notion de codage entropique .

Le codage entropique se base sur les taux d'apparition du symbole dans la suite qu'il encode (ici des valeurs numériques) . Un symbole dont le taux d'apparition est élevé sera plus le code sera court et à l'inverse un symbole qui apparaît rarement aura lui un code plus long .
Le code de Huffman est un algorithme de compression de donnée dont le taux de compression est l'entropie de la source qu'il encode . Un petit cours accéléré sur le codage de Huffman :

http://www-igm.univ-mlv.fr/~lecroq/cours/huff.pdf

En reprenant la séquence précédente on donne à chaque valeur un encodage : '0' donne 001, '1' 01, '2' 1 et '3' 000. On obtient donc le code suivant :

00101000100100011011101011110101110101101

Nous obtenons un code de longueur 42, plus compact que le code précédent ! Ce code est facilement décodable car préfixe . Mais qu'est-ce qu'un code préfixe ? C'est tout simplement un code donc chaque élément n'est pas préfixe d'un autre , 01001 de traduit assez facilement par {1, 0} . Vous pouvez essayer avec des exemples ! La longueur d'un bit moyen sur cette séquence se calcule par la longueur sur le nombre de valeur on a donc :

42/26 = 1,68 bits (par symbole)

Les probabilités sont distribuée de la manière suivante :

p0=2/25
p1=925
p2=12/25
p3=2/25

L’entropie de cette séquence vaut :

−2/25×log2(2/25)−9/25×log2(9/25)−12/25×log2(12/25)−2/25×log2(2/25)≈1,62

Dans cette exemple nous avons voulu présenter une application de l'entropie . On peut s'approcher du nombre moyen optimal de bits pour encoder une source grâce à cette dernière entre autre .

2- entropie du texte :

-exemple : code qui calcule l'entropie d'un texte en français

Conclusion

Dans ces quelques lignes nous vous avons présenté le concept d'entropie ainsi que son application au travers d'un programme et d'un exemple . Il reste beaucoup de chose à dire sur l'entropie de Shannon mais surtout sur le concept d'entropie en général . Cette idée est avant tout un théorème physique de thermodynamique dont Shannon a montré un lien avec sa propre théorie . Un exemple édifiant de deux disciplines opposées que les mathématiques ont su rapprocher .

Si le sujet vous intéresse : https://fr.wikipedia.org/wiki/Entropie_(thermodynamique)

Bibliographie : wikipédia , telecom.ulg ,images.math.cnrs,

7 Cliquer pour recommander cet article