[PDF] Codes et Automates finis La matrice de contrôle

View - Download Codes et Automates finis

Previous PDF

Next PDF

Codes et Automates finis

Cours 5 Matrice de contrôle

Introduction

On se donne un code linéairejde dimension k et de longueurnk:u=j(a),a2(F2)k, u2(F2)n. Le rendement de ce code est défini par le rapportkn La matrice génératriceGs"obtient en calculant les vecteurscj=j(ej)pour 1jkavec e j= (0; :::;0;1;0; :::;0)vecteur de base de l"espace(F2)k. Les vecteurscj2(F2)nforment

les lignes de la matrice génératrice. Sous une forme standard, on écritG= (IkP)où Ikest la

matrice identité àklignes etkcolonnes etPest la matrice de parité qui comporteklignes et(nk)colonnes.

Matrice de contrôle

La matrice de contrôle, notée le plus souventH, comporte(nk)lignes etncolonnes. Elle s"écrit à l"aide de la matrice de paritéP:H= (PtInk). Nous remarquons que dans le corpsF2, on a bien sûrPt=Pt. Mais nous gardons le signe

"moins" dans la définition générale car il permet de mettre en place une propriété qui sera

énoncée plus loin.

Exemples de matrices de contrôle

Nous calculons la matrice de contrôleHpour les exemples introduits jusqu"ici dans le cours.

Exemple 1. Duplication d"un bit :k=1 etn=2.

On aG= (1 1),P= (1)etH= (1 1).

Exemple 2. Double répétition :k=1 etn=3.

On aG= (1 1 1),P= (1 1)etH=1 1 0

1 0 1

Exemple 3. Duplication de deux bits :k=2 etn=4.

On aG=1 0 1 0

0 1 0 1

,P=1 0 0 1 etH=1 0 1 0

0 1 0 1

Exemple 4. Contrôle de parité :k=3 etn=4.

On aG=0

@1 0 0 1

0 1 0 1

0 0 1 11

A ,P=0 @1 1 11 A etH= (1 1 1 1).

Exemple 5. Code Hamming H7 :k=4 etn=7.

On aG=0

B

BB@1 0 0 0 1 1 0

0 1 0 0 1 0 1

0 0 1 0 0 1 1

0 0 0 1 1 1 11

C

CCA,P=0

B

BB@1 1 0

1 0 1 0 1 1

1 1 11

C

CCAetH=0

@1 1 0 1 1 0 0

1 0 1 1 0 1 0

0 1 1 1 0 0 11

A .François Dubois, mars 2020.

FRANÇOISDUBOIS

Propriété fondamentale de la matrice de contrôle

On a toujoursG Ht=0.

On vérifie sans difficulté cette propriété pour les cinq cas particuliers proposés ci-dessus.

Dans le cas général, il suffit d"effectuer le produit par blocs deG= (IkP)parHt=P I nk Le calcul d"un produit de deux matrices par blocs est identique au calcul d"un produit de deux

matrices dans le cas où les éléments de matrice sont des nombres. Mais il faut au préalable

s"assurer que chacun des produits matriciels a bien un sens. C"est le cas ici : I kPest bien défini etPInkl"est aussi car la matrice de paritéPest àklignes et(nk)colonnes. Par contre, si nk6=k, les produits de matricePIket InkPne sont pas définis ! Le résultat du produit de la matriceGàklignes etncolonnes par la matriceHtànlignes et kcolonnes est une matrice àklignes etkcolonnes et on a : G H t=Ik(P)+PInk=P+P=0.

Syndrome

Siv2(F2)n, le syndromes(v)est défini pars(v) =v Ht. C"est une application de(F2)n dans(F2)nk.

Le syndrome d"un mot du codev2Cest toujours nul.

Par exemple pour la duplication de deux bits (k=2,n=4), siv= (1 0 0 1), alors s(v) = (1 0 0 1)0 B

BB@1 0

0 1 1 0 0 11 C

CCA= (1 1).

