Embed Size (px)
DESCRIPTION
a. CODAGE DE HUFFMAN. 0.40. Objectif : coder les lettres avec des longueurs fonction décroissante de leur probabilité afin de réduire le débit moyen de transmission. b. 0.18. c. 0.10. d. DES LETTRES AVEC DES PROBABILITES D ’APPARITION. 0.10. e. 0.07. f. 0.06. g. 0.05. h. - PowerPoint PPT Presentation
Citation preview
a
b
c
d
e
f
g
0.40
0.18
0.10
0.10
0.07
0.06
0.05h
0.04
CODAGE DE HUFFMAN
DES LETTRES AVEC DES PROBABILITESD ’APPARITION
Objectif : coder les lettresavec des longueurs fonctiondécroissante de leur probabilitéafin de réduire le débit moyende transmission
a
b
c
d
e
f
g
0.40
0.18
0.10
0.10
0.07
0.06
0.05h
0.04
(gh)0.09
a
b
c
d
e
0.40
0.18
0.10
0.10
0.07
f0.06
Regroupement des deux lettresde plus faible probabilitéla probabilité du regroupementest la somme des deux probabilités
Les autres lettres ne sont pas traitées
Première étape
a
b
c
d
e
f
g
0.40
0.18
0.10
0.10
0.07
0.06
0.05h
0.04
(gh)0.09
(ef)0.13
a0.40
b0.18
0.10
d0.10
c
Regroupement des deux lettresou groupements de lettresde plus faible probabilité
Même critèrepour les étapes suivantes
a
b
c
d
e
f
g
0.40
0.18
0.10
0.10
0.07
0.06
0.05h
0.04
(gh)0.09
(ef)0.13
a0.40
b0.18
c0.10
d0.10
(dgh)0.19
a
b
c
d
e
f
g
0.40
0.18
0.10
0.10
0.07
0.06
0.05h
0.04
(ef)0.13 (dgh)
0.19
(cef)0.23
a0.40
b0.18
c0.10
(gh)
d
a
b
c
d
e
f
g
0.40
0.18
0.10
0.10
0.07
0.06
0.05h
0.04
(dgh)
(cef)0.23 (bdgh)
0.37
a0.40
b0.18
0.19
(gh)
(ef)
c
d
a
b
c
d
e
f
g
0.40
0.18
0.10
0.10
0.07
0.06
0.05h
0.04
(cef)0.23
(bdgh)0.37
(cefbdgh)0.60
a0.40
Codage de Huffman(gh)
(ef)
(dgh)
b
c
d
a
b
c
d
e
f
g
0.40
0.18
0.10
0.10
0.07
0.06
0.05h
0.04
(gh)0.09
(ef)0.13 (dgh)
0.19
(cef)0.23
(bdgh)0.37
(cefbdgh)0.60
a0.40
b0.18c
0.10
d0.10
Probabilitédu regroupement
racine
a
b
c
d
e
f
g
h(gh)
(ef)
(dgh)
(cef)
(cefbdgh)
racinea
b
c
d
Codage des branches
(bdgh)
a
b
c
d
e
f
g
h(gh)
(ef)
(dgh)
(cef)
(bdgh)
(cefbdgh)
racinea
b
c
d
0
1
1
CODEDE LABRANCHE
a
b
c
d
e
f
g
h(gh)
(ef)
(dgh)
(cef)
(bdgh)
(cefbdgh)
racinea
b
c
d
0
1
1
00
01
CODEDE LABRANCHE
A chaque embranchement on complètele code par un bit marquant chacune des deux branches qui en sont issues
a
b
c
d
e
f
g
h(gh)
(ef)
(dgh)
(cef)
(bdgh)
(cefbdgh)
racinea
b
c
d
0
1
1
00
01
000
001
001
CODEDE LABRANCHE
a
b
c
d
e
f
g
h(gh)
(ef)
(dgh)
(cef)
(bdgh)
(cefbdgh)
racinea
b
c
d
0
1
1
00
01
000
001
001
011
011
010CODEDE LABRANCHE
a
b
c
d
e
f
g
h(gh)
(ef)
(dgh)
(cef)
(bdgh)
(cefbdgh)
racinea
b
c
d
0
1
1
00
01
000
001
001
011
011
010
0000
0001
CODEDE LABRANCHE
a
b
c
d
e
f
g
h(gh)
(ef)
(dgh)
(cef)
(bdgh)
(cefbdgh)
racinea
b
c
d
0
1
1
00
01
000
001
001
011
011
010
0100
0101
0000
0001
CODEDE LABRANCHE
a
b
c
d
e
f
g
h(gh)
(ef)
(dgh)
(cef)
(bdgh)
(cefbdgh)
racinea
b
c
d
0
1
1
00
01
000
001
001
011
011
010
0100
0101
0000
000100011
00010
CODEDE LABRANCHE
a
b
c
d
e
f
g
h(gh)
(ef)
(dgh)
(cef)
(bdgh)
(cefbdgh)
racinea
b
c
d 0
1
1
00
01
000
001
001
011011
010
0100
0101
0000
000100011
00010
début à la racine ;progression dansle message jusqu’àune feuille : lettre décodée.
Boucle du décodage
