Théorie de l’information

Si p = 1/1024. une probabilité très petite pour avoir un 0 dans

1024 essais ! alors

H(S) =

1

1024

log2(1024) +

1023

1024

log2(

1024

1023

) = 0.0112bits

on a 0.0112 bits d’incertitude d’information par essai en moyenne.

donc si on utilise 1024 digit binaire (Code= 0 ou 1) pour coder le

résultat de 1024 essais semble être perte de ressources (1 digit

binaire par essai).

on peut arriver à coder ce message de 1024 symboles à une

moyenne de 0.0112 digit binaire/essai !!

par confusion !!! le digit binaire est appelé bit

Le Mapping binaire : Mapping des symboles de la source à des

digits binaires.

13 / 55

Mesure de l’information et Entropie

Signifiance de l’entropie

L’entropie nous renseigne sur la quantité d’information moyenne

(en bits) qui doit être fournie pour résoudre l’incertitude sur le

résultat d’un évènement (essai). Elle constitue donc la limite

inférieure sur le nombre de digit binaire, en moyenne, qui doit être

donné pour coder nos symboles (qui constitue le message)

si on envoie un nombre inférieur de digit binaire en moyenne, le

récepteur va avoir une incertitude pour décoder correctement le

message

si on envoie un nombre supérieur de digit binaire en moyenne, on

perd de ressources puisqu’on émet plus qu’on a besoin.

atteindre la limite inférieure d’entropie lors du codage est la règle

d’or pour l’encodage (de point de vue compression de donnée).

14 / 55

Plan

Codes de longueurs fixes

1 Problématique de la Communications

2 Mesure de l’information et Entropie

3 Codes de longueurs fixes

4 Codes de longueurs variables, codes préfixes

5 Algorithme de Huffman

6 Algorithme de Fano-Shannon

7

Limitations de Fano-Shannon et Huffman et Supériorité de LZW

8 Code par répétition

15 / 55

Codes de longueur fixe

Codes de longueurs fixes

un choix évident pour coder des symboles équiprobables est le

code de longueur fixe:

les 96 caractères imprimables =⇒ 7-bit ASCII

les caractères unicode =⇒ UTF-16

10 digit décimaux =⇒ 4-bit BCD (binary coded decimal)

les codes de longueurs fixes ont des avantages :

l’accès aléatoire au code est faisable: pour décoder le neme symbol,

on peut directement decoder le neme séquence de longeur fixe sans

etre obligé à décoder les séquences de 1 à n-1.

les tables look-up suffisent pour coder/decoder

16 / 55

Limitation du codage de longueur fixe

Codes de longueurs fixes

L’efficacité d’un code est η = H(S)

l’entropie mesuré ici est :

R avec R est a longueur du code

H(S) = 0.333 × 1.58 + 0.5 × 1 + 2 × 0.83 × 3.58 = 1.626 bits

Peut-on trouver un encodage où la transmission de 1000 symboles

nécessite 1626 digit binaire en moyenne ? Si oui η = 1 puisque

R = H(S) ⇒ Efficacité de 100 %

avec un encodage de longueur fixe qui utilise 2 digit binaire pour chaque

symbole, on transmet 2000 digits binaires. ici η = 1.626

Efficacité de 81,3 %

2 = 0.813 ⇒

17 / 55

Extension de source

Codes de longueurs fixes

Pour améliorer l’efficacité du codage, on peut transmettre et donc coder les symboles non

pas individuellement mais par blocs de J symboles.

Exemple: avec {A, B} on peut faire avec J = 2. les blocs {AA, AB, BA, BB}.

à partir d’une source primaire de K symboles, on construit une source secondaire de K J .

N : longueur de codage de chaque symbole de la source secondaire. alors N ≥ log2(K J )

=⇒ N ≥ J · log2(K ) et donc N = E[J · log2(K )] + 1

R: longueur de codage de chaque symbole de la source primaire:

R = N/J = E[log2(K )] + 1/J. (R n’est plus un entier)

efficacité de la source primaire avec extension de source : η2 =

H(S)

E[log2(K )]+1/J

η1 =

H(S)

E[log2(K )]+1 . IL est clair que η2 > η1

La technique d’extension de source peut ainsi améliorer l’efficacité du codage pour des

mots de codes de longueur fixe.

C’est comme si η2 = H(S)

ex: K=24 et J=3 donc K J = 13824 donc N=14 et 2N = 16384 et donc R=4.666.

