Code correcteur d’erreurs

mipCip donc il existe bien r

0

...

mi

...

0

0 = H tm = H

















































n−1

(cid:80)

i=0

r

(cid:80)

p=1

r

(cid:80)

p=1

= H





=

colonnes de H Øtant linØairement dØpendantes.

Proposition 1.5.3. S’il existe r colonnes linØairement dØpendantes de H,

alors il existe un mot du code de poids r(cid:48) ≤ r.

r

(cid:80)

p

mipCip = 0.

DØmonstration. Il existe r scalaires non tous nuls tels que

Soit m ∈ F n

les autres sont nulles. On a w(m) ≤ r.

2 dont les composantes de rang i1, i2, ...ir sont mi1, mi2, ...mir et

On en dØduit que la distance minimale dC (c’est-(cid:224)-dire le poids minimal)

est Øgale au nombre minimum de colonnes linØairement dØpendantes de H.

DØ(cid:28)nition 1.5.4. Soit m ∈ F n

s = H tm.

2 , on appelle syndrome s du mot m le vecteur

Supposons que w soit un mot erronØ, w = m + e avec m un mot du code

e l’erreur. Ainsi, H tw = H t(m + e) = H te ; le mot erronØ et l’erreur ont donc

le mŒme syndrome s. L’ensemble des mots de syndrome s est appelØ classe

latØrale (ou coset) de w. Corriger w revient donc (cid:224) trouver le mot dont le

poids w(m) vØri(cid:28)e w(m) ≤ eC dans la classe latØrale de w ; cela n’est possible

que si ce mot est unique, on suppose donc qu’il y a moins d’erreurs que la

capacitØ de correction du code.

7

Proposition 1.5.5. Chaque syndrome s est associØ (cid:224) un unique mot m ∈ F n

2

dont le poids w(m) vØri(cid:28)e w(m) ≤ eC.

DØmonstration. Supposons qu’il existe m(cid:48) ∈ F n

2

H tm = H tm(cid:48) donc H t(m − m(cid:48)) = 0 et donc m − m(cid:48) est un mot du code.

w(m − m(cid:48)) ≤ w(m) + w(m(cid:48)) ≤2eC ≤ dC − 1. Le seul mot du code x qui vØri(cid:28)e

w(x) ≤ dC − 1 est le mot nul donc m − m = 0 et m = m(cid:48).

tel que w(m(cid:48)) ≤ eC et

Il su(cid:30)t maintenant de dresser une liste des syndromes de chaque ØlØment

2 pour pouvoir retrouver l’erreur et (cid:224) fortiori le mot codØ.

de F n

S’il n’y a qu’une erreur : soit ei le mot contenant un 1 (cid:224) la i-Łme place

et des 0 ailleurs. Alors, il existe i tel que w = m + ei. Le syndrome de ei est

donc la i-Łme colonne de H, on peut donc facilement localiser l’erreur.

Proposition 1.5.6. Si C est un code systØmatique et G = (Ik|B), alors

H = (−tB|In−k).

DØmonstration. H tG =t B −t B = 0.

(cid:18)1 0 1 0

0 1 1 1

(cid:19)

.

Exemple : Prenons G =

(cid:18)1 1 1 0

0 1 0 1

Ainsi, H =

(cid:19)

.

Codons le mot m = (01), w = (01)

(cid:18)1 0 1 0

0 1 1 1

(cid:19)

= (0111).

Ajoutons lui d’abord une erreur en troisiŁme position : z = (0101).

Calculons le syndrome de z : s = H tz =

(cid:18)1 1 1 0

0 1 0 1

(cid:19)











0

1





0



1

(cid:19)

(cid:18)1

0

.

=

Cela correspond (cid:224) la troisiŁme colonne de H, l’erreur provient donc du

troisiŁme bit.

1.6 Codes parfaits

IntØressons-nous (cid:224) C en tant qu’espace vectoriel.

Proposition 1.6.1. #BH(x, r) =

r

(cid:80)

i=0

C i

n.

8

DØmonstration. Pour tout i ∈ {0, 1, ..., r}, il existe C i

d(x, y) = i.

n mots y ∈ F n

2

