[PDF] [PDF] Code de Huffman

[PDF] Code de Huffman

IFT-4003/7023 Compression de données Mohamed Haj Taieb, Département de génie électrique et de génie informatique Exemple: codage de Shannon-Fano 

[PDF] Cours/TD 5 Codage Shannon Codage arithmétique : Elias

5 1 De l'algorithme de Fano et Shannon au codage Exemple Soit une source discr`ete sans mémoire codée avec des mots code avec de longueurs li li code

[PDF] Principes généraux de codage entropique dune - FOAD - MOOC

l'algorithme de codage de Shannon-Fano l'algorithme de codage de Huffman Exemple : Calcul de l'entropie d'une source binaire Considérons le cas d'une 

[PDF] Codage statistique

fini de symboles (par exemple : lettres, chiffres, ) visuels où les messages sont des images numérisées où, par exemple, Le codage de Fano- Shannon :

[PDF] UV Théorie de lInformation Cours n° 5 : Compression de l - ASI

Ex 1 : Code de Shannon−Fano i e codage de Shannon−Fano, codage de Huffman, codage Exemples : Codage par plage et Codage de Lempel−Ziv 

[PDF] Série dexercices sur la compression de données 1 Algorithme de

a) En utilisant l'algorithme de Shannon-Fano, représentez la séquence suivante d) Si vous vous restreignez `a utiliser un code qui ne tient pas compte des Par exemple, si les 2 lettres les moins fréquentes sont A et F, la question serait 

[PDF] Théorie de linformation - Chap 1: Codage Source - ESEN

Limitations de Fano-Shannon et Huffman et Supériorité de LZW 8 Code Exemple: Source binaire Soit le codage suivant pour le même exemple précédent

[PDF] Majeure dinformatique Introduction la théorie de linformation

Code de Huffman : exemple f 0 05 e Certains nombres ont plusieurs développements, par exemple 0 25 → Code de Shannon-Fano-Elias : autre exemple

[PDF] codage de huffman exercice corrigé

[PDF] codage arithmétique pdf

[PDF] codage arithmétique algorithme

[PDF] représentation des nombres signés exercices corrigés

[PDF] exercice de systeme de numeration

[PDF] système binaire informatique

[PDF] calcul nombre binaire

[PDF] cours sur le calcul binaire pdf

[PDF] codage et représentation de l'information exercices corrigés

[PDF] le codage informatique

[PDF] exercice corrigé codage source

[PDF] combien d'information sont représentées par 15 bits

[PDF] virgule fixe et virgule flottant pdf

[PDF] virgule fixe exercices corrigés

[PDF] exercice corrigé codage virgule fixe

Faculté des sciences et de génie

Département de génie électrique et de

génie informatique

Mohamed Haj Taieb

Local: PLT 2113

Courriel: mohamed.haj-taieb.1@ulaval.ca

Compression de données

IFT-4003/IFT-7023

Notes de cours

Codage de Huffman

Édition Hiver 2012

IFT-4003/7023 Compression de données Mohamed Haj Taieb, Département de génie électrique et de génie informatique

Plan

‡Codage de Huffman:

‡Codage de Shannon-Fano

‡Procédure de construction des codes de

Huffman

‡Extension des codes de Huffman

‡Code de Huffman non binaires

‡Codes de Huffman adaptatif

‡Codes de Golomb

IFT-4003/7023 Compression de données Mohamed Haj Taieb, Département de génie électrique et de génie informatique

Codage de Shannon-Fano

Shannon.

‡Code développé en 1960 par Claude E. Shannon (MIT) et

Robert M. Fano (Laboratoires de Bell).

‡Assignation du code selon la probabilité de chaque symbole. ‡Algorithme simple avec des performances élevées. moyenne des mot code. ‡A partir de ce code un étudiant gradué a développé un autre

IFT-4003/7023 Compression de données Mohamed Haj Taieb, Département de génie électrique et de génie informatique

Algorithme de Shannon-Fano

1.Détermination des probabilités de chacun des symboles soit

