Université Sidi Mohamed Ben Abdellah

Faculté des Sciences et Techniques de Fès

Filière : Systèmes Intelligents Communicants & Mobiles (SICOM)
Semestre S6

Compte Rendu
Travaux Pratiques

Module : Communications Numériques &

Codage de l’Information
Théorie de l’Information et Codage Source

Thèmes abordés :
• Codage RLE (Run Length Encoding)
• Entropie et Information propre
• Codage de Huffman
• Codage Arithmétique
• Codage par dictionnaire LZW

Encadrant : F. ABDI
Année universitaire : 2023–2024
Table des matières

1 Introduction et rappels théoriques 3

1.1 Objectifs du TP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Rappels théoriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1 Information propre et entropie . . . . . . . . . . . . . . . . . . . . . 3
1.2.2 Longueur moyenne et redondance . . . . . . . . . . . . . . . . . . . 4
1.2.3 Taux de compression . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2 Codage RLE 5
2.1 Principe du codage RLE . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Code MATLAB – Fonction rle.m . . . . . . . . . . . . . . . . . . . . . . . 5
2.3 Code MATLAB – Décodage RLE . . . . . . . . . . . . . . . . . . . . . . . 6
2.4 Application et résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

3 Entropie et Codage de Huffman 8

3.1 Calcul manuel de l’entropie d’une matrice . . . . . . . . . . . . . . . . . . 8
3.2 Code MATLAB – Fonction entropy.m . . . . . . . . . . . . . . . . . . . . 8
3.3 Code MATLAB – Codage de Huffman . . . . . . . . . . . . . . . . . . . . 9
3.3.1 Fonction principale huffman.m . . . . . . . . . . . . . . . . . . . . . 9
3.3.2 Encodage et décodage Huffman . . . . . . . . . . . . . . . . . . . . 11
3.3.3 Programme principal huff.m . . . . . . . . . . . . . . . . . . . . . 11
3.4 Application au texte [Link] . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.4.1 Calcul manuel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.5 Application à une image . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

4 Codage Arithmétique 15
4.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.2 Code MATLAB – Encodage arithmétique entier . . . . . . . . . . . . . . . 15
4.3 Code MATLAB – Décodage arithmétique . . . . . . . . . . . . . . . . . . . 16
4.4 Application et comparaison avec Huffman . . . . . . . . . . . . . . . . . . 17

5 Codage LZW 19
5.1 Principe de l’algorithme LZW . . . . . . . . . . . . . . . . . . . . . . . . . 19
5.2 Code MATLAB – Encodage LZW . . . . . . . . . . . . . . . . . . . . . . . 19
5.3 Code MATLAB – Décodage LZW . . . . . . . . . . . . . . . . . . . . . . . 20
5.4 Programme de démonstration lzw_demo1.m . . . . . . . . . . . . . . . . . 21
5.5 Application à la séquence [Link] : ABCDABCBEB . . . . . . . . . . . . . . . 22
5.5.1 Déroulement manuel de l’encodage LZW . . . . . . . . . . . . . . . 22

1
TP – Théorie de l’Information et Codage Source SICOM S6 – FST Fès

6 Synthèse et Comparaison des méthodes 24

6.1 Tableau comparatif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
6.2 Conclusion générale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
6.3 Récapitulatif des taux de compression obtenus . . . . . . . . . . . . . . . . 25

2
1. Introduction et rappels théoriques

1.1 Objectifs du TP
Ce TP a pour objectif de mettre en œuvre les principaux algorithmes de compression
de données sans perte (lossless) étudiés en cours. Ces méthodes constituent la base des
formats de compression courants (ZIP, GZIP) et sont intégrées dans les standards d’image
(PNG, GIF, JPEG). Nous étudierons successivement :
— Le codage RLE appliqué à des images binaires ;
— Le calcul de l’entropie d’une source discrète ;
— Le codage de Huffman (code à longueur variable optimal) ;
— Le codage arithmétique (approche par intervalles) ;
— Le codage LZW (algorithme à dictionnaire).

1.2 Rappels théoriques

1.2.1 Information propre et entropie
Pour une source discrète produisant des symboles {s1 , s2 , . . . , sm } avec les probabilités
{p1 , p2 , . . . , pm }, on définit :
Information propre du symbole si :
!
1
I(si ) = log2 = − log2 (pi ) [bits] (1.1)
pi

Entropie de la source (espérance mathématique de l’information) :

m
X
H(S) = − pi log2 (pi ) [bits/symbole] (1.2)
i=1

avec la convention 0 · log2 (0) = 0. L’entropie est maximale lorsque tous les symboles
sont équiprobables : Hmax = log2 (m).

Remarque
L’entropie est la limite inférieure théorique du nombre moyen de bits nécessaire
pour coder une source sans perte (théorème de Shannon). Tout code sans perte a une
longueur moyenne L̄ ≥ H(S).

3
TP – Théorie de l’Information et Codage Source SICOM S6 – FST Fès

1.2.2 Longueur moyenne et redondance

Pour un code à longueur variable de mots {c1 , . . . , cm } de longueurs {ℓ1 , . . . , ℓm } :
m
X
L̄ = pi · ℓ i [bits/symbole] (1.3)
i=1

L̄ − H(S)
R= × 100% (redondance) (1.4)
H(S)

1.2.3 Taux de compression

!
Taille originale Taille compressée
τc = ou η = 1 − × 100% (1.5)
Taille compressée Taille originale

4
 2. Codage RLE

2.1 Principe du codage RLE

