[PDF] [PDF] Cours 3 1 Code de Hamming

[PDF] CH2 CODES CORRECTEURS - IGM

transmet des bits mais qui en modifie certains en cours de transmission Il peut soit les Si on reprend le code de Hamming [7, 4], on trouve comme matrice

[PDF] Cours 3 1 Code de Hamming

4 jan 2016 · Tout code de Hamming atteint la borne de Hamming et est donc parfait 3-1 Page 2 Observation 2 Il existe d'autres codes parfait, par exemple 

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

⇒ on parle de code x − y où x = n + m et y = m Exemple de code de Hamming : un mot de code 7 − 4 a un coefficient d'efficacité de 4/ 

[PDF] Codes Correcteurs dErreurs Cours 1 + Introduction + - LIRMM

12 nov 2008 · Dans ce cours, nous nous interessons uniquement aux codes cor- Soit un code C, sa distance minimale de Hamming, dmin, est définie

[PDF] 1 Code de Hamming 2 Codage et décodage des codes - Moais

Théorie des Codes TELECOMMUNICATIONS 1A Feuille TD 4 - Codes correcteurs - Codes linéaires 1 Code de Hamming 1 ρ = k n = 11 15 2 Le code est:

[PDF] cours 3 detection-correction erreur - Les pages perso du LIG

P Sicard - Cours Réseaux • Les données peuvent Exemple de détection: Le code de parité Distance de Hamming du code complet (ou distance minimale)

[PDF] Techniques de détection & de correction des erreurs de - LIPN

Code polynomiale (CRC) □ Codes auto-correcteurs : code de Hamming Le plan de ce cours est inspiré du cours fait par B Cousin, IFSIC, Université de 

[PDF] Théorie des codes IUT (Sil) - PAGE WEB DANDRE LEROY

Dans toute la suite du cours les codes seront des codes par blocs sur un alphabet Calculons la distance de Hamming entre x = 010011 et y = 011101 cette 

[PDF] Codes détecteurs correcteurs

Correction et détection Codes linéaires Sécurisation de la transmission d' informations Distance de Hamming Erreurs de transmission Codage par blocs

[PDF] code de hamming 7 4

[PDF] code de hamming matrice de controle

[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] code de commerce pdf maroc

[PDF] code de commerce maroc en arabe

[PDF] droit commercial marocain cours pdf

[PDF] code de commerce maroc adala

[PDF] loi 49-15 maroc

[PDF] code de commerce algerien 2016 pdf

[PDF] code de commerce français

ACCQ2044 Jan. 2016

Cours 3

Enseignant: Aslan Tchamkerten Credit: Pierre de Sainte Agathe

1 Code de Hamming

Denition 1Pour tout entierr2un code de Hamming (binaire) a pour matrice de pariteHrtelle que : H r=0 B

B@1 0 1 0 1:1

0 1 1 0 0:1

0 0 0 1 1:1

: : : : : :11 C CA ou laiemecolonne est la representation de i en binaire (1i2r1) sur rbits. Proposition 1Pour toutr2le code de Hamming a distance minimale egale a3. PreuveLes colonnes de la matrice sont deux a deux independantes, donc d >2. De plus la somme des trois premieres colonnes satisfaitH1r+H2r+H3r=

0, elles sont donc dependantes et doncd= 3.Observation 1Par la borne de Hamming

jCj Vol(n;bd12 c)2n

Pourd= 3on a

jCj 2n1n+ 1 carVol(n;1) =n+ 1. Il suit que log

2(jCj)nlog2(n+ 1):

Pour le code de Hamming,n= 2r1)r= log2(n+ 1))log2jCj= 2 rr1 =nlog2(n+ 1). Tout code de Hamming atteint la borne de

Hamming et est donc parfait.

3-1 Observation 2Il existe d'autres codes parfait, par exemple, le code[n;1;n]2, ainsi que d'autres codes du a Golay.

1.1 Decodage code de Hamming

1. Algo 1 : MAP. la complexite est en 2

