0.40

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