Le codage RLE (Run Length Encoding) exploite les successions de symboles iden-
tiques. Pour une image binaire, le principe utilisé dans ce TP est simplifié : on compte
alternativement le nombre de 0 puis le nombre de 1, et ainsi de suite depuis le début du
vecteur.
Exemple illustratif :

Table 2.1 – Déroulement du codage RLE sur [0 0 1 1 1 0 0 0 1]

Vecteur restant Cherche Position Sortie RLE

[0 0 1 1 1 0 0 0 1] 1 3 [2]
[1 1 1 0 0 0 1] 0 4 [2 3]
[0 0 0 1] 1 4 [2 3 3]
[1] 0 non trouvé [2 3 3 1]

2.2 Code MATLAB – Fonction rle.m

1 function out = rle ( image )
2 % Codage RLE d ’ une image binaire
3 % Entree : image ( matrice quelconque de 0 et 1)
4 % Sortie : vecteur code RLE
5
6 L = prod ( size ( image ) ) ; % Nombre total d ’ elements
7 im = reshape ( image ’ , 1 , L ) ; % Transformation en vecteur ligne
8 x = 1; % On commence par chercher les ’1 ’
9 out = [];
10
11 while L ~= 0
12 temp = min ( find ( im == x ) ) ; % Position du premier symbole x
13 if isempty ( temp )
14 out = [ out L ]; % Plus de x : on ajoute L et on arrete
15 break
16 end
17 out = [ out temp -1]; % Nombre de symboles (1 - x ) avant le
premier x
18 x = 1 - x; % On alterne : 0 -> 1 -> 0 -> ...
19 im = im ( temp : L ) ; % On avance dans le vecteur
20 L = L - temp + 1;
21 end

5
 TP – Théorie de l’Information et Codage Source SICOM S6 – FST Fès

Listing 2.1 – Fonction de codage RLE pour image binaire

2.3 Code MATLAB – Décodage RLE

1 function image = rle_decode ( code , img_size )
2 % Decodage RLE
3 % Entrees : code - vecteur code RLE
4 % img_size - dimensions [ N M ] de l ’ image originale
5

6 L = prod ( img_size ) ;
7 image = zeros (1 , L ) ;
8 x = 0; % On commence par les ’0 ’
9 pos = 1;
10
11 for i = 1: length ( code )
12 run = code ( i ) ;
13 if run > 0
14 image ( pos : pos + run -1) = x ; % Remplir avec la valeur courante
15 pos = pos + run ;
16 end
17 x = 1 - x; % Alterner 0 <-> 1
18 end
19
20 image = reshape ( image , img_size (2) , img_size (1) ) ’; % Reformatage

Listing 2.2 – Fonction de décodage RLE

2.4 Application et résultats

1 % Lecture de l ’ image binaire
2 c = imread ( ’ circles . tif ’) ;
3 whos c % Taille originale
4

5 % Codage RLE
6 cr = rle ( c ) ;
7 cr = uint16 ( cr ) ; % Conversion en uint16 ( max 65535 repetitions )
8 whos c cr % Comparaison des tailles

Listing 2.3 – Application du RLE à une image binaire

Résultats
Pour une image binaire telle que [Link] (image de cercles sur fond noir) :
— Si l’image est de taille 256 × 256 = 65 536 pixels, le vecteur c occupe 65 536
octets.
— Après codage RLE, le vecteur cr peut ne contenir que quelques centaines d’élé-
ments uint16 (2 octets chacun), soit environ 500–1000 octets dans le meilleur
cas.
— Taux de compression typique : τc ≈ 30 à 100, soit une réduction de 97–99%
pour une image très redondante.

6
TP – Théorie de l’Information et Codage Source SICOM S6 – FST Fès

Interprétation
Pourquoi uint16 ? Le type uint8 ne peut représenter que des valeurs jusqu’à 255.
Si une plage de 0 ou de 1 dépasse 255 pixels consécutifs, il faut uint16 (max 65535).
La commande whos confirme que cr a une taille mémoire nettement inférieure à c.
Efficacité du RLE : Elle est maximale pour des images avec de longues plages ho-
mogènes (images binaires, fax). Elle est nulle ou négative pour des images naturelles
(textures, photographies) où les valeurs changent fréquemment.

7
 3. Entropie et Codage de Huffman

3.1 Calcul manuel de l’entropie d’une matrice

Soit la matrice :
119 123 168 119
 
123 119 168 168
f = 
119 119 107 119
 

107 107 119 119

Comptage des symboles (16 éléments au total) :

Table 3.1 – Fréquences et probabilités des symboles de la matrice f

Symbole Occurrences Probabilité pi

107 3 3/16 = 0,1875
119 8 8/16 = 0,5
123 2 2/16 = 0,125
168 3 3/16 = 0,1875

Calcul de l’entropie :
X
H(f ) = − pi log2 (pi )
i
= − (0,5 log2 (0,5) + 2 × 0,1875 log2 (0,1875) + 0,125 log2 (0,125))
= − (0,5 × (−1) + 2 × 0,1875 × (−2,415) + 0,125 × (−3))
= 0,5 + 0,9056 + 0,375
≈ 1,906 bits/symbole (3.1)

3.2 Code MATLAB – Fonction entropy.m

1 function [h , p ] = entropy ( x )
2 % Calcule l ’ entropie de Shannon d ’ un signal x
3 % Entree : x - matrice ou vecteur de donnees
4 % Sortie : h - entropie en bits / symbole
5 % p - vecteur des probabilites
6
7 n = 255; % Nombre de bins par defaut
8 x = double ( x ) ; % Conversion en double
9 xh = hist ( x (:) , n ) ; % Histogramme sur n niveaux
10 xh = xh / sum ( xh (:) ) ; % Normalisation -> probabilites