tels que

Proposition 1.6.2. InØgalitØ de Hamming :

ec(cid:80)

i=0

C i

n ≤ 2n−k.

DØmonstration. Les boules BH(m, eC) centrØes en les mots du codes de rayon

eC sont deux (cid:224) deux disjointes donc :

#BH(m, eC) = (cid:80)

n ≤ |{0, 1}n| = 2n.

eC(cid:80)

C i

(cid:80)

m∈C

m∈C

i=0

Il y a 2k boules de Hamming dans le code donc :

eC(cid:80)

eC(cid:80)

2k

C i

n ≤ 2n et donc

C i

n ≤ 2n−k.

i=0

i=0

La situation optimale serait donc que les boules de Hamming forment

2 , ce qui est le cas lorsque l’inØgalitØ de Hamming est une

une partition de F n

ØgalitØ.

Figure 1 (cid:21) Situation oø chaque mot est associØ (cid:224) un unique mot du code.

DØ(cid:28)nition 1.6.3. Un code C de paramŁtres (n, k, dC) est dit parfait lorsque

les boules de Hamming centrØes en les mots du code de rayon eC forment une

partition de F n

2 .

eC(cid:80)

Ainsi,

i=0

C i

n = 2n−k et ∀ m ∈ F n

2 , il existe m qui minimise d(r, m). On

remarquera que dC est forcØment impair.

9

2 Code de Hamming

CrØons un code qui satisfait l’ØgalitØ de Hamming et qui soit capable

de corriger une erreur ; on prend donc la distance minimale la plus petite

possible, dC = 3.

Posons r = n − k.

1

(cid:80)

n = 2n−k ⇒ 1 + n = 2k

i=0

n = 2r − 1 et k = 2r − r − 1.

C i

Les codes ayant ces paramŁtres sont appelØs codes de Hamming.

DØ(cid:28)nition 2.0.1. Un code de Hamming est un code de paramŁtres (2r −

1, 2r − r − 1, dC) avec r ≥ 2 ; c’est un code parfait.

Les codes parfaits ayant une capacitØ de correction 1 sont donc nØcessai-

rement des codes de Hamming. Pour r = 2, le code parfait de paramŁtres

(3, 1, 3) est le code de rØpØtition.

Exemple : (cid:201)tudions le cas r = 3.

ConsidØrons un code linØaire systØmatique C(7, 4, 3). Soit x ∈ F4

2 , x =

d1d2d3d4 et soit ϕ : F 4

telle que ϕ(x) = d1d2d3d4p1p2p3 avec p1 =

d1 + d2 + d4 , p2 = d1 + d3 + d4 et p3 = d2 + d3 + d4 . On obtient la matrice

gØnØratrice

2 → F 7

2









G =

1 0 0 0 1 1 0

0 1 0 0 1 0 1

0 0 1 0 0 1 1

0 0 0 1 1 1 1





.





Essayons d’encoder un mot, de modi(cid:28)er un de ses bits et de le dØcoder. Pre-

nons m = (1010).

mG = (1010)

= (1010101).









1 0 0 0 1 1 0

0 1 0 0 1 0 1

0 0 1 0 0 1 1

0 0 0 1 1 1 1









Modi(cid:28)ons le 4Łme bit (1010101) −→ (1011101) Puisque le code est sys-

tØmatique, on peut rapidement trouver la matrice de contr(cid:244)le H.



H =



1 1 0 1 1 0 0

1 0 1 1 0 1 0

0 1 1 1 0 0 1



 On a bien H tG = 0.

10

Calculons le syndrome du message erronØ :

(1011101)tH = (1011101)









































1 1 0

1 0 1

0 1 1

1 1 1

1 0 0

0 1 0

0 0 1

= (111).

On obtient trois 1, il y a donc une erreur sur les trois bits de paritØ ; l’er-

reur provient donc du bit qui intervient dans la construction des trois bits

de paritØ : le quatriŁme. On aurait bien sßr reprendre l’algorithme vu prØcØ-

demment et retrouver le mŒme rØsultat.

Figure 2 (cid:21) Illustration montrant comment repØrer facilement la provenance

d’une erreur.

