Theorie de l'Information et Codage: Fiche d'exercices a rendre a Madame Delais pour le mai

Publié par

Theorie de l'Information et Codage: Fiche d'exercices 3 a rendre a Madame Delais pour le 9 mai 2012. Instructions: merci a chacun de rendre une copie manuscrite. Si vous avez reflechi a plusieurs sur un probleme, mettez les noms de vos collaborateurs. Probleme 1: (5 points) Nous allons montrer le resultat suivant: on considere un canal binaire symetrique de capacite C = 1 ?H(p). Pour toute suite de codes de longueurs n ayant M = b2Rnc mots code et une probabilite d'erreur moyenne P nE = 1M ∑M i=1 P (i) E , si R > C alors P nE ? 1 quand n ? ∞. Soit e < 1. Pour tout n, on definit rn le plus petit entier tel que: rn ∑ j=0 (n j ) pj(1? p)n?j ≥ 1? e. On considere un (M,n)-code avec maxMi=1 P (i) E ≤ e. 1. Montrer que M ∑rn?1 j=0 (n j ) < 2n. 2. Montrer que pour tout ? > 0, pour n suffisament grand, on a rn ≥ n(p? ?). 3. En conclure que pour tout > 0 et pour n suffisament grand, M ≤ 2n(C+).

  • erreur entre moyenne

  • probabilite d'erreur moyenne

  • prisonniers

  • chance de survie des prisonniers

  • matrice de hadamard de taille

  • convention ? au lieu de ?1

  • code


Publié le : mardi 1 mai 2012
Lecture(s) : 37
Source : di.ens.fr
Nombre de pages : 3
Voir plus Voir moins
Th´eoriedelInformationetCodage:Fichedexercices3 a`rendrea`MadameDelaispourle9mai2012.
Instructions:ti.eiSovmenasurce´echi`usavezr´srulpaueisrcmecuhaaci`rdnerednipocenue surunprobl`eme,mettezlesnomsdevoscollaborateurs.
Probl`eme1:(5points) Nousallonsmontrerler´esultatsuivant:onconside`reuncanalbinairesyme´triquedecapacit´eC= Rn 1H(ptoute suite de codes de longueurs). PournayantM=2oceedomstibab´tilnuteorpe P M(i) n1n d’erreur moyenneP=P, siR > CalorsP1 quandn→ ∞. E Mi=1E E Soite <1. Pourtoutn´end,ontirnle plus petit entier tel que:   rn X n j nj p(1p)1e. j j=0 (i) M Onconside`reun(M, n)code avec maxPe. i=1E P rn1n n 1. MontrerqueM <2 . j=0j 2. Montrerque pour toutδ >0, pournsuffisament grand, on arnn(pδ). n(C+ǫ) 3. Enconclure que pour toutǫ >0 et pournsuffisament grand,M2 . 4.D´emontrerlere´sultatvoulu,cest`adirequelerreurmoyennedoitapprocher1.
Probl`eme2:Canalavecme´moire(4points) Onconsid`ereuncanalbinairesyme´triqueavecYi=XiZiou`est l’addition modulo 2 etXi, Yi{0,1}. LesZ1, Z2, . . .endad´epntin´emeofcrptsasenontruotuomstnpsian1, (Z1, . . . , Zn) est inde´pendantde(X1, . . . , Xn). 1. Onsuppose queP(Zi= 1) =p= 1P(Zi= 0).SoitC= 1H(p). Montrerque maxI(X1, . . . , Xn;Y1, . . . , Yn)nC. PX ,...,x n 1
1
2. Onsuppose queP(Z1= 0) =P(Z1= 1) = 1/2 et que pouri1,P(Zi+16=Zi|Z1, . . . , Zi) = q[0,1]. Montrerque: I(X1, . . . , Xn;Y1, . . . , Yn)(n1)(1H(q)). Montrerquecettebornepeuteˆtreatteinteetcompareraucassansm´emoire.
Probl`eme3:CodesdeHadamard(5points)
1.Montrerqueparmilescodesdelongueur11pouvantcorrigerdeuxerreurs,lecodelin´eairele plus grand contient au plus 16 mots code. Nous allons construire un code plus performant.Une matrice d’Hadamard de taillenest une matrice T carre´en×nca`nsdatseniccoe{−1,+1}et telle que:HH=nI, i.e.le produit scalaire dansR dedeuxlignesdistinctesestnuletleproduitscalaireduneligneavecellemeˆmeestn. Comme 1 1T T H=H, on a aussiH H=nIet donc les colonnes deHi´etropremeplamˆotn.e´ n 2.Etantdonne´Hpeonurqrentmo,rtirdeuire`apasrocsnrttuotjuuoHune matrice de Hadamard tellequelapremi`erecolonneainsiquelapremie`relignesoientconstitue´esde+1. OndiraquunetellematricedeHadamardestnormalis´ee.Voicidesexemplesdematricesde Hadamardnormalise´es(aveclaconventionau lieu de1):   1 11 1   1 111H1= (1), H2=, H4=.(1)   11 1− − 1− −1 3. Montrerque siHest une matrice d’Hadamard de taillenalorsn= 1,2 ounest multiple de 4 (Ilsutdeconsidererles3premi`ereslignesdunematricenormalise´e). L’existence de matrices de Hadamard pour toutnmultiple de 4 est une question ouverte.Une construction simple repose sur l’observation que siHnest une matrice de Hadamard de taillenalors   HnHn H2n= HnHn est une matrice de Hadamard de taille 2n. Cetteconstruction permet d’obtenir les matrices de SylvesterH1, H2, . . .)1(dnO.ne´unit(n, M, d) code un ensemble deMmots code de longueurn ayant distance minimaled. 4.Montrerqua`partirdunematricedeHadamardnormalis´eeHn, il est possible de construire descodesbinairesayantlescaract´eristiquessuivantes:(n1, n, n/2), (n1,2n, n/21) et (n,2n, n/2). Conclure.
2
Probl`eme4:(4points) Ilya7prisonniersdansunesalle.Chacunaunchapeaubleuourougeavecprobabilit´e1/2 ind´ependammentdesautres.Chaqueprisonnierconnaˆıtlacouleurdeschapeauxdesautresprisoniers mais aucun prisonnier ne connaˆıt la couleur de son propre chapeau.Le gardien de prison demande aux prisoniers de deviner la couleur de leur chapeau:si un prisonnier se trompe, tous les prisonnierssonttue´s.Unprisonnieralapossibilit´edeneriendire(aulieudedeviner)maissiaucun prisonnierneparle,ilssont´egalementtoustu´es.Aucunecommunicationnestpermiseentreles prisonnierssaufpourxerlastrate´gieavantderentrerdanslasalleetlegardiendeprisoninterrogechaqueprisonnierse´paremment.Donnerunestrat´egiequimaximiselachancedesurviedes prisonniers.
Proble`me5:(2points) Pournetd,sestoix´ML(n, dotscodedximumdemonbmeram)eleedirnabieriae´niledocnulongueurnet de distance minimaled. Montrerque n 2 ML(n, d)  . n1n1 1 ++∙ ∙ ∙+ 1d2
3
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.