Codes détecteurs et correcteurs B Rouzeyre

et pourtant 8 erreurs (on a reçu un mot de code) " la détection d'anomalies ne permet pas de détecter le nombre d'anomalies ex : si 1 1 0 0 1 0 1 0 devient 0 0 1 1 0 1 0 0, on ne pas savoir qu'il y a eu 7 erreurs # code parité => code détecteur d'un nombre impair d'erreurs mais ne permet pas de corriger des erreurs

Codes correcteur d’erreur

Zéro erreur : y est un mot du code Quelques erreurs : corriger y en un mot du code Quelques erreurs : correction impossible Le décodeur peut se tromper Il peut choisir un mot de code à la place d’un autre Il choisit le mot qui a la probabilité la plus grande d’être correcte On suppose que

Codages détecteurs/correcteurs 1 Exercices

1 2 Détection/correction d'erreurs Exercice 3-3 Numéro INSEE Le numéro INSEE est un numéro composé de 13 chi res auquel on ajoute une clé de deux chi res pour contrôler d'éventuelles erreurs de saisie On obtient cette clé 1 en réduisant le numéro N modulo 97 : r = N (mod 97); 2 en retranchant r à 97 : la clé est k = 97 r

Cours : Codes correcteurs - ENS Rennes

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

TD Ing´enierie des R´eseaux Code d´etecteur et correcteur d

d 0x64 e 0x65 Donner la suite des octets qui seront transf´er´es V´eriﬁer que l’on corrige bien 1 erreur: exemple, le bit 7 (num´erotation de droite a gauche, en commencant par 0) du ’e’ est mal recu Exercice 4 Donner la matrice g´en´eratrice d’un code de Hammings cod´e sur 11 bits: 4 bits de contrˆole et 7 bits d’information

Theorie des codes´ correcteurs d’erreurs I

ou 10 on constate qu'il y a erreur, car ces mots ne sont pas des mots de C 00 est peut probable de le recevoir Dorénaavnt nous supposons que la probabilité de recevoir 0 et 1 en erreur est p(

Codes Correcteurs dErreurs Les codes convolutifs binaires

Figure: Diagramme d’´etat d’un codeur convolutif 2-m´emoires 1/2-taux Note : le taux ou rendement de ce code convolutif est de 1/2 (2 bits produits pour 1 bit d’information) Marc Chaumont Introduction Les codes convolutifs binaires : structure de base D´ecodeur de Viterbi Connection avec les codes blocs Introduction - D´eﬁnitions

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

permettent d’effectuer des contrôles à l’arrivée Il existe deux catégories de code : les codes détecteurs d’erreurs, les codes correcteurs d’erreurs Le code de Hamming : un code détecteur et correcteur d’erreurs Le CRC (Cycle Redundancy Check) : un code détecteur d’erreurs Ann´ee 2003-2004 – p 3/22

TD Codes correcteurs

mieux d= 3 Par exemple, le code dont les mots de code sont 00000, 01101, 10011, 11110] 2 Codes lin´eaires 1 Soit kquelconque On code un bloc de kbits en lui ajoutant un bit de contrˆole choisi de fac¸on que le nombre de 1 dans le mot de code soit toujours pair D´emontrer que ce code est lin ´eaire D ´eterminer sa distance minimale

Codes détecteurs et correcteurs B. Rouzeyre

Bibliographie n Codes correcteurs, principes et exemples

¡ J. Badrikian, Technosup, Ellipses (cours et exercices) n Codes correcteurs : Théorie et applications ¡ A. Poli, Li. Huguet, Masson (cours)

Introduction

• Codes détecteurs et/ou correcteurs • Codes en blocs linéaires Parité, Code de Hamming, Codes cycliques

CRC/FCS, code BCH, Reed-Salomon

Introduction

n Erreurs lors de la transmission