Ainsi, ce code est plus e(cid:30)cace qu’un simple code linØaire. Voil(cid:224) une com-

paraison en image (avec un taux d’erreur de 0.01) :

Figure 3 (cid:21) Code de Hamming/ Code linØaire gØnØrØ alØatoirement

Ces codes ont ØtØ rØalisØs sur Cocalc https://cocalc.com/ (ancienne-

11

ment nommØ Sage) et sont disponibles dans l’annexe. J’ai utilisØ le Jupi-

ter Notebook et le kernel le plus rØcent (SageMath Dev). Cocalc permet de

travailler facilement avec plusieurs types de codes correcteurs (linØaires, de

Hamming, cycliques) et permet de simuler l’apparition d’erreurs.

12

3 Codes cycliques

3.1 Fonctionnement des codes cycliques

DØ(cid:28)nition 3.1.1. Un code linØaire est dit cyclique s’il est stable par dØca-

lage circulaire.

Plus formellement, soit C un code de paramŁtres (n, k, dC) et m ∈ F n

2

,

m = m0m1...mn−1. On note σ(m) = mn−1m0...mn−2.

Alors, C est cyclique si ∀m ∈ C, σ(m) ∈ C.

Ainsi, ∀k ∈ N , σk(m) ∈ C et σn(m) = m.

Exemple Le code C = {000, 110, 011, 101} est cyclique.

DØ(cid:28)nition 3.1.2. Soit m = m0m1...mn−1 un mot, m(X) = m0 + m1X +

... + mn−1X n−1 est la reprØsentation polynomiale associØe (cid:224) m. On notera PC

la reprØsentation polyn(cid:244)miale d’un code (on pourra aussi utiliser C s’il n’y a

pas de risque de confusion).

En reprenant le code prØcØdent, on a PC = {0, 1 + X, X + X 2, 1 + X 2}.

Regardons (cid:224) quoi correspond un dØcalage circulaire vers la droite en

termes de polyn(cid:244)me.

σ(m)(X) = mn−1 + m0X + ... + mn−2X n−1

= Xm(X) + mn−1(1 − X n).

(mod X n − 1).

Donc, σ(m)(X) = X(m)X

C’est ce qui nous motive (cid:224) travailler dans l’anneau des polyn(cid:244)mes (cid:224) coe(cid:30)-

F2[X]

cients dans F2 modulo (X n − 1) :

X n−1.

Rappelons la dØ(cid:28)nition d’un idØal :

DØ(cid:28)nition 3.1.3. Un sous-ensemble non-vide I d’un anneau commutatif A

est un idØal si ∀a, b ∈ I, a + b ∈ I et ∀x ∈ A, x · a ∈ I.

Proposition 3.1.4. C est un code cyclique si PC est un idØal de

F2[X]

X n−1.

DØmonstration. Si PC est un idØal de

etXm(X) = σ(m)(X) ⇒ σ(m) ∈ C.

Inversement, si C est un code cyclique, σk(m) ∈ C∀k ∈ N donc X km(X) ∈

F2[X]

PC. Puisque C est un code linØaire, P (X)m(X) ∈ PC ∀P [X] ∈

X n−1 donc

PC est un idØal.

F2[X]

X n−1 alors ∀m ∈ C, Xm(X) ∈ PC

13

DØ(cid:28)nition 3.1.5. Le polyn(cid:244)me gØnØrateur g(X) d’un code cyclique C est

le polyn(cid:244)me non nul unitaire de plus bas degrØ de C.

Proposition 3.1.6. Le polyn(cid:244)me gØnØrateur est unique.

DØmonstration. Supposons que g1 et g2 soient deux polyn(cid:244)mes gØnØrateurs

distincts et di(cid:27)Ørents de 0 de C. Alors, g1 - g2 est un polyn(cid:244)me de C de degrØ

strictement infØrieur (cid:224) celui de g1 et g2, ce qui entra(cid:238)ne une contradiction.

Proposition 3.1.7. Tout mot du code est un multiple de g.

DØmonstration. Soit m ∈ C. Par division euclidienne, on a :

m(X) = q(X)g(X)+r(X) avec q(X), r(X) ∈ F2[X] et deg(r(X)) < deg(g(X)).

