UNIVERSITÉ DE BADJI MOKHTAR ANNABA
TP n°2
CODAGE HUFFMAN
BENZEDIRA YASMINE
L’année universitaire
2023/2024
Objectif du TP :
- Cordage et décodage d'une chaine de symboles numériques en utilisant l'algorithme de Huffman.
- Comprendre et utiliser quelques fonctions Matlab pour le codage Huffman : huffmandict, huffmanenco
et huffmandeco
Manipulation 1 :
>> Symbols={'C','A','B','F','G','E','D','H'}; %Définition des symboles à coder
>> p=[0.3 0.2 0.18 0.1 0.07 0.06 0.05 0.04]; %Définition des probabilités associées à chaque symbole
>> msg={'F','A','C','H','E','G','A','D'}; %Définition du msg à encoder
>> dict=huffmandict(Symbols,p); %Création du dictionnaire de codage de Huffman
>> msg_encoded=huffmanenco(msg,dict)
msg_encoded =
Columns 1 through 22
1 1 0 1 0 0 1 1 1 1 1 0 0 1 1 0 0 1 0 1 0 1
>> [dict,avglen]=huffmandict(Symbols,p) %Création du dictionnaire de codage de Huffman
avec calcul de la longueur moyenne de codage
dict =
'C' [1x2 double]
'A' [1x2 double]
'B' [1x3 double]
'F' [1x3 double]
'G' [1x4 double]
'E' [1x4 double]
'D' [1x4 double]
'H' [1x4 double]
avglen =
comp =
2.7200
Columns 1 through 22
1 1 0 1 0 0 1 1 1 1 1 0 0 1 1 0 0 1 0 1 0 1
1. Calcul de l’entropie H :
% Définir l’alphabet et les probabilités
Alphabet = {‘C’, ‘A’, ‘B’, ‘F’, ‘G’, ‘E’, ‘D’, ‘H’} ;
P = [0.3 0.2 0.18 0.1 0.07 0.06 0.05 0.04] ;
% Calculer l’entropie
For i = 1 :length(p)
H = –∑(p(i) * log2(p(i))) ;
End
% Afficher l’entropie
Résultat : H = 2.67 bits/symbole
Construction du dictionnaire de Huffman :
Dict=huffmandict(Symbols,p) ; %Création du dictionnaire de codage de Huffman
[dict,avglen]=huffmandict(Symbols,p) %Création du dictionnaire de codage de
Huffman avec calcul de la longueur moyenne de codage
Dict =
‘C’ [1x2 double]
‘A’ [1x2 double]
‘B’ [1x3 double]
‘F’ [1x3 double]
‘G’ [1x4 double]
‘E’ [1x4 double]
‘D’ [1x4 double]
‘H’ [1x4 double]
Dictionnaire de Huffman :
C : 01
A : 10
B : 000
F : 110
G : 0010
E : 0011
D : 1110
H : 1111
L’arbre de Huffman:
4-Calcul de la longueur moyenne de code L :
% Calculer la longueur moyenne de code
L=0;
For i = 1 :length(alphabet)
L = L + p(i) * length(codes{i}) ;
End
% Afficher la longueur moyenne de code :
Résultat :. L = 2.72bits/symbole
5- Comparaison de deux codes (analytique et avec Matlab):
>> Les codes obtenues analytiquement et avec Matlab sont identiques
Manipulation2 :
>> Symbols={'C','A','B','F','G','E','D','H'}; %Définition des symboles à coder
>> p=[0.3 0.2 0.18 0.1 0.07 0.06 0.05 0.04]; %Définition des probabilités associées à chaque
symbole
>> msg={'F','A','C','H','E','G','A','D'}; %Définition du msg à encoder
>> dict=huffmandict(Symbols,p); %Création du dictionnaire de codage de Huffman
>> msg_encoded=huffmanenco(msg,dict)
msg_encoded =
Columns 1 through 22
1 1 0 1 0 0 1 1 1 1 1 0 0 1 1 0 0 1 0 1 0 1
Columns 23 through 25
1 1 0
>> comp=huffmanenco(msg,dict) %Compression du msg
comp =
Columns 1 through 22
1 1 0 1 0 0 1 1 1 1 1 0 0 1 1 0 0 1 0 1 0 1
Columns 23 through 25
1 1 0
>> deco=huffmandeco(comp,dict)
comp = %Décompression du msg
deco =
Columns
'F' 'A'1 through
'C' 'H'22 'E' 'G' 'A' 'D'
1 1 0 1 0 0 1 1 1 1 1 0 0 1 1 0 0 1 0 1 0 1
Columns 23 through 25
1 1 0
>> deco=huffmandeco(comp,dict)
[Link] du message :
% Définir le message
Msg = « FACHEGAD » ;
% Encoder le message avec le dictionnaire de Huffman
Dict = huffmandict (alphabet, p) ; [Dict,avglen]=huffmandict(alphabet,p)
% Afficher le code de Huffman :
Résultats :
Code de Huffman : 1101001011000001110100011000100
[dict,avglen]=huffmandict(alphabet,p)
Dict =
‘C’ [1x2 double]
‘A’ [1x2 double]
‘B’ [1x3 double]
‘F’ [1x3 double]
‘G’ [1x4 double]
‘E’ [1x4 double]
‘D’ [1x4 double]
‘H’ [1x4 double]
Avglen =
2.7200
2. Décodage du message :
% Décoder le message avec le dictionnaire de Huffman
Message_decode = huffmandict(Dict, alphabet, p) ;
% Afficher le message décodé :
Résultat :. Message décodé : FACHEGAD
[Link] des tailles :
% Taille du message initial
Taille_originale = length(msg) * 8 ;
Taille_originale= 64
% Taille du code de Huffman
Taille_huffman = length(code_huffman) ;
Taille_huffman= 25
[Link] :
Le code de Huffman permet de compresser le message de manière significative.
La taille du message compressé est de 25 bits, ce qui représente une réduction de
60.9375 % par rapport à la taille originale de 64 bits.
[Link] du taux de compression:
Taux_compression = (1 – (taille_huffman / taille_originale)) * 100 ;
% Afficher le taux de compression :
Résultat : Taux de compression : 60.9375 %
•Le taux de compression obtenu est élevé car le message contient plusieurs
répétitions de caractères. Le codage de Huffman est particulièrement efficace
pour compresser des messages avec des répétitions.
Programme de manipulation 2:
>> Symbols={'C','A','B','F','G','E','D','H'};
>> p=[0.3 0.2 0.18 0.1 0.07 0.06 0.05 0.04];
>> msg={'F','A','C','H','E','G','A','D'}; %Définition du msg à encoder
>> dict=huffmandict(Symbols,p);
>> [dict,avglen]=huffmandict(Symbols,p)
dict =
'C' [1x2 double]
'A' [1x2 double]
'B' [1x3 double]
'F' [1x3 double]
'G' [1x4 double]
'E' [1x4 double]
'D' [1x4 double]
'H' [1x4 double]
avglen =
2.7200
>> msg_encoded=huffmanenco(msg,dict)
msg_encoded =
Columns 1 through 22
1 1 0 1 0 0 1 1 1 1 1 0 0 1 1 0 0 1 0 1 0 1
Columns 23 through 25
1 1 0
>> comp=huffmanenco(msg,dict) %Compression du msg
comp =
Columns 1 through 22
1 1 0 1 0 0 1 1 1 1 1 0 0 1 1 0 0 1 0 1 0 1
Columns 23 through 25
1 1 0
>> deco=huffmandeco(comp,dict) %Décompression du msg
deco =
'F' 'A' 'C' 'H' 'E' 'G' 'A' 'D'
>> taille_originale = length(msg)*8
taille_originale =
64
>> taille_huffman= length(msg_encoded)
taille_huffman =
25
>> Taux_de_compression=(1-(taille_huffman/taille_originale))*100
Taux_de_compression = 60.9375 %
