Principes gnraux de codage entropique d'une source

Cours : Compression d'images Master II: IASIG Dr. Mvogo Ngono Joseph

Table des matires

Objectifs Introduction I - Entropie d'une source

5 7 9

II - Dfinitions et rsultats fondamentaux lis au codage de source 11 III - Les algorithmes de codage statistiques IV - Algorithme de codage arithmtique Conclusion 13 17 21

Objectifs

L'objectif de ce module est de rappeler les rsultats fondamentaux du codage entropique ou compression reversible d'une source de donnes ( texte, image, ...). Ces rsultats prliminaires seront utiliss dans notre mthodologie de compression des images de tldtection. Plusieurs types de mthodes de codage entropique seront abordes notamment les mthodes d'ordre zro, non-adaptatives savoir : l'algorithme de codage de Shannon-Fano l'algorithme de codage de Huffman l'algorithme de codage arithmtique

Introduction

La notion de codage entropique ou compression rversible d'une source correspond un codage sans perte des symboles de la source avec pour objectif d'atteindre une limite thorique du gain de compression de Shannon caractrise par l'entropie de la source. Le but du codage entropique est de remplacer les messages mis par une source S utilisant un alphabet N-aire {s 1 , s 2 , . .. .. . .. , s N } par des messages crits dans l'alphabet binaire utilis par les systmes de stockage d'information sur ordinateur. Les codes tudis ici sont des codes de longueur variable, on suppose qu'un code associe chaque symbole si i=1, ..... N de la source un mot de code binaire m i , squence de l i bits. Un tel code doit avoir des proprits permettant de reconstruire sans ambigut les messages mis par la source, nous passerons en revue dans la section suivante quelques dfinitions et rsultats fondamentaux de la thorie des codes.

Entropie d'une source

I-

Dfinition : Notion d'entropie d'une source simple ou sans mmoire Soit une source S dfinie par son alphabet {s 1 , s 2 , . .. .. . .. , s N } de symboles et ses
caractristiques d'mission rgies par une loi de probabilit P:

{P s 1 , P s 2 , . .. .. . P s N } .Une source sera dite simple ( ou sans mmoire) si les

symboles mis par la source S sont indpendants et de mme loi. Une suite de N symboles mis aux instants 1 , 2 , .. . .. . n par S suit donc une loi de probabilit : P s1 , s 2 ,. .. .. . s n = p s1 p s 2 . . .. . p s n . L'entropie d'ordre zro H(S) d'une source simple S, de loi de probabilit P, est
N

dfinie par l'expression :

H S = p s i log 2 p s i .
i=1

L'entropie dans ce cas a la proprit suivante: H(S) est maximale si tous les symboles {s 1 , s 2 , . .. .. . .. , s N } de la source S sont quiprobables. Dans ce cas , l'entropie est gale l'information associe chaque message pris individuellement.

i{1,2,............ N } , p s i =

1 H S =log 2 N . N

Exemple : Calcul de l'entropie d'une source binaire

Considrons le cas d'une source binaire S dont l'alphabet est {0,1} tel que P(1) = p et donc P(0)=1-p

0 p1 H S = plog 2 p 1 p log 2 1 p= f p
la fonction f(p) est symtrique par rapport p=0.5 et est maximale pour p=0.5

Dfinition : Entropie d'ordre K

On suppose une source amplitude discrte avec mmoire, Il existe alors des dpendances statistiques entre les chantillons successifs de la source. Soit s=s n=s n , s n 1 ,.... , s n K 1 un vecteur constitu de K chantillons successifs de la source. Ce vecteur est caractris par sa probabilit conjointe
T

P S s
qui est indpendante du temps si on considre une source stationnaire, s est une T ralisation du vecteur alatoire S= S n , S n1 , ..... S n K 1 .On dsigne par entropie d'ordre k ou entropie conjointe des vecteurs alatoires l'expression :

H K S =

1 1 E log2 P S S = .... p S s log2 p S s K K s

II -

Dfinitions et rsultats fondamentaux lis au codage de source

Dfinition : Rgularit Dfinition : Dchiffrabilit
Un code rgulier est dchiffrable si pour toute suite il est possible de distinguer les

II

Un code est dit rgulier si tous les mots de code m i sont distincts. Tous les codes doivent au moins tre rguliers pour permettre un dcodage univoque.

m1 , m2 , ..... m n de mots de code

m i sans ambigut et reconstruire ainsi les symboles

si correspondants.
Pour les codes de longueur variable, cette proprit est satisfaite pour les codes dits sans prfixes, obtenus en vitant qu'un mot du code ne soit identique au dbut d'un autre.

