Cours 3 1 Code de Hamming - Télécom ParisTech

Code de Hamming Présentation : le code de Hamming est utilisé dans les transmissions de données car il permet de détecter et de corriger une erreur survenue dans un bloc transmis Principe du codage : on fixe un entier k et on code chaque bloc de m = 2k - k - 1 bits de données par un

Cours 3 1 Code de Hamming - Télécom ParisTech

ACCQ204 4 Jan 2016 Cours 3 Enseignant: Aslan Tchamkerten Cr edit: Pierre de Sainte Agathe 1 Code de Hamming D e nition 1 Pour tout entier r 2 un code de Hamming (binaire) a pour

RoboLab Autumn Course – Hamming Codes

Standard Hamming Code (7,4) As calculated before, we now have 4 message bits + 3 parity bits = 7-bit Hamming Code Now, for representing this linear block code there are two forms: Systematic form (e g 0101101) This means, the parity bits are simply added after the original code Non-systematic form (e g 0110011)

Lecture 1: Basic problems of coding theory

d= 3 This code is known as the Hamming code, and is due to Richard Hamming who also showed the volume bound We identify f0;1gwith the eld F 2, and think of the code as a subset of Fn 2 Let ‘2N be a parameter, and Hbe the ‘ (2‘ 1) matrix whose columns consist of all non-zero vectors in F‘ 2 We set n= 2‘ 1 and de ne our code as C

Apprendre en ligne

Author: Didier Müller Created Date: 6/19/2019 3:12:11 PM

Linear Codes - Michigan State University

Hamming weight The Hamming weight (for short, weight) of a vector v is the number of its nonzero entries and is denoted w H(v) We have w H(x) = d H(x;0) The mini-minimum weight mum weight of the code Cis the minimum nonzero weight among all codewords of C, w min(C) = min 06=x2C (w H(x)): (3 1 2) Lemma Over a eld, Hamming distance is

Notes 1: Introduction, linear codes

The fractional Hamming distance or relative distance between x;y2 n is given by (x;y) = ( x;y) n It is trivial to check that the Hamming distance de nes a metric on n De nition 2 (Hamming weight) The Hamming weight of a string xover alphabet is de ned as the number of non-zero symbols in the string More formally, the Hamming weight of a string

La couche liaison de données

• Distance de Hamming Étant donné deux mots de n bits m1 et m2, le nombre de bits dont ils diffèrent est appelé leur distance de Hamming (notée Disth) • Distance de Hamming du code complet h = { Min Disth(x1, x2) ; x1 et x2˛ M } M est l’ensemble des 2 m mots de codes possibles si on admet que les r bits de

[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

Cours 3 1 Code de Hamming - Télécom ParisTech

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.

[PDF] Cours 3 1 Code de Hamming - Télécom ParisTech

Code de Hamming - Lycée Champollion