[PDF] Mathématiques des codes correcteurs derreurs

View - Download Mathématiques des codes correcteurs derreurs

Previous PDF

Next PDF

A.A.Pantchichkine

Résumé

dedécodage. 1

Tabledesmatières

6.BornesdePlotkinetdeGilbert-Varshamov56

2

7.11.CodesgéométriquesdeGoppa:

-construction.........................83

AAnnexe:Rappelssurlescorpsnis92

CAnnexe:Bornessurcodes114

DAnnexe:Codescycliques.CodesdeGolay131

3

Introduction

Basesmathématiques:

CodesdeHamming.

6.BornesdePlotkinetdeGilbert-Varshamov.

modernitédesesmotivations. deReed-Mullerd'ordre1etdelongueur32". u=(1;2;3;4;5;6); 4 1 2 3 4 5 60
B B B B B B C C C C C C A() F 6 2 x=(x1;x2;x3;x5)del'espaceaneF5

2(il'yena32):

j1=x5+2x4+4x3+8x2+16x1;xi=0ou1; alors j2f1;2;;32g !(x1;x2;x3;x4;x5)mod22F5 2: 2: 2g=F5 2 (l'espaceF5

2toutentier),

2g

2commenceparlenumeroj=17$(1;0;0;0;0).

Puis 2g

2commencentparlenumero

OnvériequelespartiesdeF5

f(x1;x2;x3;x5)=1del'espaceaneF5 2 (d(f)=1). 2!F2: A

1 !f1;f:F5

2!F2; A

2 !f1;f(x1;x2;x3;x5)=x1"lepremierchire"dej1mod22F2;

A

3 !f1;f(x1;x2;x3;x5)=x2"lesecondchire"dej1mod22F2;

A

4 !f1;f(x1;x2;x3;x5)=x3"letroisièmechire"dej1mod22F2;

A

5 !f1;f(x1;x2;x3;x5)=x4"lequatrièmechire"dej1mod22F2;

A

6 !f1;f(x1;x2;x3;x5)=x5"ledernierchire"dej1mod22F2:

5

1A1+2A2+3A3+4A4+5A5+6A6 !f=1+2x1+3x2+4x3+5x4+6x5:

(lafonctionindicatricedelapartie f(x1;x2;x3;x5)=1del'espaceaneF5 2):

2contientauplus8éléments,doncles

danscecaslerésultatc0

Décodaged'unmotreçuy2F32

2:siyétait

unmotdecode, alors 8

1=f(0;0;0;0;0)=y1;

1+2=f(1;0;0;0;0)=y17;

1+3=f(0;1;0;0;0)=y9;

1+4=f(0;0;1;0;0)=y5;

1+5=f(0;0;0;1;0)=y3;

1+6=f(0;0;0;0;1)=y2:

C'est"l'erreurdetransmission".Alors

u

0=(1;2;3;4;5;6):

6 uncanalbruité

Codesderépétitionpure.

1.1.Principedetransmissiond'information

nisetdespolynômessurceux-ci. transmissionestlesuivant:

SOURCE

messageà transmettre aemis

ENCODEUR

message codé cemis CANAL detransmissione(erreur) BRUIT

DESTINARAIRE

message décodéa0

DECODEUR

message c

0=c+ereçu

Par

1.2.Hypothèsessuruncanalbruité

hypothèsesfondamentales: mêmeprobabilitép.

1.3.Généralitéssurlescodes

7

E:Fk!Fn

longueur.DanscecasCard(C)=qk F nFn!N (a;b)7!Cardfi2f0;1;:::;ngjai6=big (b)SoitFuncorpsni.L'applicationw:Fn!N a7!d(a;0)=Cardfi2f0;1;:::;ngjai6=0g estlepoidsdeHamming. d(a;b)=0()(ai=bi;1in)()a=b d(a;b)=d(b;a)pourtousa;bpourtousEn d=d(C)=min x;y2Fk x6=yd(C(x);C(y)) rapportR=k=n (c)1=RestlecoecientderedondancedeC.

B(x;t)=fy2Fnjd(x;y)tgFn

8

Or,destunedistance,donc

d(y;c0)d(c;c0)d(c;y) d(y;c0)t+1

D:Fn!Fk

tellequeDC=IdFk.

8y2Fn8u2Fk;d(E(u);y)d(E(D(y));y)

suite F kN3a=(a1;:::;ak;ak+1;:::;akN); où u a7!EN(a)=(E(u1);:::;E(uN))2FnN avecleshypothèses1.2.: E

N(a)7!~EN(a)2FnN

desbonscodes. correction"): =d n;etonsupposequepestassezpetit:p<2:

2"1n.Danscecas

(p+")n(

21n)n=d21t=d12

C'est-à-dire,DNEN(a)=EN(a),sip<

trèsprocheà1. 2mais nN(lerendement)estsusanteR>R0pour 9 lesdeuxlimites lim i!1k i ni=R>0;limi!1d ini=>0;

Illustrationdel'idée:

lasommedescoordonnées: E:Fk

2!Fk+12,

Uneautreméthodeestcellede

répétition: E m:Fk!Fkm; rendementtendverszéro:km nm=1m!0. k k=1;k n1m0)nm0: dudecodageerroné. (a)Montrerque P=X

0l n l (1p)lpnl=O(pn=2)lorsquep!0: restricionnm0. (b)Pourtoutp<1

1.5.ThéorèmedeShannon(1948)

codesCFn 10

H(p):=pln(p)

ln(2)(1p)ln(1p)ln(2)

H(p)=plog(p)

log(2)(1p)log(1p)log(2)

00.20.40.60.81

R

0.20.40.60.81p

R=1+plog(p)log(2)+(1p)log(1p)log(2)

Remarque1.11

P (Mn;n;p)=minC(PC=M1nM nX i=1P i) famillefCngFn

2descodesbinairesdecardinal

Card(Cn)=Mn=2[Rn]!1

2 P (Mn;n;p)=PCn=M1nM nX i=1P i!0: q] H q(0)=0;Hq()=log(q1) log(q)log()log(q)(1)log(1)log(q): 11 distancerelative

