[PDF] [PDF] Mathématiques des codes correcteurs derreurs - Institut Fourier

[PDF] 1 Codes correcteurs derreurs - Annuaire IMJ-PRG

Exercice 1 1 Soit C le code binaire : C = {00001100,00001111,01010101, 11011101} 1 Quelle est la longueur de C ? 2 La distance minimale de C est la plus 

[PDF] Corrigés exercices codes correcteurs - LIRMM

Le code par parité impaire n'est pas linéaire, sa capacité de détection est de 1 bit , pour tout n Exercice 4: a: toute erreur sur un nombre impair de bit Pas de 

[PDF] Codes détecteurs et correcteurs B Rouzeyre - LIRMM

J Badrikian, Technosup, Ellipses (cours et exercices) Codes détecteurs et/ou correcteurs Un code qui corrige jusqu'à t erreurs est appelé t-correcteur 

[PDF] Exercices Codes Correcteurs - ENSIIE

Exercices Codes Correcteurs On consid`ere le code binaire o`u on envoie 16 bits pour 9 bits significatifs de la mani`ere On rappelle qu'il corrige une erreur

[PDF] TD Réseau Les codes correcteurs et les codes détecteurs Claude

correction des erreurs Méthodes mises un code détecteur et correcteur d' erreurs Le CRC Exercice : y a-t-il une erreur dans le mot suivant ? 1 0 1 0 1 1

[PDF] Feuille dexercices n Codes correcteurs - Benjamin Collas

ii) Quelle est la plus grande dimension d'un code linéaire binaire de longueur 8 qui corrige 2 erreurs? Construire un tel code Exercice 7 Soit C le code linéaire 

[PDF] TD Codes correcteurs

Si on expédie des bits sur un canal binaire symétrique `a raison de 512 bits toutes les millisecondes, avec une probabilité d'erreur de 1 , quel est le nombre de 

[PDF] Codes correcteur derreur - Alexis Bonnecaze

a donné aux codes correcteurs d'erreurs une grande importance Beaucoup Les codes utilisés sont souvent des codes de Hamming pouvant corriger une il ne peut pas être corrigé Par exemple (1000101) exercice : en trouver d'autres

[PDF] Exercice 1 Exercice 2

Feuille n°7 : codes correcteurs d'erreurs Les premiers exercices de cette feuille sont tirés de la base WIMS Exercice 1 1 Votre correspondant vous a transmis 

[PDF] Mathématiques des codes correcteurs derreurs - Institut Fourier

C'est-à-dire, que le code corrige jusqu'à 7 erreurs de transmission : dans ce Exercice Soit p = ps la probabilité des perturbations de symboles au cours de la  

[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] confiscation telephone illegal

[PDF] nouveau code de la route maroc 2016 pdf

[PDF] sigle 90 jeune conducteur maroc

[PDF] projet de loi 116-14 pdf

[PDF] bulletin officiel code de la route maroc 2016

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