[PDF] Université Bordeaux I Master CSI 2 Année 2004-2005 Cours de

View - Download Université Bordeaux I Master CSI 2 Année 2004-2005 Cours de

Previous PDF

Next PDF

Universit´e Bordeaux I

Master CSI 2

Ann

´ee 2004-2005

Cours de codes (UE Codes/Signal)

Christine Bachoc

Bibliography

[1] J.H. van Lint,Introduction to coding theory, 3eme edition, Springer [2] W. C. Huffman, V. Pless,Fundamentals of error-correcting codes, Cam- bridge University Press 2003 [3]The handbook of Coding Theory 1

Chapter 1

Introduction

La th ´eorie des codes s"est d´evelopp´ee pour r´epondre au probl`eme de la correc- tion des erreurs introduites dans un syst `eme de transmission de l"information.`A l"origine d ´evelopp´ee par des ing´enieurs en´electronique, elle constitue maintenant une branche des math ´ematiques discr`etes. Dans le cadre du Master CSI, l"objectif de ce cours est d"initier les ´etudiants`a une autre probl´ematique de la transmission des informations, en insistant sur les applications pratiques, et de d

´evelopper les

connections de ce sujet avec la cryptographie.

Le support physique utilis

´e pour transmettre ou stocker une information (par exemple le t ´el´ephone, l"atmosph`ere, l"espace (penser aux communications par satellite), mais aussi la m ´emoire d"un ordinateur, les disques compacts, etc..) soumet cette information `a des distorsions ind´esirables, oubruit, qui l"alt`erent.

Ce bruit peut

ˆetre caus´e par un rayonnement, une alt´eration du support, des in- terf ´erences, etc.. L"information recueillie par le receveur du canal est en g´en´eral diff ´erente de celle´emise par la source. L"objectif de la th´eorie des codes est de prot ´eger l"information de cet´eventuelle alt´eration. En th ´eorie de l"information, les caract´eristiques statistiques du mode de trans- mission consid ´er´e sont mod´elis´ees par lecanal de transmission. Par exemple, le canal sym ´etrique binaire transmet des mots binairesc?Fn2, o`u chaque bit est transmis ind ´ependamment, avec une probabilit´epd"erreur.

On peut sch

´ematiser grossi`erement la situation de la fac¸on suivante: 2 Afin d"augmenter la fiabilit´e du canal, c"est-`a-dire le taux d"information cor- rectement transmise, on peut penser `a introduire de la r´ep´etition dans cette in- formation. Tous les enseignants savent bien que pour transmettre une informa- tion

`a leurs´el`eves, et pourˆetre sˆurs que celle-ci n"a pas´et´e d´enatur´ee, il ne faut

pas h ´esiter`a la r´ep´eter aussi souvent que possible. Sur ce beau principe, imagi- nons que nous voulons envoyer le message binaire suivant :11111111. Si nous l"envoyons deux fois, le receveur pourra comparer les deux versions de notre mes- sage. Si ces deux versions ne sont pas identiques, il peut conclure `a l"existence d"une erreur au moins dans la transmission. Il faut remarquer ici que cet objectif est aussi atteint en rajoutant seulement unbit de contrˆole de parit´e, c"est-`a-dire la valeur de la somme des bits modulo2. Ici cela donnerait111111110.`A nouveau, silasommedesbitsn"estpas0modulo2`al"arriv´ee, onpeutconclure`al"existence d"une erreur au moins. Il est bon de remarquer que, dans le premier cas, letaux de transmissiondu canal, qui est la proportion d"information utile transmise, est´egal a1/2, tandis que dans le second cas, ce taux vaut8/9. Reprenant l"exemple de la r ´ep´etition, on voit intuitivement que, si le message est r´ep´et´e un grand nombre de fois, le receveur pourra "jeter" `a coup sˆur un plus grand nombre de messages erron ´es, et avoir une confiance plus solide en les messages qui ont "l"air" corrects.

Un nouveau ph

´enom`ene apparait mˆeme: si le message est r´ep´et´erfois, et que ces rcopies ne sont pas toutes identiques, le receveur peut opter pour la version du message la plus souvent rec¸ue.

1.1 Lecanalsym

´etriquebinaireetlath´eoriedeShan-

non

Le canal sym