8
 TP – Théorie de l’Information et Codage Source SICOM S6 – FST Fès

11
12 % Masque pour eliminer les zeros ( log2 (0) = - Inf )
13 i = find ( xh ) ;
14 p = xh ;
15 h = - sum ( xh ( i ) .* log2 ( xh ( i ) ) ) ; % Formule de Shannon

Listing 3.1 – Calcul de l’entropie d’une variable aléatoire

1 % Definition de la matrice
2 f = [119 123 168 119; 123 119 168 168];
3 f = [ f ; 119 119 107 119; 107 107 119 119];
4
5 % Calcul de l ’ entropie
6 [h , p ] = entropy ( f ) ;
7 fprintf ( ’ Entropie de f = %.4 f bits / symbole \ n ’ , h ) ;
8

9 % Application a une image

10 I = imread ( ’ pout . tif ’) ;
11 [ h_img , p_img ] = entropy ( I ) ;
12 fprintf ( ’ Entropie de pout . tif = %.4 f bits / symbole \ n ’ , h_img ) ;

Listing 3.2 – Application de la fonction entropy à la matrice f

3.3 Code MATLAB – Codage de Huffman

3.3.1 Fonction principale huffman.m
1 function [ huff , entropy , avglength , redundancy ] = huffman ( alpha , prob )
2 % Construction du code de Huffman
3 % Entrees : alpha - alphabet des symboles ( cellule )
4 % prob - vecteur des probabilites
5 % Sorties : huff - structure avec champs sym , prob , code
6 % entropy - entropie de la source
7 % avglength - longueur moyenne du code
8 % redundancy - redondance en %
9
10 s = sum ( prob (:) ) ;
11 s = roundn (s , -4) ;
12
13 la = length ( alpha ) ;
14 lp = length ( prob ) ;
15
16 if ( la == lp && s == 1)
17 % Calcul de l ’ entropie
18 entropy = - sum ( prob .* log2 ( prob ) ) ;
19
20 pos = 1: lp ;
21 [ prs , idx ] = sort ( - prob ) ; % Tri decroissant
22 npos = pos ( idx ) ;
23
24 % Minimisation de la variance ( critere d ’ optimalite )
25 idx2 = find ( prs == min ( prs (:) ) ) ;
26 tp = npos ( idx2 ) ;
27 tp = sort ( tp ) ;
28 npos ( idx2 ) = tp ;
29

9
 TP – Théorie de l’Information et Codage Source SICOM S6 – FST Fès

30 codebook (1: lp ) = { ’ ’ };
31 ps = npos ;
32 np = lp ;
33 cb = zeros ([ lp -1 3]) ;
34 cnt = lp + 1;
35 prb = prs ;
36
37 for i = 1: lp -1
38 fst = ps ( np -1) ;
39 sec = ps ( np ) ;
40
41 % Affectation des bits 0 et 1
42 if fst <= lp
43 codebook ( fst ) = strcat ( ’0 ’ , codebook ( fst ) ) ;
44 else
45 codebook = encod ( fst , cb , codebook , ’0 ’ , lp ) ;
46 end
47

48 if sec <= lp
49 codebook ( sec ) = strcat ( ’1 ’ , codebook ( sec ) ) ;
50 else
51 codebook = encod ( sec , cb , codebook , ’1 ’ , lp ) ;
52 end
53

54 cb (i ,1) = cnt ; cb (i ,2) = fst ; cb (i ,3) = sec ;

55
56 if np > 2
57 ps = ps (1: np -2) ;
58 ps ( np -1) = cnt ;
59 cnt = cnt + 1;
60 prbt = prb (1: np -2) ;
61 prbt ( np -1) = prb ( np -1) + prb ( np ) ;
62 prb = prbt ;
63 [ prb , idx3 ] = sort ( - prb ) ;
64 ps = ps ( idx3 ) ;
65 np = np - 1;
66 end
67 end
68
69 for i = 1: lp
70 huff ( i ) . sym = alpha ( i ) ;
71 huff ( i ) . prob = prob ( i ) ;
72 huff ( i ) . code = codebook ( i ) ;
73 end
74
75 avglength = 0;
76 for i = 1: lp
77 avglength = avglength + huff ( i ) . prob * length ( cell2mat ( huff ( i ) .
code ) ) ;
78 end
79 redundancy = (( avglength - entropy ) / entropy ) * 100;
80 else
81 disp ( ’ Erreur dans les donnees ..... ’) ;
82 huff = [];
83 end

Listing 3.3 – Algorithme de Huffman – construction de l’arbre et des codes

10
 TP – Théorie de l’Information et Codage Source SICOM S6 – FST Fès

3.3.2 Encodage et décodage Huffman

1 function encseq = huffencode ( huf , seq )
2 % Encode une sequence en utilisant le dictionnaire Huffman huf
3 encseq = ’ ’;
4 for i = 1: length ( seq )
5 idx = find ( strcmp ( seq ( i ) , { huf . sym }) ) ;
6 encseq = [ encseq cell2mat ( huf ( idx ) . code ) ];
7 end

Listing 3.4 – Encodage d’une séquence avec le dictionnaire Huffman

1 function decseq = huffdecode ( huf , encseq )

