Coding 11
Coding 11
Coding 11
Emily Clement
Enseignant : Delphine Boucher
Master 1 de Mathématiques
Semestre 2
2015-2016
Table des matières
3 Codes cycliques 42
I Définition et propriétés . . . . . . . . . . . . . . . . . . . . . . 42
II Matrice génératrice et matrice de contrôle. . . . . . . . . . . . 48
III Factorisation de X n ´ 1. . . . . . . . . . . . . . . . . . . . . . 53
4 Codes BCH 57
I Principe (cas linéaire) . . . . . . . . . . . . . . . . . . . . . . . 57
II Définition et théorème (borne BCH) . . . . . . . . . . . . . . 63
III Décodage des codes BCH . . . . . . . . . . . . . . . . . . . . . 65
1 Premier algorithme : via système linéaire . . . . . . . . 66
2 Deuxième algorithme : via Euclide étendu (partiel) . . 71
5 Codes de Goppa 77
I Rappels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
II Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
III Propriétés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
IV Décodage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
1
TABLE DES MATIÈRES
I Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
Exemple 1.1.
On utilise des turbo-codes pour la mission Rosetta (ESA, Europear Space
Agency), concurrent des turbo-codes : codes LDPC.
Disques compacts : Codes de Reed-Solomon.
Télévision à satellite : DVC. S2 (Digital Vidéa Broadcasting) : on utilise des
codes LDPC + BCH.
Billet de banque, code ISBN, code sécurité sociale etc.
Les codes en gras seront ceux que l’on va étudier.
3
CHAPITRE 1. GÉNÉRALITÉS SUR LES CODES CORRECTEURS
k
Le rendement ou taux d’information du code est R “ .
n
rks
Quand k n’est pas un entier on trouve parfois l’écriture R “ .
n
Principe :
Proposition 1.1.
Démonstration.
Montrons le quatrième point : @a, b P F n w pa ` bq ď w paq ` w pbq
Soient a, b P F n w pa ` bq “ # ti P J1, . . . , nK, ai ` bi ‰ 0u
Or @i P J1, nK ai ` bi ‰ 0 ñ ai ‰ ď0 ou bi ‰ 0
Donc ti|ai ` bi ‰ 0u Ă ti|ai ‰ 0u ta|bi ‰ 0u
Donc w pa ` bq ď w paq ` w pbq
Soient x, y, z P F n :
w ppy ´ zq ´ px ´ zqq ď w px ´ zq ` w pz ´ yq
d“ min dH pc, c1 q
c,c1 PC,c‰c1
d
Le taux de correction est r0 “
n
Proposition 1.2.
Démonstration.
d´1
Soit c1 P C tel que dH py, c1 q ď t u
2
Par l’inégalité triangulaire :
dH pc, c1 q ď d pc, yq ` d py, c1 q ă d
Or d est la distance minimale de C donc dH pc, c1 q “ 0 donc c “ c1
Proposition 1.3.
Démonstration.
Si y P C et y ‰ c alors par définition de d :
dH py, cq ě d
Exemple 1.3.
A “ F “ F2
Ak Ñ A2k ` ˘
1. φ : , C “ φ Ak
m ÞÑ pm|mq
1
rendement :
2
Taux de correction ?
Si on prend c1 “ p10 . . . 0|10 . . . 0q P C et c2 “ p0 . . . 0|0 . . . 0q P C
dH pc1 , c2 q “ 2
Soient m, m1 P Ak , c “ pm|mq et c1 “ pm1 |m1 q
w pc ´ c1 q “ w ppm ´ m1 |m ´ m1 qq
“ 2 ¨ w pm ´ m1 q
” 0 r2s
2
donc d “ 2, r “
n
Exemple :
10011001 ÞÑ 10001001
on ne peut pas corriger...
2. Un exemple plus fort mais avec un moins bon rendement :
Ak Ñ A3k
φ:
m ÞÑ pm|m|mq
` ˘
, C “ φ Ak
1
Rendement :
3
Si on prend c1 “ p10 . . . 0|10 . . . 0q P C et c2 “ p0 . . . 9|0 . . . 0q P C
dH pc1 , c2 q “ 3
Soient m, m1 P Ak , c “ φ pmq et c1 “ φ pm1 q
w pc ´ c1 q “ 3w pm ´ m1 q “ 0 r3s don d “ 3
On peut corriger 1 erreurs, et détecter 2 erreurs.
3
r “ le taux de correction n’a pas bougé, c’est t qui a changé.
n
Ak Ñ Ak`1
3. φ :
m ÞÑ pm|m1 ` ¨ ¨ ¨ ` mk q
` ˘
C “ φ Ak code de parité.
k
R“
k`1
Si on prend p0 . . . 0|0q P C et p1 0 . . . 0|1q P C donc d ď 2.
Soient m, m1 P F k
k
ÿ
1 1 1 1
c “ pm|tq avec t “ m1 ` ¨ ¨ ¨ ` mk et c “ pm |t q avec t “ m1i
i“1
c ´ c1 “ pm ´ m1 |t ´ t1 q
On a plusieurs cas :
si m “ m1 alors t “ t1 et c “ c1
si m ‰ m1 w pm ´ m1 q ě 1
— Si w pm ´ m1 q ě 2 alors w pc ´ c1 q ě 2
— w pm ´ m1 q “ 1 alors t ‰ t1 donc w pc ´ c1 q “ 2
Objectif :
1. Construire des codes de longueurs arbitrairement grande avec un taux
d’information et un taux de correction élevé.
2. Construire des algorithmes de corrections d’erreurs qui soient efficaces
(complexité en temps polynomial.)
On a besoin de plus de structures : on va introduire les codes linéaires.
II Codes linéaires.
Définition 1.6 (Codes linéaires).
Remarque 1.1. ¨ ˛
Propriétés 1.1.
Démonstration.
Soit c P C c ‰ 0 w pcq “ dH pc, 0q ě d car 0 P C car C est un espace-vectoriel.
Soit c1 , c2 P C tel que dH pc1 , c2 q “ d (ces deux mots existent par définition
de la distance minimale)
Soit c “ c1 ´ c2 , c P C car C est linéaire.
w pcq “ d
dďn´k`1
C’est vrai aussi pour les codes non-linéaires (on verra la preuve en
TD)
Démonstration.
“ ˝? . . .?, 1 , ?, . . . , ?, 0 , 0 . . . , 0 , ?, . . . , ?‚
Ò Ò Ò
j1 j2 jk
#
w pcq ě 1
On a :
w pcq ď n ´ k ` 1
Donc c est un mot de code non nul de poids inférieur à n ´ k ` 1.
donc :
dďn´k`1
Remarque 1.2.
Les codes tels que d “ n ´ k ` 1 sont des codes MDS : Maximum Distance
Separable, ce sont des codes optimaux.
Par exemple les codes de Reed-Solomon (1960) sont MDS.
(
Attention, on écrit plus les vecteur en colonne mais en ligne ! C m ¨ G, m P Fkq
G P Mk,n pFq q, de rang k.
Définition 1.7 (Code dual).
Remarque 1.3.
(
C K “ x P Fnq , @c P C, c ¨t x “ 0
(
“ x P Fnq , Gt x “ 0
Or Rg pGq “ k car
` dim˘ C “ k donc d’après le théorème du rang, dim pker pGqq “
n ´ k donc dim C K “ n ´ k.
Notons H une matrice de contrôle de C, H P Mn´k,n pFq q et Rg pHq “ n ´ k
G ¨t H “ 0 et H ¨t G “ 0
Définition 1.8.
Propriétés 1.2.
Démonstration.
On a que :
Rg pHq “ n ´ k et dim pker pHqq “ k
` (˘
Donc dim pCq “ dim x P Fnq |H ¨t x “ 0 Soit G une matrice génératrice
de C telle que H ¨t G “ 0, on a @x P C, Dm P pFq qk x “ m ¨ G` ˘
Soit x P C soit m P Fkq tel que x “ mG alors H ¨t x “ H ¨ t ¨t m “ 0 car
H ¨t G “ 0 (
Donc C Ă x P Fnq | H ¨t x “ 0 l’autre inclusion vient par égalité de dimen-
sion des espaces.
Remarque
¨ 1.4.˛
Théorème 1.2.
Démonstration.
d “ min w pcq.
c‰0,cPC
Soit c un mot de C de poids w ‰ 0, on a :
H ¨t c “ 0
¨ ˛
w
ÿ
donc cij Hij “ 0 où Hi désigne le i-ème colonne de H et c “ ˝0, . . . , 0, ci1 , 0 . . . , ciw , . . . 0‚
˚ ‹
j“1 ∦ ∦
0 0
L’indépendance linéaire vient avec le caractère minimal de d !
Exemple 1.4.
Fk2 Ñ F2k ` ˘
1. φ : 2 C “ φ Fk2
m ÞÑ pm|mq
Matrice génératrice G “ pIk |Ik q
Matrice
¨ de contrôle
˛ H “ pIk |Ik q
G “ ˝A| B ‚
Ø Ø
k n´k
mG “ pmA|mBq
A “ I ô mA “ m
donc d “ 3
Principe :
Soit y P Fnq on cherche la ligne (ou coset) qui contienne y.
Soit e le premier élément de la ligne (coset leader), ie c’est un
mot de plus petit poids tel que y ´ e P C.
Alors c “ y ´ e est un mot de code le plus proche de y. (on a
pas nécessairement unicité)
d´1
Il existe au plus un coset leader de poids ď t u dans un coset.
2
Démonstration.
d´1 d´1
Soient x1 , x2 tels que w px1 q ď t u et w px2 q ď t u et x1 ´ x2 P C
2 2
Alors w px1 ´ x2 q ď w px1 q ` w p´x2 q ă d donc x1 “ x2
xRy ô y ´ x P C
ô H ¨t py ´ xq “ 0
H ¨t x “ H ¨t y
Construction du tableau :
1. Sur la première ligne on a le mot nul et son syndrome. (vecteur nul)
2. Chaque ligne suivante commence par un mot de plus petits poids dont
le syndrome n’apparaît pas dans le tableau.
¨ ˛
ˆ ˙ 1 0 1 0 0
1 0 1 1 0
Exemple avec : G “ et H “ ˝1 1 0 1 0‚
0 1 0 1 1
0 1 0 0 1
t
e, coset leader S peq
00000 000
10000 110
01000 011
00100 100
00010 010
00001 001
11000 101
Exemple 1.6.
Soit y “ p1, 1, 0, 0, 1q P F52 .
Le syndrome de y est :
¨ ˛ ¨ ˛ ¨ ˛ ¨ ˛
1 0 0 1
˝1‚` ˝1‚` ˝0‚ “ ˝0‚
0 1 1 0
IV Codes de Hamming
But : Construire une famille infinie de codes linéaire 1´correcteurs d’er-
reurs.
Rg pHq “ r
M “ 2k
Algorithme 1.3.
¨ ˛
S1
˚ .. ‹
où S “ ˝ . ‚ avec Si P F2 Correction de l’algorithme (point 3) pour l’amé-
Sr
liorer :
r´1
ÿ
iÐ Sr´l ¨ 2l
l“0
Exemple 1.8.
1. y “ p1, 1, 1, 0, 0, 0, 0q
¨ ˛
0 0 0 1 1 1 1
H “ ˝0 1 1 0 0 1 1‚
1 0 1 0 1 0 1
r“3 ¨ ˛
0
t
S “ H ¨ y “ 0‚
˝
0
donc y P C.
2. y “ p1, 1, 1, 0, 0, 1, 0q
¨˛
1pP F2 q
S “ H ¨t y “ ˝ 1 ‚
0
donc i “ 0 ¨ 20 ` loomo
2 on ¨21 ` 1 ¨ 22 “ 6
PN
Donc e “ p0, 0, 0, 0, 0, 1, 0q et c “ p1, 1, 1, 0, 0, 0, 0q
Exercice 1.1.
t
ÿ
Cni “ 1 ` n “ 2r “ 2n´k
i“0
2.
Remarque 1.5 (Tableau standard).
p0, ¨ ¨ ¨ , 0q p0, ¨ ¨ ¨ , 0q
p1, 0, ¨ ¨ ¨ , 0q H1
p0, 1, 0, ¨ ¨ ¨ , 0q H2
.. ..
. .
p0, ¨ ¨ ¨ , 0, 1q Hn
C “ tc P Fn2 |c pαq “ 0u
r´1
ÿ
où c ´ pc0 , ¨ ¨ ¨ , cn q où c pαq “ ci αi Montrer que C est un code
i“0
rn, n ´ r, 3s2
V Codes de Golay
Le code de Golay linéaire étendue G24 a été utilisé par les sondes Voyager
I et II (1979 ´ 81) pour la transmission de photos de Jupiter et Saturne.
Il a pour matrice génératrice G “ pI12 Aq où :
¨ ˛
0 1 ¨¨¨ 1
˚ 1 ‹
A“˚ .
˚ ‹
˝ .. B
‹
‚
1
et B P M11,11 pF2 q est une matrice dite circulante définie par sa première
ligne :
¨ ˛
p1q p2q p3q p4q p5q p6q p7q p8q p9q p10q p11q
˚ 1 1 0 1 1 1 0 0 0 1 0 ‹
˚
˚ 1 0 1 1 1 0 0 0 1 0 1 ‹
‹
˚ 0 1 1 1 0 0 0 1 0 1 1 ‹
B“˚
˚ ‹
‹
˚ ‹
˚ ‹
˚ ‹
˝ ¨¨¨ ‚
0 1 1 0 1 1 1 0 0 0 1
Théorème 1.3.
Démonstration.
w pu ` vq “ # ti|ui ` vi “ 1u
“ # ti|ui “ 1, vi “ 0u ` # ti|ui “ 0, vi “ 1u
“ # ti|ui “ 1u ´ # ti|ui “ 1, vi “ 1u
` # ti|vi “ 1u ´ # ti|ui “ 1, vi “ 1u
w pu ` vq “ w puq ` w pvq ´ 2u ˚ v
où u ˚ v “ # ti|ui “ vi “ 1u
n
ÿ ÿ
Or xu, vy “ 0 “ ui vi “ 1
i“1 ui “1,vi “1
avec w pxq “ r.
Nécessairement r ď 4
Si r “ 4 alors w pxq “ 4 et w pxAq “ 0 or c’est impossible car A est inversible
(A2 “ I)
Si r “ 3, alors w pxq “ 3 donc w pxn Aq “ 1
Or Dy #P F12
2 tel que c “ pyA|aq
x “ yA
Donc donc w pyq “ 1 et w pyAq “ 3, yA est une ligne de A car
xA “ y
w pyq “ 1 : impossible car les poids des lignes de A sont 11 ou 7.
Si r “ 1 : alors c est une ligne de G : impossible car les poids des lignes de
G sont 8 ou 12.
Si r “ 2 alors :
c “ g1 ` gi
où gi désigne la i´ème ligne de G et i ą 1
ou c “ g2 ` gi où i ą 2
ou c “ gi ` gj où i ‰ j 3 ď i ă j Matrice a finir voir feuille
w pg1 ` g2 q “ 8 ‰ et w pg1 ` gi q “ 8 ‰ 4 pour i ě 2.
w pg2 ` g3 q “ 2 ` 6 “ 8 et on vérifie w pg2 ` hi q “ 8 ‰ 4 pour i ě 3.
Conclusion
# : G24 ne possède pas de mot de poids 4.
dď8
Or
d ” 0 r4s
Donc d “ 8
Exercice 1.2.
On appelle G23 la code de Golay binaire, il est obtenu en ôtant une coordonnée
(la dernière) aux mots de G24 .
Montrons que G23 est un code r23, 12, 7s2 parfait.
3
ÿ
i 2 3
C23 “ 1 ` 23 ` C23 ` C23
i“0
23 ¨ 22 23 ¨ 22 ¨ 21
“ 1 ` 23 ` `
2 3¨2
“ 1 ` 23 ` 253 ` 23 ˆ 11 ˆ 7
“ 277 ` 1771
“ 2048
“ 21 1
Décodage
G24 est un code binaire r24, 12, 8s2 de matrices génératrices (et de contrôle
car ce code est auto-dual) :
ej “ ˝0 ¨ ¨ ¨ , 0, 1, 0 ¨ ¨ ¨ , 0‚
Ò
j
` ˘
et H “ pA|I12 q “ t A|I12 .
et A “t A et A ¨t A “ A2 “ I12 de plus sa distance minimale est 8.
¨ ˛
T “ G ¨t r “ lo ¨t ocn `G ¨t e “t x ` A ¨t y
Gomo
“0
Lemme 1.1.
1. w pxq “ 0 ô w psq ď 3
2. w pyq “ 0 ô 0 ô w pT q ď 3
Démonstration.
Si w pxq “ 0 alors S “t y
Or w pxq ` w pyq ď 3 donc w psq ď 3.
Si w pxq ‰ 0
Lemme 1.2.
Démonstration.
O a w psq “ w pyq “ 1 ou w pxq “ 2 w pyq “ 1 ou w pxq “ 1 et w pyq “ 2
˚ Supposons Dj P J1, 12K T “ Aj “ 0.
Alors t x ` A ¨`t y “ A ¨˘t ej
Donc t x “ A t y `t ej car on est en binaire (donc ´ “ `)
Nécessairement y ‰ ej sinon x “ 0.
py ` ej q ¨ G “ py ` ej | py ` ej q ¨ Aq est un mot non nul de G24 donc son
poids est ě 8 (distance minimale)
Donc w py ` ej q ` w ppy ` ej q Aq ě 8
Or x “ py ` ej q A donc$w py ` ej q ` w pxq ě 8.
&w pxq ď 2
’
C’est impossible car : w pyq ď 2 (donc w py ` ej q ď 3)
’
w pej q “ 1
%
Donc @j P J1, 12K w pT ´ Aj q ą 0
De même @j P J1, ¨ ¨ ¨ , 12K, w pS ´ Aj q ą 0
˚ :Supposons Dj P J1, 12K T “ Aj “ 1.
Soit z P F12 t
2 tel que T ´ Aj “ z avec w pzq “ 1
t
x ` A ¨t y ´ A ¨t ej “t z
` ˘
donc t x `t z “ A t y `t ej
— Si y “ ej alors x “ z “t T ´t Aj
— Si y ‰ ej alors py ` ej | py ` ej q Aq est un mot de G24 non nul. Donc
loooooooooomoooooooooon
py`ej q¨G
son poids est ě 8.
Donc w py ` ej q ` w ppy ` ej q Aq ě 8 or w ppy ` ej q Aq “ w px ` zq
Donc w py ` ej q ` w px ` zq ě 8
Or w pej q “ 1, w pxq ` w pzq ď 3 et w pzq “ 1
t
x ` A ¨t y ´ A ¨t ej “t z
` ˘
donc t x `t z “ A t y `t ej
— Si y “ ej alors x “ z “t T ´t Aj
— Si y ‰ ej alors py ` ej | py ` ej q Aq est un mot de G24 non nul. Donc
loooooooooomoooooooooon
py`ej q¨G
son poids est ě 8.
Donc w py ` ej q ` w ppy ` ej q Aq ě 8 or w ppy ` ej q Aq “ w px ` zq
Donc w py ` ej q ` w px ` zq ě 8
Or w pej q “ 1, w pxq ` w pzq ď 3 et w pzq “ 2
Donc w py ` ej q ` w px ` zq ď z pxq ` w pyq ` w pej q ` w pzq ď 6
Contradiction. Donc y “ ej
˚ : Supposons qu’il existe j P J1, 12K w pS ´ aj q P t1, 2u
Alors on montre que x “ ej et y “t S `t Aj
˚ : Supposons que @j P lbbracket1, 12K w pT ` Aj q ě 3
et @i P J1, 12K, w pS ` Ai q ě 3
` ` ˘˘
w t x ` A t e j `t y ě 3
Algorithme 1.4.
Entrée : r, G, H
Sortie : c.
1. S Ð H ¨t r
2. T Ð G ¨t r ¨ ˛
Remarque 1.6.
Cet algorithme est adaptable à tout code binaire auto-dual de distance mi-
nimale ě 8 ayant une matrice génératrice sous forme systématique :
G “ pIK |Aq
avec A ¨t A “ IK
Code de Reed-Solomon
généralisés
But : Construire une famille de codes linéaires MDS sur Fq ainsi qu’un
algorithme de décodage en temps polynomial.
car α ‰ β, β ‰ γ, α ‰ γ
C’est la déterminant d’une matrice de Vandermonde pα ´ βq pα ´ γq pβ ´ γq
29
CHAPITRE 2. CODE DE REED-SOLOMON GÉNÉRALISÉS
d“4
Définition 2.1.
et ¨ ˛
v1 0
Dnpvq
˚
“˝ .. ‹
. ‚
0 vn
On dit que α1 , ¨ ¨ ¨ , αn sont les localisateurs du code.
et que v1 , ¨ ¨ ¨ , vn sont les multiplicateurs du code.
Si n “ q ´ 1 on dit que le code est primitif.
Si @i P t1, ¨ ¨ ¨ , nu vi “ 1 on dit que le code est normalisé.
On note GRS les code de Reed-Solomon généralisé.
Pour remarque
¨ ˛
v1 v2 ¨¨¨ vn
˚
˚ α1 v1 α2 v 2 ¨¨¨ αn v n
‹
‹
pαq
Vn´k,n ¨ Dnpvq
˚
“˚ α12 v1 α22 v2 ¨¨¨ αn2 vn
‹
‹
˚ .. .. ‹..
˝ . . ‚ .
n´k´1 n´k´1 n´k´1
α1 v1 α2 v2 ¨ ¨ ¨ αn vn
Exemple 2.2.
1. q “ 7, n “ 6 @i P t1, ¨ ¨ ¨ , 6u αi “ i
k “ 4 @i P t1, ¨ ¨ ¨ , 6u vi “ i
¨ ˛
ˆ ˙ 1 0
1 ¨¨¨ 1 ˚ .
H“ ¨˝ .. ‹
1 2 ¨¨¨ 6
‚
0 6
F8 ” F2 rXs {pP q
Théorème 2.1.
Démonstration.
Soit C un code GRS rn, k, dsq .
Soient α1 , ¨ ¨ ¨ , αn P Fq z t0u distincts 2 à 2 ses localisateurs.
v1 , ¨ ¨ ¨ , vn P Fq z t0u ses multiplicateurs.
On a
d ď n ´ k ` 1 (Borne de Singleton)
‰0
Proposition 2.1.
Le dual d’un code GRS est un code GRS (ayant les mêmes localisa-
teurs).
Démonstration.
soit C un code GRS rn, k, n ´ k ` 1sq de localisateurs α1 , ¨ ¨ ¨ , αn et multipli-
cateurs v1 , ¨ ¨ ¨ , vn
` ˘K
soit une matrice de contrôle de C K , ie matrice génératrice de C K “ C.
Notons : ¨ ˛
1 ¨¨¨ 1 ¨ ˛
˚ α1 v 1 0
¨¨¨ αn ‹
H “ ˚ ..
˚ ‹ ˚
.. ‹ ¨ ˝ ... ‹
‚
˝ . . ‚
0 vn
α1n´k´1 ¨ ¨ ¨ αnn´k´1
H est une matrice de contrôle de C.
Montrons qu’il existe v11 , vn1 tels que G ¨t H “ 0 ie que les lignes de G et H
soient orthogonales entre elles.
n
ÿ
G ¨t H ô @i P t1, ¨ ¨ ¨ , n ´ k} , @j P t1, ¨ ¨ ¨ , ku , αli´1 ¨ vl ¨ αlj´1 ¨ vl1 “ 0
l“1
pαq
Vn´1,n Dnpvq est une matrice de contrôle d’un GRS rn, 1, nsq
Tous les mots d’un code GRS rn, 1, nsq ont un poids nul ou ě n donc tous
les mots ‰ 0 ont un poids égal à n.
(@i, vi1 ‰ 0)
où ¨ ˛
1 ¨¨¨ 1 ¨ ˛
˚1 1 ¨ v11
¨¨¨ 6‹˚ . ‹
‹
.. ‹ ˝ .. ‚ “ 0
˚
˚ ..
˝. .‚
6 ¨ v61
14 ¨ ¨ ¨ 64
pαq pvq
Ce qui correspond à V5,6 ¨ D6 (cd preuve)
v11 “ ¨ ¨ ¨ “ v61 “ 1 est solution (dans F7 )
` ˘n
pour un certain n´uplet de F˚q v “ pv1 , ¨ ¨ ¨ , vn q
(
C “ mG|m P Fkq
$ ¨ ˛ ,
1 ¨ ¨ ¨ 1 ¨ 1 ˛
v1 0
’
’ /
/
α α
’ /
&` ˘˚
˚ 1 ¨ ¨ ¨ ‹
n ‹˚
.
“ m0 , ¨ ¨ ¨ , mk´1 ˚ .. .. ‹ ˝ . .. ‚ tel que mi P Fq
‹
’ ˝ . . ‚ 1
/
0 vn
’
’ /
/
k´1 k´1
α1 ¨ ¨ ¨ αn
% -
$ ¨ 1 ˛ ,
˜ ¸ v1 0
& k´1
’ ÿ k´1
ÿ k´1
ÿ /
.
“ mi α1 , i i
mi α2 , ¨ ¨ ¨ , i
mi αn ˝
˚ . .. ‹
‚ tq m i P F q
’
% i“0 i“0 i“0 1
/
0 vn
-
$ ¨ 1 ˛ ,
’
& v1 0 /
.
“ pm pα1 q , m pα2 q , ¨ ¨ ¨ , m pαn qq ˝
˚ . .. ‚ tel que m pXq P Fq rXs , deg pmq ď k ´ 1
‹
’ 1
/
0 vn
% -
Exercice 2.1.
Montrer qu’un code GRS est MDS en utilisant la caractérisation polynomiale.
Rappels
Soit C le code GRS r6, 2, 5s7 de matrice de contrôle :
¨ ˛
¨ ˛ 1
1 1 1 11 1 ˚ 2
˚ 0 ‹
‹
˚1 2 3 4 5 6‹˚ 3 ‹
H“˚ ˝12 22 32 42 52 62 ‚˚ 0
‹˚ ‹
˚ 4 ‹
‹
3 3 3 3 3 3 ˝ 5
1 2 3 4 5 6 ‚
6
où les coefficients de la 2e ligne de la première matrice sont les localisateurs,
et les coefficients diagonaux de la deuxième les multiplicateurs.
(
C “ x P F67 tel que H ¨t x “ 0
où f “ n0 ` m1 x
Donc C “ tpf p1q , f p2q , ¨ ¨ ¨ , f p6qq , f P F7 rXs , deg pf q ă 2u Vérifions que
la distance minimale de C est 5 en utilisant :
Le théorème de Singleton : d ď 6 ´ 2 ` 1 ď 5
Soit c dans C de poids ď 4, montrons que c “ 0
f dans F7 rxs tel que deg pf q ă 2 et c “ pf p1q , ¨ ¨ ¨ , f p6qq, d ď 4 donc
Algorithme de Berlekamp-Welch
Soit C un code GRS rn, k, n ´ k ` 1sq de localisateur α1 , ¨ ¨ ¨ , αn P F˚q avec
@i ‰ j, αi ‰ αj
d´1
On suppose que d p“ n ´ k ` 1q est impair et on note t “
2
Soit c “ pf pα1 q , ¨ ¨ ¨ , f pαn qq avec f P Fq rxs et deg pf q ă k
Soit r P FnQ tel que dH pc, rq ď t
Étant donné r on chercher à retrouver f .
On note I “ ti P t1, ¨ ¨ ¨ , nu , ci ‰ ri u
On a |I| ď t
n a f pαi q “ ri pour i P t1, ¨ ¨ ¨ , nu zI où f est inconnu, et αi , ri connus.
Pour retrouver f on va construire deux polynômes Q0 pxq , Q1 pxq tel que :
1. Construction de Q0 et Q1
On cherche Q0 et Q1 tels que :
$
&@i P t1, ¨ ¨ ¨ , nu , Q0 pαi q “ ri ¨ Q1 pαi q p1q
’
deg pQ0 q ă n ´ t p2q
’
deg pQ1 q ă t ` 1
%
p3q
ă max pn ´ t, k ` tq
¨ ˛
˚ n´k n ´ k‹
ă max ˚n ´ ,k `
˚ ‹
‹
2 loooomoooon
˝loooomoooon 2 ‚
n
2
` k2 n
2
` k2
deg pφq ă n ´ t
@i P I ri ‰ f pαi q
@i P t1, ¨ ¨ ¨ , nu zI ri “ f pαi q
I “ ti|ri ‰ f pαi qu |I| ď t
De plus @i P J1, nK
Q0 pαi q ´ ri Q1 pαi q “ 0
Donc @i P J1, nKzI
Remarque 2.1.
Les équations #
@i P t1, ¨ ¨ ¨ , nu
Q0 pri q “ ri Q1 pαi q
peuvent s’écrire :
$
’
’Q0 ” P ¨ Q1 rF s
’
’
’
’
’deg pQ0 q ă n ´ t
’
° pQ q ă t ` 1
1
’
’P pαi q “ ri , deg pP q ă n
’
’ n
’
’ ź
’
’
%F “ px ´ αi q
i“1
II Codes de Reed-Solomon
Les codes de Reed-Solomon sont des codes GRS particuliers.
Définition 2.2.
αi “ αi“1 , i “ 1, ¨ ¨ ¨ , n
et de multiplicateurs :
vj “ αbpj´1q , j “ 1, ¨ ¨ ¨ , n
` ˘2
Pas divisible par x et par X ` 1 : X 4 ` X 3 ` 1, X 4 ` X 2 ` 1 “ x2 ` X ` 1
X 4 ` X ` 1, X`4 ` X 3 ` X 2˘ ` X ` 1
F24 » F2 rXs { X 4 ` X ` 1
Soit α P F24 tel que α4 ` α ` 1 “ 0
On a α15 “ 1
α3 ‰ 1 car α4 ` α ` 1 “ 0 et X 4 ` X ` 1 est irréductible sur F2
α5 “ α4 ¨ α “ pα ` 1q α “ α2 ` α ‰ 1
On a donc α15 “ 1, α3 ‰ 1 et α5 ‰ 1 donc α est une racine primitive 15´eme
de 1.
Prenons b “ 3 et k “ 13 :
ˆ ˙
1 1 1 ¨¨¨ 1 ` 3 6 9 12 3 6 9 12
˘
H“ ¨ diag 1, α , α , α , α , 1, α , α , α , α , 1, ¨ ¨ ¨
1 α α2 ¨ ¨ ¨ α14
(5 blocs.)
Interprétation
¨ polynomiale ˛
b
1 α α2b ¨ ¨ ¨ αbpn´1q
b`1
˚1 α ¨ ¨ ¨ ¨ ¨ ¨ αpn´1qpb`1q ‹
˚ ‹
˚. .. .. ‹
˚ .. . ¨ ¨ ¨ ¨ ¨ ¨ . ‹
H“˚
˚ ‹
i 2 i pn´1q ‹
i
` ˘ ` ˘ ‹
˚1 α α ¨¨¨ α
˚ ‹
˚ .. .. .. ‹
˝. . ¨¨¨ ¨¨¨ . ‚
b`d´2 pn´1qpb`d´2q
1 α ¨¨¨ ¨¨¨ α
d“n´k`1 (
C “ c inFnq |H ¨t c “ 0 c “ pc0 , ¨ ¨ ¨ , cn´1 q
¨ ` ˘ ` ˘2 ` ˘n´1 ˛
c0 ` c1 αb ` c2 αb ` ¨ ¨ ¨ ` cn´1 αb
˚ c0 ` c1 αb`1 ` c2 αb`1 2 ` ¨ ¨ ¨ ` cn´1 αb`1 n´1 ‹
˚ ` ˘ ` ˘ ` ˘ ‹
˚ ‹
˚ .. ‹
˚ . ‹
H ¨t c “ ˚ ` i
˘ ` i 2
˘ ` i n´1
˘ ‹
c c α c α c α
˚ ‹
˚ 0 ` 1 ` 2 ` ¨ ¨ ¨ ` n´1 ‹
˚ .. ‹
˚
˝ . ‹
‚
` b`d´2 ˘ ` b`d´2 ˘2 ` b`d´2 ˘n´1
c `c α ` c2 α ` ¨ ¨ ¨ ` cn´1 α
¨ 0 ` 1˘ ˛
c αb
˚ ` b`1 ˘ ‹
˚ c α ‹
H ¨t c “ ˚ ..
‹
˝ ` .
˚ ‹
b`d´2
˘‚
c α
où c pxq “ c0 ` c1 x ` ¨ ¨ ¨ ` cn´1 xn´1 donc :
` ˘ ` ˘ ` ˘
H ¨t c “ 0 ô c αb “ c αb`1 “ ¨ ¨ ¨ “ c αb`d´1 “ 0
ô g pxq |c pxq
bd´2
ź
où g pxq “ px ´ αi q
i“b
De plus g pxq |xn ´ 1 : on a un code cyclique.
Remarque : c P Fnq ô c pxq P Fq rXs { pxn ´ 1q
Codes cycliques
C’est une sous-classe des codes linéaires, et ils sont plus facile à encoder.
I Définition et propriétés
Fq désigne un corps fini à q éléments, et n un entier non nul.
Définition 3.1.
´ ¯
n´1
cπ pXq “ X c0 ` c1 X ` ¨ ¨ ¨ ` cn´1 X
“ X ¨ c pXq
42
CHAPITRE 3. CODES CYCLIQUES
Définissons :
! )
n´1
C pXq “ c0 ` c1 X ` ¨ ¨ ¨ ` cn´1 X |c “ pc0 , ¨ ¨ ¨ , cn´1 q P C
Lemme 3.1.
Démonstration.
ñ
Montrons que : @a pXq P Fq rXs{pX n ´1q , @c pXq P C pXq
a pXq c pXq P C pXq
C est cyclique
` donc˘ @c pXq P C pXq, Xc pXq P C pXq
donc X X ¨ c pXq P C pXq
i
donc...@i P N X c pXq P C pXq
Or, C est linéaire donc @a pXq “ a0 ` a1 X ` ¨ ¨ ¨ ` an´1 X n´1 P Fq rXs{pX n ´1q
ð
Comme C pXq est un idéal de Fq rXs{pX n ´1q ,
L’anneau Fq rXs{pX n ´1q est un anneau non intègre dont tous les idéaux sont
principaux, ce qui va permette de caractériser les codes cycliques.
Théorème 3.1.
Démonstration.
et
c0 ` ¨ ¨ ¨ ` cn´1 X n´1 P Fq rXs{pX n ´1q
! )
On note C pXq “ c pXq P Fq rXs{pX n ´1q |c P C
Exemple 3.1.
1. Soit n P N˚ .
X ´ 1|X n ´ 1 dans F2 rXs donc X ` 1 engendre un code cyclique C de
longueur n sur F2
Soit x P Fn2
3. n “ 7, q “ 2
X 7 ` 1, comment factoriser ?
7 “ 23 ´ 1
n
ź
Or on sait que X 2 ´ X “ f
f irré
degpf q“d,d|n
ź
2n ´1
Donc X ´1“ f
f irré,f ‰X
degpf q“d,d|n
X 3 `? ` 1
X 3 ` X 2 ` 1, X 3 ` X ` 1
Donc :
` ˘` ˘
X 7 ` 1 “ pX ` 1q X 3 ` X ` 1 X 3 ` X 2 ` 1
` ˘` ˘
X 3 ` X ` 1 “ pX ` αq X ` α2 X ` α4
c P C ô X 3 ` X ` 1|c pXq
` ˘` ˘
ô pX ` αq X ` α2 X ` α4 |c pXq
$
&X ` α|c pXq
’
ô X ` α2 |c pXq
’
X ` α4 |c pxq
%
$
&c `pαq ˘“ 0
’
ô c α2 “ 0
’
% ` 4˘
x α “0
ô c pαq “ 0 car on est sur F72 rXs
ô c0 ` c1 α ` ¨ ¨ ¨ c6 α 6 “ 0
` ˘ ` ˘ ` ˘
ô c0 ` c1 α ` c2 α2 ` c3 pα ` 1q ` c4 α2 ` α ` c5 α2 ` α ` 1 ` c6 α2 ` 1 “ 0
ô pc0 ` c3 ` c5 ` c6 q ` pc1 ` c3 ` c4 ` c5 q α ` pc2 ` c4 ` c5 ` c6 q α2 “ 0
$
&c0 ` c3 ` c5 ` c6 “ 0
’
ô c1 ` c3 ` c4 ` c5 “ 0
’
c2 ` c4 ` c5 ` c6 “ 0
%
¨ ˛
¨ ˛ c0
1 0 0 1 0 1 1 ˚c ‹
˚ 1‹
ô 0 1 0 1 1 1 0‚˚ . ‹ “ 0
˝
˝ .. ‚
0 0 1 0 1 1 1
c6
α0 “1
α1
α2
α3 “α`1
α4 “ α2 ` α
α5 “ α2 ` α ` 1
α6 “ α2 ` 1
α7 “1
On a c “ mG où m “ pm0 , ¨ ¨ ¨ , mk´1 q
C est un code rn, ksq
$ ,
’ /
k
( & .
C “ mG|m P Fq “ loooooomoooooon
m pXq g pXq |m pXq P Fq rXs , deg pm pXqq k
’
% /
-
degăn
Autre matrice génératrice
On a : X i “ g pXq Qi pXq`Ri pXq pour 0 ď ` i ď k ´1 avec˘deg Ri pXq ă n´k
X i`r ´ Ri pXq “ g pXq Qi pXq P C pXq et X i`r ´ Ri pXq 0ďiďk´1 est libre.
Donc une matrice génératrice de C est du type :
¨ ˛
´R0
˚
˚ ´R1 ‹
‹
˚
˚ I ‹ ‹
˚
˝ .
.. ‹
‚
´Rk´1
` ˘
en prenant pour base de départ 1, ¨ ¨ ¨ , X r´1 , X r , ¨ ¨ ¨ , X n´1 .
Exemple 3.2.
q ´ 2, n ´ 7, g “ X 3 ` X ` 1
Première matrice génératrice :
¨ ˛
1 1 0 1 0 0 0
˚0 1 1 0 1 0 0‹
G“˚ ˝0 0
‹
1 1 0 1 0‚
0 0 0 1 1 0 1
X3 mod X3 ` X `1“X `1
X4 mod X3 ` X ` 1 “ X2 ` 1
X5 mod X3 ` X ` 1 “ X 3 ` X 2 mod X 3 ` X ` 1 “ X 2 ` X ` 1
X6 mod X3 ` X ` 1 “ X 4 ` X 3 mod X 3 ` X ` 1
“ X 2 ` 1 ` X 3 mod X 3 ` X ` 1 “ X 2 ` 1
¨ ˛
1 1 0 1 0 0 0
˚0 1 1 0 1 0 0‹‹ X n ´ 1 “ g pXq h pXq
G1 “ ˚
˝1 1 1 0 0 1 0‚
1 0 1 0 0 0 1
h pXq ¨ g pXq “ X n
$
&@l P tk, ¨ ¨ ¨ , n ´ 1u :
’
k
Donc ÿ
% hi ¨ cl´i “ 0
’
i“0
On a donc @c P Fnq : (on va de l “ k à n ´ 1
¨ ˛
hk hk´1 ¨ ¨ ¨ h0 0 ¨ ¨ ¨ 0
˚0 hk ¨¨¨ h0 0 ¨ ¨ ¨ 0‹
˚ ‹ ˜ ¸
˚0 0 hk ¨ ¨ ¨ h0 0 ¨ ¨ ¨ 0‹ c 0
cPCñ˚.
˚ ‹
. ... ... ... ... ... .. ‹ ¨ .
˚ .. .. .‹ ..cn´1
˚ ‹
˝ 0‚
0 ¨¨¨ 0 hk ¨ ¨ ¨ h0
Théorème 3.2.
Démonstration.
Remarque 3.1.
Le dual de C a pour matrice génératrice H, C 1 est donc un code cyclique de
ˆ ˙
k 1
On a bien X h |X n ´ 1.
X
En effet g pXq ¨ h pXq “ X n ´ 1 donc
ˆ ˙ ˆ ˙ ˆ ˙
k 1 n´k 1 n 1
X h ¨X g “X ¨ ´1
X X Xn
“ 1 ´ Xn
Exemple 3.3.
2. q “ 2, n “ 7 g “ X 3 ` X ` 1
` 7 ˘ ` ˘` ˘
X ` 1 “ pX ` 1q X 3 ` X ` 1 X 3 ` X 2 ` 1
` ˘
h “ pX ` 1q X 3 ` X 2 ` 1
“ X 4 ` X63 ` X ` X 3 ` X 2 ` 1
“ X4 ` X2 ` X ` 1
¨ ˛
1 0 1 1 1 0 0
Une matrice de contrôle est H “ ˝0 1 0 1 1 1 0‚
0 0 1 0 1 1 1
III Factorisation de X n ´ 1.
On suppose que n et q premiers entre eux.(alors X n ´ 1 est sans facteur
carré).
On veut factoriser X n ´ 1 sur une extension de Fq en produit de facteurs
linéaires.
Pour cela, on va chercher le corps fini (extension de Fq ) contenant les racines
n´ième de 1.
Soit m le plus petit entier non nul tel que n|q m ´ 1 : c’est l’ordre multiplicatif
de q modulo n.
m
alors : X n ´ 1|X q ´1 ´ 1
donc les racines de X n ´ 1 sont dans Fqm
soit α une racine primitive n´ième de 1 dans Fqm .
n´1
ź
Donc on a X n ´ 1 “ pX ´ αi q (factorisation dans Fqm rXs
i“0
On va chercher à rassembler les facteurs linéaires pour obtenir une factorisa-
tion dans Fq rXs
Définition 3.2.
Soit s P t0, ¨ ¨ ¨ , n ´ 1u
La q-classe cyclotomique de s modulo n est :
" *
2 ms ´1
C psq “ s, s ¨ q , s ¨ q , ¨ ¨ ¨ , s ¨ q
mod n mod n mod n
où ms est le plus petit entier non nul tel que s ¨ q ms ´1 ” s rns Les
classes cyclotomiques forment une partition de t0, ¨ ¨ ¨ , n ´ 1u
On définit : ź ` ˘
Mαs pXq “ X ´ αi
iPCpsq
ź
On a X n ´1 “ Mαs pXq où s parcourt les représentants des classes
S
cyclotomiques.
Proposition 3.1.
Démonstration.
F m Ñ Fq m
σ: q est un automorphisme laissant fixes les éléments de Fq .
a ÞÑ aq
@a P Fqm :
a P F q ô aq “ a
Montrons que @i P t0, ¨ ¨ ¨ ms u , ai P Fq
ź ` ˘
Mαs pXq “ X ´ αi par définition
iPCpsq
ms
ÿ
“ ai X i
i“0
˜ ¸q
ms
ÿ
q
Mαs pXq “ ai X i
i“0
m s
ÿ q
“ ai X q¨i
i“0
iPCpsq
ź ` ˘
“ X q ´ αj
jPCpsq
“ Mαs pX q q
car αn “ 1
Donc Mαs pXq P Fq rXs
Soit f irréductible
ź dans Fq rXs divisant Mαs pXq
` ˘
Or Mαs pXq “ X ´ αi
iPCpsq
` ˘
Donc Di P C psq tel que f ` αi˘ “ 0 ` ˘q ` ˘
donc Di P C psq tel que f αi “ 0 et f αi “ f αiq “ 0 car f P Fq rXs
donc Di P C psq :
` ˘ ` ˘
f αi “ f αqi
´ 2¯
“ f αq i
“ ¨¨¨
“0
` ˘
donc @i P C psq , f αi “ 0
Donc f “ Mαs pXq
Exemple 3.4.
q “ 2 n “ 7 “ 23 ´ 1
F23 » F2 rXs{pX 3 `X`1q
Soit α P F23 tel que α3 ` α ` 1 “ 0 alors α7 “ 1 (α P F23 ), or 7 est premier
donc α est une racine primitive 7-ème de l’unité.
6
ź
7
` ˘
X ´1“ X ´ αi
i“0
“X`1 “X 3 `X`1
` ˘` ˘` ˘
Mα3 “ X ´ α3 X ´ α5 X ´ α6
¨ ˛
` 3 ˘ ‹` ˘
α ` α5 X ` α‚ X ` α6 “ X 3 ` α2 X 2 ` αX ` α6 X 2 ` αX ` 1
“ ˝X ` loooomoooon
˚
“α2
` ˘
“ X ` α ` α6 X 2 ` 1
3 2
“ X3 ` X2 ` 1
Exemple avec q “ 2 et n “ 5
24 ” 1 r5s, 22 ” ´1 r5s ı 1 r5s
On cherche une racine primitive 5-ème de 1 dans F24
Irréductible de degré 4 :
Pas être divisible par X ou X ` 1 : constante égale à 1 et nombre impair de
terme.
Pas être divisible pas X 2 ` X ` 1.
— X 4 ` X ` 1( ` ˘2
4 (((
` X2 ` 1 “ X2 ` X ` 1
(
— ( X(
— X4 ` X3 ` 1
— X4 ` X3 ` X2 ` X ` 1
Soit α P F24 tel que α4 ` α ` 1 “ 0
α5 “ α2 ` α donc α racine primitive 15´ème de l’unité.
Si g pαq “ 0, g P` Fq˘rXs
i
` i ˘ g pαq “ g α “ ¨ ¨ ¨ “ 0
Alors
g α “ 0 @i P C p1q ź ` ˘
f irréductible P Fq rXs tel que f pαq “ 0 f “ X ´ αi
iPCp1q
g P Fq rXs tq g pαq “ 0
` ˘
alors @i P C p1q , g αi “ 0 ô X ´ αi |g
Soit ξ “ α5
Alors ξ 5 “ 1 et @i P t1, ¨ ¨ ¨ , 4u ξ i ‰ 1
4
ź
5
` ˘
X ´1“ X ´ ξi
i“0
C p0q “ t0u
C p1q “ t1,
` 2, 4, 3u˘ ` ˘` ˘` ˘` ˘ ` ˘
X 5 `1 “ X ´ ξ 0 X ´ ξ 1 X ´ ξ 2 X ´ ξ 3 X ´ ξ 4 “ pX ´ 1q X 4 ` X 3 ` X 2 ` X ` 1
Codes BCH
57
CHAPITRE 4. CODES BCH
Algorithme 4.1.
où e “ ˝0, ¨ ¨ ¨ , 1 , 0, ¨ ¨ ¨ 0‚
Ò
i`1
α2 ¨ ¨ ¨ n´1
ˆ ˙
1 α α
H“ ` ˘
f p1q f pαq ¨ ¨ ¨ f αn´1
où f : F2r Ñ F2r
Soit y “ c ` e avec e pXq “ X i ` X j et 0 ď i ă j ď n ´ 1
S “ H ¨t c ` H ¨t e
H ¨t e
˜ ¸
i j
α ` α
“ ` ˘ ` ˘
f αi ` f αj
Algorithme 4.2.
Entrée
$ : y
$ tel que y , “ c ` e et
’
’ & .
&c P C “ x P Fn | loomo
’
H ¨ t
x “ 0
2 on
% -
’ p˚q
’
’
%w peq ď 2
Sortie : c
1. S Ñ H ¨t y, u, v Ñ coordonées de S
2. Si S “ 0 alors rendre pyq
3. Si v “ u3 alors déterminer
¨ i P t0, ¨ ¨ ¨ , n ´˛1u tel que u “ α
i
rendre py ` eq où e “ ˝0, ¨ ¨ ¨ , 1 , 0 ¨ ¨ ¨ , 0‚
Ò
i`1
e “ ˝0, ¨ ¨ ¨ , 1 , 0 ¨ ¨ ¨ , 0, 1 , 0 ¨ ¨ ¨ , 0‚ (e pXq “ X i ` X j )
Ò Ò
i`1 j`1
¨ ¨ ¨ αn´1
ˆ ˙
1
p˚q : H “
1 α3 ¨ ¨ ¨ α3pn´1q
Remarque 4.2.
On utilise parfois le réciproque de P :
ˆ ˙
˚ v ` u3 2 2 1
P “ 1 ` uZ ` Z “Z P
u Z
` ˘ ` ˘
et on cherche i ă j tel que P ˚ α´i “ P ˚ α´j “ 0
Avantage : Si S ‰ 0 le degré de P ˚ fournit le nombre d’erreurs.
Remarque 4.3.
Soit c P Fn2
¨ ˛
ˆ ˙ 0
c`pαq˘ ˚ .. ‹
cPCô “ ˝.‚
c α3
loooomoooon 0
H¨t c
ô Mα pXq |c pXq et Mα3 pXq |c pXq
ô ppcm pMα pXq , Mα3 pXqq |c pXq
looooooooooooooomooooooooooooooon
divise X n ´1
Mα pXq , Mα2 pXq , Mα3 pXq , Mα4 pXq sont tous égaux.
i P t0, ¨ ¨ ¨ , r ´ 1u 3 ” 1 ˆ 2i mod n (n “ 2r ´ 1)
Exemple 4.2 (Exemple pour r “ 4).
On considère α P F24 tel que α4 ` α ` 1 “ 0
On a bien :
1. X 4 `
$X ` 1 irréductible dans F2 rXs
4
&X ` X ` 1 mod
’ X“1‰0
car X 4 ` X ` 1 mod X `1“1‰0
’
% 4
X ` X ` 1 mod X2 ` X ` 1 “ 1 ‰ 0
2. α d’ordre 15 car : α3 ‰ 0 α5 “ α2 ` α ‰ 1
On considère le code sur F2 de matrice de contrôle :
˜ ¸
1 α ¨ ¨ ¨ α14
H“ ` ˘4
1 α3 ¨ ¨ ¨ α3
u “ α3 et v “ α2
On veut retrouver e connaissant u et v.
u3 “ α9 ‰ v
Soit :
u3 ` v
P pZq “ Z 3 ` uZ `
u
9
α ` α2
“ Z 2 ` α3 Z `
α3
α11
“ Z 2 ` α3 Z ` 3
α
“ Z 2 ` α3 z ` α8
` ˘
P α0 “ 1 ` α3 ` α8
“ α3 ` α2 ‰ 0
` 1˘
P α “ α2 ` α4 ` α8
“α‰0
` 2˘
P α “ α4 ` α5 ` α8
“ α ` 1 ` α2 ` α ` α2 ` 1
“0
` ˘
Comme le produit des racines de P est α8 , on a P α6 “ 0
On a donc :
e pXq “ X 2 ` X 6
Soit n un entier non nul, soit q une puissance d’un nombre premier.
On suppose n et q premiers entre eux.
Soit m l’ordre multiplicatif de q modulo n.
Soit α une racine primitive n-ième de l’unité dans Fqm . (nq m ´ 1)
Soit b un entier et soit δ P N˚ .
Le code BCH de distance prescrite δ et associé à α est le code cyclique
de longueur n et de polynôme générateur :
Démonstration.
Supposons que le code possède un mot C de poids ď δ ´ 1
@j P t1, ¨ ¨ ¨ , δ ´ 1u , cij “ 0
On a g pXq |c pXq
Donc @i P t0, ¨ ¨ ¨ , δ ´ 2u
Mαb`i pXq |c pXq
donc @i P t0, ¨ ¨ ¨ , δ ´ 2u ` ˘
c αb`i “ 0
donc : ¨ ˛ ¨
αbi1 αbis´1
˛
¨¨¨ ci 1 ¨ ˛
˚ pb`1qi1 pb`1qiδ´1 ‹ ˚ 0
˚ α ¨¨¨ α ‹ ˚ ci 2 ‹ ‹ ˚ .. ‹
.. .. ‹¨˚ . ‹ “ ˝.‚
˚ ‹
. . ‚ ˝ .. ‚
˚
˝
` b`δ´2 ˘i1 0
α ¨ ¨ ¨ αpb`δ´2qiδ´1 ciδ´1
¨ ˛
1 ¨¨¨ 1
˚ α i1 ¨¨¨ αiδ´1 ‹ ` ˘
On a H1 “ ˚ .. ‹ diag αbi1 , ¨ ¨ ¨ , αbiδ´1
˚ ‹
..
˝ . . ‚
αpδ´2qi1 ¨ ¨ ¨ αpδ´2qiδ´1
Notons pour j P t1, ¨ ¨ ¨ , δ ´ 1u ρj “ αij
¨ ˛
1 ¨¨¨ 1
˚
˚ ρ1 ¨ ¨ ¨ ρδ´1 ‹‹
` b b
˘
On a H1 “ H2 ¨ diag ρ1 , ¨ ¨ ¨ , ρδ´1 où H2 “ ˚
˚ ρ21 ¨ ¨ ¨ ρ2δ´1 ‹
‹
˚ .. .. ‹
˝ . . ‚
ρδ´2
1 ¨ ¨ ¨ ρδ´2
δ´1
Or α est une racine primitive nième de l’unicité de 1 et 0 ď i1 ă i2 ¨ ¨ ¨ ă
iδ´1 ă n
Donc @j ‰ l P t1, ¨ ¨ ¨ , δ ´ 1u ρj ‰ ρl
Donc det pH2 q ‰ 0 (déterminant matrice de Vandermonde)
Donc det
¨ pH˛ 0 ˛
1q ‰ ¨
ci 1 0
˚ .. ‹ ˚ .. ‹
Donc ˝ . ‚ “ ˝ . ‚ donc c “ 0
ciδ´1 0
Exemple 4.3.
d“3
C p1q “ t1, 2, 4, 6u
donc
Mα “ Mα2 “ Mα4
et Mα3 “ X 4 ` X 3 ` X 2 ` X ` 1 (cf exemple précédent et CC1)
Donc
` ˘` ˘
g pXq “ X 4 ` X ` 1 X 4 ` X 3 ` X 2 ` X ` 1
“ X8 ` X7 ` X6 ` X5 ` X4 ` X5 ` X4
` X3 ` X2 ` X ` X4 ` X3 ` X2 ` X ` 1
“ X8 ` X7 ` X6 ` X4 ` 1
c P C ô g pxq |c pxq
` ˘
ô @i P t1, ¨ ¨ ¨ , 2tu , c αi “ 0
Soit c P C :
y pxq “ c pxq ` e pxq avec w peq “ r ď t.
r
ÿ
e pxq “ Yj xij , Yj P Fq , Yi ‰ 0 où 0 ď i1 ă ¨ ¨ ¨ ă ir ď n ´ 1.
j“1
On a @i P t1, ¨ ¨ ¨ , 2tu :
` i˘ ` ˘
Si “ lo α on `e αi
c omo
“0
r
ÿ
“ Yr Xki où Xk “ αik
k“1
But : déterminer r, Y1 , ¨ ¨ ¨ , Yr , X1 , ¨ ¨ ¨ , Xr
Sont connus : S1 , ¨ ¨ ¨ , S2t les syndromes.
Elle sont linéaires en les Yi mais polynomiales en les Xi .
On a 2t équations, et 2r ď 2t inconnues.
Définition 4.2.
On la réécrit :
$ r`1
’
’X1 ` s1 X1r ` ¨ ¨ ¨ ` sr X1 “ 0 pˆY1 q
&X r`1 ` s X r ` ¨ ¨ ¨ ` s X “ 0 pˆY q
’
2 1 2 r 2 2
’¨ ¨ ¨
’
’
% r`1
Xr ` s1 Xrr ` ¨ ¨ ¨ ` sr Xr “ 0 pˆYr q
En sommant :
Sr`1 ` S1 Sr ` ¨ ¨ ¨ sr S1 “ 0
r
ÿ
(On rappelle : Si “ Yj Xji )
j“1
On multiplie chaque ligne par X1 , ¨ ¨ ¨ , Xr :
$ r`1
’
’ X1 ` s1 X1r ` ¨ ¨ ¨ ` sr X1 “ 0 pˆY1 X1 q
&X r`1 ` s X r ` ¨ ¨ ¨ ` s X “ 0 pˆY X q
’
2 1 2 r 2 2 2
’
’
’ ¨¨¨
% r`1
Xr ` s1 Xrr ` ¨ ¨ ¨ ` sr Xr “ 0 pˆYr Xr q
Sr`2 ` s2 Sr`1 ` ¨ ¨ ¨ ` sr S2 “ 0
On re multiplie par X1 , ¨ ¨ ¨ , Xr :
$ r`1 ` ˘
’
’ X1 ` s1 X1r ` ¨ ¨ ¨ ` sr X1 “ 0 ˆY1 X12
&X r`1 ` s X r ` ¨ ¨ ¨ ` s X “ 0 `ˆY X 2 ˘
’
2 1 2 r 2 2 2
’¨ ¨ ¨
’
’
% r`1 ` ˘
Xr ` s1 Xrr ` ¨ ¨ ¨ ` sr Xr “ 0 ˆYr Xr2
@i, j P t1, ¨ ¨ ¨ , ru :
Sij “ Si`j´1
ÿr
“ Yk Xki`j´1
`k“1 ˘
“ V ¨ D ¨t V i,j
#
V “ Xij´1 1ďi,jďr
` ˘
où toutes deux inversibles
D “ diag pX1 Y1 , ¨ ¨ ¨ , Xr Yr q
Algorithme 4.3.
s1 ´S2r
6. σ Ð 1 ` s1 z ` ¨ ¨ ¨ ` sr z r
` ˘
7. Déterminer X1 , ¨ ¨ ¨ , Xr tels que σ Xi´1 “ 0
8. Déterminer 1 , ¨ ¨ ¨ , ir tels que Xj “ αij
9. $
Déterminer Y1 , ¨ ¨ ¨ , Yr solution de :
&S1 “ X1 Y1 ` ¨ ¨ ¨ ` Xr Yr
’
’
..
’ .
’
%S “ ¨ ¨ ¨
2t
r
ÿ
10. c Ð y ´ Yj xij
j“1
S1 “ α2 ` α6 “ α3
S2 “ α6
S3 “ α6 ` α13 “ α2
S4 “ α12
ˆ ˙ ˆ ˙
S1 S2 α3 α6
S“ “
S2 S3 α6 α2
det pyq “ α5 ` α12 ‰ 0 donc r “ 2.
On résout :
ˆ 3 ˙ˆ ˙ ˆ 2 ˙ ˆ 3 ˙ˆ ˙ ˆ 2 ˙
α α6 s2 α α α6 s2 α
6 2 “ 12 ô 11 “
α α s 1 α 0 α s 1 α14
$
&s1 “ α3
ô 2 9
%s2 “ α ` α “ α8
α3
On obtient le polynôme localisateur :
σ pzq “ 1 ` α3 z ` α8 z 2
` ˘
σ α0 “ 1 ` α3 ` α8 “ α6 ‰ 0
` ˘
σ α1 “ 1 ` α4 ` α10 ‰ 0
..
.
` 9˘
σ α “ 1 ` α12 ` α11 “ 0
..
.
` 13 ˘
σ α “ 1 ` α ` α4 “ 0
On a donc :
e pxq “ x15´9 ` x15´13 “ x6 ` x2
Propriétés 4.1.
— @l P t1, ¨ ¨ ¨ , ru
r
ź
` ˘ ` ˘
w Xl´1 “ Xl Yl 1 ´ Xj Xl´1
j“1,j‰l
Démonstration.
2t
ÿ
S pzq “ Si z i´1
i“1
˜ ¸
ÿ2t r
ÿ
“ Yj Xji z i´1
i“1 j“1
r
ÿ 2t
ÿ
“ Xj Yj pXj zqi´1
j“1 i“1
ÿr
“ Xj Yj par p˚q :
j“1
r
ÿ 1 “ 2t ‰
” Xj Yj z
j“1
1 ´ Xj z
« ff
2t
ÿ
pXj zqi´1 p1 ´ Xj zq ” 1 z 2t
“ ‰
p˚q
i“1
r
ÿ r
ź “ ‰
car S pzq “ Xj Yj p1 ´ Xi zq { pσ pzqq z 2t
j“1 i“1,i‰j
r
ÿ r
ź “ ‰
donc S pzq σ pzq “ Xj Yj p1 ´ Xi zq z 2t
j“1 i“1,i‰j
loooooooooooooomoooooooooooooon
wpzq
Théorème 4.3.
r0 “ z2t,r1 “ S pzq
u0 “ 1, u1 “ 00
v0 “ 0,v1 “ 0
Démonstration.
#
@i P t0, ¨ ¨ ¨ , ku
On a :
ri pzq “ z 2t ˆ ui pzq ` S pzq ˆ vi pzq
En particulier :
p1q S pzq ¨ vk pzq ` z 2t ¨ uk pzq “ rk pzq pˆσ pzqq
Or : “ ‰
S pzq σ pzq ” w pzq z 2t
donc, il existe u pzq tels que :
p2q S pzq ¨ σ pzq ` z 2t ¨ u pzq “ w pzq pˆvk pzqq
On en déduit de p1q et p2q :
z 2t pσ pzq uk pzq ´ vk pzq u pzqq “ lo
loooooooooooooooooomoooooooooooooooooon rokmoon loσomo
pzq vokmo
pzqon ´ lo pzq womo
on lo pzq
on
degě2t ou σpzquk pzq´vk pzqupzq“0 ăt ďt ? ăt
Or deg pvk pzqq “ deg pr0 pzqq ´ deg prk´1 pzqq “ 2t ´ loooooomoooooon
deg prk´1 pzqq ď t
ět
Donc :
deg prk pzq σ pzq ´ vk pzq w pzqq ă 1t
#
rk pzq σ pzq ´ vk pzq w pzq “ 0 p3q
Nécessairement, D’après p3q, σ pzq |vk pzq w pzq.
σ pzq uk pZq ´ vk pzq ¨ u pzq “ 0 p4q
Or σ pzq ^ w pzq “ 1.
Donc d’après le lemme de Gauss :
D’après p4q :
vk pzq |σ pzq uk pzq
Or uk pzq ^ vk pzq “ 1 donc vk pzq |σ pzq
Donc σ pzq et vk pzq sont doc égaux, à une constante multiplicative près. De
plus σ p0q “ 1 donc :
vk pzq
σ pzq “
vk p0q
D’après p3q : rk pzq {vk p0q “ w pzq
Algorithme 4.4.
Entrée : g, α, t, y
Sortie : m
ÿr
` i ˘ i´1
1. S Ð yomo
lo αon z
i“1
Si
2. Si S “ 0 alors c Ð y
3. r0 Ð z 2t , v0 Ð 0
r1 Ð S, v1 Ð 1
Tant que deg pr1 q ě t faire :
q Ð quotient pr0 , r1 q
r0 , r1 Ð r1 , r0 ´ q ¨ r1
v0 , v1 Ð v1 , v0 ´ qv1
v1 pzq
4. σ pzq Ð
v1 p0q
r1 pzq
w pzq Ð
v1 p0q
5. r Ð deg pσq
` ˘
6. Déterminer X1 , ¨ ¨ ¨ , Xr tels que σ Xj´1 “ 0
7. Déterminer i1 , ¨ ¨ ¨ , ir tels que Xj “ αij
` ˘
w Xl´1
8. Pour l “ 1, ¨ ¨ ¨ , r faire Yl Ð r
ś ` ˘
Xl 1 ´ Xl´1 Xj
j“1,j‰l
r
ÿ
9. c Ð y ´ Yj xij
j“1
Initialisation :
z4 “ z4 ˆ 1 ` S ˆ 0
S “ z4 ˆ 0 ` S ˆ 1
z4 “ z4 ˆ 1 ` S ˆ 0
S “ z4 ˆ 0 ` S ˆ 1
` ˘
α13 z 2 ` α8 z ` α11 “ z 4 ˆ 1 ` S ˆ α3 z ` α8
On a :
` ˘` ˘
α3 z ` α8 “ α13 z 2 ` α8 z ` α11 α14 z ` α14 ` α12
z4 “ z4 ˆ 1 ` S ˆ 0
S “ z4 ˆ 0 ` S ˆ 1
` ˘
α13 z 2 ` α8 z ` α11 “ z 4 ˆ 1 ` S ˆ α3 z ` α8
` ` ˘` ˘˘
α12 “ z 4 ˆ? ` S ˆ 1 ` α14 z ` α14 α3 z ` α8
On obtient,
` à un˘ coefficient multiplicatif près σ pzq :
α2 z 2 ` α2 ` α7 z ` α7 ` 1 “ α2 z 2 ` α12 z ` α9
σ pzq “ 1 ` α3 z ` α8 z 2
Comme précédemment, on a :
` ˘ ` ˘
σ α13 “ σ α9 “ 0
D’où e pxq “ x2 ` x6
Codes de Goppa
I Rappels
Soit C un code BCH strict binaire de longueur n, de distance prescrite δ
et associé à α racines primitives n-ièmes de 1 dans F2m .
Généralisation
CBCH définie sur Fq de longueur n, valant CRS X Fnq se généralise en les
codes de Goppa :
Ce sont CGoppa sur Fq vaudront CGRS X Fnq .
que valent leur localisateurs ? Leur multiplicateurs ?
77
CHAPITRE 5. CODES DE GOPPA
II Définition
Soit C un code BCH strict sur Fq de longueur n, de distance prescrite
2t ` 1, associé à α racine primitive n-ième de 1 dans Fqm .
Soit c P Fnq .
` ˘
c P C ô @i P J1, 2tK, c αi “ 0
2t´1
ÿ ` ˘
ô c αi`1 z i “ 0
i“0
looooooomooooooon
PFqm rzs
n´1
ÿ ` ˘ “ ‰
ô c αi`1 z i ” 0 z 2t
i“0
n´1
ÿ n´1
ÿ ` ˘j “ ‰
ô cj αi`1 z i ” 0 z 2t
i“0 j“0
˜ ¸
n´1 n´1
i`1 j
ÿ ÿ ` ˘ “ ‰
ô cj α z i ” 0 z 2t
j“0 j“0
looooooooomooooooooon
p˚q
p˚q :
˜ ¸
n´1 n´1
i`1 j
ÿ ` ˘ ÿ ` ˘p´i´1q
α zi “ α´j zi
j“0 i“0
n´1
ÿ ` ˘n´1´i
“ α´j z6i
i“0
n n
z ´ pα´j q zn ´ 1
“ “
z ´ α´j z ´ α´j
n´1
zn ´ 1
ÿ “ 2t ‰
cPCô ci ” 0 z
i“0
z ´ α´j
1
Notons l’inverse de z ´ α´j modulo z 2t .
z ´ α´j
On a :
n´1
ÿ 1 “ 2t ‰
c P C ô pz n ´ 1q ci ” 0 z
i“0
z ´ αi
n´1
ÿ 1 “ ‰
ô ci ” 0 z 2t
i“0
z´α ´i
Mise en garde ! ! ! : dans cette définition g pzq n’a rien à voir avec
un polynôme générateurs, c’est juste une notation
Définition 5.1.
1
où est l’inverse de z ´ γi modulo g pzq
z ´ γi
III Propriétés
Déterminons une matrice de contrôle (à coefficients dans Fqm ) de Γ pL, gq.
Soit c P Fm
q .
n´1
ÿ 1
c P Γ pL, gq ô cj ” 0 rg pzqs
j“0
z ´ γj
g pzq ´ g pγj q
@j P J0, n ´ 1K, g pzq “ pz ´ γj q ` g pγj q or g pγj q ‰ 0.
ˆ z˙´ γj
g pzq ´ g pγj q ´1
Donc pz ´ γj q ” 1 rg pzqs
z ´ γj g pγj q
looooooooooooomooooooooooooon
inverse de pz´γj q mod gpzq
n´1 ˆ ˙
g pzq ´ g pγj q
ÿ ´1
c P Γ pL, gq ô cj ” 0 rg pzqs
j“0
z ´ γj f pγj q
$
1
&hj “
’
’
g pγj q
’
Notons : ÿr
%g pzq “ gk z k
’
’
’
k“0
On a :
r
g pzq ´ g pγj q ÿ z k ´ γjk
“ gk
z ´ γj k“0
z ´ γj
r
ÿ k´1
ÿ
“ gk pγj qk´1´i z i
k“0 i“0
Donc
˜ ¸
n´1
ÿ r
ÿ k´1
ÿ
c P Γ pL, gq ô cj gk pγj qk´1´i z i hj ” 0 rg pzqs
j“0 k“0 i“0
g1 ¨ ¨ ¨ ¨ ¨ ¨ gr´1 gr
looooooooooomooooooooooon
D
loooooooooooooooomoooooooooooooooon V matrice de Vandermone
matrice inversible car gr ‰0
¨ ˛
c0
˚ .. ‹
ô V ¨ D ˝ . ‚“ 0
cn´1
Théorème 5.1.
Démonstration.
1. La distance ě r ` 1 ?
supposons que Γ pL, gq possède un mot c non nul de poids ď r.
` ˘
avec 1, α, α2 base de F8 sur F2 .
On déduit de H une matrice de contrôle H̃ :
¨ ˛
1 1 1 1 1 0 0 1 1
α ˚0 1 0 1
˚ 0 0 0 0‹‹
α2 ˚˚0 1 1 1 1 1 1 0‹‹
1 ˚˚0 1 0 0 1 0 1 0‹‹
α ˝1 0 0 0 0 1 0 0‚
α2 0 0 1 1 0 0 1 0
Démonstration. ` ˘
On va montrer`que Γ˘ pL, gq “ Γ L, g 2
— On a Γ L, g 2 Ă Γ pL, gq car @c P Fn2 :
n´1 n´1
ÿ 1 “ 2
‰ ÿ 1
ci ” 0 g pzq ñ ci ” 0 rg pzqs
i“0
z ´ γi i“0
z ´ γi
En effet, g|g 2 .
n´1
ÿ 1
— Soit c P Γ pL, gq, ci” 0 rg pzqs
i“0
z ´ γi
n´1
ź
Considérons le polynôme f pzq “ pz ´ γi qdi P F2m rzs où di “
i“0
#
0 si ci “ 0
à noter que di “ 0, 1 P N et ci “ 0, 1 P F2 !
1 si ci “ 1
n´1
f 1 pzq ÿ ci
“
f pzq i“0
z ´ γi
f 1 pzq
Donc ” 0 rg pzqs donc f 1 pzq ” 0 rg pzqs
f pzq
ÿs
Notons f pzq “ fi z i
i“0
s
ÿ ÿ
f 1 pzq “ fi iz i´1 “ fi z i´1
i“0 i“0,iimpair
ÿ
“ f2j`1 z 2j
j,2j`1ďs
2 m
De plus f2j`1 P F2m donc f2j`1 “ f2j`1
ÿ m
2
Donc f 1 pzq “ f2j`1 z 2j .
j
˜ ¸2
ÿ ´ m´1 ¯2 ÿ
2 2m´1
f 1 pzq “ f2j`1 zj “ f2j`1 z j
j j
f 1 pzq est le carré d’un polynôme de g pzq |f 1 pzq, g pzq est donc sans
facteur carré.
f 1 pzq
donc g pzq2 divise f 1 pzq donc ” 0 g pzq2 donc c P Γ L, g 2 .
“ ‰ ` ˘
` 2
˘ f pzq
Conclusion : Γ pL, gq “ Γ L, g . ` ˘
2
` 2 ˘ précédemment, la distance minimale de Γ L, g est
D’après le théorème
ě 2r ` 1 “ deg g ` 1 donc la distance de Γ pL, gq est ě 2r ` 1.
IV Décodage
Théorème 5.3.
86
CHAPITRE 6. CRYPTOSYSTÈME DE MAC ELIECE
Définition 6.1.
“ pmSGq
loomoon ` e ¨ P ´1
loomoon
mot du code C erreur de poids ďt
car G1 “ SGP
Bob utilise l’algorithme de décodage associé à C pour retrouver pmSq G
pour x “ mS il en déduit m “ x ¨ S ´1 .` ˘
Complexité du déchiffrement : O n2 avec algorithme de déco-
dage en temps quadratique.
4. Sécurité
La sécurité du cryptosystème est basé sur le problème du décodage
par syndrome :
Soit H une matrice pn ´ kq ˆ n de rang n sur Fq , soit S dans Fn´kq ,
déterminer e tel que H ¨t e “ S avec w peq ď t.
Exemple 6.2 (q “ 2, n “ 1024, t “ 50).
50
C1024 „ 3 ˆ 1085 possibilité
Attaques :
— Stern
— Contour et Zijlstra : Projet tutoré (à venir) pISDq : Information
Set Decoding.
I Exemples
Bob construit le code de Goppa binaire C “ Γ pL, gq (où g pzq “ z et L le
corps fini privé de 0 : F23 z t0u “ α, α2 , α3 , α4 , α5 , α6 , α7 où α3 ` α ` 1 “ 0
1 0 1 0 1 0 1
e “ p0, 1, 0, 0, 0, 0, 0q
“ p0, 1, 0, 0, 1, 0, 1q ` p0, 1, 0, 0, 0, 0, 0, 0q
“ p0, 0, 0, 0, 1, 0, 1q
y “ c ¨ P ´1 “ p0, 0, 1, 0, 1, 0, 0q
1 1
“ ` mod z 2
z ´ α3 ˆz ´˙α2 ˆ ˙ˆ ˙
z 2 ´ α6 ´1 z 2 ´ α10 ´1
“ ` mod z 2
z ´ α3 α6 z ´ α5 α10
` ˘ ` ˘
“ z ` α3 ¨ α ` z ` α5 α4
“ α ` α2 z
` ˘
Polynôme localisateur d’erreur : z ` α6
Le mot de code associé à y est donc :
y ` p0, 0, 0, 0, 0, 1, 0q “ p0, 0, 1, 0, 1, 1, 0q
On a donc :
mSG “ p0, 0, 1, 0, 1, 1, 0q
mS “ p0, 0, 1, 0q
¨ ˛
0 1 1 0
˚1 1 0 0‹
m “ p0, 0, 1, 0q ˚
˝1 0
‹ “ p1, 0, 1, 1q
1 1‚
1 1 1 0
Attaque :
Si on dispose de c “ p0, 0, 0, 0, 1, 0, 1q “ pmG1 ` eq avec w peq ď 1 et
¨ ˛
0 1 1 0 0 1 1
˚1 0 1 1 0 1 0‹
G1 “ ˚ ˝1 0 0 0 0 1 1‚
‹
1 0 1 0 1 0 1
¨ ˛
0 1 1 1 1 0 0 ˆ ˙
1 1 t 1
En fait on trouve H “ 1 0 1
˝ 1 0 1 0‚ et on trouve H ¨ c “
0 1
1 1 0 1 0 0 1
Donc e “ p0, 1, 0, 0, 0, 0, 0q Une fois qu’on a H 1 , on calcule : H 1 ˆt c “
H 1 ˆt pmG1 q `
loooooomoooooon H 1 ˆt e
loomoon
0 0 où e“0, ou colonne de H1
On a donc l’équation :
mG1 “ p0, 1, 0, 0, 1, 0, 1q
¨ ˛ ¨ ˛
0 1 1 1 0
˚1 0 0 0‹ ¨ ˛ ˚1‹
˚1 1 0 1‹ m1
˚ ‹ ˚ ‹
‹ ˚m2 ‹ ˚0‹
˚ ‹
˚
ô˚ ˚0 1 0 0‹ ˝m3 ‚ “ ˚0‹
‹˚ ‹ ˚ ‹
˚0 0 0 1‹ ˚1‹
˚ ‹ m4 ˚ ‹
˝1 1 1 0‚ ˝0‚
1 0 1 1 1
¨ ˛
1 0 0 0 ¨ ˛
˚0 1 0 0‹ ¨ ˛ 1
˚ ‹ m1 ˚0‹
˚0 1 1 1‹ ˚ ‹ ˚ ‹
˚ ‹ m2 ‹ ˚0‹
ô ˚0 0 0 1‹ ˚ “˚ ‹
˚ ‹ ˝m3 ‚ ˚1‹
˚˚ ˚ ˚ ˚‹
‚ m4
˝ ‚
˝ ..
.. .. .. .. .
. . . .
¨ ˛¨ ˛ ¨ ˛
1 0 0 0 m1 1
˚0 1 0 0‹ ˚m2 ‹ ˚0‹
ô˚ ˝0 0 1 0‚˝m3 ‚ “ ˝1‚
‹˚ ‹ ˚ ‹
0 0 0 1 m4 1