5

Codes détecteurs codes correcteurs

1. Pourquoi coder ?

2. Distance de Hamming

3. Erreurs de transmission

4. Correction et détection

MVA004

Chapitre 17Codes détecteurs - Codes correcteurs

6

antennes

Pour transmettre des données, on envoie des mots binaires :0011010100110010111100011010100110010111101100011

7

orage

Diverses causes produisent des erreurs

0 —> 1 1 —> 0

8

que faire ?

28 Mbit/s = 100 800 000 000 bits/heure

Même si seulement 1 bit sur 1 million est faux, au bout d'une heure :

100 800 bits sont mal transmis !

Que faire ?

9

emballage

Donner un aspect caractéristique aux mots binaires que l'on transmet en ajoutant des bits supplémentaires qui serviront d'emballage.

10

devinette

Si je reçois, sans aucune protection :

0011010100110010111100011010100110010111101100011

est-ce que je peux deviner la présence d'une erreur ? Non …

Mais si je reçois ?

00000 11111 00000 00000 11101 00000 11111 00000 11111

00000 11111 00000 00000 11101 00000 11111 00000 11111

11

code détecteur

Inconvénients : 1) la retransmission peut être fausse elle aussi,2) on n'a pas toujours le temps de retransmettre !

On peut mettre en place un dispositif qui détecte la présence de bits faux afin de recommencer la transmission.

12

code correcteur

Inconvénients : 1) la correction n'est pas complètement fiable,2) plus la correction est bonne, plus elle va ralentir le débit …

On peut mettre en place un dispositif qui détecte et corrige par lui-même les bits faux.

13

§2 distance

Chapitre 17Codes détecteurs - Codes correcteurs

1. Pourquoi coder ?

2. Distance de Hamming

3. Erreurs de transmission

4. Correction et détection

MVA004

14

XOR

Préliminaires mathématiques

Le poids d'un mot binaire est le nombre de ses bits égaux à 1.

w(001110101101) = 7

Addition modulo 2 de deux bits (parité)

autre nom : XOR (eXclusive OR)

15

ajout d'un bit

Remarque :

addition d'un 0

0 —> 01 —> 1

addition d'un 1

0 —> 11 —> 0

· · modifier un bit, c'est lui ajouter 1,· · le laisser tel quel, c'est lui ajouter 0.

Règle :

16

add de mots binaires

Addition modulo 2 de deux mots binaires de même longueur

0 1 1 0

1 0 1 0

1 1 0 0

a

b+a b

Propriétés :+a b + ab=

+(a b) c+ a= +(b c)+ = +a b c+

+a 0 a= +a a 0=

17

chang mbr

+a b c= +b ca ==>

Dans une égalité, tout terme change librement de membre !

Propriété fondamentale

Règle :

+a b c=

18

distance de Ha

0010110100001101

0010110101010110

0010110100001101

0010110101010110

Question : Comment mesurer la dissemblance de 2 mots binaires de même longueur ?

Réponse :

Compter le nombre de fois où leurs bits diffèrent

Le nombre de bits différents s'appelle la distance de Hamming des deux mots binaires

19

propriétés de distance

Propriétés :

d(a,b ) = d(b,a )

d(a,b ) ≥ 0 d(a,b ) = 0 <=> a = b

d(a,b ) + d(b,c) ≥ d(a,c)

d(a + x,b + x) = d(a,b )

d(a,b ) = w( a + b)

20

cube

000 100

001

010 110

111011

101

La distance entre deux mots binaires est le nombre d'arêtes qu'il faut longer pour se rendre de a à b par le chemin le plus court

Règle :

4

complément

Complément

Si a et b sont de même longueur, alors :d(a,b) = w(a + b) et w(a) + w(b) ont la même paritéAutrement dit :d(a,b) = w(a + b) = w(a) + w(b) - 2h,où h est un entier positif ou nul.

Exemples

00101101+ 00001101 00100000

00101101+ 01010110 01111011

5

détection

émetteur et receveur se mettent d'accord pour choisir les mots de code

envoyé

Creçu

R

Détection :

– quand R est un mot de code, on n'en sait rien.

– quand R n'est pas un mot de code, la transmission est fausse,

6

correction(1)

Correction : le receveur devine e, puis il calcule :

Pour deviner e il fait la somme de R et de tous les mots de code, puis il choisit le mot de plus petit poids dans la liste qu'il obtient, car c'est le vecteur d'erreur le plus probable.

La carte de géographie des erreurs est donnée par le vecteur d'erreur :

e = C + Rw(e) = d(C,R) est le nombre d'erreurs.

reçu

Renvoyé

C

R = C + e

7

correction(2)

Pour faire cette liste, le receveur calcule tous les

Puisque : w(e' ) = d(R,C' ), décider que w(e) est la plus petite valeur possible pour w(e' ) revient à décider que C est le mot de code le plus proche de R.

Tout revient à dire que le receveur corrige R en le remplaçant par le mot de code le plus proche.

avec tous les mots de code C'.

e' = C' + R

8

§4

1. Pourquoi coder ?

2. Distance de Hamming

3. Erreurs de transmission

4. Codage par blocs

5. Correction et détection

MVA004

Chapitre 17Codes détecteurs - Codes correcteurs

9

codage par blocs(1)

Codage par blocs1) On groupe les bits à envoyer en blocs de k bits.Le nombre k s'appelle la dimension des blocs.

