48 Application des corps ﬁnis aux codes correcteurs d’erreur

Le code de Hamming est donc un code binaire parfait On peut de la même manière construire un code de Hamming pour toutes les valeurs de k La matrice de contrôle de parité est constituée de tous les 2k – 1 vecteurs non nuls de longueur k On a donc toujours un code 1-correcteur parfait La matrice H est de taille (2k –1) x k

Codes Correcteurs dErreurs Cours 1 + Introduction + Codes

Exemple de code d´etecteur et correcteur d’erreur : le code de r´ep´etition Technique de codage : Pour un bit d’information, 3 bits sont envoy´es (cad cod´es) tels que: 0 → 000 1 → 111 Technique de d´ecodage : Le d´ecodage se fait par vote majoritaire Par exemple, si le mot re¸cu est 001, alors on d´eduit que le bit ´emis

Techniques de détection & de correction des erreurs de

R Kanawati, Cours réseaux, IUT de Villetaneuse, département GTR, 1er année, 2002-2003 Code de Hamming n La distance de Hamming entre deux séquences binaires de même taille est égale au nombre de bits de rang identique par lesquels elles différent n Exemple : d(1100110, 1010110) = 2 n Soit un code composé de N mot valides

TD Réseau Les codes correcteurs et les codes détecteurs

Le code de Hamming (2) Retrouver l’erreur dans un mot de Hamming Si les bits de contrôle de réception C0 2C 0 1C 0 0 valent 0, il n’y a pas d’erreur sinon la valeur des bits de contrôle indique la position de l’erreur entre 1 et 7 Si C0 0 vaut 1, les valeurs possibles de C 0 2C 0 1C 0 0 sont 001, 011, 101, 111, c’est-à-dire 1, 3

Cours : Codes correcteurs

Cours : Codes correcteurs Emily Clement Enseignant : Delphine Boucher Master 1 de Mathématiques Semestre 2 2015-2016

Theorie des codes´ correcteurs d’erreurs I

1 6 Capacité de détection et de correction d'un code 7 1 8 Bornes sur les codes 9 1 9 Codes Parfaits 10 1 10 Exercices 11 Chapitre 2 Codes linéaires 15 2 1 Dé nition 15 2 2 Matrice génératrice 15 2 4 Code dual et matrice de contrôle 16 2 9 Distance minimale 18 2 12 Décodage 21 2 16 Rayon de couverture 24 2 17 Construction de

Le contrôle d’erreur - imag

• Distance de Hamming du code complet (ou distance minimale) h = { Min Disth(x1, x2) ; x1 et x2 ∈ M et x1≠x2} M est l’ensemble des 2 m mots de codes possibles si on admet que les r bits de contrôle sont calculés en fonction des m bits de données Contrôle d’erreur : un modèle d’étude

48 Application des corps ﬁnis aux codes correcteurs d’erreur

4 8 Application des corps ﬁnis aux codes correcteurs d’erreur Cette section se veut une introduction succincte et très partielle à la vaste théorie des codes correcteurs, l’une des applications pratiques les plus célèbres de la théorie des corps

Mot information Mot code

RSE : exercices MRI 20-21 7 La chaîne 1011001 a été reçue par une entité de la couche liaison dont le protocole implique l'utilisation du code de Hamming correcteur d'une erreur Si vous savez qu'au maximum une seule erreur s'est produite, corrigez la chaîne et donneu les bits d'information transmis originalement 8

4.8 Application des corps finis aux codes correcteurs d'erreur

Cette section se veut une introdu

ction succincte et très partielle à la vaste théorie des

codes correcteurs, l'une des applications pratiques les plus célèbres de la théorie des corps

fi nis (qui n'a jamais entendu parler de corps fi nis sans être informés qu'ils sont indispensables à la technologie des disques compacts?). Les exigences du programme o ffi ciel en la matière ne sont pas claires : le contenu exact est " codes cycliques », sans aucune autre précision... On se concentre ici sur les aspects directement liés aux outils mathém atiques qu'on a vus dans les sections précédentes, sans vraiment insister sur l'aspect pratique de la mise en oeuvre e ff ective des codes correcteurs et l'e ffi cacité des algorithmes de décodage; il faudrait

déjà pour cela introduire la notion de complexité d'un algorithme; ceux qui connaissent cette

notion pourront essayer d'estimer la complexité des algorithmes présentés et/ou se reporter aux références ci-dessous. La démonstr ation de certains résultats fait l'objet d'exercices de TD.

Si vous souhaitez approfondir le sujet,

l'ouvrage destiné aux étudiants de licence le plus complet en ce qui concerne la théorie des codes est sans doute le

Cours d'algèbre

, de Michel

Demazure

, aux éditions Cassini. Il contient entre autre un chapitre décrivant précisément le codage réellement employé sur les disques compacts.

Nous signalons aussi comme références ut

iles : le complément 1 du chapitre 4 de

Mathématiques L2

, ouvrage collectif aux éditions

Pearson;

le chapitre 21 de

Toute l'algèbre de la licen

ce , de Jean-Pierre

Escofier

, aux éditions

Dunod.

Ces deux références couvrent peu ou prou le même matériel que ce qui suit, avec sans doute

plus d'exemples.

4.8.1 Introduction en agitant les mains

L'idée de départ qui sous-tend la théorie des codes correcteurs d'erreurs est la suivante. transmises par un certain canal. Le canal de transmission n'étant pas parfait, ces informations sont également susceptibles d'être altérées au cours de la transmission. d'un plus gros ensemble d'informationsℬ. Cet ensembleℬest munie d'une certaine distance qui mesure à quel point deux éléments de sont semblables.

Le codage doit véri

