69
Codes Correcteurs d’Erreurs Limours, 19 Novembre 2003 Michel Waldschmidt Lycée Jules Verne

Codes Correcteurs d’Erreurs

  • Upload
    crete

  • View
    62

  • Download
    0

Embed Size (px)

DESCRIPTION

Lycée Jules Verne. Codes Correcteurs d’Erreurs. Limours, 19 Novembre 2003 Michel Waldschmidt. Applications des codes correcteurs d’erreurs. Télévision, Cd, CdRom, minitel, DVD, ordinateurs, internet,… Transmissions dans l’espace : Voyager 1 et 2, satellites, sondes spatiales, … Téléphonie, - PowerPoint PPT Presentation

Citation preview

Page 1: Codes Correcteurs d’Erreurs

Codes Correcteurs d’Erreurs

Limours, 19 Novembre 2003Michel Waldschmidt

Lycée Jules Verne

Page 2: Codes Correcteurs d’Erreurs

Applications des codes correcteurs d’erreurs

• Télévision, Cd, CdRom, minitel, DVD, ordinateurs, internet,…

• Transmissions dans l’espace : Voyager 1 et 2, satellites, sondes spatiales, …

• Téléphonie, téléphonie mobile, …

Page 3: Codes Correcteurs d’Erreurs
Page 4: Codes Correcteurs d’Erreurs

Ecouter un CD rayé

• Sur un disque compact comme sur un ordinateur, chaque son est codé par une suite de 0 et de 1, regroupés par paquets (les octets).

• Pour garantir la fidélité de l’enregistrement, on rajoute d’autres octets qui permettent de repérer et de corriger les petites erreurs dues aux poussières et aux rayures.

Page 5: Codes Correcteurs d’Erreurs

Un disque compact de bonne qualité contient facilement 500 000 erreurs!

• 1 seconde de signal audio = 1 411 200 bits.• La théorie mathématique des codes correcteurs d’erreur

permet d’augmenter la fiabilité du son tout en diminuant le coût du codage. Elle s’applique aussi à la transmission des informations par internet ou satellites.

Page 6: Codes Correcteurs d’Erreurs

Codage du son sur un CD

En utilisant un corps fini à 256 éléments, on peut corriger 2 erreurs sur chaque mot de 32 octets avec 4 octets de contrôle pour 28 octets d’information.

Page 7: Codes Correcteurs d’Erreurs

Olympus Mons sur la planète Mars

Image obtenue par la sonde spatiale Mariner 2 en 1971.

Page 8: Codes Correcteurs d’Erreurs

La sonde envoyait à la terre ses informations en utilisant un code correcteur d’erreurs capable de corriger jusqu’à 7 bits erronés sur 32.

Dans chaque groupe de 32 bits, 26 étaient des bits de contrôle et les 6 autres constituaient l’information nette.

Page 9: Codes Correcteurs d’Erreurs

Voyager 1 et 2 (1977)

• Itinéraire: Cap Canaveral, Jupiter, Saturne, Uranus, Neptune.

• Envoyait les informations en utilisant un code binaire permettant de corriger 3 erreurs sur des mots de longueur 24.

Page 10: Codes Correcteurs d’Erreurs

Codes et Maths• Algèbre (mathématiques

discrètes, corps finis, algèbre linéaire,…)

• Géométrie

• Probabilités et statistiques

Page 11: Codes Correcteurs d’Erreurs

Construire des codes qui détectent et corrigent le plus grand nombre possible d’erreurs, tout en allongeant le moins possible les messages, et qui soient faciles à décoder.

Page 12: Codes Correcteurs d’Erreurs

Transmission de données

Transmission

Source But

Page 13: Codes Correcteurs d’Erreurs

Transmission d’un message codé

transmission

Source Texte codé

Texte codé

But

Page 14: Codes Correcteurs d’Erreurs

Transmission imparfaited’un message codé

transmission

Source Texte codé

Bruit

Texte codé

But

Page 15: Codes Correcteurs d’Erreurs

Détecter une erreur

• Envoyer deux fois le même message

2 mots autorisés sur 4=22

(1 lettre utile sur 2)

