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

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

Cours/TD 5 Codage Shannon Codage arithmétique : Elias 5 1 De l'algorithme de Fano et Shannon au codage arithméthique Si N-1 ∑ j=0 2-lj < 1 l'inégalité 

[PDF] Codage statistique

cet exemple, l'efficacité du code binaire naturel est donc de seulement 3 2,552 = 85 Page 14 Chapitre 5 CODAGE STATISTIQUE Codage Arithmétique 

[PDF] Compression par codage arithmétique

Le codage de HUFFMAN présente certains défauts (malgré son optimalité codage arithmétique permet de s'affranchir de ces limites et, par exemple, de coder 

[PDF] Notes de cours - ULaval

codage arithmétique Édition Hiver 2012 Première étape: décider de la longueur du mot code m Comme on utilise maintenant une arithmétique entière

[PDF] Principes généraux de codage entropique dune sourcepdf

II - Définitions et résultats fondamentaux liés au codage de source 11 III - Les algorithmes de codage statistiques 13 IV - Algorithme de codage arithmétique

[PDF] Codage dHuffman, Lempel-Ziv, arithmétique

Huffman Codage arithmétique données Mots de code courts pour les symboles probables Les fichiers PDF (version 1 4 et supérieure) peuvent contenir 

[PDF] Décodage MVP des Codes Arithmétiques - SETIT 2021 9th

Mots clés: Algorithme SA, Codage arithmétique, Codage Conjoint Source Canal, Codage SPIHT Le principe de décodage MVP d'un code arithmétique

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

i e codage de Shannon−Fano, codage de Huffman, codage par plage, codage arithmétique, etc ¢ c £ 1 fichiers au format PDF ; • − fichiers Z, zip, gzip, 

[PDF] ProQuest Dissertations - CORE

3 3 Construction du code binaire 30 3 3 1 Codage de Huffman 30 3 3 2 Codage a base de dictionnaire 33 3 3 3 Codage arithmetique 35 3 3 4 Codage par 

[PDF] Un nouvel algorithme de compression exploitant le codage - LIRMM

25 déc 2002 · codage arithmétique en lui introduisant de nouveaux Mots clefs : Codage arithmétique, Compression, sans perte, entropie, table de 

[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

[PDF] virgule flottant ieee 754

[PDF] conversion des nombres avec virgule en binaire

Cours/TD 5 Codage Shannon.

Codage arithmetique : Elias

5.1 De l'algorithme de Fano et Shannon au codage

arithmethique Si N1X j=02 lj<1 l'inegalite de Kraft-McMillan est veriee, alors il existe un code uniquement decodable et m^eme prexe, qui admette l

1;l2;:::;lN1comme distribution de longueurs. Un algorithme simple qui donne un code

prexec1;:::;cN1a partir d'une distribution de longueursl1;l2;:::;lN1veriant l'inegalite de Kraft-McMillan est :a chaque mot de codeci(a trouver) on associe le nombre= 0;c i2 [0;1[dont les decimales de l'ecriture en base 2 est formee des bits deci. On noteIil'intervalle I i= [c i;c i+ 2li[.

Exemple.ci= 010donnec

i= 0;010 = 14 . etIi= [0;010;0;011[= [14 ;38 [est l'ensemble des nombres de[0;1[dont les decimales en base 2 commencent parci. Le mot codecidetermine uniquement l'intervalleIi: tronquer le developpement binaire de la limite gauche de l'intervalle (de longueurli) a log21l ibits pour retrouverci. La condition de code prexe deviennent : lesIisont des intervalles disjoints. Donc l'inegalite de Kraft- McMillan dit que la somme des longueurs desIiest strictement plus petite que 1. S'ils sont disjoints, on peut donc les mettre bout-a-bout en restant dans le segment [0;1[. Ainsi un algorithme de construction du code instantane sera : On met bout-a-bout les intervallesIi, classes par longueurs decroissantes (licroissantes) dans le segment [0;1[ en partant de la gauche.

I1 I2 I3 ....

||{I|||{I||{I||||{ 0.0 0.10 0.110 0.111

Au debutc

0= 0:0:::0. En general a chaque etape on rajoute aci1un 1 et on obtientc

il' extremite droite deIi. On peut completer avec des zeros si necessaire pour obtenir une longueurli+1> li. 1 Exemple.Soit une source discrete sans memoire codee avec des mots code avec de longueurs l il icode1 0 2 10 3 110

5 11100

5 11101

5 11110

6 111110

6 111111

Noter qu'avec cet algorithme on detecte automatiquement si si les li ne verient pas l'inegalite de Kraft-McMillan : on "depasse" alors l'extremite droite du segment[0;1[, et on ne peut plus continuer comme dans : l icode1 0 2 10 3 110

4 1110

5 11110

5 11111

6Erreur

1=2 + 1=4 + 1=8 + 1=16 + 1=32 + 1=32 + 1=64>1

Soit une source discrete et sans memoire produisant (independament) des symboles (lettres/mots) d'un alphabeta0;a1;;aN1selon la distribution de probabilitep= (p0;p1;:::;pN1) . Supposons que les symboles de l'alphabet sont deja ordonnes par probabilite decroissante. p

0p1 pN1.

Idee naturelle (Shannon et Fano) etait d'associer aux symboles de notre alpha- bet des mots code binaires dont la longueur est egale au contenu d'information des symboles a coder. Pour un symbolajavec une probabilites d'apparitionpjqui n'est pas une puissance binaire ce contenu d'information estI(aj) =log2pjet Shannon demande que la longueur de bits necessaires soitlj=dI(aj)e=dlog2pje. L'interpretation geometrique de l'algorithme de Fano : Par la suite d'une dichotomie binaire reitteree sur [0, 1 [l'algorithme de Fano trouvait une partition d'intervalles. La dichotomie d'un interval s'arr^etait quand l'intervalle [Aj;Aj+1[ avait la longueur egale a la probabilite 2 ljde ( la production de ) du symbolaj(i.e. un seul 2 2/8 [1/20 11 100
1

4/8 6/8

110
111

7/82/4 3/41/4

5/83/81/8)Figure5.1 { Arbre partiel de dichotomie binaire reitere de [0;1) pourp=12

;14 ;18 ;18 element par intervalle). Le mot code etait le developpement binaire ni de la borne inferieure A jde cet intervalle. La precision de ce mot etait exactementlj=log2pj{ voir gure 5.1. L'algorithme simplie de Fano peut ^etre lui aussi generalise mais le code produit n'est pas unique, ni optimal.

1. ordonner les symboles de l'alphabet sur une colonne par probabilite decroissante.

2. diviser l'ensemble des symboles en deux sous-ensembles de probabilites cumulees presque

egales.

3. coder avec "0" (resp. "1") les elements du premier (resp. deuxieme) sous-ensemble

4. continuer de maniere recursive jusqu'au moment ou tous les sous-ensembles ne com-

portent plus qu'un element D'une maniere plus generale l'algorithme de Shannon associe aussi d'une maniere biuni- voque : { aux symboles de l'alphabet une partition d'intervalles dans [0;1[ { a un symbol un mot code qui est un nombre reel dans l'intervalle correspondant.

5.2 Algorithme de Shannon

L'interpretation geometrique de l'algorithme de Shannon est de trouver une partition d'intervalles avec la propriete que la longueur de chaque intervalle [Aj;Aj+1[ est egale a la probabilite de ( la production de ) du symbolaj:pj= A j+1Aj, 0jN1. A 0= 0 A 1=p0 A

2=p0+p1

3 A

3=p0+p1+p2...

A

N=p0+p1++pN1= 1

Un mot codecjest associe a l'intervalle [Aj;Aj+1[[0;1[ de la maniere suivante : c(Aj;Aj+1) =12:::lj()A= 0:12:::lj( debut du developpement binaire du nombre reelAj), avec l j=dlog2(pj)e. On prend autant de bits de ce developpement que le "contenu d'information de l'intervalle" l jle dicte. Maintenant pour assurer la correspondance biunivoque il faut prouver que le mot code associe a un intervalle [Aj;Aj+1[ est unique. Plus on peut montrer que : Lemme1.Le code Shannon est prexe, i.e. le mot codecj=c(Aj;Aj+1)ne peut pas^etre un prexe du motcj+1=c(Aj+1;Aj+2), pour0jN2. Preuve.Supposons que le codage binaire deAja la longueurlj=dlog2pje.

Reecrivons les conditions de Shannon :

l j1Par constructionAkAj+1=Aj+pjAj+12 lj. DoncAkAj12 lj, i.e. leurs developpements binaires sont dierents sur les premiersljpositions. Par consequence le mot codecjn'est pas un prexe du mot codeck,j < k. Remarque.On note que on peut dire aussi que le codage Shannon-Fano associe au symbol a jle bits du plus petit (i.e. celui avec moins de bits) nombre binaire rationnel de l'interval [Aj;Aj+1[.

Algorithme de Shannon1. ordonner les symboles de l'alphabet sur une colonne par probabilite decroissante.

2. calculerA0= 0 etAj+1=Aj+pj

3. pour chaque 0jN1 ecrire le developpement dyadiqueA= 2Ajjusqu'au

l j=dlog2pje"decalage de la virgule " { siA1, alors1= 1 etA= 2A1 { siA1, alors1= 0 etA= 2A

4. acherAj= 0:1234:::lj

Exemple.Trouver le developpement binairea= 0:1234:::dea=111 4

2a=211

<1 =)1= 0, 4a=411 <1 =)2= 0

8a=811

<1 =)3= 0, 16a=1611 = 1 +511 =)4= 1 a (4)=511 = 0:567:::, 2a(4)=1011 <1 =)5= 0

4a=2011

= 1 +911 =)6= 1 a (6)=911 = 0:789:::, 2a(6)=1811 = 1 +711 =)7= 1 a (7)=711 = 0:8910:::, 2a(7)=1411 = 1 +311 =)8= 1 a (8)=311 = 0:91011:::, 2a(8)=611 <1 =)9= 0

4a(8)=1211

= 1 +111 =)10= 1 a (10)=111 = 0:111213=a. Le developpement binaire ( 10-periodique ) dea=111 = 0:0001011101

Exercice.Trouver les mots codec(A;B)suivants :

1.c111

;15 2.c38 ;12

3.c112

;78 4.c35 ;34 5.c17 ;16

1.c111

;15 Premier pas :Determiner la precision du developpement dyadique. La longueur du codage est donnee par l'information qui correspond a l'intervalBA=15 111
=655 . Doncdlog2556 e=

4, parce que 8<556

<16. 111
= 0:1234 Deuxieme pas :Obtenir le developpement binaire du nombreA=111 qui est entre 0 et 1.

Donc111

= 0:0001=)c111 ;15 =1234= 0001 2.c38 ;12 Premier pas :Determiner la precision du developpement dyadique. La longueur du codage est donnee par l'information qui correspond a l'intervalBA=18 . Donc log28 = 3. 38
= 0:123 5 Deuxieme pas :Obtenir le developpement binaire du nombreA=38 qui est entre 0 et 1. 238
=1:23 238
=68 <1 =)1= 0 et68 = 0:23 268
=2:3 268
=128 = 1 +48 = 1 +12

1 =)2= 1 et12

= 0:3 212
=3 212
= 1 =)3= 1 =)c38 ;12 =123= 011 Exercice.Determiner tous les intervalles[A;B[tels quec(A;B) = 10101. ( Chercher d'abord l'intervalle le plus naturel determine par10101, puis re echir dans quelle mesure ceci est "deformable" sans eet sur le mot code ). Exercice.Considerons la source qui produit les huit lettresa0;a1;:::;a7selon la distribution de probabilitep= (p0;p1;:::;p7)avecp0=12 ,p1=14 ,p2=p3=116 ,p4=p5=p6=p7=132

Trouver le code de Shannon associe.

Exercice.Notre source sans memoire qui produit les huit lettres A, B, C, D, E, F, G, H selon la distribution de probabilitep= (p(A);p(B);:::;p(H)), avecp(A) =2764 ,p(B) =p(C) =316 p(D) =116 ,p(E) =p(F) =364 ,p(G) =132 ,p(H) =164

1. Trouver le code de Shannon associe.

2. Calculer la longueur moyenneldes mots code.

5.3 Coder plusieurs symboles successifs en m^eme temps

Pour le codage Human nous avons deja vu que le codage par blocs densymboles permet de prendre en compte plusieurs symboles en m^eme temps. C'est un codage vectoriel (en dimensionn) qui remplace la source initiale par une "extension d'ordren" ayant comme symboles des vecteurs densymboles successifs de la source initiale. Le theoreme de Shannon pour le codage de source sans pertes propose de realiser un codage vectoriel en grande dimension pour toute source. pour s'approcher de l'entropie. Pour coder une source discrete sans memoire sur un alphabet aNsymboles en dimensionn l'alphabet de l'"extension d'ordren" augmente exponentiellement avecn. Donc, le codage vectoriel en grande dimension est d'un inter^et purement theorique. 6 Pour resoudre ces problems d'autres systemes de codage de source sans pertes ont ete proposes. Ils permettent aussi de prendre en compte les dependances temporelles (d'un sym- bole a l'autre) de la source (avec memoire). Ces systemes de codage permettent de coder une source quelconque sans conna^tre a priori ses statistiques (c'est ce qu'on appelle du codage "universel"). Les plus connus sont les systemes de codage de Lempel-Ziv (1976)et de codage arithmetique (1982). Le codage arithmetique est probablement le plus important dans les applications et les normes actuelles. Il est une extension iterative d'une technique de codage connue depuis les annees 50, appelee codage d'Elias (ou de Shannon-Fano-Elias).

5.4 Le codeur d'Elias

Le codeur d'Eliasetait, a l'origine, considere comme une construction purement academique. Sa premiere presentation ( tardive ) date de 1968. C'est entre 1976 et 1979 ( Pasco, Jones, Rubin ) que l'on decouvrit son inter^et pratique de sa variantebinaire!binaire. Le codeur d'Elias code optimalement, c.ad. il approche l'entropie de la source :

H(p)ln

< H(p) +1n Soit une source binaire ( sans memoire ), produisant selon la distribution de probabilite p= (p0;p1), avecp0p1. Le codeur d'Elias construit un arbre binaire d'intervalles, obtenu parp0-dichotomie. Soit les intervalles [Ak;Bk[ les intervalles [Ak+1;Bk+1[ sont calcules :

D=Ak+p0(BkAk)

A k+1=Ak;Bk+1=D(code avec 0) etAk+1=D;Bk+1=Bm(code avec 1)

Lesnpremiers bitsaj1aj2:::ajnd'un

ot source binaire sont interprete commeche- mindans cet arbre. Le chemin pointe sur un intervalle [A;B[. Le motcode d'Elias c(aj1aj2:::ajn) est le mot code de l'intervalle [A;B[, c.a.d. le developpement dyadiqueA jusqu'aul=dlog21BAe"decalage de la virgule " Exemple.Soit une source binaire ( sans memoire ) produisant selon la distribution de probabilitepdonnee parp0=34 ,p1=14 Trouvez le mot code d'Elias de la sequence 001 produite par la source, c.a.d. de l'intervalle 2764
;916 Premier pas: Pour le codage, il faut trouver dans l'hierarchie de l'arbre dep0dichotomie le chemin ("poupee russe") d' intervallesembo^tesqui correspond a la sequencesproduite par la source. Calcul deD=34 = 0:11 s

1= 0 et doncA1= 0;B1=34

7

Calcul deD=916

= 0:1001 s

1s2= 00 et doncA2= 0;B2=916

Calcul deD=2764

= 0:011011. s

1s2s3= 001 et doncA3=2764

;B3=916 Deuxieme pas :Determiner la precision du developpement dyadique. La longueur du codage est donnee par l'information qui correspond a l'intervalBA=916 2764
=964 . Donc log 2649
= 0:123 Troisieme pas :Obtenir le developpement binaire du nombreA=2764 qui est entre 0 et 1. 22764
=1:23 22764
=2732 <1 =)1= 0 et2732 = 0:23 22732
=2:3 22732
=2716 = 1 +1116

1 =)2= 1 et1116

= 0:3 21116
=3 22216
>1 =)3= 1 =) 2764
;916 [=123= 011 Exemple.Soit une source binaire ( sans memoire ) produisant selon la distribution de probabilitepdonnee parp0=34 ,p1=14

Decodez le mot code d'Elias : 1000000.

Notre intervalle est [An;Bn[ avecAn= 0:1000000et12

7(BnAn)<12

6. Pour le decodage, il faut retracer les decisions ducodeurdans l'hierarchie de l'arbre de p

0dichotomie : un codage est decrit par une "poupee russe" d' intervallesembo^tes.

Premier pas: Calcul deD=34

= 0:11 A n< D=)[An;Bn[[0;D[l'intervalle de 0. 8

0001 1110

0 110

1113/4

1 3/4 10

027/64 9/16 45/64 3/4 57/649/16

1

000 001 010 011 100 1011

0

15/16 63/64

15/16Figure5.2 { Arbrep0dichotomique

=)s1= 0 etA1= 0;B1=34

Deuxieme pas: Calcul deD=916

= 0:1001 A n< D=)[An;Bn[[0;D[l'intervalle de 00. =)s1s2= 00 etA2= 0;B2=916

Troisieme pas: Calcul deD=2764

= 0:011011. D < A n=)[An;Bn[[D;B2[l'intervalle de 001. =)s1s2s3= 001 etA3=2764 ;B3=916

Quatrieme pas: Calcul deD=135256

= 0:10000111 A n< D=)[An;Bn[[A3;D[ l'intervalle de 0010. =)s1s2s3s4= 0010 etA4=2764 ; B4=135256

Cinquieme pas: Calcul deD=5131024

= 0:1000000001.AnetDont lem^eme developpement binaire - jusqu'a la partie masquee deAn. Pour un decodage coherent et logique d'un code prexe on considereAn=Dets5= 1 ( c.ad. [An;Bn[[D;B4[ ). Alors on a trouve un ot sourcequotesdbs_dbs12.pdfusesText_18