Codes Correcteurs d
58 pages
Français
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

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

-

Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
58 pages
Français

Description

IntroductionLes codes lin´eaires en blocsCodes Correcteurs d’ErreursCours 1+ Introduction+ Codes lin´eaires en blocMarc ChaumontNovember 12, 2008Marc Chaumont IntroductionIntroductionLes codes lin´eaires en blocsSources”The Art of Correcting Coding”, Robert H. Morelos-Zaragoza,2002Cours de Pierre Abbrugiati, Universit´e de Nice,Cours de Marc Uro, INT Evry.Marc Chaumont IntroductionPr´eambuleIntroduction Les 3 principaux param`etres : longueur, dimension, distanceLes codes lin´eaires en blocs Capacit´e de d´etection et de correction des erreursExercicePlan1 IntroductionPr´eambuleLes 3 principaux param`etres : longueur, dimension, distanceCapacit´e de d´etection et de correction des erreursExercice2 Les codes lin´eaires en blocsD´efinitionMatrice g´en´eratrice et de v´erification de parit´eExerciceLe poids = la distance !Marc Chaumont IntroductionPr´eambuleIntroduction Les 3 principaux param`etres : longueur, dimension, distanceLes codes lin´eaires en blocs Capacit´e de d´etection et de correction des erreursExerciceCode d´etecteur/correcteur d’erreurPar 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.Marc Chaumont IntroductionPr´eambuleIntroduction Les 3 principaux param`etres : longueur, dimension, distanceLes codes lin´eaires en blocs ...

Sujets

Informations

Publié par
Nombre de lectures 172
Langue Français

Exrait