Mots autorisés

(deux lettres)

0 0

1 1

Taux: 1/2

Page 16: Codes Correcteurs d’Erreurs

Principe du codage :

on autorise seulement certains « mots »

(code = dictionnaire des mots autorisés).

Les lettres « utiles » sont celles qui portent l’information, les autres (bits de contrôle, clefs) permettent de détecter des erreurs.

Taux: nombre de lettres utiles / nombre total de lettres

Page 17: Codes Correcteurs d’Erreurs

Principe du codage permettant de détecter une erreur:

deux mots autorisés distincts ont au moins deux lettres différentes

Page 18: Codes Correcteurs d’Erreurs

Corriger une erreur

• Envoyer trois fois le même message

2 mots autorisés sur 8=23

(1 lettre utile sur 3)

Mots autorisés

(trois lettres)

0 0 0

1 1 1

Taux: 1/3

Page 19: Codes Correcteurs d’Erreurs

• On corrige 0 0 1 en 0 0 0

• 0 1 0 en 0 0 0

• 1 0 0 en 0 0 0

et

• 1 1 0 en 1 1 1

• 1 0 1 en 1 1 1

• 0 1 1 en 1 1 1

Page 20: Codes Correcteurs d’Erreurs

Principe du codage permettant de corriger une erreur:

deux mots distincts autorisés ont au moins

trois lettres différentes

S’il y a une erreur et une seule, il y a exactement un mot du code qui la corrige.

Page 21: Codes Correcteurs d’Erreurs

Un autre code détectant une erreur

Améliorer le taux 1/2 du code {(0,0), (1,1)} Mots autorisés (trois lettres):

0 0 00 1 11 0 11 1 0

bit de parité: (x y z) avec z=x+y modulo 2.

4=22=22 mots autorisés sur 8=2 2 2=23

(2 lettres utiles sur 3).Taux: 2/3

Page 22: Codes Correcteurs d’Erreurs

Mots autorisés Mots Interdits

0 0 0

0 1 1

1 0 1

1 1 0

0 0 1

0 1 0

1 0 0

1 1 1

Deux mots autorisés distincts ont au moins deux lettres différentes.

Page 23: Codes Correcteurs d’Erreurs

Un autre code corrigeant une erreur

Améliorer le taux 1/3 du code {(0,0,0), (1,1,1)}

Mots de 7 lettres

Mots autorisés: (16=24 sur 128=27)

(a b c d e f g)Avec (modulo 2)

e=a+b+d f=a+c+d g=a+b+c

Taux: 4/7

Page 24: Codes Correcteurs d’Erreurs

Le code binaire de Hamming et Shannon (1948) 16 mots de 7 lettres autorisés

0 0 0 0 0 0 0

0 0 0 1 1 1 0

0 0 1 0 0 1 1

0 0 1 1 1 0 1

0 1 0 0 1 0 1

0 1 0 1 0 1 1

0 1 1 0 1 1 0

0 1 1 1 0 0 0

1 0 0 0 1 1 1

1 0 0 1 0 0 1

1 0 1 0 1 0 0

1 0 1 1 0 1 0

1 1 0 0 0 1 0

1 1 0 1 1 0 0

1 1 1 0 0 0 1

1 1 1 1 1 1 1

Deux mots distincts ont au moins trois lettres différentes.

Page 25: Codes Correcteurs d’Erreurs

Distance de HammingRichard W. Hamming (1915-1998)

• La distance de Hamming de deux mots est le nombre de lettres différentes.

• Un code permettant de détecter n erreurs est un code dont la distance de Hamming entre deux mots distincts est au moins n+1.

• Un code permettant de corriger n erreurs est un code dont la distance de Hamming minimale est au moins 2n+1.

Page 26: Codes Correcteurs d’Erreurs

But: décrire des codes dont les mots ont des distances de Hamming mutuelles grandes, avec un taux maximal.

Cela revient à trouver des « points » dont les distances mutuelles sont aussi grandes que possible.

Page 27: Codes Correcteurs d’Erreurs

Outils mathématiques

Algèbre linéaire: les bits de contrôle sont déterminés par des équations linéaires.

