Semestre : 6

Unité d’enseignement : UEF 3.2.2

Cours 3

Codage et Théorie de
l’information
Dr Mahmoud Hadef

1
 Codage de source

Partie 3
Codage de source

• Codage efficace de l’information

• Codage de Shannon-Fanno
• Algorithmes de Huffman

2
 Codage de l’information
Définitions
• Coder pour compresser les données  réduire (en
moyenne) la longueur des messages  tenter de supprimer
un maximum de redondance des messages

• Une source d’information est un générateur de messages

c’est-à-dire un générateur de séquences de symboles.

• Un symbole est simplement un élément d’un ensemble,

appelé alphabet 3
 Codage de l’information
Définitions
• Seuls les alphabets finis seront abordés  la source
d’information est discrète  la taille de l’alphabet est
appelée l’arité de la source.

• Seuls les messages de longueur finie seront considérés

• Les messages de la source entrent alors dans un codeur qui

les transforme en une séquence de mots de code.

• Un mot de code est simplement une séquence de symboles

pris dans l’alphabet de codage, un autre alphabet employé4
par le codeur.
 Codage de l’information
Définitions
• Chaque symbole a une probabilité P(Ut = ui) d’être émis par
la source à l’instant t. On dit que la source est sans mémoire
si la probabilité qu’un symbole ui soit émis ne dépend pas
des valeurs émises précédemment

∀t ≥ 1 ∀ui ∈ VU P(Ut = ui|U1...Ut−1) = P(Ut = ui)

• les sources stationnaires  les sources pour lesquelles P(Ut

= ui) ne dépend pas de t  P(U = ui) sera dans la suite noté
simplement pi

5
 Codage de l’information
Définitions
• le processus de codage Z := f(U) est une application de
l’alphabet de la source VU à l’ensemble de mots de code VZ

• Le code est non-singulier  deux symboles différents de la

source correspondent à deux mots de code différents
um ≠ un ⇒ zm ≠ zn

• Exemple  code Morse. Il emploie essentiellement deux

symboles : un point (·) et un tiret (–).Par exemple, les lettres
E, A et K sont respectivement codées «·», «· –» et «– · –».
6
 Codage de l’information
Définitions
Le code non-ambigu  si et seulement si chaque séquence
(de longueur finie) de mots de code ne correspond qu’à un seul
message de la source

Exemple (Code ambigu)

Considérons la source composée des trois symboles a, b et c.
Le codage suivant de cette source
a → 1 b → 00 c → 11 est ambigu.
une fois codés, il n’y a aucun moyen de distinguer le message
«aaaa» du message «cc» deux sont codés «1111»
a → 1 b → 00 c → 10 est non-ambigu 7
 Codage de l’information
Définitions
• On dit qu’une séquence z de longueur n (n ≥ 1) est un
préfixe d’une autre séquence z′ si et seulement si les n
premiers symboles de z′ forment exactement la séquence z

Exemple: abba est un préfixe de abbabc

• On dit que le code d’une source discrète est sans préfixe

lorsqu’aucun mot de code n’est le préfixe d’un autre mot de
code

• Tout code sans préfixe est non-ambigu 8

 Codage de l’information
Définitions
Exemple
Considérons la source composée des trois symboles a, b et c.
Le code suivant de cette source :
a → 0 b → 10 c → 11 est sans préfixe
D’autre part, le code suivant :
a → 1 b → 00 c → 10 n’est pas sans préfixe
puisque 1 (le mot de code pour a) est un préfixe de 10 (le mot
de code pour c).

9
 Codage de l’information
Définitions
• Un code est instantané  si et seulement si chaque mot de
code dans toute chaîne de mots de code peut être décodé
dès que l’on a atteint sa fin

• Un code est instantané si et seulement si il est sans préfixe

• code est instantané garantit qu’il n’est ni nécessaire de

mémoriser les mots de code reçus ni d’attendre les suivants
pour effectuer le décodage  permet d’économiser du
temps et de l’espace dans le processus de décodage d’un
message codé
10
 Codage de l’information