Autre exemple avec le contrôle de parité (k=3,n=4). Siv= (1 1 1 0), alors s(v) = (1 1 1 0)0 B BB@1 1 1 11 C

CCA= (1).

Linéarité

L"application syndrome(F2)nk3v7!s(v) =v Htest linéaire.

Caractérisation des mots du code

Rappelons que l"ensembleCdes mots du code est défini par C=fj(a);a2(F2)kg=fa G;a2(F2)kg. C"est un sous-ensemble de(F2)n. Si l"ensembleC des mots du code résulte d"un codage linéaire, on a la propriété suivante. Un motv2(F2)nest un mot du code (v2C) si et seulement si son syndrome est nul (s(v)=0) ; on a l"équivalence(v2C)()(v Ht=0). Le syndrome permet de s"intéresser au vecteur d"erreurgtel quev=u+gavecu2C.

Par linéarité, on as(v) =s(g)puisqueu2C.

Attention ! La décompositionv=u+gavecu2Cn"est pas unique en général. Dans l"exemple suivant, pour la duplication de deux bits, on a d"une part v= (1 0 1 1) = (1 0 1 0)+(0 0 0 1)et d"autre partv= (1 0 1 1) = (1 1 1 1)+(0 1 0 0). Les vecteurs d"erreursg1= (0 0 0 1)etg2= (0 1 0 0)sont tous deux de poids égal à un. 2

CODES ETAUTOMATES FINIS

Siv=u+g, alors la distance de Hammingd(u;v)est égale au poidsjgjde l"erreurg: c"est le nombre de bits oùuetvdiffèrent.

Corriger un mot reçu

Afin de corriger un mot reçuv62C, on a besoin d"utiliser la distance minimaleddu code linéairej. Deux mots différents du codeCdifferent d"au moinsdbits. On a vu lors de la leçon précédente que l"on ad=minfjuj;u2Cetu6=0gpour un code linéaire. La distance minimale est le plus petit des poidsjujdes mots du code non nuls. Une inégalité entre dimension, longueur et distance minimale Pour un code linéaire de dimensionk, de longueurnet de distance minimaled, on a l"inégalité suivantedn+1k. Pour les cinq codes déja introduits dans ce cours, on peut vérifier cette inégalité. Exemple 1. Ajout d"un bit de contrôle :k=1 etn=2. On aC=f00;11getd=2. On a bien 22+11. Exemple 2. Double répétition :k=1 etn=3. Dans ce cas,C=f000;111getd=3. On vérifie que 33+11. Exemple 3. Duplication de deux bits :k=2 etn=4. Le codeCcomporte 22mots : C=f0000;0101;1010;1111getd=2. On a bien la relation 24+12. Exemple 4. Contrôle de parité :k=3 etn=4. Le codeCest composé de 23mots : C=f0000;1001;0101;0011;1100;1010;0110;1111g. Il est clair qued=2 et 24+13. Exemple 5. Code Hamming H7 :k=4 etn=7. On a vu lors de la leçon précédente qued=3.

De plus, 37+14.

Code détecteur

Un codeC(F2)nde distance minimaledpeut détecter à coup sûr au plus(d1)erreurs de transmission. En d"autres termes, sid2 et siv2(F2)npeut s"écrire sous la formev=u+g avecu2Cet 1 jgj d1, on est certain quev62C.

La chaîne de bits reçue n"appartient pas à l"ensemble des mots du code et elle est assez proche

de l"ensembleC. Alors on est cartain qu"il y a eu au moins une erreur de transmission.

Une notation

On rapproche les trois nombres entiers de longueur, dimension et distance minimale sous la forme[n;k;d].

Code correcteur ?