´etrique binaire (BSC) transmet des mots binaires de longueurn, ap- partenant `auncodeC?Fn2. Onsupposequelesbitssonttransmisind´ependamment, et que un bit est transmis correctement avec probabilit

´e1-p, incorrectement avec

probabilit ´ep. On supposep <1/2et dans la pratiquepest petit. (Sch´ema). On suppose ´egalement que les mots deCsont´equiprobables. repr

´esentant le mot rec¸u. On a:

3 prob(y|c) =n? i=1prob(yi|ci) = (1-p)card{i|yi=ci}pcard{i|yi?=ci} = (1-p)n?p1-p? card{i|yi?=ci} Und´ecodeur par maximum de vraisemblancechoisit de renvoyer le motˆcqui maximisec?C→prob(y|c). Commep/(1-p)<1, maximiserprob(y|c) revient `a minimisercard{i|yi?=ci}. Ainsi, le d´ecodeur renvoi un mot du code qui diff `ere deysur le moins de coordonn´ees. On voit apparaitre ici la notion dedistance de Hammingentre deux mots: d

H(c,y) = card{i|yi?=ci}.

Letaux de transmissiond"un codeCest par d´efinitionR= log(|C|)/n. Il mesure la quantit ´e d"information utile transmise. On pourrait penser que la fia- bilit ´e de la transmission ne peutˆetre obtenue qu"au d´etriment de ce taux de trans- mission. En fait il n"en est rien, comme l"a montr

´e Shannon en 1948.`A tout canal est associ´e une valeur, appel´eecapacit´e. Sans entrer dans les

d ´etails, la capacit´e du canal BSC estC(p) = 1+plogp+(1-p)log(1-p). Soit P errla probabilit´e d"erreur, c"est-`a-dire la moyenne des probabilit´es queˆc?=c. Th ´eor`eme 1 (Shannon, 1948)SoitR < C(p)et soit? >0. Pournassez grand, il existe des codesC?Fn2de taux de transmission´egal`aR, et tels quePerr< ?. Leth ´eor`emedeShannon, quenousned´emontreronspasici, laisseentiersdeux probl `emes majeurs: D"abord il est purement existentiel, il ne r´epond donc pas`a la question de la construction effective de tels codes; ensuite, il ne prend pas en compte le probl `eme algorithmique, qui est surtout celui de r´ealiser un d´ecodage efficace. 4

Chapter 2

Codes, Codes lin

´eaires, g´en´eralit´es

Dans ce chapitre, nous allons

´etudier les codes lin´eaires sur un corps finiFq. M ˆeme si l"on ne s"int´eresse ultimement qu"aux codes binaires, il est n´ecessaire de consid c"est pourquoi nous nous plac¸ons d"embl ´ee dans ce cadre plus g´en´eral (mais pas plus difficile..).

Pour l"instant, les seules choses

`a savoir sur les corps finis sont les suivantes: sipest un nombre premier, il existe un unique (`a isomorphisme pr`es) corps fini`ap el´ements qui estZ/pZmuni des op´erations usuelles. Pour un entierqquelconque, il existe un corps fini `aq´el´ements si et seulement siqest une puissance d"un nombre premierp, soirq=pr; dans ce cas il est unique (`a isomorphisme pr`es), il contient un unique sous-corps isomorphe `aFp=Z/pZ, sur lequel il est un espace vectoriel de dimensionr.

2.1 Poids et distance de Hamming

Introduites par Hamming en 1950, ces notions sont fondamentales comme on l"a vu pour estimer l"efficacit ´e d"un code dans le cadre d"un canal o`u les variables al ´eatoires d´efinies par les coordonn´ees sont ind´ependantes et´egales. D ´efinition 1Soitx= (x1,...,xn)?Fnq. Lepoids de Hammingdex, not´ewt(x) est ´egal au nombre de coordonn´ees non nulles dex. Soitx,y?Fnq. Ladistance de Hammingdexety, not´eedH(x,y)est´egale au nombre d"indicesio`u les coordonn´ees dexetydiff`erent. 5 lesupportd"un´el´ementx?Fnqest l"ensemble des indicesitels quexi?= 0.

Le poids dexest donc le cardinal de son support.

Il faut remarquer que la distance de Hamming, est une vraie distance au sens m ´etrique du terme. Rappelons bri`evement les propri´et´es d"une distanced(x,y), faciles `a v´erifier surdH. •d(x,y) = 0?x=y •d(x,y) =d(y,x) Laboule de centrexet de rayonRest par d´efinition l"ensemble

On peut remarquer quey?B(x,R)?y-x?B(0,R).

Exercice:Montrer quecard(B(x,R)) =?R

k=0? n k?(q-1)k. D ´efinition 2UncodeCde longueurnest un sous-ensemble deFnq. Ladistance minimaledeC, not´eed(C), est le minimum des distances entre deux´el´ements distincts deC. d(C) = minx,y?C,x?=ydH(x,y). Proposition 1Notonst= [d-12]. Les boulesB(x,t)avecx?Csont deux`a deux disjointes, ettest la valeur maximale du rayon pour cette propri´et´e. Supposons que l"on utilise un codeCpour la transmission de mots deFnq, de distance minimaled. On notecun mot transmis etyle mot rec¸u, avece=y-c. Un d ´ecodeur peut op´erer de la fac¸on suivante. Siyappartient`a l"une des boules B(z,t)avecz?C, il renvoiˆc=z. Sinon, il renvoi un message d"erreur (variante: il renvoi un des mots les plus proches mais pas unicit

´e). On voit queˆc?=cd`es

quey /?B(c,t). Alors: 6

Perr=?

c?Cprob(c)prob(wt(e)> t) 1|C|? e?Fn2,wt(e)>t(1-p)n?p1-p? wt(e) (1-p)n|C|n w=t+1? p1-p? w?n w? (q-1)w et on voit quePerrdiminue lorsquetaugmente. En clair,`a cardinal fix´e, on cherche un code avecdaussi grand que possible. On dit queCd´etected-1erreurs et corriget= [(d-1)/2]erreurs.

