Cours/TD 5 Codage Shannon Codage arithm etique : Elias
Cours/TD 5 Codage Shannon Codage arithm etique : Elias 5 1 De l’algorithme de Fano et Shannon au codage arithm ethique Si NX 1 j=0 2 l j
Codage de Source à longueur variable
Codage de Shannon-Fano Utilisé dans les années cinquante, le code de Shannon-Fano est le premier code à avoir exploité la redondance d'une source L'algorithme de Shannon-Fano consiste à faire en sorte que les éléments binaires composant les mots code apportent une quantité d'information moyenne la plus grande possible
Théorème de Shannon (codage source)
Codage source M J Rendas Codage Source Propriété d’équi-répartition assymptotique Pour n ˛ 1 , x(n) (symboles iid d’une source X) appartient presque surement à un sous-ensemble de X qui contient seulement 2nH(X) éléments, chacun avec une probabilité proche de 2−nH(X) Équivalente au Théorème de Shannon: Codage source
Notes de cours Codage de Huffman - Université Laval
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
Principes généraux de codage entropique dune source
Exemple : Algorithme de Shannon-Fano Méthode : Algorithme de Huffman Comme pour le codage de shannon-Fano, les probabilités d'apparition des symboles sont placées dans un tableau trié par ordre décroissant de probabilités L'algorithme de Huffman est implémenté suivant une structure d'arbre
Chap 1: Codage Source Rhouma Rhouma https://sitesgooglecom
Théorème de Shannon : Pour avoir un codage sans erreur, une 7 Limitations de Fano-Shannon et Huffman et Supériorité de LZW 8 Code par répétition 20/55
Cours/TD 2 Codage ”proche de l’entropie”
Un algorithme similaire d´ecouvert de mani`ere ind´ependante par Shannon permet de trou-ver un code binaire pr´efixe unique Le codage Shannon, et celui de Fano ont ´et´e remplac´ees par celui de Huffman qui propose des codes plus proches de l’entropie Mais, le codage du
Codage et compression - Inria
2 1 Codage de Shannon-Fano Le codage de Shannon-Fano est un codage pr´efixe binaire optimisant la taille d’une source I e si on appelle source une s´erie de symboles, alors il existe diff´erentes fa¸cons de repr´esenter cette source, le codage de Shannon-Fano cherche une mani`ere r´eduisant le nombre de bits n´ecessaires pour faire
TCM - ResearchGate
Codage de Shannon-Fano - Algorithme de génération d'un codage optimal symbole par symbole - Code à longueur variable codes longs pour probas faibles Extraction des probabilités
Introduction à la Théorie de l’Information
Théorie de l'Information 2 Plan Quantité d’information et entropie d’une source Le codage de source • Théorème du codage de source • Codage de Shannon-Fano • Codage binaire de Huffman • Codage Arithmétique • Codage LZ78 Introduction au codage de canal • Codes linéaires • Codes cycliques • Codes convolutifs Conclusion
[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
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 l1;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.111Au 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 1105 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 1104 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. p0p1 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 1001
4/8 6/8
110111
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 A2=p0+p1
3 A3=p0+p1+p2...
AN=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 j1Algorithme de Shannon1. ordonner les symboles de l'alphabet sur une colonne par probabilite decroissante.