Modélisation et résolutions numérique et symbolique de problèmes via les logiciels Maple et MATLAB

Stef Graillat & Mohab Safey El Din

Description

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 ...

Informations

• Publié par: Phewyig
• Nombre de lectures: 49
• Langue: English

Extrait

SaSef&t.MlialG.ar6)MOarisiv.Py(Un3/1)2˚nsruoc(LED

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 n o 2 : Codes correcteurs d’erreurs

5

yeU(S.faaPirin.vS.Grat&Maill

Rappels sur les corps finis

Introduction à Maple

Rappels sur Euclide

2/2)

Résumé du cours précédent

35uoc(˚nsrM)6sLEDO

S.atllaiGryefaS.M&aP.vinU(ris6)MODEL(cours˚n)2/353

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

uoc(˚nsrM)6sLEDO

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

snurcoL(DEMO6)israP.vinU(yefaS.Mlat&railS.G

Message→ seMegas ocnErued dé →Canal→Message reçu→ Mseaseg dé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

(couODEL2)9/rsn˚in.vyeU(6sM)aPir

L’information à transmettre peut être vue comme une suite de symboles pris dans un ensemble fini. unalphabetAest un ensemble fini de symboles (typiquementA=F 2 ouA=F q corps fini de cardinalitéq=p r avecppremier). 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

ni(UPav..S&Meyafc(LEsruo6sirDOM)rGiallta.S

Problématique : On envoie un motc∈ Cmais le mot reçurn appartient ’ pas àC; on va chercher à le décoder. 2 idées : 1 DoterF n q d’une structure d’espace métrique (on se donne une distance)
trouver un motc 0 deCt.q. sa distance àrest exactement la distance deràC; Principe de vraisemblance 2 les codes correcteurs en les dotant de propriétésConstruire supplémentaires (algébriques)

5

Définition de codes

Définition 1 Uncode correcteurCsurF q delongueur nest un sous-ensemble deF qn . Les éléments deCsont appelés desmots.

11/3n˚2)