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

Description

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

Informations

• Publié par: pefav
• Publié le: 01 mai 2012
• Nombre de lectures: 38
• Langue: Français

Extrait

Th´eoriedel’InformationetCodage:Fiched’exercices3 a`rendrea`MadameDelaispourle9mai2012.

Instructions:ti.eiSovmenasurcefl´echi`usavezr´srulpaueisrcmecuhaaci`rdnerednipocenue surunprobl`eme,mettezlesnomsdevoscollaborateurs.

Probl`eme1:(5points) Nousallonsmontrerler´esultatsuivant:onconside`reuncanalbinairesyme´triquedecapacit´eC= Rn 1−H(ptoute suite de codes de longueurs). PournayantM=⌊2⌋oceedomstibab´tilnuteorpe P M (i) n 1 n d’erreur moyenneP=P, siR > CalorsP→1 quandn→ ∞. E M i=1 E E Soite <1. Pourtoutn´end,onfitir n le plus petit entier tel que:   r n X n j n−j p(1−p)≥1−e. j j=0 (i) M Onconside`reun(M, n)code avec maxP≤e. i=1 E P  r n −1 n n 1. MontrerqueM <2 . j=0 j 2. Montrerque pour toutδ >0, pournsuffisament grand, on ar n ≥n(p−δ). n(C+ǫ) 3. Enconclure que pour toutǫ >0 et pournsuffisament grand,M≤2 . 4.D´emontrerlere´sultatvoulu,c’est`adirequel’erreurmoyennedoitapprocher1.

Probl`eme2:Canalavecme´moire(4points) Onconsid`ereuncanalbinairesyme´triqueavecY i =X i ⊕Z i ou`⊕est l’addition modulo 2 etX i , Y i ∈ {0,1}. LesZ 1 , Z 2 , . . .endad´epntin´emeofcrptsasenontruotuomstnpsian≥1, (Z 1 , . . . , Z n ) est inde´pendantde(X 1 , . . . , X n ). 1. Onsuppose queP(Z i = 1) =p= 1−P(Z i = 0).SoitC= 1−H(p). Montrerque maxI(X 1 , . . . , X n ;Y 1 , . . . , Y n )≥nC. P X ,...,x n 1

1