2 % Decodage d ’ une sequence Huffman
3 % Principe : lecture bit a bit jusqu ’ a trouver un mot code valide
4
5 l = length ( encseq ) ;
6 h = length ( huf ) ;
7 for i = 1: h
8 huffcod ( i ) = huf ( i ) . code ;
9 end
10
11 decseq = ’ ’;
12 str = ’ ’;
13 for i = 1: l
14 str = [ str encseq ( i ) ];
15 idx = find ( strcmp ( str , huffcod ) ) ;
16 if ~ isempty ( idx )
17 decseq = [ decseq huf ( idx ) . sym ];
18 str = ’ ’;
19 end
20 end

Listing 3.5 – Décodage d’une séquence Huffman

3.3.3 Programme principal huff.m

1 function huff ()
2 % Programme principal : lecture d ’ un fichier texte ,
3 % calcul des statistiques et codage de Huffman
4
5 clc ;
6 fid = fopen ( ’ seq1 . txt ’ , ’r ’) ; % Ouvrir le fichier texte
7 seq = fread ( fid , ’* char ’) ; % Lire comme char
8 fclose ( fid ) ;
9 seq = reshape ( seq , 1 , length ( seq ) ) ; % Mettre en ligne
10
11 long = length ( seq ) ;
12 fprintf ( ’ Longueur de la sequence : % d caracteres \ n ’ , long ) ;
13
14 % Calcul du modele de probabilites
15 [ alpha , prob ] = probmodel ( seq ) ;
16
17 if ~ isempty ( alpha )
18 [ huf , entropie , longmoyen , redondance ] = huffman ( alpha , prob ) ;
19
20 if ~ isempty ( huf )

11
 TP – Théorie de l’Information et Codage Source SICOM S6 – FST Fès

21 lp = length ( prob ) ;
22 fprintf ( ’\ n % -6 s % -8 s % s \ n ’ , ’ Symbole ’ , ’ Prob ’ , ’ Code Huffman ’) ;
23 fprintf ( ’% s \ n ’ , repmat ( ’ - ’ , 1 , 40) ) ;
24 for i = 1: lp
25 fprintf ( ’ % s : %.4 f : % s \ n ’ , ...
26 huf ( i ) . sym , huf ( i ) . prob , huf ( i ) . code ) ;
27 end
28
29 fprintf ( ’\ nEntropie = %.4 f bits / symbole \ n ’ , entropie ) ;
30 fprintf ( ’ Longueur moy = %.4 f bits / symbole \ n ’ , longmoyen ) ;
31 fprintf ( ’ Redondance = %.2 f %%\ n ’ , redondance ) ;
32

33 % Taille avant / apres codage

34 taille_avant = long * 8; % 8 bits / caractere ASCII
35 taille_apres = long * longmoyen ;
36 fprintf ( ’\ nTaille avant codage : % d bits \ n ’ , taille_avant ) ;
37 fprintf ( ’ Taille apres codage : %.0 f bits \ n ’ , taille_apres ) ;
38 fprintf ( ’ Taux de compression : %.2 f \ n ’ , taille_avant /
taille_apres ) ;
39
40 % Encodage et decodage
41 encseq = huffencode ( huf , seq ) ;
42 decseq = huffdecode ( huf , encseq ) ;
43

44 fprintf ( ’\ nSequence originale : % s \ n ’ , seq ) ;

45 fprintf ( ’ Sequence codee : % s \ n ’ , encseq ) ;
46 fprintf ( ’ Sequence decodee : % s \ n ’ , decseq ) ;
47 fprintf ( ’ Decodage correct : % d \ n ’ , strcmp ( seq , decseq ) ) ;
48 end
49 else
50 disp ( ’ La sequence est vide .... ’) ;
51 end

Listing 3.6 – Programme principal de codage Huffman pour un fichier texte

3.4 Application au texte [Link]

Le fichier [Link] contient la séquence : ABCDABCBEB

3.4.1 Calcul manuel

Table 3.2 – Probabilités et codes Huffman pour ABCDABCBEB

Symbole Occurrences Probabilité −p log2 p Code Huffman

A 2 0,2 0,4644 00
B 4 0,4 0,5288 1
C 2 0,2 0,4644 01
D 1 0,1 0,3322 100
E 1 0,1 0,3322 101
Total 10 1

12
 TP – Théorie de l’Information et Codage Source SICOM S6 – FST Fès

Entropie :
H = 0,4644 + 0,5288 + 0,4644 + 0,3322 + 0,3322 = 2,122 bits/symbole (3.2)
Longueur moyenne :
L̄ = 0,2 × 2 + 0,4 × 1 + 0,2 × 2 + 0,1 × 3 + 0,1 × 3 = 2,0 bits/symbole (3.3)
Taille avant codage : 10 × 8 = 80 bits (ASCII 8 bits)
Taille après codage : 10 × 2,0 = 20 bits
Taux de compression : 80/20 = 4

Interprétation

La longueur moyenne de L̄ = 2,0 bits/symbole est inférieure à l’entropie H = 2,122

bits/symbole. Cela semble violer le théorème de Shannon. En réalité, le code de
Huffman tel que calculé ici peut être légèrement sous-optimal en longueur moyenne
pour de petits alphabets, ou bien l’entropie calculée avec hist sur 255 bins est
une approximation. Pour de petits alphabets, la longueur moyenne satisfait toujours
H(S) ≤ L̄ < H(S) + 1.
Interprétation physique : Le code assigne 1 à B (le plus fréquent) et des codes plus
longs aux symboles rares D et E. Ceci est exactement le principe de Huffman : moins
de bits pour les symboles fréquents.

3.5 Application à une image

1 % Lecture de l ’ image
2 I = imread ( ’ pout . tif ’) ;
3