Si tous les symboles sont équiprobables : H(S) = 4.585 et η2 = 98.25% > η1 = 91.7%.

R = J·H(S)

N

18 / 55

Premier Théorème de Shannon

Codes de longueurs fixes

Il découle de l’extension de source

on a η2 = H(S)

R = J×H(S)

N ≤ 1

on a donc N > J × H(S) + 1.

J = R ≥ H(S) + 1

de point de vue source primaire: N

J

en posant 1

J = ε, ε peut être aussi petit que l’on veut

Théorème de Shannon : Pour avoir un codage sans erreur, une

source S doit etre codée en moyenne avec au moins H(S) bits :

R ≥ H(S)

19 / 55

Codes de longueurs variables, codes préfixes

Plan

1 Problématique de la Communications

2 Mesure de l’information et Entropie

3 Codes de longueurs fixes

4 Codes de longueurs variables, codes préfixes

5 Algorithme de Huffman

6 Algorithme de Fano-Shannon

7

Limitations de Fano-Shannon et Huffman et Supériorité de LZW

8 Code par répétition

20 / 55

Codes de longueurs variables, codes préfixes

Codes préfixe

examiner ces trois codes de cette source de 4 symboles et coder

le message BOF.

21 / 55

Codes de longueurs variables, codes préfixes

Codes préfixe

1 Avec le code I, le message envoyé est : 001001. C’est ce que voit le récepteur. Comment

peut-il l’interpréter? De manière correcte bien sûr mais aussi 00 1 00 1 c’est à dire BIBI.

Problème, le message n’est pas décodable de manière unique. Ceci est du au fait que le

1, code attribué à I est le début d’un autre code 10 attribué au O. Pour éviter cette

situation, il ne faut pas qu’un code soit le "préfixe" d’un autre code. Les codes qui

remplissent cette condition sont des codes préfixes.

2 Avec le code III, le message envoyé est 01111011. Au décodage nous pouvons voir 0

111... c’est à dire IO... Mais ici nous nous rendons compte du fait que ce qui suit c’est à

dire soit 1, soit 10, soit 101 ne sont pas des codes et donc, nous pouvons revenir en

arrière pour modifier l’interprétation soit 01 111 011 et retrouver le bon message. Le code

n’est pas décodable de manière instantanée. Ceci est aussi dû au fait que le code utilisé

n’est pas un code préfixe.

3 Le code II est lui un code préfixe et nous avons les deux propriétés souhaitées: décodable

de manière unique et de manière instantanée.

22 / 55

Codes de longueurs variables, codes préfixes

Règles de construction d’arbre

Un déplacement à gauche correspond à un "0".

Un déplacement à droite correspond à un "1".

Chaque déplacement crée un noeud de l’arbre.

Chaque noeud à un père (vers le haut) et peut avoir deux fils (vers

le bas).

Le lien entre deux noeuds est une branche.

Un noeud qui n’a pas de fils est une feuille.

23 / 55

Codes de longueurs variables, codes préfixes

Inégalité de Kraft

un arbre de profondeur n ⇒ le nb de codes possibles est 2n.

à la hauteur nk , on décide d’attribuer ce noeud à un code Ck ⇒ ce noeud devient une

feuille. Cela interdit tous les noeuds fils. le nombre de noeuds interdits est 2n−nk .

si l’alphabet à coder contient K symboles auxquels sont attribués des codes de long

variable nk , le nb total de feuilles interdites est: (cid:80)K

Le nb de feuilles interdites est inférieur ou égal au nb de feuilles finales: (cid:80)K

inégalité de kraft : (cid:80)K

k =1 2n−nk

k =1 2−nk ≤ 1

k =1 2n−nk ≤ 2n

24 / 55

Codes de longueurs variables, codes préfixes

2eme théorème de Shannon: Limites sur R

i=1 pi · ni avec ni

longueur moyenne d’un code variable est R = (cid:80)K

est la longueur du symbole Si

Depuis l’inégalité de Kraft on peut montrer que H(S) ≤ R

on a l’égalité H(S) = R si pk = 2−nk

donc pour atteindre la limite basse, on choisit nk tel que 2−nk = pk

: plus un symbole est probable moins on lui attribue de bits.

mais cette condition n’est pas facilement réalisable car nk est un

entier. en pratique on choisit nk ≥ −log(pk ) ≥ nk − 1 ou