r(X) = q(X)g(X) − m(X) donc r est un mot du code d’aprŁs les propriØ-

tØs prØcØdentes (multiple de g(X) et linØaritØ). Si r(X) (cid:54)= 0, cela contre-

dit l’hypothŁse que g(X) soit le polyn(cid:244)me gØnØrateur. Donc, r(X) = 0 et

m(X) = q(X)g(X).

Proposition 3.1.8. g(X) divise X n − 1.

DØmonstration. On sait que X kg(X) = gk(X) oø gk(X) est le polyn(cid:244)me

obtenu en dØcalant les composantes de g(X)k fois vers la droite, c’est donc un

mot du code. Ce qui implique qu’il existe a(X) tel que X kg(X) = a(X)g(X)

et donc (X k + a(X))g(X) = X n − 1.

DØ(cid:28)nition 3.1.9. Un idØal I de A est dit principal s’il existe i ∈ I tel que

I = {i ∗ a|a ∈ A}.

C est donc un idØal principal de

F2[X]

Xn−1 et C = {m(X)g(X)|m(X) ∈

F2[X]

Xn−1}.

Proposition 3.1.10. dim(C) = n−deg(g(X)) et (g(X), Xg(X), ..., X n−1−deg(g(X))g(X))

est une base de C.

DØmonstration. Soit m ∈ C, deg(m(X)) ≤ n − 1 par dØ(cid:28)nition. Sim(X) =

q(X)g(X) alors deg(q(X)) ≤ n − 1 − deg(g(X)). Cela montre que m(X) est

une combinaison linØaire des polyn(cid:244)mes g(X), Xg(X), ..., X n−1−deg(g(X))g(X)).

Donc, dim(C) = n − deg(g(X)) et comme chaque combinaison linØaire

est de degrØ au plus n − 1, ces polyn(cid:244)mes forment une famille libre de

F2[X]

X n−1.(X, Xg(X), ..., X n−1−deg(g(X))) est bien une base de C.



De ce fait, on en dØduit que la matrice gØnØratrice G liØe (cid:224) C est de la

· · ·

· · ·

a0

0

0

an−k

a1

a0

0

0

0

0



∈ Mk,n(F2), deg(g(X)) =

forme









0

· · ·

· · · an−k

· · ·

a1

...

0

· · ·









a0

a1

· · · an−k

14

n − k.

Proposition 3.1.11. Soit C un code cyclique et g(X) son polyn(cid:244)me gØnØ-

rateur de degrØ r, g(X) = a0 + a1X + ...ar−1X r−1 + X r. Alors, a0 = 1.

DØmonstration. Supposons que a0 = 0.

g(X) = a1X + ...an−1X n−1 + X r

g(X) = X(a1 + ...an−1X n−2 + X r−1)

Si on dØcale g(X)n − 1 fois vers la droite (ou 1 fois vers la gauche), on obtient

le polyn(cid:244)me ci-dessus de degrØ < r ce qui gØnŁre une contradiction.

DØ(cid:28)nition 3.1.12. On appelle polyn(cid:244)me de contr(cid:244)le le polyn(cid:244)me h(X)

qui vØri(cid:28)e g(X)h(X) = X n − 1.

Son existence est garantie par g(X) | X n − 1.

En outre, si m ∈ C et m(X) = q(X)g(X),

h(X)m(X) = h(X)g(X)q(X)

= (X n − 1)q(X)

F2[X]

Xn−1.

= 0 dans

h(X) remplit bien un r(cid:244)le similaire (cid:224) celui de la matrice de contr(cid:244)le ; on

considØrera d’ailleurs la matrice de contr(cid:244)le H associØe. Si h(X) = b0 +b1X +

... + bkX k , H =











hk hk−1

0

hk

...

0

0

0

· · · h0

· · · h1 h0

· · ·

0 hk

· · ·

· · ·

0

0

...

· · · h0



∈ Mn−k,n(F2).









On a bien H tG = 0.

3.2 Recherche des codes cycliques

Soit C un code cyclique. Puisque le polyn(cid:244)me gØnØrateur divise X n − 1,