2) À chaque bloc on ajoute r bits de contrôle, choisis en fonction du bloc, pour obtenir un mot de code de longueur n = k + r. Cette opération s'appelle le codage du bloc.

Question : Comment choisir les mots de code ?

Quand les bits de contrôle sont placés à la fin du bloc, on dit que le codage est systématique.

k k r

10

codage par blocs(2)

Le rendement (ou le taux) du code est le rapport k/n

Les mots binaires de longueur n s'appellent les messages.Les mots de code sont certains messages particuliers.

Il y a 2n messages ; parmi eux 2k sont les mots de code.

On voudrait que le rendement soit le plus près possible de 1.

Le nombre n s'appelle la longueur du code.

Le nombre k s'appelle la dimension du code.

11

Test de parité(1)

Exemple 1 : test de pariték = 3, r = 1 : on ajoute un bit de parité de façon que le poids du mot obtenu soit pair.n = 4, taux = 0,75

Codage

000 —> 0000001 —> 0011010 —> 0101011 —> 0110100 —> 1001101 —> 1010110 —> 1100111 —> 1111

12

représentation

Test de parité : k = 3, r = 1, n = 4.

Représentations :

ou

blocs

000 001 010 011 100 101 110 111

mots decode

0000 0011 0101 0110 1001 1010 1100 1111

mots decode

0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 1

blocs

13

Test de parité(2)

0001

0000

0010 0100 1000

0011

0101

0111

0110

1001

1011 1101 1110

1111

1010

1100

R = 1011 ?

R = 1111 ?

Détection

14

Test de parité(3)

0000 q4

0001 p q3

0010 p q3

0011 p2q2

0100 p q3

0101 p2q2

0110 p2q2

0111 p3q1000 p q3

1001 p2q2

1010 p2q2

1011 p3q1100 p2q2

1101 p3q1110 p3q1111 p4

Total : q4 + 4 pq3 + 6p2q2 + 4p3q + p4 = (p + q)4 = 1

Probabilité de bonne transmission : q4

Probabilité de mauvaise transmission :

4 pq3 + 6p2q2 + 4p3q + p4 = 4 p - 6p2 + 4p3 - p4

Probabilité de ne pas s'en apercevoir :

6p2q2 + p4 = 6p2 - 12p3 + 7p4

Proportion de messages faux non détectés :

6p2 - 12p3 + 7p4

4 p - 6p2 + 4p3 - p4environ 1,5p

e

15

Test de parité(4)

Correction ?

Applications