O(n)! (besoin de lister tous les

mots codes.

2. Algo 2 :

Si le motyrecu verieHy= 0 alors c'est un mot code. FIN

Sinon, on \

ip" successivement chaque bit deyet on verie si le mot obtenu appartient aC. La complexite est alors enO(nT(n)) ouT(n) =O(nlog2(n)) est la complexite du test de verication d'appartenance (multiplication d'un vecteur par une matrice) pour une position \ ipee". D'ou une complexite totale enO(n2log2(n))

3. Algo 3 : Dans le cas ou une erreur se produit au maximum par mot

code envoye on ay=C+eavec e=0 B

BBBBBBBBB@0

0 1 0 01 C

CCCCCCCCCA

AlorsHy=Hc+He=Hece qui correspond a laiemecolonne deH(i etant la position du 1 danseet donc de l'erreur dansy). La complexite est ici enO(nlog2(n)) (un seul calcul matriciel a faire).

2 Codes MDS : maximum distance separable

Rappel: la borne du singleton nous dit que pour tout code dnk+ 1)r+1)r1: 3-2 Soitqkmots codes formant un code de distance minimaled. En retirant d1 symboles dans chaque mot code (a la m^eme position pour tous les mots codes), on obtientqkmots codes tous dierents car ils forment un code de distance minimale1. L'unicite desqkmots codes du code \ponctue" donne q kqnd+1)dnk+ 1. Corollaire 1Un code satisfaitd=nk+ 1()Pour tout ensemble de kcoordonnees les mots codes sont distincts (i.e. leskcomposantes de tout mot code denissent le mot code). Denition 2Un code est dit MDS (maximum distance separable) sid= nk+ 1. Denition 3SoitCun code avecqkmots codes surFqet de longueurn. SoitJun sous-ensemble def1;2;::;ngde coordonnees.Jest unensem- ble d'informationsi pour tout mot code, les composantes de J le determine entierement. Corollaire 2Pour un code MDS, toutJavecjJj=kest un ensemble d'information. Conjecture 1Tout code lineaire[n;k]qMDS satisfaitnq+1si1< k < q sauf siqest pair etk= 3ouk=q1auquel cas on anq+ 2.

3 Codes de Reed-Solomon (vers 1950)

Soitk2[1;n];Fqtel quenqet1;2;:::;ndespoints d'evaluation distincts deFq.

Soit le code

C=f(f(1);f(2);:::;f(n)) :f2Fq;deg(f)< kg

Ce code, appele code de Reed-Solomon, est un code lineaire car pour tout messagemetm0 f m(X) +fm0(X) =fm+m0(X) et afm(X) =fam(X)

Ce code a pour parametres:

3-3 longueurn dimensionqk. En eet, si il existaitf6=f0telles quef(i) =f0(i)8i et telles quedeg(f)< ketdeg(f0)< k, alors en posantg=ff0on aurait que le nombres de racine degestnkalors quedeg(g)< k ce qui impossible. On deduit dont que tout polyn^ome donne un mot code dierent. une distance minimaled=nk+ 1. En eet par un raisonnement analogue on a d= minc2C;c6=0wt(c) et comme le nombre de racines est au plusk1, on a quedn(k1). Il suit qued=nk+ 1 par la borne superieure de Singleton. Observation 3Les codes de Reed-Solomon sont donc des codes MDS. A noter que la borne de Singleton implique la borne asymptotiqueR1. Or nous savons que la borne de PlotkinR1avec= 11q est strictement meilleure et doncR= 1ne peut ^etre atteint. Plus precisement, etant donne un alphabet[q]on ne peut pas construire une suite de code de telle facon a obtenirR= 1. Si l'on permet d'augmenter la taille de l'alphabet avec n, comme pour les codes RS, on peut atteindreR= 1asymptotiquement. Observation 4RS(n;k1)RS(n;k)car les polyn^ome de degreksont aussi de degrek1. Observation 5Eliminer (ponctuer) une m^eme coordonnee a tous les mots codes d'un code de RS(n,k) donne un code de Reed Salomon (on fait une evaluation en moins) pour autant quen1k.

3.1 Decodage

SoitCun code RS, (1;2;:::;n)2Fnq, etc2Ctel queci=f(i)

On observey=c+eet l'on veut retrouvery.

CAS 1: Pas d'erreur

y i=f(i)8i. 3-4 Alors 0 B B@y 1 y n1quotesdbs_dbs2.pdfusesText_3