Dfinition : Codes instantans

On dit d'un code qu'il est dcodage instantan s'il est possible de dcoder les mots de code ds lors que tous les symboles qui en font partie ont t reus.

Dfinition : Extension d'un code

L'extension d'ordre n d'un code est le code form par les squences de n mots du code initial.

Fondamental : Condition ncessaire et suffisante de dchiffrabilit

Pour qu'un code soit dchiffrable il faut et il suffit que toutes ses extensions soient rgulires.

Attention
L'ingalit de Kraft constitue un rsultat fondamental en thorie des codes. Elle fournit une condition ncessaire et suffisante d'existence de codes dchiffrables et instantans, exprime en fonction de la longueur des mots de code.

Fondamental : Ingalit de Kraft Soient l 1 , l 2 , ..... , l N des longueurs de mots candidates pour coder une source Naire dans un alphabet binaire. Alors l'ingalit de Kraft :

11

Dfinitions et rsultats fondamentaux lis au codage de source

1 1 li i=1 2
est une condition ncessaire et suffisante d'existence de codes dchiffrables et instantans respectant ces longueurs de mots.

Fondamental : THORME DE SHANNON

Limite infrieure de la longueur moyenne d'un code. Soit une source stationnaire sans mmoire, la longueur moyenne cods m i est limite par la valeur de l'entropie de la source S.
N i=1 N i=1

n des mots

n = l i p si p s i log 2 p si .
Borne suprieure de la limite suprieure ( code de Shannon) Il est galement possible de trouver un code dchiffrable tel que :

H S nH S 1 .

12

III -

Les algorithmes de codage statistiques

III

Le principe des algorithmes de codage statistique est d'utiliser les probabilits d'occurence de chaque symbole dans une squence de symboles manant de la source. Dans le cadre de ce cours nous examinerons dans cette catgorie deux algorithmes.

Mthode : Algorithme de Shannon-Fano

L'algorithme comporte les tapes suivantes : 1) Les probabilits d'apparition de chaque symbole sont places dans un tableau tri par ordre dcroissant de probabilits . 2) Le tableau est coup en deux groupes de symboles S 0 et S1 dont la somme des probabilits de chaque groupe avoisine 0.5. 3) Le groupe S0 est cod par un "0" et S1 par un "1". 4) Si un groupe Si n'a qu'un seul lement, c'est une feuille terminale, sinon la procdure reprend rcursivement l'tape 2 sur le groupe Si.

Exemple : Application de l'algorithme de Shannon-Fano

1. Pour illustrer cet algorithme, nous allons coder la phase suivante :

"Le codage est indispensable" Pour simplifier nous n'allons pas prendre en compte le symbole espace (blanc). cette phase est une source de 24 symboles Tous ces symboles manent de l'alphabet.

A={E , S , A , D , I , N , L , B ,G , P , T ,O , C }
Cet Alphabet a N=13 symboles ETAPE 1

Application successive des tapes 2,3 et 4

13

Les algorithmes de codage statistiques

Exemple : Algorithme de Shannon-Fano

Mthode : Algorithme de Huffman

Comme pour le codage de shannon-Fano, les probabilits d'apparition des symboles sont places dans un tableau tri par ordre dcroissant de probabilits. L'algorithme de Huffman est implment suivant une structure d'arbre. Le principe de cet algorithme consiste regrouper les deux symboles de probabilits la plus faible pour en faire un nouveau symbole dont la probabilit est la somme des probabilits de ces deux symboles. On itre cette opration et chaque tape le nombre de symboles diminue. On construit de cette manire un arbre dont les feuilles sont les symboles coder et les embranchements les codages intermdiaires.

Exemple : Algorithme de Huffman

Considrons nouveau l'exemple prcdent : Il s'agit de coder la phrase : "Le codage est indispensable". Le tableau des probabilits d'occurrence est le suivant :

On applique successivement les tapes de l'algorithme selon le principe de l'algorithme prcdemment indiqu.

14

Les algorithmes de codage statistiques

L'arbre de Huffman associ est prsent ci-aprs :

15

IV -

Algorithme de codage arithmtique

