Code de huffaman :
Le codage de Huffman est un procédé très utilisé en compression de données.
Il sert à encoder un texte en binaire, en utilisant pour chaque lettre un nombre
de bits dépendant du nombre de fois où la lettre est présente : plus la lettre
apparaît, plus le nombre de bits est petit. Ainsi, le nombre total de bits utilisés
pour encoder le texte est réduit par rapport à un codage ASCII standard qui
utilise huit bits pour chaque lettre.
Le code binaire associé à chaque lettre est défini par un arbre binaire. Les
feuilles de l’arbre correspondent aux lettres de l’alphabet. Les nœuds interne
ne contiennent pas d’information. Le chemin emprunté pour atteindre une
feuille depuis la racine définit le code de la lettre sur cette feuille : à gauche 0,
à droite 1.
Les instructions présentées ci-dessous, vous aident pour accomplir les
opérations de codage et décodage de Huffman :
Symboles = ; %Création des variables “symboles” composée de N éléments.
p = [] ; %les probabilités d’occurrence des symboles.
dict = huffmandict () ; %Création de la variable « dict » qui représente le
dictionnaire de Huffman basé sur les symboles et leurs probabilités
sig = randsrc (, , [ ; ]) ; %Génération du vecteur de symboles aléatoires
comp = huffmanenco( , ) ; % Instruction du Codage de Huffman
dsig = huffmandeco( , ) ; %Instruction du Décodage de Huffman
isequal( , ) ; % pour la vérification que les données décodées correspondent
aux données originales
binarySig = de2bi( ) ; %Convertissions du message originale en format binaire
seqLen = numel(binarySig) ; %détermination de la longueur d'un message
objectif
- Effectuer le codage et le décodage d'une chaine de symboles
numériques en utilisant l'algorithme de Huffman.
- Exploiter quelques fonctions de Matlab
Travail demandé :
Exercice 1 :
Soit une source d’information 𝑆1, qui fournit un vecteur aléatoire de
longueur N (N=100). L’alphabet de la source est muni dans l’intervalle [1 : 6].
Les probabilités d'occurrence correspondantes à chaque symbole sont données
par le vecteur p = [.5 .125 .125 .125 .0625 .0625].
1/ Codage et decodage de source d’information S1 :
Etape 1 : Créez des symboles et probabilité a chaque symbole
X= 1 :6 ;
P=[ .5 .125 .125 .125 .0625 .0625]
Etape 2 : Générer un vecteur de symboles aléatoires et Créez un
dictionnaire Huffman basé sur les symboles et leurs probabilités.
Sg = randsrc(100,1,[x ;p]) ;
Dict = huffmandict(x,p) ;
Resulta:
Sg = { 4 2 5 3 2 4 5 6 1 4 2 6 . . . . }
Dict=
1 [0]
2 [1, 0, 0]
3 [1 ,1 ,1]
4 [1 ,1, 0]
5 [1 ,0 ,1, 1]
6 [1,0 ,1 ,0 ]
Etape 3: Encodez les symboles aléatoires :
Comp= huffmanenco(sg,dict) ;
Resulta :
Comp = {1 1 0 1 0 0 1 0 1 1 1 1 . . .} code de huffman du S1
Etape 4 : Décodez les données
Dsig = huffmandeco(comp,dict) ;
Resulta :
Dsig= {4 2 5 3 2 4 5 6 1 . . . } S1
2/ Vérifiez que le message décodé correspondant bien au message d'origine :
G= isequal(dsig,sig) ;
Resulta :
G= 1
Remarque :
G=1 le message décodé correspondant bien au message d'origine
G= 0 le message décodé correspondant si pas bien au message d'origine
Exercice 2 :
Soit les lignes d’instructions suivantes :
sig = repmat(['A','B','C','D','E','F'],1,1); % le message délivré par la source
symbols = cellstr(char('A','B','C','D','E','F')); % symboles de données distincts
apparaissant dans sig.
p = [0.23 0.09 0.30 0.19 0.14 0.05] ;% probabilités d’occurrence pour chaque
symbole.
1/ Codé le message FCAFCAFCAFCA :
Créez des symboles , probabilité a chaque symbole et généré le message de
source :
Sym=cellstr(char( 'A', 'B', 'C', 'D', 'E', 'F' )) ;
P=[0.23 0.09 0.30 0.19 0.14 0.05 ]
Sig= rempmat (['F', 'C', 'A'],1,4);
Resulta=
sig= FCAFCAFCAFCA
Créez un dictionnaire Huffman et Encodez le message :
dict=huffmandict(sym,p) ;
cop=huffmanenco(sig,dict) ;
resulta:
Décodé le message ‘’ 1001100111 ‘’, et donner le message d'origine :
Le meme programme avout plus :
Y=[1 ,0 ,0 ,1 ,1 ,0 ,0 ,1 ,1 ,1] ;
Dsig=huffmandeco(y,dict) ;
Resulta :
Le message d’origine est :
Exercice 3 :
Considérons une source discrète sans mémoire qui produit des symboles avec
la loi de probabilité p= {0.4 0.15 0.1 0.05 0.2 0.05 0.05} sur l’alphabet {a, f, o,
r, u, x, s}
Trouve le code de huffman :
a 1
u 000
f 010
o 0010
r 0011
x 0110
s 0111
aforuxs :: 10100010001100001100111
1
0.6
0.35
Codé le message ‘aforuxs’ :
Sym=cellstr(char('a','f','o','r','u','x','s')) ;
P=[0.4 0.15 0.1 0.05 0.2 0.05 0.05 ] ;
Sig=repmat(['a','f','o','r','u','x','s'] ,1,1);
Dict =huffmandict(sym,p);
Comp= huffmanenco(sig,dict);