Quand on reçoit le mot de quatre bitsv= (1 0 1 1)pour le codageviala duplication de deux bits, nous avons vu plus haut que l"on a à la fois(1 0 1 1) = (1 0 1 0)+(0 0 0 1), avec (1 0 1 0)2Cetg1= (0 0 0 1)et(1 0 1 1) = (1 1 1 1)+(0 1 0 0), avec(1 1 1 1)2C etg2= (0 1 0 0). On ne sais pas dire que l"une des erreursg1oug2est plus petite que l"autre car elles sont toutes deux de poids égal à un. Dans le cas contraire, on peut projeter le motsv2(F2)nsur les mots du code, c"est à dire trouveru2Cunique de distance minimale. Alorsu2C,d(u;v)d(eu;v),8eu2Cet de plus si eu2Cest différent deu, alorsd(eu;v)d(u;v)+1. Dans ce cas, l"erreurg=vu 3

FRANÇOISDUBOIS

comporte moins de bits égaux a 1 que toutes les autres erreurs eg=veu. C"est l"erreur la plus probable. On corrige en général le mot reçuven le remplaçant par le mot du codeu2Cle plus proche. On parle dans ce cas d"un code correcteur. Distance minimale nécessaire d"un code correcteur On se donne un entiert0 et un code de distance minimaled. Ce code corrigeterreurs si et seulement sid2t+1. Parmilescinqexemplesdecodeslinéairesconsidérésdanscechapitre, seulsladoublerépétition ([3, 1 , 3]) et le code de Hamming H7 ([7, 4 , 3]) satisfont àd3 et peuvent corriger au plus une erreur sans ambiguité.

Un critère pratique

Un code linéaire corrige une erreur (t=1) si et seulement si les colonnes de sa matrice de contrôleHsont distinctes et non nulles.

On vérifie que ce critère est effectivement satisfait pour les cinq codes introduits jusqu"ici.

Exemple 1. Ajout d"un bit de contrôle :d=2 etH= (1 1). Cette matrice a deux colonnes égales. Ce code est détecteur et détecte au plus une erreur. Exemple 2. Double répétition :d=3. On a maintenantH=1 1 0 1 0 1 . Les trois colonnes

de la matrice de contrôleHsont différentes. Ce code corrige une erreur et en détecte deux. Par

contre, son rendement (1/3) est faible. Exemple 3. Duplication de deux bits :d=2. On a cette foisH=1 0 1 0

0 1 0 1

. Cette matrice

a deux paires de colonnes égales. Ce code n"est pas correcteur et détecte a coup sûr au plus une

erreur. Exemple 4. Contrôle de parité :d=2. On a vu queH= (1 1 1 1). Toutes les colonnes sont

égales. Ce code détecte au plus une erreur.

Exemple 5. Code Hamming H7 :d=3 etH=0

@1 1 0 1 1 0 0

1 0 1 1 0 1 0

0 1 1 1 0 0 11

A . Cette matrice a

toutes ses colonnes différentes. Ce code détecte de façon certaine au plus deux erreurs. Il en

corrige au plus une en choisissant l"erreur la plus probable. Son rendement (3/7) est supérieur

à celui du codage par double répétition.

Exercice

Étude d"un code linéaire

On code des blocs de trois bits de la façon suivante : le blocb1b2b3est codéb1b2b3a1a2a3 ou les trois derniers bits sont donnés par les relationsa1=b1+b2,a2=b1+b3et a

3=b1+b2+b3.

a) Donner la dimensionket la longueurnde ce code. b) Montrer que ce code est linéaire. c) Déterminer sa matrice génératriceG. 4

CODES ETAUTOMATES FINIS

d) Déterminer la transposéeHtde sa matrice de contrôle. e) Ecrire la listeCdes mots du code. f) Quelle est la distance minimaledde ce code ? g) Pourej= (0; :::;0;1;0; :::0)vecteur de base de(F2)6, calculer le syndromes(ej). On reçoit les messages suivants :m1=110110,m2=011001 etm3=111111. h) Calculer leurs syndromes et, le cas échéant, les corriger. Le canal de transmission est supposé symétrique, sans mémoire et on notepla probabilité d"erreur dans la transmission de un bit. i) Quelle est la probabilité de se tromper en corrigeant le motm2? j) Donner l"ordre de grandeur de cette probabilité sip=1100 5quotesdbs_dbs29.pdfusesText_35

[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