2−nk ≤ pk ≤ 2−nk +1

à partir du coté droite de l’inégalité on peut arriver à la limite haute

de R: R < H(S) + 1

d’où le théorème de codage source de shannon :

H(S) ≤ R < H(S) + 1

25 / 55

Codes de longueurs variables, codes préfixes

Codes de longueur variable

Huffman l’a introduit en 1951

utiliser des codes courts pour des symboles très probables

utiliser des codes plus longues pour des symboles peu probables

noter que les symboles sont des feuilles de l’arbre de Huffman

=⇒ c’est une condition nécessaire et suffisante pour un code

instantané et décodable

26 / 55

Codes de longueurs variables, codes préfixes

Longueur Moyenne et efficacité du code

La longueur moyenne d’un code à longueur variables est définie

par:

N

(cid:88)

R =

pk nk

k =1

avec pk probabilité du symbole sk . et nk longueur du code de sk .

N est le nombre de symboles

Efficacité d’un code η = H(S)

R

ex: efficacité du code de Huffman est η = 1.626

1.666 100% = 97.6%

ex : efficacité d’un code de longueur fixe de K=24 symboles :

R = E[log2(K )] + 1 = 5 or 25 = 32. Il y a donc 5 codes

non-utilisés. Si tous les symboles sont équiprobables, on a

H(S) = log2(24) = 4.585. et l’efficacité η = 4.585

× 100%

5 × 100% = 91.7 %

27 / 55

Plan

Algorithme de Huffman

1 Problématique de la Communications

2 Mesure de l’information et Entropie

3 Codes de longueurs fixes

4 Codes de longueurs variables, codes préfixes

5 Algorithme de Huffman

6 Algorithme de Fano-Shannon

7

Limitations de Fano-Shannon et Huffman et Supériorité de LZW

8 Code par répétition

28 / 55

Algorithme de Huffman

Algorithme de Huffman

1 A chaque étape, les noeuds sont rangés dans un tableau par

ordre de probabilités décroissantes.

2 Les deux noeuds du bas du tableau, donc ceux de probabilités les

plus faibles sont associés pour donner un noeud "père". Celui-ci

se voit attribuer comme probabilité la somme des probabilités de

ses deux "fils".

3 Nous avons un nouvel ensemble de noeuds ayant un élément en

moins (remplacement des deux "fils" par le "père") et nous

reprenons l’étape 1 jusqu’à l’arrivée au sommet de l’arbre

(ensemble de noeuds d’un seul élément).

4 L’ensemble initial des noeuds est constitué des feuilles donc des

symboles de la source;

29 / 55

Exemple

Algorithme de Huffman

Initialement S = {(A, 1/3)(B, 1/2)(C, 1/12)(D, 1/12)}

Première itération:

les symboles peu probables sont C et D

créer un nouveau noeud

ajouter un nouveau symbole à la source

S = {(A, 1/3)(B, 1/2)(CD, 1/6)}

Deuxième itération :

les symboles peu probables sont CD et A

créer un nouveau noeud

ajouter un nouveau symbole à la source

S = {(B, 1/2)(ACD, 1/2)}

Troisième itération :

les symboles peu probables sont ACD et B

créer un nouveau noeud

ajouter un nouveau symbole à la source

S = {(BACD, 1)}

Terminé !

30 / 55

Un autre code (qui n’est pas décodable)

Algorithme de Huffman

Soit le codage suivant pour le même exemple précédent

Pour quel raison ce code ne fonctionne pas correctement ?

La longueur moyenne d’un message encodé par ce code est :

(0.333 + 0.5)(1) + (0.083 + 0.083)(2) = 1.22bits

cette longueur moyenne est inférieur à sa limite qui est l’entropie

H(S) = 1.626 !!!

31 / 55

un autre exemple

Algorithme de Huffman

Soit une source de 5 symboles

S = {(A, 0.1)(B, 0.3)(C, 0.2)(D, 0.3)(E, 0.1)}

Appliquer Huffman pour trouver les codes de cette source.

32 / 55

construction de l’arbre

Algorithme de Huffman

33 / 55

labeler les branches

Algorithme de Huffman

34 / 55

Algorithme de Huffman

35 / 55

Algorithme de Huffman

36 / 55

arbre de code final

Algorithme de Huffman

37 / 55

Algorithme de Fano-Shannon

Plan

1 Problématique de la Communications

