USDB/ Département D’Electronique/ Master1 RT / Semestre 02/ Module: CC / 2019/2020
Td N°=02. Techniques de codage et de compression de données.
Rappels : Toute fraction intelligible d’un message est constituée de symboles. Le langage est l’ensemble de ces
symboles. Un codage va associer à chaque symbole un mot de code. Chaque mot de code est constitué d’un
ensemble de signes élémentaires, encore appelés symboles de code, et est de longueur l i correspondant au
nombre de signes élémentaires qui le décrivent. Un codage est :
-intelligible :si la suite des signes élémentaires correspondant à une succession de symboles possède une unique
interprétation ;
- instantané :s il est possible de le décoder au fur et à mesure de l’arrivée des mots de code ; - préfixe, si aucun
mot de code n est le début d’ un autre mot de code ;
- complet s il est intelligible et si tout ajout d’un mot de code de longueur inférieure ou égale à n le rend inintelligible
et Lp = pour tout p > n. Une condition nécessaire pour qu’un codage de valence V (dont les mots de code ont une
longueur maximale n) soit complet et intelligible est donnée par l’égalité de Kraft-McMillan :
𝐿𝑝
∑𝑛𝑝=1 𝑉 𝑝−1
=V.
L’efficacité d’un code est estimée par ses caractéristiques :
𝐻𝑠 𝐻𝑠
-longueur moyenne : lmoy =∑𝑖 𝑙𝑖𝑃𝑖 . Il est montré que 𝑙𝑜𝑔2(𝑣) ≤lmoy, la limite théorique est donc : lmin= 𝑙𝑜𝑔2(𝑣)
𝑙𝑚𝑖𝑛
- Rendement R= 𝑙𝑚𝑜𝑦 et la redondance ρ= 1-R
Exercice1 : Soit le codage représentant les quatre symboles A, C, G, T où A est représenté par le mot de code «
0 », C par « 100 », G par « 101 », T par « 111 ».
1. Quels sont les valeurs L1, L2, L3, L4 ? Est-ce un codage intelligible ? Est-ce un codage complet ?
Exercice2 :
Soient deux s de 6 sources discrètes d’information sans mémoire S1 et S2, chacune possède un alphabet de 6
symboles, S1={X1, X2, X3, X4, X5, X6} de probabilités 1/2, 1/4, 1/8, 1/16, 1/32, 1/32 et S2= {Y1, Y2, Y3, Y4, Y5,
Y6} de distribution uniforme.
1- Quelle est la source la moins prédictible et pourquoi ?
2- Représenter le codage Huffman de chaque source. Quel le codage le plus efficace celui de S1 ou S2 ?
Exercice3 :
Soit une source (S) à 11 symboles (s1 à s11) définie par les probabilités suivantes :
S S1 S2 S3 S4 S5 S6 S7 S8 S9 S10 S11
pi 0.22 0.15 0.12 0.11 0.10 0.08 0.07 0.06 0.04 0.03 0.02
1-Calculer l’entropie de la source.
2-Que vaudrait l’entropie si tous les symboles étaient équiprobables ?
3-Donner le codage Shannon correspondant ?
USDB/ Département D’Electronique/ Master1 RT / Semestre 02/ Module: CC / 2019/2020
4-Donner le Codage de Fano-Shannon
Exercice4 : ( Remarque : utiliser l’arbre comme celui montré par la figure ci-dessous)
1. Donner l’arbre du codage huffman correspondant au texte « RESEAUX ET
TELECOMMUNICATIONS » en calculant les probabilités d’occurrence ?
2. Donner la séquence codée ?
3. Donner le gain de compression si on avait utilisé le code ASCII ?
Exercice 5 :
Soit la séquence suivante : « abracadabrabracadabra »
1- Donner l’arbre du codage huffman correspondant ?
2-Donner la séquence codée ?
3-Donner le gain de compression si on avait utilisé le code ASCII ?
Exercice 6 (codage arithmétique)
Le principe de cette méthode est de calculer les fréquences d’apparition des symboles puis d’associer à
chaque symbole un intervalle réel compris entre 0 et 1.
Par exemple si on a la chaîne « abbc », on associe les intervalles suivants :
- a : fréquence ¼ : intervalle ]0 ; 0.25[
- b : fréquence ½ : intervalle ]0.25 ; 0.75[
- c : fréquence ¼ : intervalle ]0.75 ; 1[
Donner la séquence codée et procéder par la suite à l’opération de décodage
Exercice 7 (codage LZW)
Initialisation : un dictionnaire est créé, typiquement avec tous les caractères du code ASCII.
1. Soit la séquence suivante ‘’cagataagaaggtaa ’’
2. construire le codage dictionnaire correspondant?
3. Donner la séquence codée ?
Exercice 8(codage LZW)
Soit l’ensemble de caractère indexé par la base de dictionnaire suivante :
lettre a b e i j l o r
indice 1 2 3 4 5 6 7 8
Donner le code de la séquence suivante : « jolierababa »
