TD Codes correcteurs

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

Universit

´e de Provence Licence Math Info 2`eme ann´ee S3 Ann

´ee 2011/12 Fondements de l"Informatique

TD. Codes correcteurs

1 Concepts fondamentaux

1. Si on exp

´edie des bits sur un canal binaire sym´etrique`a raison de 512 bits toutes les millisecondes, avec une

probabilit

´e d"erreur de1%, quel est le nombre de bits faux exp´edi´es au bout de 3h ? (on assimilera probabilit´e et

´equence).

Solution :512:103:3600:3 = 5529600000bits envoy´es en 3 heures. On a donc55296000=100 = 55296000bits

erron

´es.

2. Dans un code de dimensionk, et de longueurn, combien faut-il connaˆıtre de bits pour d´efinir le codage ?

Solution :Il faut donner le mot de code de taillenpour chaque mot de longueurk. Il faut doncn2kbits.

3. Dans le cas o

`uk= 2etr= 1, faire la liste de tous les codages syst´ematiques possibles.

Solution :Il y en a24= 16: en prenant les bits de contrˆole des 4 mots, de toutes les fac¸ons possibles.

4. Les valeurs deret dek´etant fix´ees, combien y a-t-il de codages syst´ematiques diff´erents ?

Solution :Pour chaque mot de longueurkon peut ajouter n"importe quel mot de longueurren tant que bits

de contr ˆole. On a donc2kchoix`a faire et`a chaque fois, on peut choisir parmi2r. On a donc2r2kcodages syst

´ematiques diff´erents.

5. A partir d"un code[n;k;d], on construit un nouveau code de longueurn+ 1en ajoutant le bit 1`a la fin des

anciens mots de code. Quelle est la distance minimale de ce nouveau code ?

Solution :Deux mots qui´etaient s´epar´es par la distancedle sont encore : la distance minimale ne change pas.

6. On fabrique un code[2k;k]en collant,`a la fin de chaque bloc, le compl´ement du bloc. Quelle est la distance

minimale du bloc ?

Solution :La distance minimale est de 2 car si deux mots sont diff´erents sur un bit, leur compl´ementaire est

diff

´erent sur un bit.

7. Dans un code[5;2], quelle peutˆetre la plus grande valeur ded? Donner un exemple.

Solution :In´egalit´e de Hamming :C05+C1523< C05+C15+C25car68<16. On a donct= 1, donc au mieuxd= 3. Par exemple, le code dont les mots de code sont00000,01101,10011,11110]

2 Codes lin

´eaires

1. Soitkquelconque. On code un bloc dekbits 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.

Permet-il de corriger des erreurs ? Pourquoi ?

Solution :

Preuve de lin

´earit´e : soientx;y;ztrois mots de longueurktels quex=yz. Si le nombre de1danszetya la m

ˆeme parit´e alorsxa un nombre pair de1. En effet,w(x) =w(y) +w(z)2p(x;y)o`up(x;y)est le nombre de

1qui sont`a la mˆeme position dansyetz. Il en suit que le code dex:(x)est´egal`ax:0qui est bien´egal`a soit

ay:1z:1ou bien`ay:1z:1.

Pour la m

ˆeme raison, si les nombres de1ont des parit´es diff´erentes danszetyalorsxa un nombre impair de1.

Il en suit que le code dex:(x)est´egal`ax:1qui est bien´egal`a soit`ay:0z:1, ou bien`ay:1z:0.

La distance minimale est de2car deux mots diff´erents de code ne peuventˆetre`a distance 1. En effet, cela

impliquerait que l"un des deux aurait un nombre impair de 1 (poids impair). Il est impossible de corriger les erreurs car on ne sait pas o `u elles se trouvent.

2. Le code

`a r´ep´etition d"ordrencode un bloc de 1 bit en le r´ep´etantnfois. D´emontrer qu"il s"ait d"un code

lin

´eaire. D´eterminer sa matrice g´en´eratrice, sa matrice de contrˆole, son tableau standard, sa liste de syndromes,

sa distance minimale.

Solution :

Lin ´earit´e imm´ediate car on a que deux mots de code :0net1n.

Matrice g

´en´eratrice = une matrice ligne constitu´ee denbits`a 1.

