Théorie de l'information et codage

De
Publié par

Théorie de l'information et codage 2010/2011 Cours 11 — 10-17-24 mai 2011 Enseignant: Marc Lelarge Scribe: Nicolas Daviaud - Marc Lelarge Pour information – Page web du cours 11.1 Code de Hamming cycliques Rappel : la matrice de parité d'un code de Hamming de longueur n = 2m ? 1 a pour colonnes les 2m ? 1 m-uplets distincts et non nuls. Si ? ? F(2m) est un élément primitif, alors 1, ?, . . . ?2m?2 sont distincts et non nuls, et peuvent être représentés par des m-ulpets. On définit le code de Hamming Hm avec paramètres n = 2m ? 1, k = n ? m, dmin = 3 par la matrice de parité H = ( 1 ? · · · ?2m?2 ) où les ?i sont remplacés pas les m-uplets correspondants. E?????? 11.1.1: C??? ?? H??????H3 On se place dans le cas F(23) et ?3 + ? + 1 = 0 H = ? ? ? ? ? ? ? ? 0 0 1 0 1 1 1 0 1 0 1 1 1 0 1 0 0 1 0 1 1 ? ? ? ? ? ? ? ? Un vecteur c = (c0 · · · cn?1) appartient à Hm ssi HcT = 0 ssi c(?) = 0 où c(X) = c0 + c1X + · · ·+ cn?1Xn?1.

  • classe cyclotomique modulo

  • irreductible de degré

  • représentant de la classe

  • polynôme minimal de ?

  • xn ?

  • décodage du code bch

  • code de hamming hm


