Travaux dirigés de Compression de Données Master 1 (INFO, BIHAR, MBDS)
2023-2024 page 1
Exercice 0
Exercice 1
F T
Soit un alphabet A = {a1 , a2 , a3 , a4 }. Calculer l’entropie en bits pour les situa-
tions suivantes :
1. P (a1 ) = 0, P (a2 ) = 0, P (a3 ) = 0, P (a4 ) = 1
2. P (a1 ) = 0.25, P (a2 ) = 0.25, P (a3 ) = 0.25, P (a4 ) = 0.25
A
3. P (a1 ) = 0.505, P (a2 ) = 0.25, P (a3 ) = 0.125, P (a4 ) = 0.12
Exercice 1 bis
R
Soit un alphabet source A = {a1 , a2 , a3 , a4 , a5 } avec des probabilités suivantes
P (a1 ) = 0.15, P (a2 ) = 0.04, P (a3 ) = 0.26, P (a4 ) = 0.05, P (a5 ) = 0.5.
1. Calculer l’entropie de la source..
2. Trouver le code de Huffman de la source.
3. Calculer la longueur moyenne de ce code.
D
4. Calculer la redondance de ce code.
5. Calculer l’efficacité de ce code.
Exercice 2
Soit une première source avec un modèle de probabilité P = {p1 , p2 , · · · , pm } et
une entropie HP . Et soit une seconde source avec un modèle Q = {q1 , q2 , · · · , qm }
et une entropie HQ . Supposons que qi = pi , i = 1, 2, · · · , j − 2, j + 1, · · · , m et
qj = qj−1 = (p1 + p2 )/2
1. Démontrer que : HQ ≥ HP
GHISLAIN PANDRY
Travaux dirigés de Compression de Données Master 1 (INFO, BIHAR, MBDS)
2023-2024 page 2
Exercice 3
Soit une source X discrète sans mémoire délivrant en sortie la séquence sui-
vante : ”1 2 1 2 3 3 3 3 1 2 3 3 3 3 1 2 3 3 1 2”
1. Quels sont les symboles de cette source.
2. Déterminer sa probabilité d’occurrence (pi).
3. Calculer l’entropie de la source H(X).
T
Exercice 4
Soit une séquence d’origine S0 = [2 4 8 12 14 0 2 1].
F
1. Calculer pour une échelle égale à 3 (S3 ), les coefficients d’ondelettes de S0
en utilisant de l’ondelette de Harr.
2. Déterminer la séquence finale obtenue après décomposition en ondelettes
1D de Haar.
A
Exercice 5
Soit une image suivante :
D R
Remarque le résultat (S3 ) devra être présenté comme suit :
GHISLAIN PANDRY
Travaux dirigés de Compression de Données Master 1 (INFO, BIHAR, MBDS)
2023-2024 page 3
T
1. Calculer pour une échelle égale à 3 (S3 ), les coefficients d’ondelettes de S0
en utilisant de l’ondelette de Harr.
2. Quantifier S3 . (Règle de quantification : Si |D| < 30 alors D=0 sinon D =
sng(D) × E(|D|/10) × 10 avec D = {HB1 , HB2 , BH1 , HB2 , HH1 , HH2 }
F
3. Coder la matrice quantifiée à l’aide de Huffman.
4. Quel est le taux de compression ?
Exercice 6
A
En utilisant la table ASCII hexadécimale (7bits) ci-dessous comme dictionnaire
initial,
D R 1. Compresser la chaîne “BLEBLBLBA” avec LZW ;
2. Décompresser.
GHISLAIN PANDRY
Travaux dirigés de Compression de Données Master 1 (INFO, BIHAR, MBDS)
2023-2024 page 4
Exercice 7
F T
A
Choisissez un texte
1. Construire le code de Shannon-Fano correspondant.
2. Construire le code de Huffman correspondant.
3. Quelle est la longueur moyenne de chaque code ?
R
4. Comparer à la limite théorique donnée par le théorème de Shannon.
Exercice 8
D 1. Quel serait le codage RLE de cette image ?
GHISLAIN PANDRY
Travaux dirigés de Compression de Données Master 1 (INFO, BIHAR, MBDS)
2023-2024 page 5
2. Y-a-t-il un gain ?
3. Quel serait le codage sur blocs de 5 bits en 16 niveaux de gris ? Et le gain ?
Peut-on compresser plus avec ce système ?
4. Et en 255 niveaux de gris (avec au plus 16 pixels identiques consécutifs) ?
5. Et en colonnes ?
Exercice 9
T
U s1 = a s2 = b s3 = c s4 = b
Soit S la source d’alphabet {a, b, c, d} et de probabilités :
P (U ) 0.5 0.25 0.125 0.125
a b c d
On code S avec le code suivant :
0 10 110 111
F
1. Coder adbccab. Décoder 1001101010.
2. Est-ce un code instantané ?
3. Calculer l’entropie de la source.
A
Exercice 10
On veut construire un code compresseur binaire sur une source S = (S, P ) (sup-
posée infinie) où S = (0, 1) est l’alphabet source et P = (P (0) = p, P (1) = 1 − p)
est la loi de probabilité de S.
R
On propose le code suivant : on compte le nombre d’occurrences de “0” avant
l’apparition d’un “1”. Les deux règles de codage sont :
— Une chaîne de quatre “0” consécutifs (sans “1”) est codée par 0.
— Si moins de quatre “0” apparaissent avant un symbole “1”, on code la
cha^ıne par le mot de code “1e1e2”, où e1e2 est la représentation binaire
D
du nombre de “0” apparus avant le “1”.
Par exemple, l’apparition de quatre zéros consécutifs “0000” est codée par “0”,
tandis que l’occurrence “001” est codé par “110” car deux “0” sont apparus avant
le “1” et que “10” est la représentation binaire de deux.
1. Expliciter les 5 mots de code. Le code possède-t-il la propriété du préfixe ?
2. Sachant que la probabilité d’apparition de deux symboles successifs s1 et s2
est, dans notre cas où l’on suppose la source sans m´emoire, p(s1 ) ∗ p(s2 ),
calculer la probabilité d’occurrence dans S d’une chaîne de k “0” suivis d’un
“1”.
3. Pour chaque mot du code, calculer le nombre de bits de code nécessaires
par bit de source. En déduire le taux de compression de ce code, c’est-à-dire
la longueur moyenne par bit de source.
GHISLAIN PANDRY
Travaux dirigés de Compression de Données Master 1 (INFO, BIHAR, MBDS)
2023-2024 page 6
Exercice 11
On cherche à coder des jets successifs (en nombre supposé infini) d’un dé faussé.
Les symboles de la source sont notés (1, 2, 3, 4, 5, 6), et suivent la loi de probabilité
d’apparition (0.12, 0.15, 0.16, 0.17, 0.18, 0.22).
1. Quelle est l’entropie de cette source ?
2. Proposer un code binaire issu de l’algorithme de Huffman pour cette source.
Quelle est sa longueur moyenne ? Quelle longueur moyenne minimale peut-
T
on espérer pour un tel code binaire ?
3. Même question pour un code ternaire.
Exercice 12
F
A l’aide de la représentation des codes instantanés par desarbres de Huffman,
donner une preuve du théorème de McMillan.
RA
D GHISLAIN PANDRY