2.2 Codes lin

´eaires

Dans notre

´etude des codes contenus dansFnq, nous allons nous concentrer sur les codes lin ´eaires, c"est-`a-dire ceux qui ont une structure d"espaces vectoriels. En ef- fet, les outils de l"alg `ebre lin´eaire facilitent dans ce cas les op´erations d"encodage et de d ´ecodage, comme nous le verrons. De plus, il a´et´e d´emontr´e que le r´esultat (non constructif) de Shannon reste vrai si l"on se restreint aux codes lin

´eaires.

Nous voil

`a donc rassur´es, on peut en principeˆetre tout aussi efficace dans la cor- rection de l"information avec des codes lin

´eaires..

D ´efinition 3Un code est ditlin´eairesiCest unFq-sous espace vectoriel deFnq.

Dans ce cas, on noteksa dimension.

SiCest lin´eaire, on peut remarquer que, sixetysont dansC, alorsx-y appartient ´egalement`aC. CommedH(x,y) =wt(x-y), la distance minimale deCest´egale au minimum des poids des´el´ements non nuls deC. On a: d(C) =wt(C) = min{wt(x),x?C\ {0}}. D"un point de vue algorithmique, le calcul de la distance d"un code quel- conque n ´ecessite|C|2op´erations, tandis que pour un code lin´eaire il n"en faut que|C|(environ). SiCest un code lin´eaire, longueur, dimension et distance sont les param`etres fondamentaux deCet sont not´es[n,k,d]. 7

2.3 Orthogonalit´e

Nousintroduisonsunenotiond"orthogonalit

symm ´etrique non d´eg´en´er´eex·y=?n i=1xiyi. LorsqueFq=F2, on identifie souvent un mot deFn2avec son support. La notationx∩yd´esigne donc le mot de support l"intersection des supports respectifs dexety. On a alors: •x·y=wt(x∩y) mod 2 •En particulier,x·x=wt(x) mod 2. •wt(x+y) =wt(x) +wt(y)-2wt(x∩y)

Parfoisonconsid

`ered"autresformesquecelled´efinieplushaut. Uncasimpor- tant est celui deFq=F4. Rappelons queF4={0,1,w,w2}, o`uw2+w+ 1 = 0. Sur ce corps, l"applicationx→x2est un automorphisme de corps, qui d´efinit une involution encore appel ´ee conjugaison. On note aussi¯x=x2. Il est usuel de consid

´erer surFn4la formehermitiennex·y=?n

i=1xi¯yi.

2.4 Matrice g

´en´eratrice, de contrˆole de parit´e

D ´efinition 4SoitCun code lin´eaire de longueurnet de dimensionk. Unema- trice g ´en´eratricedeCest une matricek×ndont les lignes forment une base deC. Lecode dualdu codeCest l"orthogonalC?deCpour la forme usuelle x·y=?n i=1xiyi. C ?:={u:u?Fnq|u·v= 0pour toutv?C}. Unematrice de contˆole de parit´edeCest une matrice(n-k)×ng´en´eratrice de C ?. Un code est ditautoduals"il est´egal`a son dual. Proposition 2SoitCun code lin´eaire, de longueurnet de dimensionk, soitG une matrice g ´en´eratrice deCet soitHune matrice de contrˆole de parit´e deC. alors: •x?C?Il existeu?Fkq|x=uG •x?C?Hxt= 0 8 •Ccontientunmotdepoidsauplusw, ssiwcolonnesdeHsontlin´eairement d

´ependantes.

quotesdbs_dbs27.pdfusesText_33

[PDF] BI JÛUX - Standard

[PDF] Bi lingue - Parcours Bilingue (Français

[PDF] BI Lösung Lage

[PDF] BI N° 4 - L`association Autocars Anciens de France - France

[PDF] BI N° 5 - L`association Autocars Anciens de France - France

[PDF] BI N° 6 - L`association Autocars Anciens de France - Gestion De Projet

[PDF] BI N° 7 - L`association Autocars Anciens de France - France

[PDF] BI rejets facturation SSR-code FF10 - Anciens Et Réunions

[PDF] BI rencontre education

[PDF] BI RT-2012 PAU

[PDF] BI Soirées étudiant créateur IES.indd

[PDF] BI Specialist II

[PDF] BI trail GTJ 2012 - Courir et découvrir

[PDF] BI-84 DEPARTMENT: HOME AFFAIRS REPUBLIC OF SOUTH - Anciens Et Réunions

[PDF] Bi-bloc Basse Température Nouvelle Génération - France