BornedeHamming.BornedeSingleton.

Danscecaslesboules

B(x;t)=fy2Fnjd(x;y)tgFn

Définition2.1(a)Lenombret=d1

2estditlacapacitédecorrection

t(C)etencasd'égalitélecodeCestdit parfait.

Questions:

recouvrement(C)xé?

CardB(x;r)=jB(x;r)j=:Vq(n;r)("

levolumedelabouledeHamming").

CardB(x;r)=Vq(n;r)=rX

i=0(q1)in i ir.

CalculonsCard(S(x;i))pourxetixés

Card(S(x;i))=Cardfy2Fnjd(x;y)=dg

Ilyadoncn

êtredeq1façons,c'estàdire

Card(S(x;i))=(q1)in

i 12

2.2.BornedeHammingetbornedeSingleton

2etdecardinalM=Card(C).Alors

M tX i=0(q1)in i qn;doncVq(n;t)qn=M()Mqn=Vq(n;t):

Preuve:DansFn,ilyan

1+n

1(q1)++n

capacitédecorrectiont=d1

2.Alors

max

C(Card(C))qn=Vq(n;t)

(C).Alors minC(Card(C))qn=Vq(n;(C)) knd+1()R1+1=n; oùR=k=n,=d=n.

Preuve.Onpose

poidsdeCestd,d'oùknd+1. enanglais). existeetpositivesleslimites lim i!1k i ni=R>0;limi!1d ini=>0; quelquesrelations. 13 onpose

R=limsup

i!1k i ni;=limsup i!1d ini; alors R1 obtientlerésultat:R1. q] H q(0)=0;Hq()=log(q1) log(q)log()log(q)(1)log(1)log(q)