Principes de base
On associe chaque symbole coder un intervalle [ a k , b k [ de [0,1[ On itre ce processus jusqu' ce que toute la squence soit traite La squence est alors code par un rel de l'intervalle [0,1[

IV

Contrairement aux deux algorithmes prcdents, le code est associ la squence et non chaque symbole pris individuellement.

Mthode : Algorithme de codage

Cet algorithme comporte 5 tapes successives : 1) On initialise l'intervalle de codage [ac,bc[ avec les valeurs ac=0 et bc=1, cet intervalle a une largeur L=bc-ac=1 2) cet intervalle est partitionn en N sous-intervalles ( N nombre de symboles de l'alphabet de la source) proportionnellement aux probabilits p(s k) de chaque symbole sk. cette partition est constitue de sous-intervalles [ak,bk[ tels que :
k 1 k i=1

bk-ak=p(sk) avec ak=ac+largeur x

i=1

p si et bk=ac+largeur x p s i

3) On choisit le sous-intervalle correspondant au prochain sk coder dans la squence et on met jour les valeurs ac et bc de la manire suivante : ac=ac+largeur x ak et bc=ac+largeur x bk 4) Avec le nouvel intervalle [ac,bc[ on recommence le processus de l'tape 2. 5) Les tapes 2,3 et 4 sont rpts jusqu' puisement des symboles de la squence et obtention du dernier intervalle [ac,bc[ La reprsentation binaire de tout rel xc de l'intervalle [ac,bc[ est un code de la squence.

Exemple : Codage arithmtique d'une source

On considre la source S={a,b,c,d,e} avec les probabilits respectives d'occurrence des symboles suivantes : P(a)=0.3, P(b)=0.25,P(c)=0.20, P(d)=0.15, P(e)=0.1 On souhaite coder la squence bdcea Pour coder cette squence on divise l'intervalle [0,1[ en 5 sous-intervalles, puis on se place sur le sous-intervalle correspondant au premier symbole de la squence coder, il s'agit du symbole "b". Pour le symbole suivant de la squence "d" on subdivise le sous intervalle de b, [0.3,0.55[ en 5 sous-intervalles correspondant au nombre de symboles de l'alphabet de la source S. On procde ainsi rcursivement pour toute la squence ( voir figure ci-dessous). (Cliquez pour afficher)

17

Algorithme de codage arithmtique

Mthode : Algorithme de dcodage

Cet algorithme comporte six tapes successives : 1) On initialise ac=0 et bc=1 2) On calcule la largeur du sous-intervalle du code : largeur = bc-ac 3) On trouve le sous-intervalle [

a k , b k [ du symbole sk avec 1k N tel que :

x a a k c c bk largeur
On rappelle que xc est le rel codant la squence. 4) On obtient le symbole sk 5) On met jour le sous-intervalle de codage : ac=ac+largeur x ak et bc=ac+largeur x bk 6) On rpte les 2,3,4 et 5 jusqu' obtenir le dcodage de tous les symboles de la squence.

Exemple : Dcodage de l'exemple prcdent

On applique l'algorithme de dcodage l'exemple prcdent : On considre la valeur xc=0.51508125 codant la squence Etape 1 : On initialise ac=0 et bc=1 Etape 2 : On calcule la largeur du sous-intervalle du code : largeur = bc-ac =1 Etape 3 : On calcule le nombre

xc ac dont la valeur est 0.51508125 et on cherche k tel largeur

que ce nombre soit compris dans la partition initiale. Etape 4 : k=2, Il s'agit du sous-intervalle [0.3,0.55[ qui correspond au symbole b. Etape 5 :

18

Algorithme de codage arithmtique

On met jour le sous-intervalle de codage ac=ac+largeur x ak et bc=ac+largeur x bk ac=0 + 1x0.3=0.3 bc=0+1 x 0.55=0.55 On rpte l'tape 2 : largeur = 0.55-0.3=0.25 Etape 3 : (0.51508125-0.3)/0.25 = 0,860325 Etape 4 : k=4, il s'agit du sous-intervalle [0.75,0.90[ qui correspond au symbole d. On revient l'tape 5 et ainsi de suite ...

19

Conclusion

Dans le cadre de ce module, nous avons rappel quelques rsultats lis au codage de source et avons prsent quelques algorithmes de codage entropique d'une source notamment le codage de Shannon-Fano, le codage de Huffman et le codage arithmtique. Ces algorithmes ont la particularit d'avoir une longueur moyenne de code qui approche la limite de Shannon qui est l'entropie de la source. Les algorithmes tudis dans ce module implmentent les mthodes d'ordre zro, non adaptatives. Le lecteur intress par la thorie des codes pourrait avantageusement tudier les mthodes d'ordre suprieur, les mthodes adaptatives et les algorithmes base de dictionnaire tel que l'algorithme de Lempel,Ziv et Welsch.

21