[PDF] CH.2 CODES CORRECTEURS Un code est 1-correcteur

View - Download CH.2 CODES CORRECTEURS

Previous PDF

Next PDF

Codage ch 2 1

CH.2 CODES CORRECTEURS

• 2.1 Le canal bruité • 2.2 La distance de Hamming • 2.3 Les codes linéaires • 2.4 Les codes de Reed-Muller • 2.5 Les codes circulaires • 2.6 Le câblage des codes circulaires • 2.7 Les performances pratiques

Codage ch 2 2

2.1 Le canal bruité

On considère une source qui envoie un message constitué d'une suite de

0 et 1 (on peut aussi considérer un alphabet plus grand). Un message peut

alors être vu comme un mot x. Ce message va être codé yet transmis à travers un canal bruité. Il s'agit d'un canal de communication qui transmet des bits mais qui en modifie certains en cours de transmission. Il peut soit les rendre illisibles (effacement), soit les échanger. On va supposer que certains bits sont échangés. A l'autre extrémité du canal, on reçoit donc un autre mot, y'= y+ e, où eest le vecteur d'erreurs. Il code les positions où les bits de yont été modifiés. Le décodeur doit, dans la mesure du possible, retrouver le vecteur ypour en déduire le xtransmis. Ce qui revient au même, le décodeur doit trouver le vecteur d'erreurs en ne connaissant que le mot y'reçu.

Codage ch 2 3

SourceCodeurDécodeurRécepteur

Canal bruité x yy'x Un code simple est le code à répétition de longueur 3 : chaque octet de xest répété 3 fois. Si x= 00101011, alors y= 00101011 00101011 00101011. Supposons que le canal modifie tous les bits de la sixième à la treizième position incluses. Donc, y'= 00101100 11010011 00101011. Le vecteur d'erreurs est ici e= 00000111 11111000 00000000. En effectuant bit par bit un décodage à la majorité, on reconstitue le vecteur x. Tout vecteur d'erreurs comportant des 1 dans au plus 8 positions consécutives sera ainsi corrigé. Un tel entrelacementpermet ainsi la correction d'erreurs en rafale.

Codage ch 2 4

2.2 La distance de Hamming

Nous allons considérer uniquement des codes de longueur fixe nsur l'alphabet {0, 1}. Pour que l'altération d'un bit d'un mot du code permette de retrouver le mot d'origine, il est nécessaire que ce mot altéré ne soit pas dans le code. Le nombre de bits où deux mots diffèrent est appelé distance de Hammingde ces deux mots. C'est une distance au sens mathématique. Puisque les mots sont binaires, si on note e= x+ y, la distance de Hamming d(x, y) = d(0, e) est le poids, ou nombre de 1 de e. Lorsqu'on reçoit un mot y, on va supposer qu'il résulte d'un mot du code par l'altération du minimum de bits. On cherche donc le mot xle plus proche de y.

Codage ch 2 5

Si deux mots du code xet ydiffèrent en 2epositions ou moins, une modification de ebits de xet de ebits de ypeuvent donner le même mot. En revanche, si on est sûr que deux mots quelconques diffèrent en 2e+ 1 positions au moins, une modification de ebits d'un mot permettra de retrouver le mot d'origine.

Théorème

Un code Cest e-correcteur si et seulement si la distance minimum de deux mots de Cest supérieure ou égale à 2e+1. On peut imaginer chaque mot du code entouré d'une sphère de rayon e. Le code est e-correcteur si et seulement si ces sphères sont disjointes. On a intérêt à avoir un code comportant le plus possible de mots pour une longueur donnée n. Ce problème est un cas particulier du problème consistant à trouver un empilement compact de sphères.

Codage ch 2 6

Malheureusement, le problème de l'empilement des sphères est ... La situation la plus favorable se présente lorsque tousles mots de 2 n sont dans une sphère. On dit qu'on a alors un code e-correcteur parfaitde longueur n. Les codes à répétition tel que {000, 111} sont parfaits, mais pas très intéressants. Nous verrons d'autres exemples de codes binaires parfaits.

Codage ch 2 7

2.3 Les codes linéaires

Pour des raisons pratiques (facilité de codage et de décodage), on va s'intéresser à une classe particulière de codes correcteurs qui sont les codes linéaires. Il a en fait été démontré par van Lint que le théorème de Shannon restait vrai même si on imposait aux codes d'être linéaires. On considère ici les mots du code comme des vecteurs dans l'espace vectoriel de dimension nsur le corps à deux éléments 2 . Un code linéaireest un sous-espace vectoriel de 2n . Comme tout sous-espace vectoriel, un code linéaire a donc une dimension k. Le nombre de mots d'un tel code est donc 2 k Si xet ysont deux mots d'un code linéaire, il en est de même de x+ y.

Codage ch 2 8

Si donc la distance minimum entre deux mots du code est 2e+ 1, en ajoutant ces deux mots, on trouve un autre mot non nul du code, de poids 2e+ 1. D'où la proposition suivante.

Proposition

Un code linéaire Cest e-correcteur si et seulement si le poids minimum d'un mot non nul de Cest 2e+ 1. Les trois paramètres longueur n, dimension ket poids minimum d'un mot non nul dpermettent d'en évaluer les performances. On dit qu'on a affaire à un code [n, k, d].