Théorie des corps finis

(Evariste Galois, 1811-1832).

Résolution des équations algébriques par radicaux.

Géométrie algébrique, codes géométriques.

Page 28: Codes Correcteurs d’Erreurs
Page 29: Codes Correcteurs d’Erreurs

Le code binaire de Hamming et Shannon

C’est un code linéaire (la somme de deux mots du code est un mot du code) et les 16=24 boules de rayon 1 centrées aux mots du code recouvrent l’espace formé par les 128=27 mots binaires de longueur 7=23-1

(chaque mot a 7 voisins, et (7+1)16= 256).

Page 30: Codes Correcteurs d’Erreurs

Empilement de sphères

Page 31: Codes Correcteurs d’Erreurs

Empilement de sphères

• Problème de Kepler: densité maximale d'empilement de sphères identiques:

  / 18= 0,740 480 49…

Conjecturé en 1611.

Démontré en 1999 par Thomas Hales.

• Liens avec la cristallographie.

Page 32: Codes Correcteurs d’Erreurs

Le problème des chapeaux

• Trois personnes ont chacune un chapeau, blanc ou noir, sur la tête. Les couleurs sont choisies au hasard. Chacun voit la couleur du chapeau sur la tête des deux autres, mais ne connaît pas la couleur de son propre chapeau. Ils ne communiquent pas.

• Chacun écrit sur un papier la couleur qu’il devine pour son propre chapeau: blanc, noir, ou bien il s’abstient.

Page 33: Codes Correcteurs d’Erreurs

• L’équipe gagne si une au moins des trois personnes ne s’est pas abstenue, et tout ceux qui ne se sont pas abstenus ont donné une réponse correcte.

Page 34: Codes Correcteurs d’Erreurs

• Stratégie simple: ils conviennent à l’avance que deux d’entre eux s’abstiennent, le troisième donne une réponse au hasard. La probabilité qu’ils gagnent est : 1/2.

• Peut-on améliorer cette probabilité?

Page 35: Codes Correcteurs d’Erreurs

• Indication:

Améliorer les chances en utilisant l’information disponible: chacun connaît la couleur des deux autres.

Page 36: Codes Correcteurs d’Erreurs

• Meilleure stratégie: si l’un des trois voit deux chapeaux (sur la tête des autres) de la même couleur, il parie que son chapeau est de l’autre couleur. S’il voit deux chapeaux de couleurs distinctes, il s’abstient.

Page 37: Codes Correcteurs d’Erreurs

Gagné!

Page 38: Codes Correcteurs d’Erreurs

Perdu!

Page 39: Codes Correcteurs d’Erreurs

Gagnant:

Page 40: Codes Correcteurs d’Erreurs

Perdant:

Page 41: Codes Correcteurs d’Erreurs

• L’équipe gagne exactement quand les trois chapeaux ne sont pas tous de la même couleur, c’est-à-dire dans 6 cas sur 8

• Probabilité de gagner: 3/4.

Page 42: Codes Correcteurs d’Erreurs

• Y a-t-il de meilleures stratégies?

Réponse: NON!• Y a-t-il d’autres stratégies donnant la

probabilité de gagner 3/4?

Réponse: OUI!

Page 43: Codes Correcteurs d’Erreurs

Pile ou Face

• Lancer une pièce de monnaie trois fois de suite

• Il y a 8 résultats possibles:

(0,0,0), (0,0,1), (0,1,0), (0,1,1),

(1,0,0), (1,0,1), (1,1,0), (1,1,1).

Page 44: Codes Correcteurs d’Erreurs

Si vous pariez que le résultat sera (0,1,0), vous avez :

• Les trois valeurs justes si la suite est (0,1,0).

• Exactement deux bonnes valeurs si c’est (0,1,1), (0,0,0) ou (1,1,0),

• Exactement une bonne valeur si c’est (0,0,1), (1,1,1) ou (1,0,0),

• Aucune bonne valeur pour (1,0,1).

Page 45: Codes Correcteurs d’Erreurs

Quelque soit le résultat final (8 possibilités),

chaque pari

a les trois valeurs justes dans 1 cas

