Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Examen du cours de Theorie de l'Information et Codage Temps imparti: 3h

De
3 pages
Examen du cours de Theorie de l'Information et Codage Temps imparti: 3h. Dans tout le sujet, on note H : x 7? ?x log2(x)? (1? x) log2(1? x). 1. Probleme 1: Vous avez 8 bouteilles de vin dont une exactement est empoisonnee avec les probabilites suivantes: p1 = p2 = 1/45, p3 = p4 = 6/45, p5 = 7/45, p6 = p7 = p8 = 8/45. Vous voulez determiner quelle bouteille est empoisonnee en les testant sur des rats. Un rat qui boit du poison meurt instantanement et un rat qui boit du vin n'est plus fiable pour une nouvelle degustation! Vous devez donc utiliser chaque rat au plus une fois. Determiner quelle bouteille est empoisonnee en minimisant le nombre moyen de rats utilises. Pourquoi Brigitte Bardot n'aime pas votre protocole? 2. Probleme 2: Soient U1, U2, . . . les lettres generees par une source sans memoire d'alphabet U . On suppose que la distribution pU des lettres est soit p1 soit p2, c'est a dire (i) P(Ui = u) = p1(u) pour tout u ? U et i ≥ 1, ou; (ii) P(Ui = u) = p2(u) pour tout u ? U et i ≥ 1.

  • mot-code

  • ??n? erreurs par mot-code

  • codes correcteurs d'erreurs

  • dictionnaire pour la source

  • limitation theorique sur le debit

  • bits utiles par symbole emis

  • memoire utile


Voir plus Voir moins
ExamenducoursdeThe´oriedelInformationetCodage Temps imparti:3h.
Dans tout le sujet, on noteH:x7→ −xlog (x)(1x(1) logx). 2 2 1.Proble`me1:Vousavez8bouteillesdevindontuneexactementestempoisonne´eavecles probabilit´essuivantes:p1=p2= 1/45, p3=p4= 6/45, p5= 7/45, p6=p7=p8= 8/45. Vous voulezde´terminerquellebouteilleestempoisonne´eenlestestantsurdesrats.Unratquiboit dupoisonmeurtinstantan´ementetunratquiboitduvinnestplusablepourunenouvelle d´egustation!Vousdevezdoncutiliserchaqueratauplusunefois.D´eterminerquellebouteille estempoisonne´eenminimisantlenombremoyenderatsutilise´s.PourquoiBrigitteBardot n’aime pas votre protocole? 2.Probl`eme2:SoientU1, U2, . . .tebahpladeriomeselttelseapree´e´´nergsnsm´cesasourruneU. On suppose que la distributionpUdes lettres est soitp1soitp2secda`teir, (i)P(Ui=u) =p1(u) pour toutu∈ Ueti1, ou; (ii)P(Ui=u) =p2(u) pour toutu∈ Ueti1. SoitK=|U |le nombre de lettres dans l’alphabetU,H1(U) l’entropie deUde loip1oeden´n par (i) etH2(U) l’entropie deUde loip2oiti).Srai(e´peodnnpj,min= minu∈Upj(u) la probabilite´delalettrelamoinsprobablesouspjun mot. Pourw=u1u2. . . une´,saprbobaliti Q n estpj(w) =pj(ui) et enfinpˆ(w) = maxj=1,2pj(w). i=1 (a) SoitnNet soitSl’ensemble desnmots maximisantpqueˆ. MontrerSpueˆtteer repr´esent´ecommelesnœudsinterm´ediairesdunarbreTayant 1+ (K1)nfeuilles. (b) SoitWl’ensemble des feuilles deT, qui forment un dictionnaire pour la source.Soit H1(W) etH2(W) l’entropie des mots du dictionnaire sousp1etp2respectivement. Montrer que pourj= 1,2,Hj(W)log(1/Q)u`oQ= minv∈Spˆ(v). 111 (c) Montrerque|W| ≤Q(p+p). 1,min 2,min ` (d) SoitEjeuguonalneenoyrml[l])W(gnoesounairrobaslapomdtdnuitnoducit´ebilipj. A partir du dictionnaireWcounreuitrnsco,nO.e´natnatsniednoteρjle nombre de bits e´misparlettredelasourcesiladistributiondelasourceestpj. Montrerque 11 1 + log(p+p) 1,min 2,min ρj< Hj(U) +. Ej[long(W)] (e)Montrerquecettem´ethodecomprimelasourcedemani`ereoptimaleasymptotiquement quandntend vers l’infini. 3.Probl`eme3: (a)Etantdonne´uncanaldiscretsansm´emoire(X, p(y|x),Ycapacit´e)deCis`dreleo,cnnoe canalo`udeuxsortiesind´ependantessontobserve´espourchaqueentr´ee:(X, p(y1, y2|x) = p(y1|x)p(y2|x),Y × Yd)cepacatie´C2. MontrerqueC22C. 1
Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin