Information discrète
+ Information discrète
Codage de longueur fixe
Le codage consiste à faire correspondre de façon univoque une représentation binaire à chaque symbole d’un ensemble discret d’éléments.
On distingue les codes de longueur fixe, tel ASCII, qui servent à coder des textes, et les codes de longueur variable, tel Huffman, qui servent à compresser les données.
P = 2#exposantn# ! P | nombre d’état pouvant être codés ! n | nombre de bits Nombre de bits pour coder P symboles : n = log#indice2#P Si n représente la quantité d’information Q et si p est la probabilité de réalisation de l’état Q = log#indice2# (1/p) Avec p =0,5 (1 chance/2 => 2 états) : Q = log#indice2#2
* log#indice2# (X) = 3,32 log#indice10# (X) = Exemples | ! Baudot ! ASCII ! EBCDIC ! UNICODE ! Bits | 5 | 7 | 8 | 16
Codage de longueur variable
= Entropie H = ∑#indice-i=1# #exposant—i=n#p#indicei# log#indice2# (1/p#indicei#) ! p#indicei# | probabilité d’apparition du symbole de rang i
= Algorithme d’HUFFMAN Ce codage permet de réduire le nombre d’informations à transmettre. ! 1 | Lecture complète du fichier et création de la table des occurrences ! 2 | Classement des occurrences par ordre décroissant de fréquence d’apparition ! 3 | Sommation des deux occurrences de plus faible fréquence. Encadrement du caractère correspondant éventuel ! 4 | Réordonnancement de la liste des fréquences obtenues par ordre décroissant ! 5 | Réitération des étapes 3 et 4 jusqu’à disparition complète des éléments ! 6 | Construction de l’arbre de Huffman en assignant le symbole 1 aux branches hautes et le symbole 0 aux branches basses ! 7 | Parcours de l’arbre de la racine vers les extrémités pour trouver le codage d’un caractère
Article
| Mise à jour : | 12 mai 2005 |
| Visites : | 601 |
| Auteur : | E. Angenault |
| Site : | Angenault.net |