a exactement deux valeurs justes dans 3 cas

a exactement une valeur juste dans 3 cas

has zéro valeur juste dans 1 cas

Page 46: Codes Correcteurs d’Erreurs

• But: être sûr d’avoir au moins deux valeurs justes

• Évidemment, un seul pari ne suffit pas• Suffit-il de deux paris? On rappelle qu’il y a 8 résultats possibles

et que chaque pari a au moins 2 réponses justes dans 4 cas.

Page 47: Codes Correcteurs d’Erreurs

Réponse: OUI, deux paris suffisent!

Par exemple si on parie

(0,0,0) et (1,1,1)

dans tous les cas, l’un des deux chiffres

0 et 1

sortira plus d’une fois.

Donc un (et seulement un) des deux paris aura deux ou trois résultats justes.

Page 48: Codes Correcteurs d’Erreurs

Autres solutions:

• On choisit deux tickets n’ayant pas de chiffre commun, comme

(0 0 1) et (1 1 0)

Ou bien le résultat est l’un de ces deux,

ou bien il a exactement un chiffre au même endroit en commun avec l’un des deux et deux en commun avec l’autre.

Page 49: Codes Correcteurs d’Erreurs

• Revenons au cas de (0,0,0) et (1,1,1)Les 8 mots formées de 3 lettres 0 et 1 Se répartissent en deux groupes: celles qui ont deux ou trois 0et celles qui ont deux ou trois 1

Page 50: Codes Correcteurs d’Erreurs

(0,0,1)

(0,0,0) (0,1,0)

(1,0,0)

(1,1,0)

(1,1,1) (1,0,1)

(0,1,1)

Page 51: Codes Correcteurs d’Erreurs

Distance de Hamming entre deux mots:

= nombre de places où les deux mots n’ont pas la même lettre

Exemples:

(0,0,1) et (0,0,0) sont à distance 1

(1,0,1) et (1,1,0) sont à distance 2

(0,0,1) et (1,1,0) sont à distance 3Richard W. Hamming (1915-1998)

Page 52: Codes Correcteurs d’Erreurs

• L’ensemble des huit mots de trois lettres se réparti en deux boules

• Les centres sont (0,0,0) et (1,1,1)

• Chacune des deux boules est formée des mots dont la distance est au plus 1 du centre.

Page 53: Codes Correcteurs d’Erreurs

Retour au problème des chapeaux

• On remplace blanc par 0 et noir par 1 Ainsi la répartition des couleurs devient un

mot à trois lettres sur l’alphabet {0 , 1}• On considère les centres des boules (0,0,0)

et (1,1,1).• L’équipe parie que le résultat ne correspond

pas à un des centres des boules.

Page 54: Codes Correcteurs d’Erreurs

Si la répartition des couleurs ne correspond pas à un des centres des boules

(0, 0, 0) et (1, 1, 1). alors:

• Une couleur intervient exactement deux fois (le mot comporte les deux chiffres 0 et 1).

• Un et un seul des membres de l’équipe voit deux fois la même couleur: 0 0 s’il voit deux chapeaux blancs, 1 1 s’il voit deux chapeaux noirs. Il connaît le centre de la boule: (0, 0, 0) dans le premier cas, (1, 1, 1) dans le second.

• Il parie donc que le chiffre qu’il ne connaît pas est celui qui ne produit pas le centre de la boule.

Page 55: Codes Correcteurs d’Erreurs

• Les deux autres voient deux couleurs différentes, ils ne connaissent pas le centre de la boule, ils s’abstiennent (accessoirement ils savent que l’équipe va gagner).

• Ainsi l’équipe gagne quand la répartition des couleurs ne correspond pas à l’un des deux centres..

• C’est pourquoi l’équipe gagne dans 6 cas.

Page 56: Codes Correcteurs d’Erreurs

• Maintenant si la répartition des couleurs (le mot de trois lettres) correspond à un des centres, chacun des membres de l’équipe donne la mauvaise réponse!

• Ils perdent dans 2 cas.

Page 57: Codes Correcteurs d’Erreurs

Autre stratégie:

