Solutions des Exercices du cours de Theorie de l'Information et Codage cours du fevrier

Description

Solutions des Exercices du cours de Theorie de l'Information et Codage cours 1 du 8 fevrier 2011. 1. Dans le cas R = 1/2n, avec n ? N et pour un encodage du type: repetition de chaque bit 2n fois sur le canal binaire symmetrique: donner une strategie de decodage et calculer la probabilite d'erreur correspondante Pe. Comparer au cas R = 1/(2n? 1) etudie en cours quand p ? 0. • Decodage par majorite, en cas d'egalite, tirage a pile ou face. Pe = ∑ k≥n+1 ( 2n k ) pk(1? p)2n?k + 1 2 ( 2n n ) pn(1? p)n. • quand p? 0, on a Pe ? (2n?1 n ) pn qui correspond au cas etudie en cours. 2. On considere le cas R = 2n + 1 pour n ? N et l'encodage: j'envoie la majorite de chacun des blocs de 2n+1 bits successifs emis par la source (comme decrit en cours pour R = 3). Montrer que Pe = (1? p)Q+ p(1?Q) avec Q = 1 2 ? ( 2n n ) 2?(2n+1).

• triplets de colonnes liees


• meme probabilite d'erreur pe


• bit


• probabilite d'erreur correspondante


• probabilite


• strategie de decodage


• colonnes complementaires du motif d'erreur


• majorite


• motif d'erreur

Sujets

• Probabilité
• Majorité

Informations

• Publié par: pefav
• Publié le: 01 février 2011
• Nombre de lectures: 65
• Langue: Français

Extrait

Correctiondesexercicesducours:StructuresetAlgorithmesAle´atoires cours 1 du 16 octobre 2009. 1.Vousavez3pi`ecesdontuneestbiaise´e:voussavezqu’elletombesurpileavecprobabilite´2/3. Vousnesavezpasquellepie`ceestbiaise´emaisvousfaitesuntirageavecchacunedespie`ceset lapremie`reetsecondepie`cestombentsurpiletandisquelatroisie`metombesurface.Quelle estlaprobabilite´quelapremi`erepie`cesoitcellequiestbiaise´e? •SoitE i ne´entmelev’´l:aiteee´siuiestbiastcelleqpe`iceee`meBgeratilet:enemne´ve´’l destroispie`cesdonnedansl’ordre:pilepileface.Avantletirage,nousn’avonsaucune informationsurlapie`cebiais´eedoncP(E i ) = 1/avons aussi3. Nous 2 1 11 1 P(B|E 1 ) =P(B|E 2 =) =,et,P(B|E 3 ) =. 3 2 26 12 On a donc P(B|E 1 )P(E 1 ) 2 P(E 1 |B) = P =. 3 P(B|E i )P(E i ) 5 i=1 Apre`slare´alisationdutirage,lavraisemblancepourquelapremie`repie`cesoitcellequi estbiais´eeestpass´eede1/3`a2/5. 2. Dansle cas vu en cours de la multiplication matricielle.Sans information surA, B, C, on fait l’hypothe`seaprioriqueP(AB=C) = 1/fait tourner une fois l’algorithme vu en cours2. On quinousretourneler´esultat:AB=Clellelienefsotrlmttaetnioounvqeui.l´vtAceeecpaorabib aposterioriquel’identite´soitcorrecte?Etapr`eskit´ee?hmitglrolea’nodsarit •uaacps´rcee´edtn.SoitnesoaierLerialimistsetnemEl’´ev´enem:tnedi’litneee´tcostecrr.te etFnemee´´v’llane:tthmegoriurneretol’AB=C. Oncommence avecP(E) =P(E) = 1/2. De plus,P(F|E) = 1 tandis queP(F|E)≤1/aOn).eucnuosrseluatvtr`esler´2(d’ap donc P(F|E)P(E) 2 P(E|F) =≥. P(F|E)P(E) +P(F|E)P(E ) 3 Apre`slepremiertest,onsupposemaintenantqueP(E)≥2/3 etP(E)≤1/3, on a donc apres un second test: 2/3 4 P(E|F)≥=. ˙ 2/3 + 1/31/ 2 5 Ontrouveapr`eskeratit´ions 1 P(E|F)≥1−. k 2 +1

1