2 Mesure de l’information et Entropie

3 Codes de longueurs fixes

4 Codes de longueurs variables, codes préfixes

5 Algorithme de Huffman

6 Algorithme de Fano-Shannon

7

Limitations de Fano-Shannon et Huffman et Supériorité de LZW

8 Code par répétition

38 / 55

Algorithme de Fano-Shannon

Codage de Fano-Shannon

Antérieur au codage d’Huffman,

l’arbre est construit en partant du sommet c’est à dire du MSB

pour le codage.

Il est basé sur la recherche de groupes de probabilités les plus

proches possibles.

Il donne, dans les cas simples, le même résultat que le codage

d’Huffman mais il n’a pas son caractère optimal et il induit en

général un codage moins efficace.

39 / 55

Algorithme de Fano-Shannon

Algorithme de Fano-Shannon

Ordonner les symboles de la source en probabilités décroissantes

Séparer les symboles en deux groupes de probabilités les plus

proches possibles.

Le MSB du groupe supérieur sera "0" et celui du groupe inférieur

"1".

Recommencer l’opération dans chaque sous-groupe pour affecter

les bits suivants et ce jusqu’à séparation de tous les symboles de

la source.

40 / 55

Algorithme de Fano-Shannon

exemple

Source de symbole

= {(E, 0.48)(A, 0.21)(S, 0.12)(T , 0.08)(U, 0.06)(U, 0.05)}

pour la même source, verifier que Huffman donne aussi la même

efficacité (même longueur nk ) pour chaque symbole.

41 / 55

Algorithme de Fano-Shannon

Points communs entre Fano-shannon et Huffman

Ce sont deux codes de longueurs variables

permettent de faire une compression de donnée !

nécessitent la connaissance préalable des probabilités des

symboles

il faut transmettre, en plus du message, la table de codage

Ils appartiennent à la catégorie: Codage statistique à longueur

variable

Huffman est utilisé dans :

Format TIFF (Tagged Image Format File) de compression des

images

Format JPEG (Join Photographic Expert Group) qui utilise en plus

une transformée de Fourier en cosinus (DCT)

Format MNP (Microcom Networking Protocol) de transmission de

données sur lignes téléphonique (avec adjonction d’un système

correcteur d’erreur).

42 / 55

Limitations de Fano-Shannon et Huffman et Supériorité de LZW

Plan

1 Problématique de la Communications

2 Mesure de l’information et Entropie

3 Codes de longueurs fixes

4 Codes de longueurs variables, codes préfixes

5 Algorithme de Huffman

6 Algorithme de Fano-Shannon

7

Limitations de Fano-Shannon et Huffman et Supériorité de LZW

8 Code par répétition

43 / 55

Limitations de Fano-Shannon et Huffman et Supériorité de LZW

Quelques Limitations sur Huffman et Fanon-Shanon

Probabilité des symboles

peut ne pas être connu

peut changer avec le temps

Source

peut ne pas générer des symboles iid. ex le texte Anglais. On peut

le coder symbole par symbole mais comme ça on n’exploite pas la

redondance du texte

44 / 55

Limitations de Fano-Shannon et Huffman et Supériorité de LZW

Quel est l’entropie de l’angais

Si on compte les probabilités des symboles d’une façon individuelle mais sans utiliser le

contexte, l’entropie H=4.177 bits/symbol

Mais le texte Anglais est plein de contexte ! ex: completer la lettre manquante : "Nothing

can be said to be certain, except death and ta?"

c’est "x". pourtant "x" a une très faible probabilité p =0.0017 dans l’anglais

Shannon et d’autres chercheurs ont trouvé que l’entropie de l’anglais est inférieur à 4.177

il a estimé 0.6 à 1.3 bits/lettre en utilisant l’expectation humaine

45 / 55

Limitations de Fano-Shannon et Huffman et Supériorité de LZW

Lempel-Ziv-Welch (1977,1978,1984)

développé en 1977-1978 par Abraham Lempel et Jacob Ziv et est

l’algorithme dit LZ77 et LZ78.

Une amélioration de ces algorithmes a été proposée en 1984 par

Welch ce qui donne l’algorithme LZW.

Cet alg n’ayant pas de statistiques sur la source, va se constituer

en ligne un dictionnaire où figurent les groupes de mots qui se

trouvent répétés dans le document à compresser.

Ziv est un diplômé (1950s) du MIT lui aussi comme Huffman