fi er, vis-à-vis de cette distance, les propriétés suivantes :

élément de

à distance pas trop grande de

les éléments de sont assez éloignés les uns de s autres. trouve à distance minimale de 47
Les alphabets radio (" Alpha, Bravo, Charlie... ») constituent une illustration basique mais assez parlante de ce type de construction. abet, destinées à être transmises oralement par ondes radios (typiquement un indicatif de navigation aérienne du genre " ATC ») et l'ensemble ℬest (disons) l'ensemble des mots de la langue utilisée pour la communication radio. La distance entre deux éléments de ℬmesure à quel point les prononciations de ces deux éléments sont phonétiquement di ff

érentes. Le codage associe à

chacune des lettres de l'alphabet un mot qui commence par la lettre en question (Alpha pour A, Bravo pour B, Charli e pour C, etc). Ce codage est choisi de sorte que l'ensemble de s mots associés aux lettres de l'alph abet soient mutuellement assez él oignés phonétiquement les uns des autres. Ainsi même si la communication est un peu parasitée , il sera facile de retrouver que l'émetteur a voulu transmettre par exemple Bravo (donc la lettre B) et pas un autre mot du code. En particulier il y a peu de risque de confondre après une communication pas trop parasitée les mots Bravo et Charlie, alors que phonétiquement la prononciation des

lettres B et C peut facilement être confondue dès qu'il y a un peu de " friture » sur la ligne.

4.8.2 Un cadre théorique (un peu trop) général

Les messages (ou " mots ») suscep

tibles d'être transmis sont écrits dans un certain alphabet , en d'autres termes un certain ensemble fi longueur strictement supérieure à , on le découpe en " blocs » de taille fi xe égale à Un codage (on code en " ajoutant de la redondance »). Le code proprement dit est alors l'imageC:= réellement transmis, a fi n de permettre la correction de cert aines erreurs éventuelles de transmission.

On dé

fi nit la distance entre deux éléments ( 1 et ( 1 de comme étant )) = card( 1

On véri

fi , appelée distance de Hamming

Le processus de codage/transmission/correction

/décodage peut alors se décrire ainsi;

1. Soit

un mot à transmettre; (A) on code en

éventuellement distinct

à cause des erreurs de transmission

3. (B)

àCet(C)on

calcule tel que Le nombre d'erreurs de transmission ). S'il n'y a pas d'erreur, on aura et 48
La distance minimale du codeCest la distance minimale entre deux éléments distincts 8 de C . On la note le code est d'après la dé fi he, on peut trouver au moins C ou, dans le meilleur des cas, n'e st pas l'unique élément de C véri fi ant cette propriété. est coûteux dans la pratique, puisque cela revient à augmenter la taille de l'information e ff ectivement transmise. Il est moins év ident a priori de construire des codes e ffi caces et peu coûteux, c'est-à-dire qui permettent de corriger de manière certaine un nombre raisonnable d'erreurs tout en gardant une longueur raisonnable. Noter que dans la pratique il est important aussi de disposer d'algo rithmes e ffi caces pour e ff ectuer les opérations(A),(B)et (C)de la procédure ci-dessus. L'opér ation(A)s'appelle codage, l'opération(B)correction et (B) (C) correction + décodage ; parfois (B) est appelée décodage. Il s'avère que pour construire des codes ayant de bonnes propriétés au sens ci-dessus, il est plus ou moins nécessaire de mettre plus de structure sur les objets considérés.

4.8.3 Codes linéaires

On s'intéresse désormais exclusivement à la famille particulière des codes linéaires K . Dans la pratique, il est fréquent (mais pas

systématique) de prendre pourKle corps à deux éléments, ce qui est très adapté à la

représentation par bits utilisée par les ordinateurs.

On dé

fi nit le comme étant son nombre de composantes et que la distance de Hamming est in variante par translation. dans les paramètres le cardinal du corps fi ni K de distance minimale , on a la contrainte suivante, appelée borne de Singleton 9

8. On écarte systématiquement dans la

suite le cas où le codeCest réduit à un élément, de peu d'intérêt dans la pratique.

9. du nom de R.C.

Singleton

, auteur d'un article de 1964 où ce résultat est démontré 49
Proposition 14.Avec les hypothèse précédentes (code linéaire de dimens gueur et de distance minimalequotesdbs_dbs10.pdfusesText_16

[PDF] 48 Application des corps ﬁnis aux codes correcteurs d’erreur

CH2 CODES CORRECTEURS - IGM

Codes Correcteurs dErreurs Cours 1 + Introduction + Codes

Techniques de détection & de correction des erreurs de

TD Réseau Les codes correcteurs et les codes détecteurs

Cours : Codes correcteurs

Theorie des codes´ correcteurs d’erreurs I

Le contrôle d’erreur - imag

48 Application des corps ﬁnis aux codes correcteurs d’erreur

Mot information Mot code

4.8 Application des corps finis aux codes correcteurs d'erreur

Cette section se veut une introdu

Si vous souhaitez approfondir le sujet,

Cours d'algèbre

Demazure

Nous signalons aussi comme références ut

Mathématiques L2

Pearson;

Toute l'algèbre de la licen

Escofier

Dunod.

4.8.1 Introduction en agitant les mains

Le codage doit véri

élément de

à distance pas trop grande de

érentes. Le codage associe à

4.8.2 Un cadre théorique (un peu trop) général

Les messages (ou " mots ») suscep

On dé

On véri

Le processus de codage/transmission/correction

1. Soit

éventuellement distinct

à cause des erreurs de transmission

àCet(C)on

4.8.3 Codes linéaires

On dé

8. On écarte systématiquement dans la

9. du nom de R.C.

Singleton