- numéro INSEE (http://fr.wikipedia.org/wiki/Code_Insee)

- numéro ISBN (http://fr.wikipedia.org/wiki/ISBN)

1 97 10 75 113 212 12

2 10 049149 0

16

répétition(1)

Exemple 2 : codage par répétition

On ajoute deux bits de parité pour répéter 3 fois le bit à envoyer : k = 1, r = 2, n = 3, taux = 0,33…

Codage

0 —> 0001 —> 111

000 100

001

010 110

111011

101

17

répétition (2)

000 q3

001 p q2

010 p q2

011 p2q100 p q2

101 p2q110 p2q111 p3

Total : q3 + 3 pq2 + 3p2q + p3 = (p + q)3 = 1

Probabilité de bonne transmission : q3

Probabilité de mauvaise transmission :

3pq2 + 3p2q + p3 = 3p - 3p2 + p3 = 1 - q3

Probabilité de ne pas le voir : [remarque (1)] p3

Proportion de messages faux non détectés :

p3

3p - 3p2 + p3 environ

p2

3

18

répétition (3)

Correction

000 100

001

010 110

111011

101

0 bit faux —> bonne correction1 bit faux —> bonne correction2 bits faux —> mauvaise correction3 bits faux —> mauvaise correction

Probabilité de mauvaise correction : [remarque (2)]p3 + 3p2q = 3p2 - 2p3

Proportion de messages faux mal corrigés :

3p2 - 2p3

3p - 3p2 + p3 environ p

19

remarques

(1) Probabilité de se tromper à la détection :

Remarques :

Si on note C le mot de code émis, et C' le mot de code reçu, alors, l'événement correspondant s'écrit :

Ceci ne se produit que dans le cas où le mot reçu est un mot de code autre que celui qui a été émis.

{ C émis, C' reçu et C' ≠ C }

(2) Probabilité de se tromper à la correction :

Si on note C le mot de code émis, R le mot reçu, et C' la correction choisie pour R, alors, l'événement correspondant s'écrit :

Ceci se produit lorsque le mot reçu n'est pas un mot de code, et qu'il est « mal » corrigé.

{ C émis, R reçu corrigé en C', et C' ≠ C }

20

§5

1. Pourquoi coder ?

2. Distance de Hamming

3. Erreurs de transmission

4. Codage par blocs

5. Correction et détection

Chapitre 17Codes détecteurs - Codes correcteurs

21

distance minimale

– quand R est un mot de code, on n'en sait rien.

– quand R n'est pas un mot de code, la transmission est fausse,

On a donc intérêt à ce que les mots de code soient le plus possible éloignés les uns des autres !

On note d la plus petite distance séparant deux mots de code. Le nombre d s'appelle la distance minimale du code.

- Quand on prend deux mots de code quelconques, la distance qui les sépare est supérieure ou égale à d.- On peut trouver deux mots de code particuliers qui se trouvent exactement à la distance d l'un de l'autre.

Remarques :

Détection

22

Th distance minimale

- Tant que 0 < N < d, le receveur détecte la présence d'erreur.- Quand N ≥ d, il arrive que le receveur ne détecte pas la présence d'erreur.

ThéorèmeN, le nombre d'erreurs, est égal à d(R,C).

Petit nombre d'erreurs (0 < N < d) —> certitudeGrand nombre d'erreurs (N ≥ d) —> doute

Commentaire

reçu

Renvoyé

C

Donc, d - 1 est le nombre maximum d'erreurs détectées de façon certaine, ou « à coup sûr ».On dit que le code détecte à coup sûr jusqu'à (d - 1) erreurs, ou qu'il est « (d - 1)-détecteur ».

23

Th distance minimale (ex)

000 100

001

010 110

111011

101

0001

0000

0010 0100 1000

0011

0101

0111

0110

1001

1011 1101 1110

1111

1010

1100

d = 2 (code 1-détecteur)

d = 3 (code 2-détecteur)

24

correction

CorrectionOn remplace R par le mot de code le plus proche.

- Tant que 0 ≤ N < d/2, la correction est bonne.- Quand N ≥ d/2, il arrive qu'elle ne soit pas bonne.

Théorème

Démonstration

Avec 0 ≤ N < d/2, la correction pourrait-elle être mauvaise ?

envoyé

Creçu

Rcorrigé

C'

d(R,C') < d(R,C)d(C,C') ≤ d(C,R) + d(R,C')

25

t

Tant que 0 ≤ N ≤ t, la correction est bonne.

d t

1 02 03 14 15 26 27 3

On note t le plus grand nombre entier strictement inférieur à d/2.

t = (partie entière)d - 1

2

On dit que le code corrige de façon certaine (ou « à coup sûr ») jusqu'à t erreurs, ou encore qu'il est « t-correcteur ».

Si t = 0, on dit que le code n'est pas correcteur.

26

correc (ex)

000 100

001

010 110

111011

101d = 3t = 1

Tant que 0 ≤ N ≤ 1, la correction est bonne.

La correction est bonne quand N = 0 ou N = 1.

Les nombres d et t mesurent la qualité du code.

Exemple

27

[n,k,d]

Les nombres n et k ne déterminent pas d de façon certaine.

110

111

000 100

001

010

011

101

000 100

001

010 110

111011

101

000

001

100

010 110

111011

101

On dit qu'on a un code [n,k,d]

Ayant choisi n et k, on cherche le code qui donne le meilleur d possible.

28

3-cube

Avec k fixé, on peut séparer les mots de code en augmentant n mais le taux diminue !

000 100

001

010 110

111011

101

d = 3

taux = 1/3

Exemple : codage par répétition d'ordre 3

29

4-cube

d = 4

taux = 1/4

0001

0000

0010 0100 1000

0011

0101

0111

0110

1001

1011 11011110

1111

1010

1100

Exemple : codage par répétition d'ordre 4

t = = = 1 4 - 1

2 2

3

30

inégalité de Hamming

Inégalité de Hamming

Cn0 + Cn

1 + Cn2 + … + Cn

t ≤ 2r

Il y a mieux que l'inégalité évidente : d ≤ n

Les nombres n et k étant fixés (donc r aussi), cette inégalité donne le meilleur t possible.Ce maximum s'appelle la borne de Hamming.

31

5-cube

C

- il y a Cnp messages

à la distance p de C

C'

- les messages à la distance p ≤ t de C sont tous différents des messages à la distance p ≤ t de C'.

2k (Cn0 + Cn

1 + Cn2 + … + Cn

t) ≤ 2n = 2k+r

32

inégalité de Hamming

Utilisation : On calcule

Cn0

Cn0 + Cn

1 Cn

0 + Cn1 + Cn

2

en surveillant si l'on dépasse 2r.

Quand Cn0 + Cn

1 + … + Cnm dépasse 2r, le

nombre m vient de dépasser t.

Définition :

On dit qu'un code est parfait lorsque

Cn0 + Cn

1 + Cn2 + … + Cn

t = 2r

33

inégalité de Hamming

Exemple : r = 1

Cn0 + Cn

1 + Cn2 + … + Cn

t ≤ 2

Cn0 = 1

Cn0 + Cn

1 = 1 + n

mais n = k + r ≥ 2, donc 1 + n ≥ 3 et

Par conséquent : 1 > t et t = 0.

Avec un seul bit de contrôle on ne peut pas faire un code correcteur !

Cn0 + Cn

1 > 2