Matrice de contr

ˆole = premi`ere colonne an1bits 1 accol´ee`a la matrice unit´e d"ordren1. 1

Tableau standard : 2 colonnes et2n1lignes : dans la premi`ere ligne, il y a le mot binaire 0..0, et le mot 1..1.

Dans chaque ligne, on trouve c

ˆote`a cˆote un mot binaire et son compl´ement. La distance minimale estn.p(faux apr`es correction) =pn1(1p)n

3. On d

´efinit un code syst´ematique[7;4]de la fac¸on suivante : si le bloc`a coder estb1b2b3b4, alors les bits de

contr

ˆolesc1c2c3sont tels que :

1=b1b2b3

2=b1b2b4

3=b1b3b4

(a) Montrer que ce codage est lin

´eaire

Solution :Il est facile de v´erifier que pour ce codage syst´ematiqueon a toujours(x)(y) =(xy).

(b) D ´eterminer sa matrice g´en´eratrice, les mots de code et la distance minimale de ce code.

Solution :

G=0 B

B@1 0 0 0 1 1 1

0 1 0 0 1 1 0

0 0 1 0 1 0 1

0 0 0 1 0 1 11

C CA etd= 3 (c) Que peut-on dire de plus `a propos de ce code ?

Solution :C"est un code de Hamming

4. D ´eterminer la distance minimale du code d´efini par la matrice g´en´eratrice : G=0 @1 0 0 0 1 1 1

0 1 0 1 0 1 1

0 0 1 1 1 0 11

A Mots de code =0000000,1000111,0101011,0011101,1101100,1011010,0110110,1110001 (a) Coder tous les blocs de 3 bits. Quelle est la distance minimale du code ?

Solution :d= 4

(b) Corriger les messages suivants :1111100,0111000,1110101,1111101,1100111, et0100000 Solution :On obtient :1101100,1110001,1110001,0011101,1000111,0000000 2quotesdbs_dbs6.pdfusesText_12

[PDF] TD Codes correcteurs

Universit

´ee 2011/12 Fondements de l"Informatique

TD. Codes correcteurs

1 Concepts fondamentaux

1. Si on exp

´equence).

´es.

2. Dans un code de dimensionk, et de longueurn, combien faut-il connaˆıtre de bits pour d´efinir le codage ?

3. Dans le cas o

4. Les valeurs deret dek´etant fix´ees, combien y a-t-il de codages syst´ematiques diff´erents ?

´ematiques diff´erents.

5. A partir d"un code[n;k;d], on construit un nouveau code de longueurn+ 1en ajoutant le bit 1`a la fin des

6. On fabrique un code[2k;k]en collant,`a la fin de chaque bloc, le compl´ement du bloc. Quelle est la distance

´erent sur un bit.

7. Dans un code[5;2], quelle peutˆetre la plus grande valeur ded? Donner un exemple.

2 Codes lin

´eaires

1. Soitkquelconque. On code un bloc dekbits 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

Permet-il de corriger des erreurs ? Pourquoi ?

Solution :

Preuve de lin

1qui sont`a la mˆeme position dansyetz. Il en suit que le code dex:(x)est´egal`ax:0qui est bien´egal`a soit

Pour la m

2. Le code

Solution :

Matrice g

Matrice de contr

Dans chaque ligne, on trouve c

3. On d

ˆolesc1c2c3sont tels que :

1=b1b2b3

2=b1b2b4

3=b1b3b4

´eaire

Solution :

B@1 0 0 0 1 1 1

0 1 0 0 1 1 0

0 0 1 0 1 0 1

0 0 0 1 0 1 11

Solution :C"est un code de Hamming

0 1 0 1 0 1 1

0 0 1 1 1 0 11

Solution :d= 4