Introduction

Lorsque l’on transporte une image ou un son, il faut passer du format analogique (réel) au format numérique (virtuel). Il faut donc un conditionnement et un codage. Puis il faut transporter ces informations par un « tunnel », autrement appelé « canal de transmission ». En partant du signal de base, on passe par plusieurs étapes, représentées par ce petit schéma :

Chaque message envoyé sous la forme d’un signal, peut se représenter par une courbe. Exemple, un message binaire peut être représenté par un signal carré. Ce signal peut être unipolaire ou NRZ, c’est à dire qu’il peut varier respectivement de +0 a +x ou de -x à +x.

Un signal peut être perturbé par des bruits (des parasites) qui peuvent êtres d’origines différentes. Les éléments inductifs sont ceux qui produisent le plus de parasites (moteurs électriques, transformateurs, …). Mais un message non compressé peut prendre beaucoup de place, alors qu’on peut, via plusieurs algorithmes, compresser ce message tout en gardant le même contenu. C’est l’utilité d’un codage de Shannon-Fano et Huffman.

Calcul

Bon commençons maintenant avec un peu de concret :

L’entropie est la quantité d’informations contenues dans un message, et se note de la manière suivante :

Entropie : I=log2(z)

z est ici le code décimal du message, et I l’entropie, notée en sh (Shannon) qui est une unité de mesure d’élément binaire.

Exemple : log2(32) = 5 sh, donc l’entropie de ce message est de 5 éléments binaires.

Un message peut contenir plusieurs symboles, la formule pour déterminer l’entropie dans un message à plusieurs symboles est très simple : I=log2(2^n)

Note: On utilise un log() base 2 car cela est adapté aux signaux binaires.

Si maintenant on veut calculer l’entropie moyenne par symbole dans un message nommée H :

H = I / n =- Σ pi * log2(pi) pour Σ allant de i=1 à b. pi étant la probabilité d’apparition d’un symbole.

Dans le cas ou l’apparition de symboles est équiprobable, pi = 1 / b et I = n*log2(b)

Mesurons maintenant la performance du codage de Shannon-Fano et de Huffman, que nous allons comparer. Il faut partir du principe que l’algorithme de Huffman est meilleur en performance de compression car, il est aussi bon que celui de Shannon-Fano, lorsque ce dernier est à son taux de compression maximum. Autrement dit, dans le meilleur des cas, Shannon-Fano sera aussi efficace que Huffman.

Les performances

Codage de Huffman :

Prenons par exemple, un cas ou les probabilités suivantes sont associées à des éléments :

a1	a2	a3	a4	a5	a6	a7
0.38	0.24	0.1	0.1	0.1	0.05	0.03

On commence par calculer H, la moyenne par symbole :

H =- Σ pi*log2(pi) :

H = -[( 0.38*log2(0.38) ) + ( 0.24*log2(0.24) ) + 3*( 0.1*log2(0.1) ) + ( 0.05*log2(0.05) ) + ( 0.03*log2(0.03) )]

H = 2.39 sh/s (Shannon/ seconde)

Maintenant nous allons passer à la détermination du code de chaque symbole.

Bon, comme ça, on dirait que c’est compliqué, mais ce n’est pas le cas. En fait, on doit additionner les probabilités pour arriver à 1. A chaque fois qu’un branche rejoint l’autre, on lui associe le nombre 1,et quand une branche reste au même niveau, on lui associe le nombre 0.

Ensuite, pour la lecture du code, on part du résultat total de la somme ( notre 1 final ), et on découle jusqu’à arriver vers la probabilité de départ.Exemple : Ici le code du symbole de probabilité a1 sera égal à 00, car il y a deux zéros entre le 1 final et la probabilité a1. Pour a4, ça sera 101, pour a5, 110; etc …

Voici le tableau final trouvé :

Si	Pi	Code	Li
a1	0.38	00	2
a2	0.24	01	2
a3	0.1	100	3
a4	0.1	101	3
a5	0.1	110	3
a6	0.05	1110	4
a7	0.03	1111	4

Petite explication :

• Si est le nom de la probabilité associée au symbole transmis
• Pi la probabilité d’apparition du symbole associée
• Code le code binaire qui représente le symbole
• Li la longueur du code ( le nombre de chiffres du code)

Bon, c’est presque fini, maintenant on arrive au calcul de l’efficacité de compression du message, qui se traduit par :

Ec = H / Σ(Pi*Li)

Dans notre cas, Ec donne donc :

Ec = 2.39 / (0.38*2 + 0.24*2 + 3*(0.1*3) + 0.05*4 + 0.03*4) <=> Ec = 2.39 / 2.46 = 97.6 %

Notre efficacité sera donc de 97.6 %.

Codage de Shannon-Fano :

Le plus dur est fait :p Le codage de Shannon-Fano ressemble énormément à Huffman, la seule différence réside dans le fait qu’on choisi arbitrairement les codes associés aux probabilités des symboles. Pour être plus clair, on va à chaque fois découper en deux parties les plus égales, et attribuer à chaque partie un 0 et un 1. Le schéma ci-dessous représente l’arborescence des codes de chaque probabilité.

 

On choisit arbitrairement deux parties, pour quelles aient à chaque fois la valeur la plus approchante l’une de l’autre, et tant que les parties sont divisibles, on continue ainsi. Dans le tableau, on prend ici a1 et a2, (dont la somme fait 0.62) et tout le reste, (dont la somme fait 0.38). On les sépare en deux, on met le zéro dans la partie du dessus, et les 1 dans la partie du bas. Puis on recommence pour chaque morceau de probabilité, on sépare le groupe du dessus en 2, et celui du dessous entre a3 et a4 pour le chiffre 0, et a5,a6 et a7 pour 1.

Lorsqu’on a séparé tout les groupes, il suffit de tracer des lignes entre chaque probabilité ( de a1 à a7 ici), et de lire en partant de la droite, la ligne correspondante. Pour a7, on lit 1111.

On remarquera qu’ici on retrouve le même résultat qu’avec la méthode de Huffman, mais ceci, parce que nous avons déterminé à chaque fois les deux blocs étant les plus égaux l’un envers l’autre. Si l’évaluation est mauvaise, on trouvera forcément un résultat inférieur à le méthode de Huffman, qui est donc plus performante.

J’espère que cette petite introduction pourra aider certains à comprendre. Je vous invite à me laisser un commentaire, si vous voyez une erreur, ou tout simplement pour des questions, ou autre.