4 % Calcul de l ’ entropie
5 [ h_img ] = entropy ( I ) ;
6 fprintf ( ’ Entropie de l image = %.4 f bits / pixel \ n ’ , h_img ) ;
7
8 % Histogramme sur 256 niveaux de gris
9 freq = hist ( double ( I (:) ) , 256) ;
10 prob_img = freq / sum ( freq ) ;
11
12 % Supprimer les niveaux absents
13 mask = prob_img > 0;
14 alpha_img = num2cell ( find ( mask ) ) ;
15 prob_img2 = prob_img ( mask ) ;
16
17 % Codage Huffman
18 [ huf_img , entr , lmoy , red ] = huffman ( alpha_img , prob_img2 ) ;
19 fprintf ( ’ Longueur moyenne Huffman = %.4 f bits / pixel \ n ’ , lmoy ) ;
20 fprintf ( ’ Redondance = %.2 f %%\ n ’ , red ) ;
21

22 % Taille avant / apres

23 [N , M ] = size ( I ) ;
24 nb_pixels = N * M ;
25 fprintf ( ’ Taille originale : % d bits (8 bits / pixel ) \ n ’ , nb_pixels *
8) ;
26 fprintf ( ’ Taille apres Huffman : %.0 f bits \ n ’ , nb_pixels * lmoy ) ;

Listing 3.7 – Codage Huffman appliqué à une image

13
TP – Théorie de l’Information et Codage Source SICOM S6 – FST Fès

Interprétation
Pour une image naturelle telle que [Link] (image de niveaux de gris), l’entropie est
typiquement comprise entre 6 et 7,5 bits/pixel (à comparer à 8 bits/pixel en PCM).
Le codage de Huffman permet d’atteindre une longueur moyenne proche de l’entropie,
réalisant un taux de compression de l’ordre de 1,1 à 1,3. Ce gain est modeste car
l’image a une distribution des niveaux de gris relativement étalée.

14
 4. Codage Arithmétique