Proposition2.9

1 n+1qnHqrn

Vq(n;r)=rX

i=0(q1)in i qnHqrn (2.1) z ir1=)rX i=0(q1)in i rX i=0(q1)in i z ir: r X i=0(q1)in i z irnX i=0(q1)in i z ir=zr(1+(q1)z)n=:g(z): diff(z^(-r)*(1+(q-1)*z)^n,z); z(r)r(1+(q1)z)n z+z(r)(1+(q1)z)nn(q1)1+(q1)z

Cecidit,g0(z)estégaleà

Ceciimplique

g

0(z)=0()rz1r(1+(q1)z)n1((q1)(nr)zr)=0:

donc z 0=r (q1)(nr)=r=n(q1) 1rn g(z0)=zr0(1+(q1)z0)n;1+(q1)z0=1+r nr=nnr=11rn; etleminimumest g(z0)=(q1)rr n r 1rn nr: 14

Unexemplenumérique:

restart;q:=3;r:=1;n:=3; g(z):=z^(-r)*(1+(q-1)*z)^n; q:=3 r:=1 n:=3 g(z):=(1+2z)3 z gprime(z):=(1+2z)3 z2+6(1+2z)2z >z0:= >r/((q-1)*(n-r)); z0:=1 4 >'y=g(z)';

02468101214161820

y

0.20.40.60.81z

y=g(z)

D'autrepart

q nHqr n =qnr nlog(q1) log(q)r nlog(rn) log(q)(1r n)log(1rn) log(q)= (q1)rr n r 1rn nr=g(z0); d'où l'inégalitésupérieure. r X i=0(q1)in i >(q1)rn r 1 n+1~zr(1+(q1)~z)ng(z0):(2.2) 15

Eneet,ledéveloppement(1+(q1)~z)n=Pn

i=0Ai~zicontientn+1termes,Ai~zi=n i(q1)i~zi,et i(q1)r~zrsoitmaximalparmiAi~zi: A i1~zi1

Ai~zi=1~z

n i1 n i 1 (q1)1=(2.3) 1 ~zn!(i1)!(ni+1)!i!(ni)!n!1~zA i1Ai=1~zi(ni+1)(q1):

Onvoitdoncque

A i1~zi1

Ai~zi=1~zi(ni+1)(q1)

estune ~z2r (nr+1)(q1);r+1(nr)(q1) ()12Ar1~zr1Ar~zr;Ar~zrAr+1~zr+1 ona(pourtouslesi;javec0iCeciimplique

A i1~zi1Ai~ziAr~zr;Ar~zrAr+1~zr+1Aj~zj::::

MaisparnotrechoixletermeAr~zr=n

i(q1)r~zrestmaximalparmiAi~zi,donc ~zr(1+(q1)~z)n(n+1)Ar)g(z0)(n+1)rX i=0(q1)in i

Ilresteàrapellerque

g(z0)=qnHqr n =(q1)rrn r 1rn nr; ceciimpliquelaborneinférieure: 1 n+1qnHqrn

Vq(n;r)=rX

i=0(q1)in i

Corollaire2.10Lorsquen!1,r

n!,onaquotesdbs_dbs29.pdfusesText_35

[PDF] code de hamming pdf

[PDF] code de l'éducation 2017

[PDF] code de l'éducation creation

[PDF] code de l'éducation pdf

[PDF] code de l'éducation punition

[PDF] code de l'éducation simplifié

[PDF] code de l'éducation sanctions

[PDF] confiscation téléphone portable au travail

[PDF] confiscation portable loi

[PDF] confiscation portable loi quebec

[PDF] nouveau code de la route maroc 2016 pdf

[PDF] projet de loi 116-14 pdf

[PDF] panneaux de signalisation routière ? imprimer

[PDF] signification des panneaux de signalisation routière

[PDF] tout les panneaux de signalisation a imprimer