Théorie de l'information et codage

Marc Lelarge

Description

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

Sujets

• maths
• cours
• cours de
• Mathématiques

Informations

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

Extrait

Universit´edeNice D´epartementdeMath´ematiques

Analyse : notes du cours 11 Limitesetcontinuite´

Ann´ee2007-2008 LicenceMI/SM1eann´ee

Lesnotionsdelimitesd’unefonctionenunpoint,celledecontinuite´d’unefonctionetcelledelimites d’unefonctiona`l’infinisontdeja`connues.L’objetdececoursestdedonnerlesde´finitionsformalis´ees decesimportantesnotionsetdepre´senterquelquesunesdeleurspropri´et´es.

1. Limite d’une fonction en un point Soitf:R→Ret soientaetLmulelimls.Laforedxu´ree x→a f(x) =L, qui se lit “La limite def quandxtend versase´te`aegallfgan¸icfi”e,,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|x−a|soit assez petit. Alorsquecettenotiondelimiteae´t´e´etudie´eparlesmathe´maticiensdepuisl’antiquite´etplusac- tivementapre`sl’introductionducalculdiff´erentieletint´egralparLeibnitzetNewtonau17esie`cle,ila falluattendreWeierstass(1815-1897)pourvoirapparaˆıtrelade´finitionformalis´eesuivantequetousles mathe´maticiensutilisent`apre´sent(ditede´finitionε−δ) : D´efinition:On dit que la fonctionx7→f(x) tend versLlorsquextend versae,´nottlimecri x→a f(x) = L, si et seulement si l’on a ∀ε >0∃δ >0|x−a|< δ⇒ |f(x)−L|< ε.

Fig.1 – Illustration de la definitionε−δde lim x→a f(x) =L.

Exemple :A titre d’exemple montrons que lim x→3 (4x−5) = 7. Pour cela on commence pardeviner quelle valeur deδon pourait choisir en fonction deεetteceuqefri´envsouinpioitledae´nfitasiafripours valeur convient bien. On remarque que|(4x−5)−7|< ε´es’ircreepnetueroc|4x−12|< ε, soit 4|x−3|< ε. On voit que ε ε cetteine´galit´eestvraied`esque|x−3|<serneesO.pna`opodcnδ=oix,.cechiafivoencsVq´eur’no 4 4 a bien lim x→3 (4x−5) = 7. ε Pour toutε >0, posonsδ= etmontrons que si|x−3|< δalors|f(x)−7|< ε. En effet sixest tel 4 ε que|x−3|<, on a bien alors 4 ε |f(x)−7|=|(2x−5)−7|= 4|x−3|<4 =ε. 4

Notons que la condition|x−a|< δsis´’ceiratsu−δ <|x−a|< δneneeroca`oubia−δ < x < a+δ. Doncxeadtesrfoacihsppa’sli’uqsrole´italegn´eittceitatsnaneerhc(egauaparlsoitraptr)euoi,snftiri´e ladroite(enrestantsup´erieur),soitenfinenpassantd’uncote´a`l’autrea`saguise.Lorsqu’onimposea` xde tendre versaedt´eentserdtnaeˆmuocema, on obtient les notions dete`agaucheilimet demite`ali droite.

1