Cette publication est accessible gratuitement
Télécharger
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