Définitions
nous avons rencontré différents types de codes : non-singulier,
non-ambigu, instantané. La façon dont ces différents types de
codes sont reliés les uns aux autres est résumée

11
 Codage de l’information
Exemple
Considérons une source d’information U, dont les symboles
sont u1 = 1, u2 = 2, u3 = 3, et u4 = 4, avec la distribution de
probabilité suivante :
P={ 0.5 0.25 0.125 0.125}
Considérons donc le codage suivant de cette source, (où zi est
le mot de code pour ui) :
z1 = 0 , z2 =10 z3 =110 z4 =111
1. Le code est-il non-ambigu?
2. Codez le message 1423312.
3. Décodez la séquence 1001101010.
12
 Codage de l’information
Exemple
Ces codes sont-ils sans préfixe? Non-ambigus? Instantanés?
a. z1=00, z2=10, z3=01, z4=11
b. z1=0, z2=1, z3=01
c. z1=1, z2=101

13
Codage de l’information

14
 Codage de l’information
Exemple 4

Arbre binaire (n = 2) Arbre binaire (n = 3) Arbre ternaire complet

15
Codage de l’information

16
 Codage de l’information
Exemple 5

Un arbre de codage ternaire: le mot de code représenté par

la feuille 1 est «ac» et la feuille 2 représente le mot de code
«c».

17
Codage de l’information

18
Codage de l’information

19
Codage de l’information

20
Codage de l’information

21
Codage de l’information

22
Codage de l’information

23
 Moodle
username password firstname lastname email
abed2016 qj78z8m8 Besma ABED [email protected]
belkacem2016 awj2522g Widad BELKACEM [email protected]
benaicha2016 4q3j5x2h Asma BENAICHA [email protected]
boumekhleb2016 wiz697q2 Aida BOUMEKHLEB [email protected]
bouras2016 h5bm7z26 Kawther BOURAS [email protected]
boussenane2016 i49ey4w3 Aymen BOUSSENANE [email protected]
bouteghrine2016 66c6z2vs Younes BOUTEGHRINE [email protected]
chebah2016 29fr4vt9 Ala eddine CHEBAH [email protected]
chouimet2016 4n6xe7d3 Rania CHOUIMET [email protected]
dahmani2016 h72xh28y Bilal DAHMANI [email protected]
djoualla2016 n6d7ar57 Souhila DJOUALLA [email protected]
dziri2016 54ce25ki Borhane eddine DZIRI [email protected]
hocine2016 325bdea5 Mohamed ilyes HOCINE [email protected]
houmi2016 unvk3898 Ismail HOUMI [email protected]
krouchi2016 b2d8d4d2 Mohamed KROUCHI [email protected]
24
 Moodle
lakhdarfriha2016 p9pb3p78 Achraf LAKHDAR FRIHA [email protected]
lemmouchi2016 5e8i82uy Badr eddine LEMMOUCHI [email protected]
m'haimedatt2016 4w28ugn9 Abdallahi M'HAIMEDATT [email protected]
mekseh2016 72s8mr7s Imene MEKSEH [email protected]
merazka2016 7iyv3w28 Houda MERAZKA [email protected]
imane.merazka2016 f57b25br Imane MERAZKA [email protected]
nacercherif2016 59uys88n Mohammed NACER CHERIF [email protected]
nya2016 d49d2a6s Turkiya NYA [email protected]
ouazene2016 t4v396hg Housseyne OUAZENE [email protected]
kouchen2016 4h7tw75x Khalil fadhel allah OUCHEN [email protected]
aouchen2016 fmg6f277 Abdelheq OUCHEN [email protected]
oueznadji2016 4w95yr4u Adam OUEZNADJI [email protected]
ounissi2016 sn5w48r6 Dounia OUNISSI [email protected]
ounnar2016 f2c895fa Abir OUNNAR [email protected]
oussaf2016 k69ri64e Monsif OUSSAF [email protected]
saoudi2016 j5j64p7i Souheyla SAOUDI [email protected]
tabitourt2016 39w9ir2i Elkhansa TABITOURT [email protected]
zerouali2016 7z5hs5a6 Amina maroua ZEROUALI [email protected]

25