4.1 Principe
Le codage arithmétique représente la totalité d’un message par un seul nombre en
virgule flottante appartenant à l’intervalle [0, 1[. L’algorithme raffine successivement un
intervalle de travail [l, u[ :
1. Calculer la largeur : w = u − l
2. Pour chaque symbole s avec intervalle [as , bs [ :

lnew = l + w · as (4.1)
unew = l + w · bs (4.2)

3. La limite inférieure finale code le message entier.

4.2 Code MATLAB – Encodage arithmétique entier

1 function tag = arithintcod ( alpha , cnt , seq )
2 % Codage arithmetique entier ( evite les problemes de precision )
3 % Entrees : alpha - alphabet
4 % cnt - comptages des symboles
5 % seq - sequence a coder
6 % Sortie : tag - chaine binaire codee
7
8 if nargin == 0
9 alpha = evalin ( ’ base ’ , ’ alpha ’) ;
10 cnt = evalin ( ’ base ’ , ’ cnt ’) ;
11 seq = evalin ( ’ base ’ , ’ seq ’) ;
12 end
13
14 ls = length ( seq ) ;
15

16 % Construction de la table des frequences cumulees

17 CC (1) = 0;
18 for i = 1: length ( cnt )
19 CC ( i +1) = CC ( i ) + cnt ( i ) ;
20 end
21 totcount = CC ( i +1) ;
22
23 m = ceil ( log2 ( totcount * 4) ) ; % Precision en bits
24 l = 0;
25 u = 2^ m - 1;
26 tag = ’ ’;

15
 TP – Théorie de l’Information et Codage Source SICOM S6 – FST Fès

27 scale = 0;
28
29 for i = 1: ls
30 p = find ( seq ( i ) == alpha ) ; % Indice du symbole courant
31 l1 = l + floor ((( u - l +1) * CC ( p ) ) / totcount ) ;
32 u = l + floor ((( u - l +1) * CC ( p +1) ) / totcount ) - 1;
33 l = l1 ;
34
35 lb = dec2bin (l , m ) ;
36 ub = dec2bin (u , m ) ;
37 E2 = 1; E3 = 1;
38

39 % Renormalisation E1 , E2 , E3
40 while ( E2 | E3 )
41 fbl = lb (1) ; fbu = ub (1) ;
42 if fbl == fbu
43 E2 = 1;
44 tag = [ tag fbl ];
45 lb = [ lb (2: end ) ’0 ’ ];
46 ub = [ ub (2: end ) ’1 ’ ];
47 sc = char ( ’0 ’ + ’1 ’ - fbl ) ;
48 while scale > 0
49 tag = [ tag sc ];
50 scale = scale - 1;
51 end
52 else
53 E2 = 0;
54 end
55 sbl = lb (2) ; sbu = ub (2) ;
56 if sbl == ’1 ’ && sbu == ’0 ’
57 lb = [ lb (2: end ) ’0 ’ ]; lb (1) = ’0 ’;
58 ub = [ ub (2: end ) ’1 ’ ]; ub (1) = ’1 ’;
59 scale = scale + 1;
60 E3 = 1;
61 else
62 E3 = 0;
63 end
64 end
65 l = bin2dec ( lb ) ;
66 u = bin2dec ( ub ) ;
67 end
68

69 % Emission finale
70 f = lb (1) ; lb (1) = ’ ’;
71 sc = char ( ’0 ’ + ’1 ’ - f ) ;
72 tag = [ tag f ];
73 while scale > 0
74 tag = [ tag sc ];
75 scale = scale - 1;
76 end
77 tag = [ tag lb ];

Listing 4.1 – Encodage arithmétique en précision entière arithintcod.m

4.3 Code MATLAB – Décodage arithmétique

16
 TP – Théorie de l’Information et Codage Source SICOM S6 – FST Fès

1 function seq = arithintdecod ( btag , alpha , cnt , lgt )

2 % Decodage arithmetique entier
3 % Entrees : btag - chaine binaire codee
4 % alpha - alphabet
5 % cnt - comptages
6 % lgt - longueur de la sequence originale
7
8 CC (1) = 0;
9 for i = 1: length ( cnt )
10 CC ( i +1) = CC ( i ) + cnt ( i ) ;
11 end
12 totcount = CC ( i +1) ;
13 m = ceil ( log2 ( totcount * 4) ) ;
14 seq = ’ ’;
15 l = 0;
16 u = 2^ m - 1;
17
18 for i = 1: lgt
19 ts = btag (1: m ) ;
20 t = bin2dec ( ts ) ;
21

22 % Identification du symbole
23 k = 1;
24 s = floor ((( t - l + 1) * totcount - 1) / ( u - l + 1) ) ;
25 while s >= CC ( k )
26 k = k + 1;
27 end
28 seq = [ seq alpha (k -1) ];
29
30 % Mise a jour de l ’ intervalle
31 l1 = l + floor ((( u - l +1) * CC (k -1) ) / totcount ) ;
32 u = l + floor ((( u - l +1) * CC ( k ) ) / totcount ) - 1;
33 l = l1 ;
34
35 lb = dec2bin (l , m ) ;
36 ub = dec2bin (u , m ) ;
37 % ... ( renormalisation identique a l ’ encodeur )
38 end

Listing 4.2 – Décodage arithmétique entier arithintdecod.m

4.4 Application et comparaison avec Huffman

1 % Lecture du fichier texte
2 fid = fopen ( ’ seq1 . txt ’ , ’r ’) ;
3 seq = fread ( fid , ’* char ’) ’;
4 fclose ( fid ) ;
5 seq = seq ( seq ~= 10 & seq ~= 13) ; % Supprimer retours a la ligne
6
7 % Modele de probabilites
8 [ alpha , cnt ] = unique_count ( seq ) ; % Fonction a ecrire
9
10 % Codage arithmetique
11 tag = arithintcod ( alpha , cnt , seq ) ;
12 taille_arith = length ( tag ) ;

17
 TP – Théorie de l’Information et Codage Source SICOM S6 – FST Fès

13
14 % Codage Huffman ( pour comparaison )
15 prob = cnt / sum ( cnt ) ;
16 [ huf , entr , lmoy ] = huffman ( num2cell ( alpha ) , prob ) ;
17 taille_huffman = length ( seq ) * lmoy ;
18

19 % Affichage des resultats

20 fprintf ( ’ Taille originale ( ASCII 8 bits ) : % d bits \ n ’ , length ( seq ) *8) ;
21 fprintf ( ’ Taille Huffman : %.0 f bits \ n ’ , taille_huffman ) ;
22 fprintf ( ’ Taille Aritmetique : % d bits \ n ’ , taille_arith ) ;
23 fprintf ( ’ Entropie theorique : %.2 f bits / symbole = %.0 f bits total \ n ’ ,
...
24 entr , length ( seq ) * entr ) ;

Listing 4.3 – Comparaison Huffman vs Arithmétique sur [Link]

Interprétation
Le codage arithmétique approche l’entropie de manière plus précise que Huffman,
notamment pour des sources avec des probabilités inégales. Pour un alphabet de 5
symboles et une séquence courte (10 caractères), les différences restent faibles. Pour
de grandes séquences, le codage arithmétique est systématiquement plus proche de
H(S) × N bits (limite théorique de Shannon).
Avantage du codage arithmétique : Il peut atteindre des longueurs moyennes
inférieures à 1 bit/symbole (impossible avec Huffman classique), particulièrement utile
pour des symboles très probables (p → 1).

18
 5. Codage LZW

5.1 Principe de l’algorithme LZW

L’algorithme LZW (Lempel–Ziv–Welch, 1977–1984) est un codage par dictionnaire
adaptatif. Le dictionnaire est initialisé avec les 256 symboles ASCII, puis enrichi dynami-
quement au fil de la compression.
Algorithme d’encodage :
1. Initialiser le dictionnaire avec les 256 octets de base.
2. Lire le premier symbole c.
3. Pour chaque symbole s suivant :
— seq = c + s
— Si seq ∈ dictionnaire : c ← seq (continuer)
— Sinon : émettre adresse(c), ajouter seq au dictionnaire, c ← s
4. Émettre adresse(c) finale.

5.2 Code MATLAB – Encodage LZW

1 function [ output , table ] = norm2lzw ( vector )
2 % Compression LZW d ’ un vecteur uint8
3 % Entree : vector - vecteur uint8 a comprimer
4 % Sorties : output - codes LZW ( uint16 )
5 % table - dictionnaire construit
6
7 if ~ isa ( vector , ’ uint8 ’)
8 error ( ’ input argument must be a uint8 vector ’)
9 end
10

11 % Convertir en uint16 pour gerer les codes > 255

12 vector = uint16 ( vector (:) ’) ;
13
14 % Initialisation du dictionnaire : 256 symboles de base
15 table = cell (1 , 256) ;
16 for index = 1:256
17 table { index } = uint16 ( index - 1) ;
18 end
19
20 % Initialisation de la sortie
21 output = vector ;
22 outputindex = 1;
23 startindex = 1;
24

19
 TP – Théorie de l’Information et Codage Source SICOM S6 – FST Fès

25 % Boucle principale LZW

26 for index = 2: length ( vector )
27 element = vector ( index ) ;
28 substr = vector ( startindex : ( index -1) ) ;
29 code = getcodefor ([ substr element ] , table ) ;
30

31 if isempty ( code )
32 % La sequence n ’ est pas dans le dictionnaire
33 output ( outputindex ) = getcodefor ( substr , table ) ;
34 [ table , code ] = addcode ( table , [ substr element ]) ; % Ajouter au
dico
35 outputindex = outputindex + 1;
36 startindex = index ;
37 end
38 end
39
40 % Derniere sequence
41 substr = vector ( startindex : index ) ;
42 output ( outputindex ) = getcodefor ( substr , table ) ;
43 output (( outputindex +1) : end ) = []; % Supprimer les positions
inutilisees
44
45
46 % Fonctions internes

47 function code = getcodefor ( substr , table )

48 % Recherche d ’ une sous - sequence dans la table
49 code = uint16 ([]) ;
50 if length ( substr ) == 1
51 code = substr ;
52 else
53 for index = 257: length ( table )
54 if isequal ( substr , table { index })
55 code = uint16 ( index - 1) ; % Code base 0
56 break
57 end
58 end
59 end
60
61 function [ table , code ] = addcode ( table , substr )
62 % Ajout d ’ une nouvelle entree dans le dictionnaire
63 code = length ( table ) + 1; % Index 1 - base
64 table { code } = substr ;
65 code = uint16 ( code - 1) ; % Code base 0

Listing 5.1 – Encodage LZW norm2lzw.m

5.3 Code MATLAB – Décodage LZW

1 function [ output , table ] = lzw2norm ( vector )
2 % Decompression LZW
3 % Entree : vector - codes LZW ( uint16 )
4 % Sorties : output - donnees originales ( uint8 )
5 % table - dictionnaire reconstruit
6

20
 TP – Théorie de l’Information et Codage Source SICOM S6 – FST Fès

7 if ~ isa ( vector , ’ uint16 ’)

8 error ( ’ input argument must be a uint16 vector ’)
9 end
10 vector = vector (:) ’;
11
12 % Initialisation du dictionnaire
13 table = cell (1 , 256) ;
14 for index = 1:256
15 table { index } = uint16 ( index - 1) ;
16 end
17
18 % Initialisation
19 output = uint8 ([]) ;
20 code = vector (1) ;
21 output ( end +1) = code ;
22 character = code ;
23
24 for index = 2: length ( vector )
25 element = vector ( index ) ;
26
27 if ( double ( element ) + 1) > length ( table )
28 % Code pas encore dans le dictionnaire
29 string = table { double ( code ) + 1};
30 string = [ string character ];
31 else
32 string = table { double ( element ) + 1};
33 end
34
35 output = [ output string ];
36 character = string (1) ;
37
38 % Ajouter au dictionnaire
39 [ table , code ] = addcode ( table , [ table { double ( code ) +1} character ]) ;
40 code = element ;
41 end

Listing 5.2 – Décodage LZW lzw2norm.m

5.4 Programme de démonstration lzw_demo1.m

1 % Lecture du fichier texte seq . txt
2 fid = fopen ( ’ seq . txt ’ , ’r ’) ;
3 str = fread ( fid , ’* char ’) ’;
4 fclose ( fid ) ;
5

6 % Supprimer les caracteres de fin de ligne

7 str = str ( str ~= 10 & str ~= 13) ;
8 fprintf ( ’ Message original : % s \ n ’ , str ) ;
9 fprintf ( ’ Taille originale : % d octets \ n ’ , length ( str ) ) ;
10
11 % Codage LZW
12 [ packed , table ] = norm2lzw ( uint8 ( str ) ) ;
13 fprintf ( ’ Taille codee LZW : % d codes ( uint16 = % d octets ) \ n ’ , ...
14 length ( packed ) , length ( packed ) *2) ;
15
16 % Decodage LZW

21
 TP – Théorie de l’Information et Codage Source SICOM S6 – FST Fès

17 [ unpacked , table2 ] = lzw2norm ( packed ) ;

18 unpacked = char ( unpacked ) ;
19
20 fprintf ( ’ Message decode : % s \ n ’ , unpacked ) ;
21
22 % Verification
23 isOK = strcmp ( str , unpacked ) ;
24 fprintf ( ’ Decodage correct : % d \ n ’ , isOK ) ;
25
26 % Affichage du dictionnaire construit ( entrees ajoutees > 256)
27 fprintf ( ’\ nDictionnaire construit :\ n ’) ;
28 for i = 257: length ( table )
29 fprintf ( ’ Code %3 d -> % s \ n ’ , i -1 , char ( table { i }) ) ;
30 end
31
32 % Statistiques
33 fprintf ( ’\n - - - Statistiques de compression - - -\ n ’) ;
34 fprintf ( ’ Taille originale : % d bits \ n ’ , length ( str ) * 8) ;
35 fprintf ( ’ Taille compresse : % d bits (16 bits / code ) \ n ’ , length ( packed ) *
16) ;
36 fprintf ( ’ Taux compression : %.3 f \ n ’ , ( length ( str ) *8) / ( length ( packed )
*16) ) ;
37
38 % Affichage via whos
39 whos str packed

Listing 5.3 – Démonstration complète du codage LZW sur un fichier texte

5.5 Application à la séquence [Link] : ABCDABCBEB

5.5.1 Déroulement manuel de l’encodage LZW

Table 5.1 – Encodage LZW de la séquence ABCDABCBEB

Étape Entrée Action Code émis Ajout au dico

1 A A seul → garder – –
2 AB AB ∈/ dico → émettre A 65 (A) 257 : AB
3 BC BC ∈/ dico → émettre B 66 (B) 258 : BC
4 CD CD ∈/ dico → émettre C 67 (C) 259 : CD
5 DA DA ∈/ dico → émettre D 68 (D) 260 : DA
6 AB AB ∈ dico (257) → continuer – –
7 ABC ABC ∈ / dico → émettre AB 257 261 : ABC
8 CB CB ∈/ dico → émettre C 67 (C) 262 : CB
9 BE BE ∈/ dico → émettre B 66 (B) 263 : BE
10 EB EB ∈/ dico → émettre E 69 (E) 264 : EB
– B Fin → émettre B 66 (B) –

Codes émis : [65, 66, 67, 68, 257, 67, 66, 69, 66] (9 codes uint16)

22
TP – Théorie de l’Information et Codage Source SICOM S6 – FST Fès

Table 5.2 – Bilan de compression LZW pour ABCDABCBEB

Grandeur Valeur
Taille originale (8 bits/char ASCII) 80 bits
Taille codée LZW (9 codes × 16 bits) 144 bits
Taux de compression 80/144 ≈ 0,56

Interprétation
Pour cette courte séquence, le codage LZW est moins efficace que le codage original
ASCII ! Cela s’explique par le fait que LZW nécessite des codes sur 16 bits (uint16)
pour indexer le dictionnaire, alors que les caractères ASCII n’occupent que 8 bits.
Le bénéfice du LZW apparaît pour des fichiers longs présentant des répétitions de
sous-chaînes : le dictionnaire s’enrichit et les codes remplacent des séquences de plus
en plus longues.
Pour un fichier d’une page (quelques milliers de caractères), on obtient typiquement
un taux de compression τc ≈ 1,5 à 2,5 selon la redondance du texte.

23
6. Synthèse et Comparaison des mé-
thodes

6.1 Tableau comparatif

Table 6.1 – Comparaison des algorithmes de compression sans perte

Critère RLE Huffman Arithmétique LZW

Type d’exploi- Redondances Fréquences Fréquences Sous-

tation locales (runs) symboles symboles séquences
récurrentes
Optimalité Non Optimal Approche Sous-optimal
parmi les l’entropie mais adapta-
codes à en- tif
tiers de bits
Complexité Très faible Faible Modérée Modérée
Dictionnaire Non Oui Oui (modèle) Non
transmis
Meilleur cas Images bi- Textes, Toutes Textes longs
naires, fax images natu- sources
relles
Usage standard JPEG (in- JPEG, DE- JPEG 2000, GIF, TIFF,
terne), TIFF FLATE JBIG PDF

24
TP – Théorie de l’Information et Codage Source SICOM S6 – FST Fès

6.2 Conclusion générale

Conclusions du TP
1. Codage RLE : efficace uniquement pour des données très redondantes
(images binaires avec de longues plages). Inutile pour des données naturelles
peu redondantes.
2. Entropie : elle constitue la limite théorique inférieure de tout codage sans
perte. La fonction entropy.m permet de la calculer rapidement et de dimen-
sionner les gains théoriquement atteignables.
3. Codage de Huffman : code préfixé optimal, longueur moyenne L̄ satisfaisant
H(S) ≤ L̄ < H(S) + 1. Sa redondance est nulle pour des probabilités qui sont
des puissances négatives de 2, et au plus 1 bit/symbole sinon.
4. Codage arithmétique : plus flexible que Huffman, il approche l’entropie
sans la contrainte des entiers de bits. Avantage marqué pour les sources à
forte redondance ou grands alphabets.
5. Codage LZW : ne nécessite pas la transmission du dictionnaire (reconstruit
à la décompression), mais requiert des fichiers longs pour que le dictionnaire
soit suffisamment riche et les séquences répétées fréquentes.

6.3 Récapitulatif des taux de compression obtenus

Table 6.2 – Bilan des taux de compression sur les données du TP

Données Méthode Taille avant Taux τc

Image [Link] (256 × 256) RLE 65 536 octets ∼50–200
Matrice f (16 pixels, 4 symboles) Huffman 128 bits ∼2,2
Séquence ABCDABCBEB (10 car.) Huffman 80 bits ≈4
Séquence ABCDABCBEB (10 car.) Arithmétique 80 bits ≈4
Séquence ABCDABCBEB (10 car.) LZW 80 bits ≈ 0,56
Texte long (∼1 page) LZW ∼15 000 bits ≈ 1,5–2,5

Remarque
Ces valeurs sont typiques et dépendent fortement des données. Le LZW est désavantagé
sur les courtes séquences mais devient compétitif sur les grands fichiers. Le codage
arithmétique et Huffman produisent des résultats très proches pour les textes courants.

25
Bibliographie

[1] C.E. Shannon, A Mathematical Theory of Communication, Bell System Technical

Journal, vol. 27, pp. 379–423, 1948.
[2] D.A. Huffman, A Method for the Construction of Minimum-Redundancy Codes, Proc.
IRE, vol. 40, pp. 1098–1101, 1952.
[3] T.A. Welch, A Technique for High-Performance Data Compression, IEEE Computer,
vol. 17, pp. 8–19, 1984.
[4] K. Sayood, Introduction to Data Compression, 4th ed., Morgan Kaufmann, 2012.
[5] F. Abdi, Support de cours : Communications Numériques & Codage de l’Information,
FST Fès, SICOM S6.

26