Par exemple, le code {000, 111} est [3, 1, 3].

Codage ch 2 9

Si on considère une base e

1 , e 2 , ... , e k d'un code C, tout mot de ce code est déterminé par les kcoordonnées de ce mot sur cette base, qui est une suite de kbits..

Le code étant linéaire, il suffit pour trouver l'image d'une suite de kbits,de connaître les coordonnées dans

2n des kvecteurs de base. Le vecteur x 1 e 1 + x 2 e 2 + ... + x k e k aura donc ses coordonnées données par le produit de matrices [ x] G= [ y], oùGest la matrice kx ndont les lignes sont constituées des coordonnées des kvecteurs e 1 , e 2 , ... , e k La matrice G est appelée matrice génératricedu code.

Les vecteurs e

1 , e 2 , ... , e k sont linéairement indépendants, donc la matrice Gest de rang maximum k. On peut donc, quitte à effectuer un changement de base (pivot), supposer qu'elle est de la forme suivante.

Codage ch 2 10

G= [ I

k

A], où I

k est la matrice identité de taille ket Aest une matrice kx (n-k). Par exemple, considérons le code engendré par

1 0 0 0 1 1 1

0 1 0 0 0 1 1

0 0 1 0 1 0 1

0 0 0 1 1 1 0G=

Ce code est de longueur 7 et de dimension 4. C'est le code de

Hamming[7, 4].

L'image du vecteur [ 1 0 1 1] est donc [ 1 0 1 1 1 0 0 ] On constate que le vecteur à coder se retrouve sur les kpremières positions du code. Les n-kbits suivants du code sont appelés bits de contrôle.

Codage ch 2 11

Comment effectuer le décodage et quelles sont les capacités de correction d'un code linéaire ? Dans l'exemple précédent, on pourrait vérifier que le poids minimum d'un mot du code est 3. Le code est alors un code [7, 4, 3] et donc permet la correction d'une erreur. Il n'est pas nécessaire d'écrire tous les mots du code pour faire cette vérification. On peut utiliser des propriétés générales d'algèbre linéaire. Les éléments d'un sous-espace vectoriel de dimension ksont définis par un ensemble de n-kéquations linéaires. Il est facile de trouver ces équations, étant donnée la forme de particulière de G.

Codage ch 2 12

Théorème

Un vecteur yappartient au sous-espace engendré par la matrice

G= [ I

k A] si et seulement s'il satisfait [ y] H= 0, où

H= , dans laquelle I

n-k est la matrice identité de taille n-k. A I n-k Pour le démontrer, on remarque que le produit G H= 0 (produit par blocs des matrices). Donc si [ y] = [ x] G, on a [ y] H= 0. Réciproquement, puisque la matrice Hest de rang n-k, l'ensemble des solutions du système [ y] H= 0 est un sous-espace de dimension k. On sait que les éléments du sous-espace engendré par Gsatisfont ce système et sont de dimension k. C'est donc exactement l'ensemble des solutions. Cette matrice Hest appelée matrice de contrôle de parité.

Codage ch 2 13

Si on reçoit le vecteur y'= y+ e, on peut calculer le produit de matrices [ y'] H. C'est un vecteur-ligne de taille n-k, qu'on appelle le syndromede y'. Puisque [ y] H = 0, le syndrome ne dépend pas de y, mais du vecteur d'erreurs e. Pour corriger les erreurs, il faut pouvoir, avec la seule connaissance du syndrome, identifier le vecteur d'erreurs. Pour pouvoir corriger une erreur, il suffit que les n+ 1 syndromes correspondant aux n+ 1 vecteurs d'erreurs de poids 0 ou 1 soient différents. De même, pour corriger deux erreurs, il suffit que les syndromes correspondant aux n(n-1)/2 + n+ 1 vecteurs de poids

0, 1 ou 2 soient différents.

Et ainsi de suite.

Codage ch 2 14

Le syndrome du vecteur nul vaut toujours 0.

Les syndromes des nvecteurs de poids 1 sont les nlignes de H. On a donc pour les codes 1-correcteurs le résultat agréable suivant.

Proposition

Un code est 1-correcteur si et seulement si les lignes de sa matrice de contrôle de parité sont différentes deux à deux. Si on reprend le code de Hamming [7, 4], on trouve comme matrice de contrôle de parité :

Codage ch 2 15

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

0 0 1H=Les lignes de cette matrice étant deux à deux

distinctes, le code est 1-correcteur.

Supposons que, comme dans l'exemple, le

vecteur à coder soit x= [ 1 0 1 1]. Son imagequotesdbs_dbs30.pdfusesText_36

[PDF] prix code d delta voile

[PDF] delta voiles occasion

[PDF] code d occasion

[PDF] definition voile code 0

[PDF] idéal chevaleresque définition

[PDF] les règles de la chevalerie au moyen age

[PDF] loi 49-15 maroc

[PDF] loi 32-10 maroc

[PDF] spaco diesel

[PDF] code correction production d'écrit cycle 3

[PDF] grille de correction

[PDF] orange roya fiche technique

[PDF] orange rise 31 mode d'emploi

[PDF] orange roya alcatel

[PDF] orange tecno n9 fiche technique