par mesure ou soit par estimation. croissant ou décroissant. ayant une différence de probabilité minimale. le second sous-groupes.

5.Réitérer à la 3ème étape en subdivisant les sous-groupes.

singleton.

IFT-4003/7023 Compression de données Mohamed Haj Taieb, Département de génie électrique et de génie informatique

Exemple: codage de Shannon-Fano (1)

a m

Lettres a b c m r s

Fréquence 9 3 6 8 5 7

s c r b

9 8 7 6 5 3

9 28 28-9= 19

15 20 20-15= 5

24 14 24-14= 10

Étape 1:

calcul des fréquences

Étape 2:

ordonner les fréquences

Étape 3:

Division en

groupes de fréquences rapprochées

IFT-4003/7023 Compression de données Mohamed Haj Taieb, Département de génie électrique et de génie informatique

Exemple: codage de Shannon-Fano (2)

a m s c r b

9 8 7 6 5 3

0 1 a m 9 8 s c r b

7 6 5 3

0 0 1 1 1 1

IFT-4003/7023 Compression de données Mohamed Haj Taieb, Département de génie électrique et de génie informatique

Exemple: codage de Shannon-Fano (3)

a m s c r b

9 8 7 6 5 3

0 1 s c r b

7 6 5 3

00 01 1 1 1 1

a m 9 8 0 1

IFT-4003/7023 Compression de données Mohamed Haj Taieb, Département de génie électrique et de génie informatique

Exemple: codage de Shannon-Fano (4)

a m s c r b

9 8 7 6 5 3

0 1 s c r b

7 6 5 3

00 01 1 1 1 1

a m 9 8 0 1

IFT-4003/7023 Compression de données Mohamed Haj Taieb, Département de génie électrique et de génie informatique

Exemple: codage de Shannon-Fano (5)

a m s c r b

9 8 7 6 5 3

0 1 s c r b

7 6 5 3

00 01 10 10 11 11

a m 9 8

0 1 0 1

IFT-4003/7023 Compression de données Mohamed Haj Taieb, Département de génie électrique et de génie informatique

Exemple: codage de Shannon-Fano (6)

a m s c r b

9 8 7 6 5 3

0 1 s c r b

7 6 5 3

00 01 10 10 11 11

a m 9 8

0 1 0 1

IFT-4003/7023 Compression de données Mohamed Haj Taieb, Département de génie électrique et de génie informatique

Exemple: codage de Shannon-Fano (7)

a m s c r b

9 8 7 6 5 3

0 1 s c r b

7 6 5 3

00 01 100 101 110 111

a m 9 8

0 1 0 1

0 1 0 1

Code assigné:

Condition

Sous groupes

formés par des singletons

IFT-4003/7023 Compression de données Mohamed Haj Taieb, Département de génie électrique et de génie informatique

Remarques: codage de Shannon-Fano

Lettres a b c m r s

Fréquence 9 3 6 8 5 7

Code 00 111 101 01 110 100

Probabilité 0.23684 0.078947 0.15789 0.21053 0.13158 0.18421

Longueur moyenne du code: 2.5526

Entropie de la source: 2.5096

IFT-4003/7023 Compression de données Mohamed Haj Taieb, Département de génie électrique et de génie informatique

Code de Huffman

optimale. ‡Le code de Huffman est code presque aussi simple que le code de Shannon-Fano. ‡Le code de Huffman est optimal et il est basé sur deux observation: ‡Dans un code optimal, on assigne moins de bits aux symboles les plus fréquents et plus de bits au symboles les moins fréquents. ‡Dans un code optimal, les deux moins fréquents symboles ont la même longueur.

IFT-4003/7023 Compression de données Mohamed Haj Taieb, Département de génie électrique et de génie informatique

Longueur du code de Huffman (1)

la source (code optimal). Cependant il faut que chaque mot code puisse être représenté par un nombre entier de bits. ‡Ceci étant possible si les probabilités des symboles sont des puissances négatives de 2, i.e.: 2-1, 2-2 .. McMillan. Soit C un code uniquement décodable formé par