LZW atteint asymptotiquement la limite inférieure de shannon qui

est H(S).

Normes de compression qui utilise LZW (souvent avec Huffman)

sont: gif (compression d’images), tiff, png, pdf, zip (Winzip), gzip,

pkzip,

La compression de données pour la transmission sur modem

norme V42 bis.

46 / 55

Limitations de Fano-Shannon et Huffman et Supériorité de LZW

un dictionnaire de base comportant tous les symboles est

connu par tout le monde.

lorsque un msg est traité, l’encodeur construit un tableau

qui fait le mapping entre les séquences des symboles et

un code fixe de N-bit. La taille du tableau (dictionnaire) est

2N .

l’encodeur transmet donc l’indice de la séquence (N bits)

dans le dictionnaire au lieu de la séquence ((cid:29) N bits).

d’où la compression

le dictionnaire peut être reconstruit par le décodeur

utilisant les informations du flux codé. Le dictionnaire

n’est jamais transmis.

si le dictionnaire est plain (2N positions dans le tableau

utilisés), une réinitialisation du dictionnaire est faite.

47 / 55

Limitations de Fano-Shannon et Huffman et Supériorité de LZW

Codage LZW

48 / 55

Limitations de Fano-Shannon et Huffman et Supériorité de LZW

exemple: codage de "abbbabbbab..."

49 / 55

Limitations de Fano-Shannon et Huffman et Supériorité de LZW

Décodage LZW

50 / 55

Limitations de Fano-Shannon et Huffman et Supériorité de LZW

Exemple 2 de LZW: codage de "LES PAGES D’IMAGES D’ORAGES"

on ajoute aussi deux caractère spéciaux de contrôle dans le

dictionnaire.

51 / 55

Limitations de Fano-Shannon et Huffman et Supériorité de LZW

pour plus de commodité, l’espace est noté "_". Le message sera

codé sur 10 bits ce qui permet un dictionnaire de 1024 mots

out=04C04505302005004104710302004402704904D10710910B04F 05210F 053

En ASCII, les données codées sur 8 bits occupent 27 × 8 = 216

bits.

Compactées par LZW sur 10 bits, il y a 20 × 10 = 200 bits. Nous

avons ici un taux de compression de 92.6% sur un exemple

adapté mais il est évident que l’efficacité de cet algorithme sera

d’autant plus grande que les données à compresser seront de

taille importante.

52 / 55

Limitations de Fano-Shannon et Huffman et Supériorité de LZW

Décompression

53 / 55

Plan

Code par répétition

1 Problématique de la Communications

2 Mesure de l’information et Entropie

3 Codes de longueurs fixes

4 Codes de longueurs variables, codes préfixes

5 Algorithme de Huffman

6 Algorithme de Fano-Shannon

7

Limitations de Fano-Shannon et Huffman et Supériorité de LZW

8 Code par répétition

54 / 55

Codes par répétition

Code par répétition

Le plus typique et le plus simple de ces algorithmes est la méthode RLE (Run Length

Encoding) ou encore RLC (Run Length Coding).

Elle consiste à repérer une donnée qui a des apparitions consécutives fréquentes. Dans

ce cas, elle sera remplacée par deux indications :

1 Un chiffre qui indique le nombre de répétitions.

2 La donnée elle-même.

ex: sortie d’un écran monochrome: 11111111000001111110000 sera représentée par 81

50 61 40.

On peut économiser quelques bits sachant qu’il s’agit d’une alternance de "1" et de "0" : il

n’est nécessaire de préciser que la nature du premier bit de la liste soit dans l’exemple : 81

5 6 4.

Dans le cas de couleurs, celle-ci sont représentées par un nombre entier (de 0 à 255 par

exemple). Afin de ne pas confondre le nombre de répétitions avec le code de la couleur, il

est nécessaire d’ajouter un caractère séparateur entre les différentes zones, le caractère

séparateur usuel pour RLE est le "#" et un autre caractère séparateur entre le nombre

d’occurrences et le code de couleur lui-même qui est en général l’espace.

ex: 88888888 24242424242424 67676767 est codé #8 8#7 24#4 67#

RLE est utilisé dans Les logiciels d’images plan par plan : PCX (Paintbrush), IFF/LBM (De

Luxe Paint), JPEG

utilisé dans la Télécopie : norme CCITT groupes 3 et 4.

55 / 55