rechercher les polyn(cid:244)mes gØnØrateurs possibles pour un code de longueur n

revient (cid:224) trouver les facteurs de X n − 1 (cid:224) coe(cid:30)cients dans F2.

Soit α une racine primitive n-iŁme de l’unitØ, on a X n − 1 =

dans C[X].

n−1

(cid:81)

i=0

(X − αi)

15

Si g(X) est un polyn(cid:244)me gØnØrateur, il est de la forme g(X) = (cid:81)

(X −αi)

oø Σ est une partie convenable de Fn.

i∈Σ

Proposition 3.2.1. Les coe(cid:30)cients de g(X) = (cid:81)

(X − αi) sont dans F2 ssi

Σ est stable par multiplication par 2 modulo n.

i∈Σ

DØmonstration. Si g est (cid:224) coe(cid:30)cients dans F2, chaque coe(cid:30)cient de g est

stable par ØlØvation au carrØ. Comme cette opØration respecte aussi l’addi-

tion, on voit que g(X 2) = (g(X))2. Ainsi, l’ensemble des racines de g est

stable par ØlØvation au carrØ, ce qui signi(cid:28)e que Σ est stable par multiplica-

tion par 2. Inversement, si Σ est stable par multiplication par 2 :

(X 2 − αi)= (cid:81)

(X 2 − α2i) = (cid:81)

g(X 2) = (cid:81)

et donc les coe(cid:30)cients de g sont dans F2.

i∈Σ

i∈Σ

i∈Σ

(X − αi)2 = (g(X))2

La recherche de polyn(cid:244)mes gØnØrateurs revient donc (cid:224) trouver les parties

stables par multiplication par 2 de Fn. Soit j ∈ Fn, on note Σj la plus petite

partie stable contenant j. Alors, il existe un plus petit entier s > 0 tel que

2sj ≡ j[n], on peut ainsi prendre Σj={j, 2j, ..., 2s−1j} qui est bien stable par

multiplication par 2 modulo n.

DØ(cid:28)nition 3.2.2. La classe cyclotomique de j (relative (cid:224) 2 modulo n) est

Σj={j2k mod n|k ∈ N}.

Le degrØ du polyn(cid:244)me irrØductible associØ gj = (cid:81)

i∈Σj

(X − αi) est Øgal (cid:224)

card(Σj) = s.

Cherchons les codes cycliques de longueur 7 a(cid:28)n d’illustrer tout cela.

Exemple : 2sj ≡ j[7]. Pour j = 1, s = 3 convient.

Σ1 = {1, 2, 4}. De mŒme, pour j = 3, s = 3 convient (cid:224) nouveau : Σ3 =

{3, 5, 6}

En(cid:28)n pour j = 0, Σ0 = {0}.

X 7 − 1 peut donc Œtre dØcomposØ comme produit de 3 facteurs irrØduc-

tibles :







g0 = X − 1

g1 = (X − α)(X − α2)(X − α4)

g3 = (X − α3)(X − α5)(X − α6)

16

α Øtant une racine primitive 7-iŁme de l’unitØ.

On peut tester manuellement les polyn(cid:244)mes de degrØ 3 se terminant par 1

(sinon 0 est une racine) (cid:224) coe(cid:30)cients dans F2 qui conviennent : X 3+X 2 + 1 ;

X 3 + X + 1 ; X 3 + 1 et X 3+X 2 + X + 1.

Les deux derniers admettent une racine en 1 et X 3 +1 = (X −1)(X 2 +X +1)

et X 3 + X 2 + X + 1 = (X − 1)3, il n’y a donc que deux choix possibles.

Supposons que α soit racine primitive de P (X) = X 3 + X + 1, on obtient

plusieurs informations concernant α :

α3 = α + 1

α4 = α2 + α

α5 = α4 + 1

α6 = α2 + 1

g1 = (X − α)(X − α2)(X − α4)

= X 3+X 2( α+α2+α4)+X(α3+α5+α6)

= X 3 + X + 1.

De mŒme, on trouve que g3 = X 3 + X 2 + 1 et X 7 − 1 = (X − 1)(X 3 +

X + 1)(X 3 + X 2 + 1).