K mots code de longueurs li=1..K alors:

( ) ( ) 1moyH S l H S 121i
Kl i

IFT-4003/7023 Compression de données Mohamed Haj Taieb, Département de génie électrique et de génie informatique

Longueur du code de Huffman (2)

‡Soit un code 1 qui est uniquement décodable et un code 2

‡Code 1:

‡Code 2:

Lettres a b c m r s

Code 1 00 111 101 01 110 100

Code 2 00 11 10 01 110 100

2 3 3 2 3 3

12 2 2 2 2 2 2 1 1i

Kl i

2 2 2 2 3 3

12 2 2 2 2 2 2 1.25 1i

Kl i

IFT-4003/7023 Compression de données Mohamed Haj Taieb, Département de génie électrique et de génie informatique

Longueur du code de Huffman (3)

Huffman:

‡La bande supérieure est en fait un peu lousse. En effet soit une liste de symboles tel que la probabilité maximale ( ) ( ) 1moyH S l H S max max max max ( ) ( ) , 0.5 ( ) ( ) 0.086, 0.5 moy moy

H S l H S p p

H S l H S p p

IFT-4003/7023 Compression de données Mohamed Haj Taieb, Département de génie électrique et de génie informatique

*pQpUMPLRQ G·XQ ŃRGH GH Huffman (1)

Lettres a b c d e

Probabilité 0.2 0.4 0.2 0.1 0.1

Code 0 1

b(0.4) a(0.2) c(0.2) e(0.1) d(0.1) de(0.2) 0 1 c(0.2) a(0.2) b (0.4)

IFT-4003/7023 Compression de données Mohamed Haj Taieb, Département de génie électrique et de génie informatique

*pQpUMPLRQ G·XQ ŃRGH GH Huffman (2)

Lettres a b c d e

Probabilité 0.2 0.4 0.2 0.1 0.1

Code 0 10 11

b(0.4) a(0.2) c(0.2) e(0.1) d(0.1) de(0.2) 0 1 c(0.2) a(0.2) b (0.4) 0 1 dce(0.4) a(0.2) b (0.4)

IFT-4003/7023 Compression de données Mohamed Haj Taieb, Département de génie électrique et de génie informatique

*pQpUMPLRQ G·XQ ŃRGH GH Huffman (3)

Lettres a b c d e

Probabilité 0.2 0.4 0.2 0.1 0.1

Code 1 00 010 011

b(0.4) a(0.2) c(0.2) e(0.1) d(0.1) de(0.2) 0 1 c(0.2) a(0.2) b (0.4) 0 1 dce(0.4) a(0.2) b (0.4) 0 1 adce(0.6) b(0.2)

IFT-4003/7023 Compression de données Mohamed Haj Taieb, Département de génie électrique et de génie informatique

*pQpUMPLRQ G·XQ ŃRGH GH Huffman (4)

Lettres a b c d e

Probabilité 0.2 0.4 0.2 0.1 0.1

Code 01 1 000 0010 0011

b(0.4) a(0.2) c(0.2) e(0.1) d(0.1) de(0.2) 0 1 c(0.2) a(0.2) b (0.4) 0 1 dce(0.4) a(0.2) b (0.4) 0 1 adce(0.6) b(0.4) 0 1

Longueur moyenne: 2.2

adceb(1)

IFT-4003/7023 Compression de données Mohamed Haj Taieb, Département de génie électrique et de génie informatique

*pQpUMPLRQ G·XQ ŃRGH GH Huffman avec un arbre

Lettres a b c d e

Probabilité 0.2 0.4 0.2 0.1 0.1

Code 01 1 000 0010 0011

0 1 b a 0 1 0 1 c d e 0 1

IFT-4003/7023 Compression de données Mohamed Haj Taieb, Département de génie électrique et de génie informatique

Remarques: Code Huffman (1)

Lettres a b c d e

Probabilité 0.2 0.4 0.2 0.1 0.1

quotesdbs_dbs4.pdfusesText_8