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

Brigitte Bardot

Description

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

Sujets

• Bardot

Informations

• Publié par: pefav
• Nombre de lectures: 40
• Langue: Français

Extrait

ExamenducoursdeThe´oriedel’InformationetCodage Temps imparti:3h.

Dans tout le sujet, on noteH:x7→ −xlog (x)−(1−x(1) log−x). 2 2 1.Proble`me1:Vousavez8bouteillesdevindontuneexactementestempoisonne´eavecles probabilit´essuivantes:p 1 =p 2 = 1/45, p 3 =p 4 = 6/45, p 5 = 7/45, p 6 =p 7 =p 8 = 8/45. Vous voulezde´terminerquellebouteilleestempoisonne´eenlestestantsurdesrats.Unratquiboit dupoisonmeurtinstantan´ementetunratquiboitduvinn’estplusfiablepourunenouvelle d´egustation!Vousdevezdoncutiliserchaqueratauplusunefois.D´eterminerquellebouteille estempoisonne´eenminimisantlenombremoyenderatsutilise´s.PourquoiBrigitteBardot n’aime pas votre protocole? 2.Probl`eme2:SoientU 1 , U 2 , . . .tebahpla’deriomeselttelseapree´e´´nergsnsm´cesasourruneU. On suppose que la distributionp U des lettres est soitp 1 soitp 2 se’cda`teir, (i)P(U i =u) =p 1 (u) pour toutu∈ Ueti≥1, ou; (ii)P(U i =u) =p 2 (u) pour toutu∈ Ueti≥1. SoitK=|U |le nombre de lettres dans l’alphabetU,H 1 (U) l’entropie deUde loip 1 oeden´n par (i) etH 2 (U) l’entropie deUde loip 2 oiti).Srai(e´peodnnp j,min = min u∈U p j (u) la probabilite´delalettrelamoinsprobablesousp j un mot. Pourw=u 1 u 2 . . . u n e´,saprbobaliti Q n estp j (w) =p j (u i ) et enfinpˆ(w) = max j=1,2 p j (w). i=1 (a) Soitn∈Net soitSl’ensemble desnmots maximisantpqueˆ. MontrerSpueˆtteer repr´esent´ecommelesnœudsinterm´ediairesd’unarbreTayant 1+ (K−1)nfeuilles. (b) SoitWl’ensemble des feuilles deT, qui forment un dictionnaire pour la source.Soit H 1 (W) etH 2 (W) l’entropie des mots du dictionnaire sousp 1 etp 2 respectivement. Montrer que pourj= 1,2,H j (W)≥log(1/Q)u`oQ= min v∈S pˆ(v). −1 −1−1 (c) Montrerque|W| ≤Q(p+p). 1,min 2,min ` (d) SoitE j euguonalneenoyrml[l])W(gnoesounairrobaslapomdt’dnuitnoducit´ebilip j . A partir du dictionnaireWcounreuitrnsco,nO.e´natnatsniednoteρ j le nombre de bits e´misparlettredelasourcesiladistributiondelasourceestp j . Montrerque −1−1 1 + log(p+p) 1,min 2,min ρ j < H j (U) +. E j [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(y 1 , y 2 |x) = p(y 1 |x)p(y 2 |x),Y × Yd)cepacatie´C 2 . MontrerqueC 2 ≤2C. 1