[PDF] [PDF] MSY06 : Théorie de lInformation TD n◦2 : Codage de source

[PDF] correction - Formations en Informatique de Lille

Veuillez indiquer le numéro de votre groupe de TD sur la copie qu'il est inutile de C'est impossible car la longueur moyenne d'un codage c sur une source S est Corrigé L est un code car il s'agit d'un langage préfixe En effet, ∀u, v ∈ L, 

[PDF] THEORIE DE LINFORMATION CORRIGES - E-Eisti

TD 1 Corrigé Modélisation mathématique d'une source d'information Remarque : on verra au chapitre 3 (Codage de source) avec l'inégalité de Kraft, qu'un 

[PDF] Série dexercices 2 : code de Huffman Problème 1 Problème 2

(e) Calculer l'efficacité de ce code Problème 2 Soit une source qui génère des lettres de l'alphabet A= {a1, a2,a3, 

[PDF] Examen C++ - CREATIS

I - Exercice codage de source (25 minutes) Une source binaire génère les symboles s1 et s2 avec les probabilité p(s1)=0,9 et Code corrigé : 11 10 01 00

[PDF] MSY06 : Théorie de lInformation TD n◦2 : Codage de source

TD n◦2 : Codage de source Exercice 1 : Compression des images En considérant que chaque pixel est codé sur un octet, quelle place occupe l' imagette 

[PDF] Cours/TD 3 Codage Huffman

`A chaque étape la somme des poids restera égale `a 1 L'algorithme de Huffman produit un code binaire préfixe optimal Exemple Considérons une source discr`  

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

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

[PDF] TD 1 ∑ - Raphaël Fournier-Sniehotta

TD 1 TECHNIQUES DE CODAGE ET DE COMPRESSION 1 LANGAGE / CODAGE / +1 2 3 1 Donner un code de Shannon binaire pour la source ci- dessus

[PDF] Codage canal - FR

21 nov 2012 · Codage source : compression des données pour une meilleure efficacité ▫ Codage Corriger les erreurs : FEC (Forward Error Correction) protocoles de Exercice: construire le tableau de décodage standard ▫ Exercice: 

[PDF] Corrigés exercices codes correcteurs - LIRMM

Le code par parité impaire n'est pas linéaire, sa capacité de détection est de 1 bit , pour tout n Exercice 4: a: toute erreur sur un nombre impair de bit Pas de 

[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

[PDF] virgule fixe et virgule flottant

[PDF] nombre flottant binaire

[PDF] codage et décodage définition

[PDF] définition décodage

[PDF] encodage décodage définition

[PDF] codage et décodage de l'information

[PDF] encodage décodage lecture

[PDF] encodage décodage lecture définition

[PDF] encodage definition

Théorie de l"Information

Année 2017 - 2018

L1 Semestre 2TD 2 : Information selon Shannon et codage optimal

1 Inégalité de Kraft (suite)

Exercice 1

1.

Utilisez l"inégalité de Kraft p ourmon trerqu"il est p ossiblede construire u nco depréfixe binaire

pour les caractèresa:::favec les longueurs de code suivants :caractèreabcdef longueur234243 2. Construisez effe ctivementun arbre de co dagep ourcet exemple. 3. V ousconstatez qu"un co den"est pas utilis é.Lequel ? 4.

Évidemmen t,une telle situation est em bêtantesurtout p ourle déco dagede mess ages(certains

messages ne peuvent pas être décodés). Montrez que tout alphabet fini avec au moins deux ca-

ractèresA1peut être codé par un code préfixe binaire, donc par une fonctionc:A1! f0;1g+,

de telle manière qu"il n"y ait pas de codes non utilisés. (Bien sûr, ceci n"est pas possible pour

n"importe quelles contraintes sur les longueurs des codes.) Donnez un tel code pour les caractères

a:::f. 5. Mon trezque ceci n"est pas toujours p ossiblesi on utilise un co deternaire (donc un arbre d e décodage ou chaque noeud est une feuille ou a exactement trois successeurs).

2 Entropie et longueur de codes

Exercice 2Dans cet exercice, nous nous intéressons à un codage des caractèresa;b;c;dpar des séquences

de nombres binaires, et du temps de transmission d"un texteTde 100 caractères sur le canalCqui peut

transmettre 20 bit/sec, donc 20 chiffres binaires par seconde. 1.

Supp osonsque l"o ccurrencedes caractères est équiprobable, et que les caractères a;:::dsont codés

par00;:::11respectivement. Combien de temps faut-il pour communiquer le texte sur le canalC? 2.

Supp osonsmain tenantun esource d"information Sdont la probabilité des caractères est indiquée

dans ce tableau :caractèreabcd probabilité0.50.20.20.1 et que nous continuons à coder les caractères comme dans ( 1 ). Quelle est l"espérance de la taille du code du texteT, et, en moyenne, son temps de transmission surC? 3. Nous essa yonsd"optimiser et nous prop osonsle co desuiv ant: caractèreabcd code0101101110 Vérifiez bien qu"il s"agit d"un code préfixe! Pour la distribution de probabilité de ( 2 ), nous posons de nouveau la question de la taille moyenne deTet du temps de transmission surC. 4.

Calculez l"en tropiede la source Sde (2) pour obtenir une borne inférieure du temps de transmission

deTsurC. 5.

Il s"a vèreque le co dede (

3 ) n"est pas encore optimal. Utilisez l"algorithme de Huffman pour calculer un code optimal. Comparez avec l"entropie.

Théorie de l"Information 2017 - 2018 1 TD 2

Exercice 3Une source d"information émet les caractèresa,b,c,dselon la distribution de probabilité

suivante :abcd

0.40.20.30.1

1. Quelle est l"en tropiede cette source d"information ? 2. Construisez l"arbre de Huffman et attribue zun co debinaire optimal à c hacundes caractères a,b,c,d. Calculez la taille moyenne du code, et comparez-la à l"entropie. 3.

Un collègue v ousdit qu"il arriv eà co derun texte de 24 caractères a vec18 bits. V ouslui dites qu"il

se trompe. Quelle est votre justification? 4. V otrecollègue v ousprésen teun exemple : aaaaaaaaccccccccbbbbddddcodé par

00111.10111.0111.1111. Son idée : Coder les caractèresa...dpar00...11, suivi du nombre

n1codé en binaire, pournoccurrences consécutives du caractère. Par exemple, ceci donne0111 pour la séquence de 4b. Où est le malentendu?

Exercice 4Les deux parties du théorème de Shannon donnent des bornes (inférieure et supérieure) pour

un code optimal, en fonction de l"entropie de la source d"information que le code est censé coder. Cet

exercice a pour but d"explorer ce rapport plus en détail. 1.

Une source émet les caractères a,b,c,d,eselon la distribution de probabilité suivante :abcde

1 21
41
81
161
16 Construisez l"arbre de Huffman, calculez la taille moyenne du code et comparez avec l"entropie.

Constat?

2.

V ousobserv ezque toutes les p robabilitésde l"exemple précédan ton tla forme 2k. A quelle pro-

fondeur de l"arbre de codage se trouve un caractère dont la probabilité est2k? 3. F aitesde même p ourla distribution suiv ante: abcde 1 31
41
52
151
12 4.

Nous généralisons l"observ ationdu p oint(

1 ) : Supposons qu"une source d"information émet les

caractèresc1:::cnavec des probabilités associéesp1:::pnqui sont toutes des puissances négatives

de 2, donc de la formepi= 2kiet telles quePn i=ipi= 1. Alors, la taille moyenne du code construit par l"algorithme de Huffman est égale à l"entropie de la source. Pour cela, nous montrons les invariants suivants de l"algorithme de Huffman pour l"ensemble

A=fa1:::atgdes arbres qu"il manipule :

(a) A tout instan t,tout arbre de l"ens embleAa une racine avec une valeur qui est de la forme 2 k. (b) T antqu"il existen tencore deux arbres dans l"ensem bleA, il existent au moins deux arbres dans

Adont la probabilité est minimale.

(c)

A tout instan t,l"en tropiede la source est égale à lc(a1) +:::lc(at), où, pour un arbreaavec

racine2k, nous définissonslc(a) =lnm+k(cpf(a)), etcpfest défini comme sur les transparents du cours etlnm+k(E) =P (m;p)2Ep(jmj+k). Assurez-vous que ces propriétés tiennent pour l"exemple du point ( 1 ). Démontrez ensuite qu"il

s"agit d"un invariant, à savoir, que les propriétés sont satisfaites au début de l"algorithme; qu"elles

sont préservées par chaque itération; et qu"à la fin, l"invariant implique la proposition (égalité de

la taille moyenne et de l"entropie). 5.

En applican tun raisonnemen tsimilaire au p oint(

4 ), vous pouvez généraliser ( 3 ) et montrer que si

deux caractères ont des probabilités qui ne sont pas des puissances négatives de 2, alors l"algorithme

de Huffman construit un arbre dont la longueur moyenne est strictement supérieure à l"entropie.

Théorie de l"Information 2017 - 2018 2 TD 2

quotesdbs_dbs4.pdfusesText_7