On obtient ainsi 23 = 8 codes cycliques di(cid:27)Ørents :







Code nul.

C0 = (cid:104)X 7 + 1(cid:105)

C1 = (cid:104)X + 1(cid:105)

C2 = (cid:104)X 3 + X + 1(cid:105)

C3 = (cid:104)X 3 + X 2 + 1(cid:105)

C4 = (cid:104)(X 3 + X + 1)(X + 1)(cid:105) = (cid:104)X 4 + X 3 + X 2 + 1(cid:105)

C5 = (cid:104)(X 3 + X 2 + 1)(X + 1)(cid:105) = (cid:104)X 4 + X 2 + X + 1(cid:105)

C6 = (cid:104)(X 3 + X + 1)(X 3 + X 2 + 1)(cid:105) = (cid:104)X 6 + X 5 + X 4 + X 3 + X 2 + X + 1(cid:105)

C7 = (cid:104)1(cid:105)

Ne change pas le mot.

Les code C2 et C3 ont pour paramŁtres (7, 4, 1), ce sont des codes de

Hamming. Le code C6 correspond au bit de rØpØtition.

On peut dØterminer les polyn(cid:244)mes gØnØrateurs d’une autre fa(cid:231)on :

DØ(cid:28)nition 3.2.3. On appelle polyn(cid:244)me cyclotomique le polyn(cid:244)me Φn

dØ(cid:28)ni par Φn(X) =

n )).