• On choisit deux mots dont la distance de Hamming est 3 - c’est-à-dire deux mots n’ayant pas de même lettre à la même place, comme (0,0,1) et (1,1,0)

• On considère les deux boules, centrées en ces deux mots, formées des éléments à distance au plus 1 du centre.

Page 58: Codes Correcteurs d’Erreurs

(0,0,0)

(0,0,1) (0,1,1)

(1,0,1)

(1,1,1)

(1,1,0) (1,0,0)

(0,1,0)

Page 59: Codes Correcteurs d’Erreurs

• L’équipe parie que la distribution des couleurs ne correspond pas à l’un des deux centres (0,0,1), (1,1,0) .

• Un mot qui n’est pas au centre a exactement une lettre distincte du mot du centre, et deux différentes de l’autre centre.

Page 60: Codes Correcteurs d’Erreurs

Si le mot correspondant à la répartition des couleurs n’est pas un des deux centres,

alors:

• Exactement un des membres de l’équipe connaît le centre, il sait donc quoi parier.

• Les autres ne connaissent pas le centre, ils s’abstiennent.

• Dans ce cas l’équipe gagne.

Page 61: Codes Correcteurs d’Erreurs

Si le mot correspondant à la répartition des couleurs est un des deux centres,

alors:

• Chacun des membres de l’équipe parie le mauvais résultat.

• Ainsi l’équipe perd dans 2 cas sur 8.

Page 62: Codes Correcteurs d’Erreurs

Le problème des chapeaux avec 7 personnes

• L’équipe parie que la répartition des couleurs ne correspond pas aux 16 éléments du code de Hamming.

• L’équipe perd dans 16 cas (ils se trompent tous!)• Elle gagne dans 128-16=112 cas (un seul donne la

réponse, les 6 autres s’abstiennent)• Probabilité de gagner: 112/128=7/8

Page 63: Codes Correcteurs d’Erreurs

Pile ou face 7 fois

• Il y a 27=128 résultats possibles

• Chaque pari est un mot de 7 lettres sur l’alphabet {0, 1}

• Combien de pari faut-il faire pour être sûr d’avoir au moins 6 résultats corrects?

Page 64: Codes Correcteurs d’Erreurs

• Chacun des 16 mots du code de Hamming a 7 voisins (à distance 1), la boule dont il est le centre a 8 éléments.

• Chacun des 128 mots est dans une et une seule de ces boules.

Page 65: Codes Correcteurs d’Erreurs

• Faire 16 paris correspondant aux 16 mots du code: dans tous les cas exactement un des paris aura au moins 6 réponses justes.

Page 66: Codes Correcteurs d’Erreurs

SPORT TOTO

• Un match entre deux adversaires a trois issues possibles: ou bien le joueur 1 gagne, ou bien le 2, ou sinon il y a match nul (x).

• Comment parier sur les résultats de 4 matches en étant sûr d’avoir au moins 3 réponses justes?

Page 67: Codes Correcteurs d’Erreurs

• Pour 4 matches, il y a 3 = 81 possibilités. • Un pari sur 4 matches est un mot de 4

lettres sur l’alphabet {1, 2, x}. Un mot a 8 voisins (à distance 1). Par exemple les 8 voisins de (1, 2, x, 1) sont

(2, 2, x, 1), (1, 1, x, 1), (1, 2, 1, 1), (1, 2, x, 2)(x, 2, x, 1), (1, x, x, 1), (1, 2, 2, 1), (1, 2, x, x)

4

Page 68: Codes Correcteurs d’Erreurs

• Chaque pari donne 4 réponses justes dans 1 cas et 3 réponses justes dans 8 cas, donc au moins 3 réponses justes dans 9 cas.

• Il faut donc faire au moins 9 paris pour être sûr d’avoir au moins 3 réponses justes.

Comment choisir ces 9 paris?

Page 69: Codes Correcteurs d’Erreurs

9 mots de 4 lettres (en colonnes)

x x x 1 1 1 2 2 2

x 1 2 x 1 2 x 1 2

x 1 2 1 2 x 2 x 1

x 1 2 2 x 1 1 2 x

ce code corrige une erreur

Taux: 1/2