Algèbre T1
Précisons l’isomorphisme F n
q A : on identifiera un mot a = (a 1 , . . . , a n )
du code avec le polynôme a(x) =
n
i=1 a i x i−1 (plus exactement sa classe). Faisant de même avec F k
q , l’application d’encodage n’est donc rien d’autre que la
multiplication par g.
Remarque. Les mots du code BCH(q, n, δ) sont invariants par permutation circulaire : si (a 1 , . . . , a n ) ∈ C, alors (a n , a 1 , . . . , a n−1 ) ∈ C. En effet, cette opération
correspond à la multiplication par x dans A. On parle de code linéaire cyclique.
Ces codes correspondent aux idéaux de A (qui sont tous principaux, mais A n’est
pas principal puisqu’il n’est pas intègre).
La définition précédente ne reflète pas le fait qu’un code BCH(q, n, δ) dépend
du choix de β. Cependant, les propriétés du code sont essentiellement indépendantes de β, et en particulier la distance minimale.
Théorème 1. La distance minimale de C = BCH(q, n, δ) vérifie d(C) δ. On
pourra donc corriger au moins E((δ − 1)/2) erreurs.
Démonstration. Un élément a(x) appartient au code si et seulement si a(β i ) = 0
pour 1 i < δ, ou encore si et seulement si
⎛
⎜
⎜
⎜
⎝
1 β . . .
β n−1
1 β 2 . . . β 2(n−1)
. . .
. . .
. . .
1 β δ−1 . . . β (δ−1)(n−1)
⎞
⎟
⎟
⎟
⎠
⎛
⎜
⎜
⎜
⎝
a 1
a 2
. . .
a n
⎞
⎟
⎟
⎟
⎠
= 0.
Parce que tous les déterminants de taille δ − 1 extraits de la matrice ci-dessus
sont, à une constante non nulle près, des déterminants de Vandermonde dont
les coefficients parmi les β i sont deux à deux distincts, on voit que ce système
d’équations n’admet pas de solution a = 0 tel que w(a) δ − 1. Tout élément
non nul de C vérifie donc w(a) δ.
On a vu que les racines primitives n-ièmes de l’unité sont les racines dans F q
de Φ n . L’extension cyclotomique engendrée est de degré r = m lorsque n = q m − 1
et alors, F q (β) ∗ = {1, β, . . . , β n−1 }. On parle de code BCH primitif. Dans le cas
général, si l’on pose m = [F q (β) : F q ], on sait juste que l’ordre n de β divise le
cardinal q m − 1 de F q (β) ∗ .
7. Écrire deux procédures Pol:=proc(M,n) et Mot:=proc(P,n) permettant de
passer d’un mot M = (M 1 , . . . , M n ) de F n
q , au polynôme P = M (x) =
n
i=1 M i x i−1 et réciproquement.
Générer un code BCH(2, 2 5 − 1, 7) à l’aide de la procédure Generateur déjà
écrite. On obtient un polynôme de degré 15 sur F 2 .
394
Précisons l’isomorphisme F n
q A : on identifiera un mot a = (a 1 , . . . , a n )
du code avec le polynôme a(x) =
n
i=1 a i x i−1 (plus exactement sa classe). Faisant de même avec F k
q , l’application d’encodage n’est donc rien d’autre que la
multiplication par g.
Remarque. Les mots du code BCH(q, n, δ) sont invariants par permutation circulaire : si (a 1 , . . . , a n ) ∈ C, alors (a n , a 1 , . . . , a n−1 ) ∈ C. En effet, cette opération
correspond à la multiplication par x dans A. On parle de code linéaire cyclique.
Ces codes correspondent aux idéaux de A (qui sont tous principaux, mais A n’est
pas principal puisqu’il n’est pas intègre).
La définition précédente ne reflète pas le fait qu’un code BCH(q, n, δ) dépend
du choix de β. Cependant, les propriétés du code sont essentiellement indépendantes de β, et en particulier la distance minimale.
Théorème 1. La distance minimale de C = BCH(q, n, δ) vérifie d(C) δ. On
pourra donc corriger au moins E((δ − 1)/2) erreurs.
Démonstration. Un élément a(x) appartient au code si et seulement si a(β i ) = 0
pour 1 i < δ, ou encore si et seulement si
⎛
⎜
⎜
⎜
⎝
1 β . . .
β n−1
1 β 2 . . . β 2(n−1)
. . .
. . .
. . .
1 β δ−1 . . . β (δ−1)(n−1)
⎞
⎟
⎟
⎟
⎠
⎛
⎜
⎜
⎜
⎝
a 1
a 2
. . .
a n
⎞
⎟
⎟
⎟
⎠
= 0.
Parce que tous les déterminants de taille δ − 1 extraits de la matrice ci-dessus
sont, à une constante non nulle près, des déterminants de Vandermonde dont
les coefficients parmi les β i sont deux à deux distincts, on voit que ce système
d’équations n’admet pas de solution a = 0 tel que w(a) δ − 1. Tout élément
non nul de C vérifie donc w(a) δ.
On a vu que les racines primitives n-ièmes de l’unité sont les racines dans F q
de Φ n . L’extension cyclotomique engendrée est de degré r = m lorsque n = q m − 1
et alors, F q (β) ∗ = {1, β, . . . , β n−1 }. On parle de code BCH primitif. Dans le cas
général, si l’on pose m = [F q (β) : F q ], on sait juste que l’ordre n de β divise le
cardinal q m − 1 de F q (β) ∗ .
7. Écrire deux procédures Pol:=proc(M,n) et Mot:=proc(P,n) permettant de
passer d’un mot M = (M 1 , . . . , M n ) de F n
q , au polynôme P = M (x) =
n
i=1 M i x i−1 et réciproquement.
Générer un code BCH(2, 2 5 − 1, 7) à l’aide de la procédure Generateur déjà
écrite. On obtient un polynôme de degré 15 sur F 2 .
394