(X − exp( 2kiπ

n

(cid:81)

k=1

k∧n=1

Proposition 3.2.4. X n − 1 = (cid:81)

Φd(X).

d|n

17

DØmonstration. On sait que X n − 1 =

(cid:70)

{k ∈ {1, ...n}|k ∧ n = d}.

d|n

n−1

(cid:81)

i=0

(X − αi). De plus, {1, ...n} =

X n − 1 = (cid:81)

d|n

n

(cid:81)

k=1

k∧n=1

(X − αk) = (cid:81)

(X − αkd)

n

d(cid:81)

k=1

d|n

k∧( n

d )=1

=(cid:81)

d|n

d

(cid:81)

k=1

k∧d=1

(X − α nk

d ) = (cid:81)

Φd(X).

d|n

La derniŁre ØgalitØ venant du fait que si α est une racine primitive n-iŁme

de l’unitØ, α n

d est une racine primitive d-iŁme de l’unitØ.

(cid:3)

Proposition 3.2.5. Les polyn(cid:244)mes cyclotomiques sont (cid:224) coe(cid:30)cients dans Z.

DØmonstration. On montre qu’ils sont (cid:224) coe(cid:30)cients entier par rØcurrence.

C’est vrai pour φ1(X) = X − 1. On suppose que c’est vrai jusqu’au rang

n − 1. On a X n − 1 = (cid:81)

φd(X) = φn(X)h(X) dans C[X] oø h(X) est

d|n

un polyn(cid:244)me (cid:224) coe(cid:30)cients entier par hypothŁse de rØcurrence. En faisant

la division euclidienne dans Z[X] de X n − 1 par h(X) on a : X n − 1 =

g(X)h(X) + r(X) avec deg(r) < deg(h) et g(X) dans Z[X]. Par unicitØ de

la division euclidienne dans C[X], on a φn = g et donc φn est (cid:224) coe(cid:30)cient

entier.

Le calcul des polyn(cid:244)mes cyclotomiques permet donc aussi de retrouver

les polyn(cid:244)mes gØnØrateurs.

Nous allons dØsormais introduire une minoration de la distance minimale

d’un code cyclique.

Proposition 3.2.6. S’il existe des entiers a et s > 0 tels que (cid:80) contienne

a + 1, a + 2, ..., a + s, la distance minimale du code construit est ≥ s + 1.

DØmonstration. Il faut montrer qu’un polyn(cid:244)me R ∈ F2[X] de degrØ < n qui

a au plus s coe(cid:30)cients non nuls (et donc de poids < s + 1) est identiquement

nul. Cela revient donc (cid:224) montrer le lemme suivant :

Lemme Soient d1, ...ds des entiers avec 0 ≤ d1 < · · · < ds < n, et

λ1, ..., λs des ØlØments de F2. Posons R(X) = (cid:80) λjX dj . Si R(αi) = 0 pour

i = a + 1,...,a + s, alors tous les λj sont nuls.

18

DØmonstration. Le dØterminant des αidj est un dØterminant de Vandermonde.

Mais comme α est une racine primitive n-iŁme de l’unitØ, les αdj sont deux

(cid:224) deux distincts.

Pour le code cyclique de longueur 7 vu prØcØdemment, (cid:80) contient {1, 2}

(ou {5, 6}), la distance minimale de ce code est donc ≥3.

Les di(cid:27)Ørents codes cycliques dØsormais dØterminØs, on peut passer (cid:224)

l’Øtape du codage : il su(cid:30)t de multiplier la reprØsentation polynomiale d’un

mot par le polyn(cid:244)me gØnØrateur modulo X n − 1.

Exemple : On prend g(X) = X 3 + X + 1 et m(X) = 1 + X + X 2.

g(X)m(X) = (X 3 + X + 1)(1 + X + X 2) = 1 + X + X 5.

3.3 Algorithme de dØcodage

De fa(cid:231)on analogue aux codes linØaires, le dØcodage se fait par la dØtermi-

nation du syndrome.

DØ(cid:28)nition 3.3.1. Le syndrome d’un mot S(m)(X) est le reste de la division

euclidienne de ce mot par le polyn(cid:244)me gØnØrateur modulo X n − 1.

Cette dØ(cid:28)nition vØri(cid:28)e bien que si un mot appartient au code, son syn-

drome est nul.

Proposition 3.3.2. Soit C un code cyclique de longueur n et de dimension

k. Soit w(X) = q(X)g(X) + s(X), s(X) Øtant le syndrome de w(X). Alors,

le syndrome de Xw(X) est :

Xs(X) si deg(s(X)) < n − k − 1.

Xs(X) − g(X) si deg(s(X)) = n − k − 1.

DØmonstration. Si deg(s(X)) < n − k − 1 alors deg(Xs(X)) < n − k =

deg(g(X)) et on a bien Xw(X) = Xq(X)g(X) + Xs(X) par unicitØ de la

division euclidienne.

Si deg(s(X)) = n − k − 1, s(X) = s0 + s1X + ... + X n−k−1. On note (cid:98)s(X)=s0 +

s1X + ... + X n−k−2. De mŒme, g(X) = g0 + g1X + ... + X n−k et (cid:98)g(X) =

g0 + g1X + ... + X n−k−1.

Xs(X) = X(cid:98)s(X)+X n−k = Xs(X)+g(X)− (cid:98)g(X) = g(X) +(X(cid:98)s(X)− (cid:98)g(X))

19

et deg(X(cid:98)s(X) − (cid:98)g(X)) < n − k − 1. Comme X(cid:98)s(X) = X(X) − X n−k et

(cid:98)g(X) = g(X) − X n−k, le syndrome de w(X) vaut bien Xs(X) − g(X).

Soit C un code cyclique de paramŁtres(n, k, dC), g(X) son polyn(cid:244)me gØ-

nØrateur et w un mot erronØ. Ainsi, w(X) = m(X) + e(X) oø m est un mot

du code et e l’erreur associØe (cid:224) w. On rappelle que le mot peut Œtre corrigØ si

w(e) ≤ eC = (cid:98) dC −1

2 (cid:99), w dØsignant le poids du mot (le nombre de composantes

non nulles). L’objectif du dØcodage est donc de dØterminer le polyn(cid:244)me e(X).

DØterminons la forme de l’erreur. Soit e(cid:48) = (ts,0) oø 0 dØsigne le vecteur

(cid:224) k 0 et s le syndrome de w. Le degrØ de e(cid:48)(X) Øtant strictement infØrieur

(cid:224) celui du polyn(cid:244)me gØnØrateur par dØ(cid:28)nition, son syndrome est le mŒme

que celui de e. De plus, si on suppose que w(s) ≤ eC alors w(e(cid:48)) ≤ eC cela

implique que e(cid:48) = e car il n’existe qu’un seul vecteur de poids ≤ eC associØ

(cid:224) chaque syndrome. L’erreur est donc de la forme (ts,0).

On veut maintenant se ramener au cas oø w(s) ≤ eC a(cid:28)n de pouvoir

dØterminer l’erreur. Supposons que e possŁde k 0 (cid:224) la suite et que w(e) ≤ eC.

Alors, il existe i ∈ {0, 1, .., n − 1} tel que les k 0 de σi(e) soient situØs (cid:224) la

(cid:28)n du mot. Ainsi, σi(e) est de la forme(β,0), β Øtant un vecteur de longueur

n-k ; donc deg(β(X))≤ n − k − 1 =deg(g(X)) − 1. Le syndrome de β(X)

est donc β(X) lui-mŒme. Comme w(β(X)) ≤ eC, w(si(X)) ≤ eC oø si(X)

est le syndrome de X ie(X) modulo X n − 1. D’aprŁs l’argument prØcØdent,

e(X)X i = (tsi,0) donc e(X) = X n−i(tsi,0).

On peut donc expliciter l’algorithme de dØcodage :

1. On dØtermine le syndrome de w(X) par division euclidienne.

2. On prend i = 0 et si w(si(X)) ≤ eC, e(X) = X n−i(si,0) et

m(X) = w(X) − e(X).

3. Sinon, i = i + 1 et on calcule si(X) ;on recommence jusqu’(cid:224) ce que i = n.

Si i = n la correction est impossible.

Exemple Soit C un code cyclique de paramŁtres (15, 7, 5) de polyn(cid:244)me

gØnØrateur g(X) = X 8 + X 7 + X 6 + X 4 + 1 ; sa capacitØ de correction est

donc de 2.

Prenons m(X) = 1 + X + X 3 et w(X) = m(X)g(X).

w(X) = (1 + X + X 3)(1 + X 4 + X 6 + X 7 + X 8) = 1 + X + X 3 + X 4 + X 5 +

X 6 + X 7 + X 10 + X 11.

20

Modi(cid:28)ons deux de ses composantes, disons la quatriŁme et la huitiŁme et

notons ce nouveau polyn(cid:244)me z(X) = 1 + X + X 3 + X 5 + X 6 + X 7 + X 8 +

X 10 + X 11.

Par division euclidienne, on obtient z(X) = (X 3 + X)(1 + X 4 + X 6 + X 7 +

X 8) + X 7 + X 6 + 1.

Le syndrome est donc s(X) = X 7 + X 6 + 1 de poids 3 > 2.

deg(s(X)) = 7 = deg(g(X)) − 1 donc s1(X) = Xs(X) − g(X).

s1(X) = X 8 + X 7 + X − (X 8 + X 7 + X 6 + X 4 + 1) = X 6 + X 4 + X + 1.

s2(X) = X(X 6 + X 4 + X + 1) = X 7 + X 5 + X 2 + X.

s3(X) = X 8+X 6+X 3+X 2−(X 8+X 7+X 6+X 4+1) = X 7+X 4+X 3+X 2+1.

...

...

s10(X) = X 7 + X 6 + X 5.

s11(X) = X 8 + X 7 + X 6 − (X 8 + X 7 + X 6 + X 4 + 1) = X 4 + 1.

w(s11(X)) = 2 , c’est ce que l’on recherchait.

e(X) = X n−11s11(X) = X 4(X 4 + 1) = X 8 + X 4.

Les erreurs sont bien en position 4 et 8, l(cid:224) oø on les avait placØes. Il su(cid:30)t

ensuite de diviser le mot obtenu par le polyn(cid:244)me gØnØrateur a(cid:28)n de

retrouver le mot initial.

Toutefois, l’algorithme de dØcodage n’aurait pas fonctionnØ si e(X) ne

comportait pas au moins k zØros (cid:224) la suite (ce qui arrive forcØment pour un

code de longueur 15 et de dimension 7 lorsqu’il n’y a que deux erreurs).

DØ(cid:28)nition 3.3.3. Un "burst" de longueur λ est un mot de Fn

composantes non nulles sont con(cid:28)nØes dans λ positions consØcutives.

2 dont l...