Introduction Lescodesline´airesenblocs
Codes Correcteurs d’Erreurs Cours 1 + Introduction Codesline´airesen
+
M
Marc Chaumont
November 12, 2008
racCahmunotIntroduction
bloc
Sources
Introduction Lescodesline´airesenblocs
”The Art of Correcting Coding”, Robert H. Morelos-Zaragoza, 2002 CoursdePierreAbbrugiati,Universite´deNice, Cours de Marc Uro, INT Evry.
aMcrChaumontnIrtoudction
scodesliuctionLenIrtdori3peseLulmbear´Pscolbneseriae´ndimeeur,ongues:le`rtramauapxcnpiectdneioioctreorerresedncrexEsrun,dinsioceCastan´tdeapicettcdee´iceaMcromtnhCua
2
Lescodeslin´eairesenblocs D´enition Matriceg´ene´ratriceetdeve´ricationdeparit´e Exercice Le poids = la distance !
trInucodonti
Introduction Pre´ambule Les3principauxparame`tres:longueur,dimension,distance Capacit´edede´tectionetdecorrectiondeserreurs Exercice
1
Plan
eurrrectiononetdecosrxEreicedesrrueeceturteCoced´dedruerreroc/tcermuahItnoMCcraion
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.
ntroductprinLes3bule´eamscrPbnolerese´iainsldecoesnLioctudortnId´etectiacit´edeatcnCepaisnod,si,durenimlos:ueng`marerteapicapxu
ocseLnoitcudortnIeleLmaubrPe´olscsenbairein´edesldeontiecrseurrsenoitceterrocedteicecxEreetm`s:renglouruerp3sicnixuaparapnceCapacit´eded´d,mineisnod,siat
Danslagrandemajorit´edescas,unetres´eodnnnoedsiisnamsse fait en utilisant une voie de communication qui n’est-ntite`erempsane able: lecanal de communication.
Constat
Bref,ilfautdesme´canismesdeetd´tiecedontiecrrcodeeton ces erreurs...
Autrement dit, les´eesdonn, lorsqu’elles circulent sur cette voie, sontssuectpbieldsˆterealt´er´ees.
oinudtcntroontIhaumarcCM
Sch´emaclassiquedelathe´oriedelinformation
Figure:
Transmissionaveccodagede´tecteur/correcteurderreurs
oductionomtnnIrtaMcrhCuasrxEreicecrrectiondeserreud´etectionetdecoatcnCepacatie´ed,durenimonsiis,d`marerteol:seugnprinLes3uxpacipascrPbnolubele´mainsldecosereai´eudortnIseLnoitc
decoinslioctesnLtnIudorprinLes3bule´eamscrPbnolerese´iaenim,duruenglos:erte`marapxuapiconsiis,dnctaapeCticaede´te´ditceonetdecorrectionedesrruesrxEreicplemExcealanecednummocednoitaciahmuraCcMionductntroontI
Surinternet,(paquetsIP)lecodecorrecteurselimitea`la d´etectiondeserreurs(sommedecontrˆole).Lacorrectionest alorsrealis´eeparunenouvelledemandedetransmissiondumes-´ sage (protocole TCP). Danslecasdudisquecompact,leserreurspeuventeˆtrecaus´ees pardesrayuresoudesimpuret´esdusupport,ellessontmoins fre´quentesmaisbeaucoupplusvolumineuses.Lanormedela socie´t´ePhilipsimposelacapacit´edecorrectionderreursdans lecasdunerayurede0,2millim`etre,danslapratique,lecode utilis´ecorrigejusqua`4096bitscons´ecutifssoitunerayurede plusdunmillim`etredelarge. Communications sans fils : GSM, satelite, sous-marine...
CleCRdepecedoe´teratierreursExerciceEdtceroertcoidnseteecdurreer:lurpmexedeledocte´dsnoiidemue,rnouges:l`etraramauxpenoitcete´dede´tcipaCaceanstdin,seil´naenoeLcsdotroductiInirp3picnlubmseLesPocear´esirblencudonoit
lecodedeparite´: Ge´ne´ralement,onajoute`a7bitsdedonne´es1bitvalant1silya unnombreimpairde1,et0sinon.Si`alar´eceptionundes8bits esterrone´,ilyade´tectionderreur. controˆlederedondancecyclique:CRC Less´equencesbinairessonttrait´eescommedespolˆesdontles ynom coecientscorrespondenta`las´equencebinaire.Onajoute`ala s´equencebinairelerestedunedivisionpolynomiale(divisionparle ` polynˆomege´n´erateur).Alar´eceptionlerestedeladisisionrecuet ¸ lerestedeladivisioncalcul´edoiventcoincideroualorsilyaerreur de transmission.
MarcChaumontIntr
ititnonioctduronttIon
Techniquedede´codage: Lede´codagesefaitparvotemajoritaire.Parexemple,silemotre¸cu est001,alorsonde´duitquelebit´emis´etait0.
0000 1111
Technique de codage : Pourunbitdinformation,3bitssontenvoye´s(cadcod´es)telsque :
ahmuraCcMroertcuedrerruer:lecodeder´ep´eicrexEeclpmecedeedodte´eeucttcrenoteceitrrceedocdesetionrsExrreunoisnemicnatsid,itacapeCetd´de´euxparam`principagneurud,teer:solserelonbinslai´eelub3seLrPscmae´IntocedLnsetcoiorud
Lescodeslin´eairnIrtdocuitnor,digueuion,mensmae`pxral:nortse3peseLulauipncricolbnesebmae´rPscrciCedoerruEsexiondeserecorrectoitcdtendedeete´paCat´cistdiceansfitulovnocseodscsuersvocblesucodonti
laquellelescodesblocnepouvaientpasˆetred´ecode´sdemani`eresouple.
Note2:Historiquement,lescodesconvolutifsont´et´epr´ef´er´espourleurde´codagesoupleetlacroyanceselon
Note3:Lesmeilleurscodesconnusa`cejour(de´butdu21e`mesi`ecle)sontlescodesblocs(i´uliers`afaibledensit´e rreg
Note1:Lechoixduncoded´ependdelapplication.
codes blocs versus codes convolutifs Lescodescorrecteursderreur(ECC)peuventeˆtredivise´sen2 classes : les codes en bloc traitent chaque bloc d’information: Ils ind´ependammentlesunsdesautres.Chaquemotdecodeest inde´pendantdesautresmotsdecode. les codes convolutifseidnuoc:aLostrutold´ifurdenvconeped delinformationcourantea`coderainsiquedelinformation pre´ce´denteetl´etatducodeur.
deparit´e)aMcrhCuaomtnnIrt