Codes Correcteurs d'Erreurs Cours 1 + Introduction + Codes linéaires en bloc

De
Publié par

Introduction IntroductionLes codes lin´eaires en blocs Les codes lin´eaires en blocsSourcesCodes Correcteurs d’ErreursCours 1+ Introduction ”The Art of Correcting Coding”, Robert H. Morelos-Zaragoza,2002+ Codes lin´eaires en blocCours de Pierre Abbrugiati, Universit´e de Nice,Cours de Marc Uro, INT Evry.Marc ChaumontNovember 12, 2008Marc Chaumont Introduction Marc Chaumont IntroductionPr´eambule Pr´eambuleIntroduction Les 3 principaux param`etres : longueur, dimension, distance Introduction Les 3 principaux param`etres : longueur, dimension, distanceLes codes lin´eaires en blocs Capacit´e de d´etection et de correction des erreurs Les codes lin´eaires en blocs Capacit´e de d´etection et de correction des erreursExercice ExercicePlan Code d´etecteur/correcteur d’erreur1 IntroductionPr´eambulePar codes, on peut entendre plusieurs concepts distincts :Les 3 principaux param`etres : longueur, dimension, distanceles codes pour la cryptographie,Capacit´e de d´etection et de correction des erreursExercice les codes pour la compression,les codes pour la correction d’erreur.2 Les codes lin´eaires en blocsDans ce cours, nous nous interessons uniquement aux codes cor-D´efinitionrecteurs d’erreurs.Matrice g´en´eratrice et de v´erification de parit´eExerciceLe poids = la distance !Marc Chaumont Introduction Marc Chaumont IntroductionPr´eambule Pr´eambuleIntroduction Les 3 principaux param`etres : longueur, dimension, distance Introduction Les 3 principaux ...
Publié le : samedi 24 septembre 2011
Lecture(s) : 116
Nombre de pages : 15
Voir plus Voir moins
IntroductionLesocedlsnie´iaereslonbcsIntroocselsedtcudLnoinbsecslo´einreaiecsoSruomuanItnaMhCcronodtrtiucaMcrhCuaomtnIntroduction
Plan
1 Introduction Pr´ bule eam Les3principauxparame`tres:longueur,dimension,distance Capacit´eded´etectionetdecorrectiondeserreurs Exercice 2 Lescodesline´airesenblocs D´enition Matricege´ne´ratriceetdeve´ricationdeparit´e Exercice Le poids = la distance !
Par codes, on peut entendre plusieurs concepts distincts : les codes pour la cryptographie, les codes pour la compression, les codes pour la correction d’erreur. Dans ce cours, nous nous interessons uniquement aux codes cor-recteurs d erreurs.
Codes Correcteurs d’Erreurs Cours 1 + Introduction +Codesline´airesenbloc Marc Chaumont
Marc Chaumont Introduction Pr´eambule Introduction Les3principauxparam`etres:longueur,dimension,distance Lescodesline´airesenblocs Capacite´dede´tectionetdecorrectiondeserreurs Exercice
”The Art of Correcting Coding”, Robert H. Morelos-Zaragoza, 2002 CoursdePierreAbbrugiati,Universit´edeNice, Cours de Marc Uro, INT Evry.
Marc Chaumont Introduction Pr´eambule Introduction Les3principauxparame`tres:longueur,dimension,distance Lescodesline´airesenblocs Capacit´eded´etectionetdecorrectiondeserreurs Exercice Coded´etecteur/correcteurder reur
November 12, 2008
iaernie´edlsseocionLductntroIecetd´dedeetontiCecnatsie´ticapaExereursConsciceceitocrresrrnoedLeleprs3ciinuxpabnesscole´rPubmaueur,dimension,dapar`mteer:solgntateleL3srprPe´maubsenblocsin´eaireocselsedtcudLnoiIrontiquedelath´eorieiceccS´hmecaalssdeonrrserseuerExnoitedterrocitceit´eapacetecded´nod,neiscnCesiatnglos:reim,duruexuapicnite`marapdelinformationMarcChaumontIntrdocuitno
Surinternet,(paquetsIP)lecodecorrecteurselimite`ala d´etectiondeserreurs(sommedecontrˆole).Lacorrectionest alorsre´alise´eparunenouvelledemandedetransmissiondumes-sage (protocole TCP). Danslecasdudisquecompact,leserreurspeuventˆetrecause´es pardesrayuresoudesimpurete´sdusupport,ellessontmoins fre´quentesmaisbeaucoupplusvolumineuses.Lanormedela soci´ete´Philipsimposelacapacit´edecorrectionderreursdans lecasdunerayurede0,2milli`etre,danslapratique,lecode m utilise´corrigejusqua`4096bitsconsecutifssoitunerayurede ´ plusdunmillim`etredelarge. Communications sans fils : GSM, satelite, sous-marine...
Figure: Transmissionaveccodagede´tecteur/correcteurderreurs
no
le code de p it´ ar e : Ge´ne´ralement,onajoute`a7bitsdedonne´es1bitvalant1silya unnombreimpairde1,et0sinon.Sia`lar´eceptionundes8bits esterron´e,ilyad´etectionderreur. controˆlederedondancecyclique:CRC Less´equencesbinairessonttrait´eescommedespolynoˆmesdontles coecientscorrespondenta`las´equencebinaire.Onajoutea`la se´quencebinairelerestedunedivisionpolynomiale(divisionparle ` polynˆom´´ateur)Alar´eceptionlerestedeladisisionre¸cuet e gener . lerestedeladivisioncalcule´doiventcoincideroualorsilyaerreur de transmission.
Autrement dit, les donne´es , lorsqu’elles circulent sur cette voie, sont susceptiblesdeˆtrealte´re´es . Bref,ilfautdesm´ecanismesde de´tectionetdecorrectionde ces erreurs ...
Marc Chaumont Introduction Pr´eambule Introduction Les3principauxparam`etres:longueur,dimension,distance Les codes lineaires en blocs Capacit´edede´tectionetdecorrectiondeserreurs ´ Exercice Exemple de code d´etecteur d’erreur : lecodedeparite´ et le CRC
Marc Chaumont Introduction P ´ mbul rea e Introduction Les3principauxparame`tres:longueur,dimension,distance Lescodesline´airesenblocs Capacit´eded´etectionetdecorrectiondeserreurs Exercice Exemple de canal de communication
Danslagrandemajorite´descas,une transmissiondedonne´es se fait en utilisant une voie de communication qui n’est pas entierement fi-` able : le canal de communication .
rtdocuitaumontInMarcCh
r´eaocsPeLesmbul´naeseilnelbrisetiucodtrodscLeonnI´tdedee´ecaCapicn,distandimensiougno,ruerte`l:sexpauamarri3pipncocvndoseuscsvsreblocodesiceCxercEsruerresednoitcreorectdneiocttecicrexEeelpmocedd´deeceturtecoettcoiendtceroertciondeserreursExenoitietrurrceerrudreoded:lecp´eter´eifutolnvddenepd´nudeitrocruedocte`auranraincodefnroleinoocamitonti´epredc´teenuqisledefniamror.Note1:Lechoixdtele´atdtcudoueoN.noitacilppaldendpe´eedodncunoovedcsseoctnl,uemeoriqHistte2:uopsuelr´fe´e´reett´pr´etiluonfsyonaecesetealrcgesouplrd´ecodaficslotulbcodosesuscsverconvodesLsfitulocsedocseeuctreorreerdrsruE(CCp)ueevtneˆtredivis´esen2clessael:sdocsneseocblls:Iaitrntteinfoocdueblchaqepdndne´oiinmrtasadenssulentmeamdtomeuqahC.sertuind´epenecodeesttuermstoadtnedasscleesodecsde.od:sfiosaLvnoctulobe´d(ruojeca`suncl`esime`e21duuteLmset:3.oNpuelsconcodeeurseill´derdoceaptnteˆseri`soesd´eanemllleseocollnqaeuepouvaiedesblocnntInaumouctitrodnofa`aleibnsde´eitaped´tiraM)ehCcre)sontlescodesblco(sri´rgelueisresirblenliesean´eLnodocsdortitcuauxparam3principbmluLesecoPs´raeonInuctitrodntInuaomcrhCaMcrexPecinalioctesndreersEuroisnemidnatsid,n:lestr`er,euguonoienettcroerdtcepaciceCaed´et´ed
1 Introduction Pr´eambule Les3principauxparam`etres:longueur,dimension,distance Capacite´ded´etectionetdecorrectiondeserreurs Exercice 2 Lescodesline´airesenblocs D´enition Matriceg´en´eratriceetdev´ericationdeparit´e Exercice Le poids = la distance !
Marc Chaumont Introduction Pre´ambule Introduction Les3principauxparam`etres:longueur,dimension,distance Lescodesline´airesenblocs Capacit´edede´tectionetdecorrectiondeserreurs Exercice Qu’attend-on d un bon code
Un bon code doit avoir : unbonrendement(taux)cest-a`-direungrandnombredebits dinformationparrapportauxbitscod´es. unebonnecapacit´edede´tectionetcorrectionderreurs, uneproce´duredede´codage(etdecodage)susammentsimple et rapide. Toutleproble`medelath´eoriedescodescorrecteursderreursest l`a:construiredescodesquide´tectentetcorrigentleplusderreurs possible, tout en allongeant le moins possible les messages, et qui soientfacilesa`decoder. ´
Technique de codage : Pourunbitdinformation,3bitssontenvoye´s(cadcod´es)telsque : 0 000 1 111 Techniqueded´ecodage: Lede´codagesefaitparvotemjaire.Parexemple,¸ a orit si le mot recu est001,alorsond´eduitquelebit´emise´tait0.
itnodocunIrtomtnChauMarcemsnoi,nidtsnaecCapacit´eded´etecniruapirapxe`maestron:leugudir,aeriil´nlbcoseneeambsPr´es3puleLrtnIontiucodesodscLe
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.