Modélisation et résolutions numérique et symbolique de problèmes via les logiciels Maple et MATLAB
38
pages
English
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
38
pages
English
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
Modélisation et résolutions numérique et symboliquede problèmes via les logiciels Maple et MATLAB(MODEL)oCours n 2 : Codes correcteurs d’erreursStef Graillat & Mohab Safey El DinUniversité Pierre et Marie Curie (Paris 6)S. Graillat & M. Safey (Univ. Paris 6) MODEL (cours n˚2) 1 / 35Résumé du cours précédentIntroduction à MapleRappels sur EuclideRappels sur les corps finisS. Graillat & M. Safey (Univ. Paris 6) MODEL (cours n˚2) 2 / 35Objectifs de ce cours1 Introduction aux codes correcteurs d’erreurs2 Codes linéaires3 Algorithme de codage et de décodage des codes linéairesS. Graillat & M. Safey (Univ. Paris 6) MODEL (cours n˚2) 3 / 35Plan du cours1 Généralités2 Modélisation3 Codes linéaires4 Décodage par syndromeS. Graillat & M. Safey (Univ. Paris 6) MODEL (cours n˚2) 4 / 35Bibliographie en françaisAlgèbre discrète et codes correcteurs, Odile Papini et JacquesWolfmann, Springer, 1996Cours d’algèbre. Primalité. Divisibilité. Codes, Michel Demazure,Cassini, 1997Codage, cryptologie et applications, Bruno Martin, PressesPolytechniques et Universitaires Romandes (PPUR), 2004Théorie des Codes : Compression, Cryptage et Correction, J.-G.Dumas, J.-L. Roch, E. Tannier and S. Varrette, Dunod, 2007Codes correcteurs : théorie et applications, A. Poli et L. Huguet,Masson, 1989Mathématiques et Technologie, C. Rousseau et Y. Saint-Aubin,Springer, 2008Codes correcteurs d’erreurs, G. Cohen, J.L. Dornstetter et P.Godlewski, Masson, 1992Article « Code ...
Voir
Publié par
Langue
English
Stef Graillat & Mohab Safey El Din
Université Pierre et Marie Curie (Paris 6)
Modélisation et résolutions numérique et symbolique de problèmes via les logiciels Maple et MATLAB (MODEL)
Cours no2 : Codes correcteurs d’erreurs
5
Rappels sur les corps finis
Introduction à Maple
Rappels sur Euclide
2/2)
Résumé du cours précédent
35uoc(˚nsrM)6sLEDO
Objectifs de ce cours
1
Introduction aux codes correcteurs d’erreurs
2
Codes linéaires
3
Algorithme de codage et de décodage des codes linéaires
3
Codes linéaires
Décodage par syndrome
4
1
Généralités
2
Modélisation
4/2)
Plan du cours
35ialltaM&.SrGniv.Pari.Safey(U
Algèbre discrète et codes correcteurs, Odile Papini et Jacques Wolfmann, Springer, 1996 Cours d’algèbre. Primalité. Divisibilité. Codes, Michel Demazure, Cassini, 1997 Codage, cryptologie et applications, Bruno Martin, Presses Polytechniques et Universitaires Romandes (PPUR), 2004 Théorie des Codes : Compression, Cryptage et Correction, J.-G. Dumas, J.-L. Roch, E. Tannier and S. Varrette, Dunod, 2007 Codes correcteurs : théorie et applications, A. Poli et L. Huguet, Masson, 1989 Mathématiques et Technologie, C. Rousseau et Y. Saint-Aubin, Springer, 2008 Codes correcteurs d’erreurs, G. Cohen, J.L. Dornstetter et P. Godlewski, Masson, 1992 Article « Code correcteur » de Wikipedia
llai&Mataf.S(UeyrG.S(coursn˚2)5/35
Bibliographie en français
in.vaPir6sM)DOLE
Applications of Abstract Algebra with Maple and MATLAB, Richard E. Klima, Neil Sigmon et Ernest Stitzinger, 2nd édition, Chapman & Hall/CRC, 2006 An Introduction to Coding Theory, J.H. van Lint, 3e édition, Springer, 1998 The theory of error-correcting codes, F. MacWilliams et N. Sloane, 11e édition North-Holland, 2003 Information and Coding Theory, G. A. Jones and J. M. Jones, Springer, 2000 Introduction to coding theory, R. M. Roth, Cambridge University Press, 2006 Coding theory and cryptography, the essentials, 2nd édition, D.R. Hankerson, D.G Hoffman, et al, Marcel Dekker, 2000 Fundamentals of error-correcting codes, W. C. Huffman et V. Pless, Cambridge University Press, 2003
2)6/35
Bibliographie en anglais
c(uosr˚n6sM)DOLEU(yefaS.iraP.vinGrS.&Matllai
S.
Graillat
&
M.
Safey
(Univ.
Paris
6)
Généralités
MODEL
(cours
n 2) ˚
7
/
35
Message→seMegasocnErueddé→Canal→Message reçu→Mseasegdécodé → enco
Problématique
Un messageMsera une suite dekbits.
Problème : lors de la transmission via lecanal, des erreurs peuvent s’être introduites (communications satellites, CD/DVD, modems, etc).
Idée : ajouter de laredondancepermet de pallier des erreurs (détection/correction).
2˚8)3/5
L’information à transmettre peut être vue comme une suite de symboles pris dans un ensemble fini. unalphabetAest un ensemble fini de symboles (typiquementA=F2 ouA=Fqcorps fini de cardinalitéq=pravecppremier). Unmessageou unmotsuite à valeur dans un alphabet, ilest une correspond à une suite de lettres. possibilité de modification (pas d effacement) de symboles lors de la ’ transmission. on traite l’information bloc par bloc (code en bloc).
Modélisation du problème
53GrS.llai&Mataf.S
Détection d’erreur par ajout de redondance : Le bit de parité
Exemple : |10|→|101| permet de détecter une erreur mais pas de corriger⇒on a vraiment besoin d’une distance
Sur un paquet dekbits, on ajoute unbit de paritéde sorte que la somme desk+1 bits envoyés soit paire. On détecte une erreur surk+1 bits envoyés.
/35c(uoDOLE)201sr˚niraPM)6sU(ye.vin&Mataf.SGrS.llai
Problématique : On envoie un motc∈ Cmais le mot reçurn appartient ’ pas àC; on va chercher à le décoder. 2 idées : 1DoterFnqd’une structure d’espace métrique (on se donne une distance)trouver un motc0deCt.q. sa distance àrest exactement la distance deràC; Principe de vraisemblance 2les codes correcteurs en les dotant de propriétésConstruire supplémentaires (algébriques)
5
Définition de codes
Définition 1 Uncode correcteurCsurFqdelongueur nest un sous-ensemble deFqn. Les éléments deCsont appelés desmots.
11/3n˚2)