n Information découpée en blocs de k bits (mots d'information) n Blocs codés de longueur n supérieure à k n Longueur constante n n Chaque mot de code ne dépend que du mot d'information n (n-k) : redondance de code n ρ = k/n : rendement du code n La fonction de codage doit être injective ¡ 2 informations distinctes donnent 2 codes distincts ¡ certains mots reçus ne sont pas des codes

Information Codage Détection Correction Information Correction n Pour un codage de blocs de k bits vers des blocs de n bits, il y a :

¡ 2

k mots d'info à coder ¡ 2 n messages reçus possibles de longueur n dont 2 k sont des mots du code et donc (2 n - 2 k ) qui ne sont pas corrects Rappel n Conclusion : si on détecte une erreur, on corrige vers le code demandant le moins de changements, càd le plus "proche" => correction "optimiste"

0 0.1 1 2 3 4 5 6 7 8 9 10 r

n=10, p=0,01

Introduction

rnrr n ppCP -=)1.(. n parmi erronés bitsr p=probabilité qu'un bit soit mal transmis

Introduction n Codes systématiques

¡ Codage : construction du mot de code en ajoutant à la suite des k bits d'information i 1 ,i 2 ,i k , s=(n-k) bits l 1 ,..,l s bits appelés bits de contrôle formant la clé de contrôle on obtient c 1 ..c k ,c n = i 1 ,i 2 ,i k ,l 1 ,..,l s ¡ Contrôle : les k premiers bits étant les bits d'information, on recalcule à l'arrivée la clé de contrôle c k+1 ,c n

à l'aide de c

1 ,..,c k n si idem : ok n sinon erreur Exemple 1 : code de parité n Transmission d'un texte : 1 caractère = 7 bits (Ascii 0-127) n Bloc = caractère n On ajoute un 8 e bit / le nombre total de '1' soit pair (ou impair)

ex (parité paire) : 1 1 0 0 1 0 1 => 1 1 0 0 1 0 1 0 1 1 0 0 1 1 1 => 1 1 0 0 1 1 1 1 n Les 2

7 =128 caractères sont codés parmi les 2 8 =256 messages possibles n Il s'agit d'un code systématique

Exemple 1 : code de parité (contrôle)

n Réception : la règle de codage est appliquée et la parité du résultat est comparée au 8

eme bit reçu

Ex : 1 1 0 0 1 0 1 1 => incorrect (le 8eme bit devrait être 0) n Remarques ¡ on ne sait pas d'où vient l'anomalie ¡ lorsque le nombre de bits erronés est pair, il n'y a pas de détection ex : si 1 1 0 0 1 0 1 0 devient 0 0 1 1 0 1 0 1 la communication semble correcte

et pourtant 8 erreurs (on a reçu un mot de code)

¡ la détection d'anomalies ne permet pas de détecter le nombre d'anomalies ex : si 1 1 0 0 1 0 1 0 devient 0 0 1 1 0 1 0 0, on ne pas savoir qu'il y a eu 7

erreurs q code parité => code détecteur d'un nombre impair d'erreurs mais ne permet pas de corriger des erreurs

Exemple 1 : probabilité de détection

n p : probabilité d'erreur sur chaque bit (hyp constante quel que soit le bit), n q = 1-p : probabilité de transmission correcte d'un bit kk pp 8k 8 )1(C k)P(X n) parmi erreursP(k 88
)1( 0)P(X parfaite)sion P(transmisqp=-=== 177
8 355
8 533
8 711
8 det qpCqpCqpCqpC7)P(X5)P(X3)P(X1)P(X

7)X 5X 3X 1P(X visible)anomalie P(unep

8 err 1pq-=

0,57 p

42,0p

0,1 pPour

err det => 42/57 càd 74% des messages erronés sont détectés

0,0772 p

0746,0p

0,01 pPour

err det => 97% des messages erronés sont détectés

Exemple 2 : Code de parité croisée

n Bloc : suite de L caractères => suite de 7L bits n Codage : les L caractères sont rangés dans un tableau de L lignes et 7 colonnes. On ajoute une parité horizontale et une parité verticale a 1,1 a 1,2 a 1,3 a 1,4 a 1,5 a 1,6 a 1,7 a 1,8 a 2,1 a 2,2 a 2,3 a 2,4 a 2,5 a 2,6 a 2,7 a 2,8 ... ... ... ... ... ... ... a L,1 a L,2 a L,3 a L,4 a L,5 a L,6 a L,7 a L,8 a L+1,1 a L+1,2 a L+1,3 a L+1,4 a L+1,5 a L+1,6 a L+1,7

Code de parité croisée

n Décodage n Un 1 indique une erreur a 1,1 a 1,2 a 1,3 a 1,4 a 1,5 a 1,6 a 1,7 a 1,8 0 a 2,1 a 2,2 a 2,3 a 2,4 a 2,5 a 2,6 a 2,7 a 2,8

0 ... ... ... ... ... ... ... ... 0 a

L,1 a L,2 a L,3 a L,4 a L,5 a L,6 a L,7 a L,8 a L+1,1 a L+1,2 a L+1,3 a L+1,4 a L+1,5 a L+1,6 a L+1,7 a L+1,8

0 0 0 0 0 0 0 0 0

Code de parité croisée : un bit erroné

n Décodage n Tous les messages ne contenant qu'une erreur sont détectés et peuvent être corrigés (un 1 sur une ligne ou une colonne) a 1,1 a 1,2 a 1,3 a 1,4 a 1,5 a 1,6 a 1,7 a 1,8 0 a 2,1 a 2,2 a 2,3 a 2,4 a 2,5 a 2,6 a 2,7 a 2,8

1 ... ... ... ... ... ... ... ... 0 a

L,1 a L,2 a L,3 a L,4 a L,5 a L,6 a L,7 a L,8 a L+1,1 a L+1,2 a L+1,3 a L+1,4 a L+1,5 a L+1,6 a L+1,7 a L+1,8

0 0 0 0 1 0 0 0 0

Code de parité croisée : deux bits erronés n Décodage n Pour 2 erreurs sur une même ligne ou même colonne : détection mais pas de correction possible (quelle ligne ?) a 1,1 a 1,2 a 1,3 a 1,4 a 1,5quotesdbs_dbs10.pdfusesText_16

[PDF] Codes détecteurs et correcteurs B Rouzeyre

Codes détecteurs et correcteurs B. Rouzeyre

Introduction

CRC/FCS, code BCH, Reed-Salomon

Introduction

¡ 2

0 0.1 1 2 3 4 5 6 7 8 9 10 r

Introduction

Introduction n Codes systématiques

à l'aide de c

Exemple 1 : code de parité (contrôle)

Exemple 1 : probabilité de détection

7)X 5X 3X 1P(X visible)anomalie P(unep

0,57 p

0,1 pPour

0,0772 p

0746,0p

0,01 pPour

Exemple 2 : Code de parité croisée

Code de parité croisée

0 ... ... ... ... ... ... ... ... 0 a

0 0 0 0 0 0 0 0 0

Code de parité croisée : un bit erroné

1 ... ... ... ... ... ... ... ... 0 a

0 0 0 0 1 0 0 0 0