Publié le : dimanche 1 mai 2011
Lecture(s) : 56
Tags :
Source : di.ens.fr
Nombre de pages : 3
Voir plus Voir moins
Universit´edeNice D´epartementdeMath´ematiques
Analyse : notes du cours 11 Limitesetcontinuite´
Ann´ee2007-2008 LicenceMI/SM1eann´ee
Lesnotionsdelimitesdunefonctionenunpoint,celledecontinuite´dunefonctionetcelledelimites dunefonctiona`linnisontdeja`connues.Lobjetdececoursestdedonnerlesde´nitionsformalis´ees decesimportantesnotionsetdepre´senterquelquesunesdeleurspropri´et´es.
1. Limite d’une fonction en un point Soitf:RRet soientaetLmulelimls.Laforedxu´reexaf(x) =L, qui se lit “La limite def quandxtend versase´te`aegallfgan¸ice,,sdieformoninq,euleelf(x) est arbitrairement proche deL d`esquexesttr`esprochedea. Ou encore que l’on a|f(x)L|< εpour n’importe quelε, aussi petit que l’on veut, pourvu que|xa|soit assez petit. Alorsquecettenotiondelimiteae´t´e´etudie´eparlesmathe´maticiensdepuislantiquite´etplusac-tivementapre`slintroductionducalculdi´erentieletint´egralparLeibnitzetNewtonau17esie`cle,ila falluattendreWeierstass(1815-1897)pourvoirapparaˆıtrelade´nitionformalis´eesuivantequetousles mathe´maticiensutilisent`apre´sent(ditede´nitionεδ) : D´enition:On dit que la fonctionx7→f(x) tend versLlorsquextend versae,´nottlimecrixaf(x) = L, si et seulement si l’on a ε >0δ >0|xa|< δ⇒ |f(x)L|< ε.
Fig.1 – Illustration de la definitionεδde limxaf(x) =L.
Exemple :A titre d’exemple montrons que limx3(4x5) = 7. Pour cela on commence pardeviner quelle valeur deδon pourait choisir en fonction deεetteceuqefri´envsouinpioitledae´ntasiafripours valeur convient bien. On remarque que|(4x5)7|< ε´esircreepnetueroc|4x12|< ε, soit 4|x3|< ε. On voit que ε ε cetteine´galit´eestvraied`esque|x3|<serneesO.pna`opodcnδ=oix,.cechiavoencsVq´eurno 4 4 a bien limx3(4x5) = 7. ε Pour toutε >0, posonsδ= etmontrons que si|x3|< δalors|f(x)7|< ε. En effet sixest tel 4 ε que|x3|<, on a bien alors 4 ε |f(x)7|=|(2x5)7|= 4|x3|<4 =ε. 4
Notons que la condition|xa|< δsis´ceiratsuδ <|xa|< δneneeroca`oubiaδ < x < a+δ. Doncxeadtesrfoacihsppasliuqsrole´italegn´eittceitatsnaneerhc(egauaparlsoitraptr)euoi,snftiri´e ladroite(enrestantsup´erieur),soitennenpassantduncote´a`lautrea`saguise.Lorsquonimposea` xde tendre versaedt´eentserdtnaeˆmuocema, on obtient les notions dete`agaucheilimet demite`ali droite.
1
De´nition:On dit que la fonctionx7→f(x) tend versLlorsquextend versapar la gauche, et on ´ecritlimxaf(x) =L, si et seulement si l’on a ε >0δ >0aδ < x < a⇒ |f(x)L|< ε. Demeˆmeonditquex7→f(x) tend versLlorsquextend versapar la droite,miltirce´notexaf(x) =L, + si et seulement si l’on a ε >0δ >0a < x < a+δ⇒ |f(x)L|< ε.
Ainsi on peut montrer par exemple que limx1E(x) = 0, que limx1E(x) = 1 ou bien encore que + 2 limx0x= 0 (il suffit de prendreδ=ε). + Notons queLest la limite defenasi et seulement siLetimilsiofala`tsea`rdioetetlimite`agauche defena.
2.Continuit´e De´nition:On dit qu’une fonctionf:RRfest continue au pointaRsi et seulement si limf(x) =f(a). xa La fonction est continue sur un intervalleIsi elle est continue en tout point de cet intervalle. Par exemple la fonctionE(x) est continue en tout pointxnon entier et discontinue aux points entiers. Par contre elle estordca`neouintetiaux pointsnZpuisque limxnE(x) =E(n) =nmais + pasuagacehcnue`ontien ces points. Proposition 1Soitxnune suite convergente de limitelet soitfune fonction continue sur un intervalle contenantl. Alors la suite imageyn=f(xn)converge et a pour limite l’imagef(l)del; on a donc : limf(xn) =f(limxn).(1) Ilestfaciledesassurerqueceth´eoremedevientfauxlorsquefn’est pas continue. Ainsi, pour la fonctionfed´rapein 2 xsix6= 2 f(x) = 0 six= 2 qui n’est pas continue enx= 2, toute suitexntendant vers 2 a pour image une suitef(xn) qui tend vers 4 et non versfevtuorsquononctionlde´tfaletnociunierurladeesfdssaonciestdratimp´e.0lI2(=) e´changerlimiteetfonctioncommedanslaformule(1). Preuve :dospthutxeu`eysh`sremeed´nhoolesppele:Raxnest convergente de limiteldonc ε >0,N,n > N|xnl|< ε etfest continue enx=ldonc limxlf(x) =f(l), soit ε >0δ >0|xl|< δ⇒ |f(x)f(l)|< ε Montrons que la suitef(xn) converge versf(lquemontronserid-a`-tsec,) ε >0,N,n > N|f(xn)f(l)|< ε. Soitε >0 quelconque. Commefest continue, il existeδ >0, notons leδ0, tel que lorsque|xnl|< δ0 alors|f(xn)f(l)|< εsuotruorpliabets´onulvodetei`rne´eralegO.tecrmentcellequenoustie´sept´rcesie´ lesnzessaelsotsuopruemtnis´er´ecds(pgrann > N,NolippanM.)rssiaeretnemid´`aeypoth`esliquelh de convergence dexnen choisissant pourεleδ0peiatruoteˆtrver(elledoislouesε >0 donc en particulier pourε=δ0) alors on obtient l’existence d’unN, notons leN0, tel quen > N0,|f(xn)f(l)|< ε.D`ou la convergence def(xn) versf(l).Enge´neral,lorsquonveutsassurerquunefonctionestcontinue,ilnestpasne´cessairedutiliser lad´enition:eneet,onutiliselefaitquedunepartlaplupartdesfonctionsusuelles,lin´eaires, polynˆomiales,rationnelles,puissances,exponentielles,logarithmes,trigonome´triques,....sontcontinues entouslespointso`uellessontd´enieset,dautrepartlasomme,leproduit,lequotient,lacompose´ede
2
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.