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

De
Publié par

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


Publié le : mardi 19 juin 2012
Lecture(s) : 39
Tags :
Source : di.ens.fr
Nombre de pages : 3
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
(b)Unepucem´emoireestconstitu´eedunmilliondecelluleschacunem´emorisantunbit. Cependantunecelluleestde´fectueuseavecuneprobabilite´p= 0.e´dni10ntpendamme desautres.Plutoˆtquedattendre(tr`eslongtemps)pourunepuceparfaite,nousfaisons aveclespucesimparfaites.Lapremi`ereoptionestdetesterchaquecellule,didentierles cellulesd´efectueusesetdenutiliserquelesautrescellules.Quelleestalorslame´moire utilemoyenne?Uneautresolutionquie´vitedefairecestests,estdutiliserdescodes correcteursderreurs.Quellesestalorslam´emoireutiledanslesdeuxcassuivants: i.unecellulede´fectueusecorresponda`uneacement. ii.unecellulede´fectueusedonneenlecturelinversedecequia´et´ee´crit. 4.Probl`eme4: (a)Montrerquelenombremoyende1parmotcode(moyenn´esurtouslesmotscode)dans uncodebinairelin´eairedelongueurNest au plusN/2. L (b)End´eduirequeladistanceminimaleduncodebinaireline´airedelongueurNayant 2 motscode satisfait: L1 2N dmin. L 21 (c)Montrerquecetteine´galite´estvalidepourtoutcodebinaire(nonn´ecessairementline´aire). 5.Proble`me5: (a) Montrerque tout code binairetcorrecteurCde longueurn(2t < n):eire´v t  X n n |C| ≤2, i i=0 etend´eduireunebornesup´erieuresurled´ebitducode(enbitsutilesparsymbole´emis). (b) Onfait maintenant tendre la taillendes motscode vers l’infini et l’on souhaite pouvoir 1 corrigerjusqua`t=εnerreurs par motcode (0ε <donne alors la borne). Que 2 pr´ec´edemmentobtenue?Onexprimeralare´ponsea`laidedelafonctionH. (c)Commentpouvaitonpre´voirdirectementcettelimitationthe´oriquesurled´ebit?La borne obtenue estelle atteignable asymptotiquement ? 6.Proble`me6:LaclassedescodesdeJustesenestlaseuleclassedecodesline´airesbinaires explicitement connue contenant des codes (Ci)i1seapar`mdnoltetres(ni, ki, di)i1satisfont: kidi ni−→+,lim inf>lim inf0 et>0. nini i→∞i→∞i→∞ NotonsPropsedelbmesnel´egrdedeesomnˆlyauplusrsur le corps finiFqet soitL= m (α1, . . . , αn) une famille den > r`a2dnts2nctsistiedle´eme´Fq. m
2
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.