Cet ouvrage et des milliers d'autres font partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour les lire en ligne
En savoir plus

Partagez cette publication

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