Travaux pratiques
L’algèbre fournit des codes très utiles. Un code linéaire sur F q , de dimension
k et longueur n, est un sous-espace C de dimension k de F n
q . Le choix d’une base
définit une application d’encodage E : F k
q → F n
q dont l’image est C.
Afin de transmettre un message, on commence par l’identifier à un élément de
F k
q . Si l’on prend, par exemple, q = 2 et k = 64, et si l’on désire transmettre un
message rédigé en ASCII (1) , alors chaque lettre ASCII peut être identifiée à un
octet et un bloc de 8 lettres à un « mot » de F 64
2 .
Pour chaque mot a = (a 1 , . . . , a 64 ) ∈ F n
q , on note
w(a) = Card({i, a i = 0})
son poids de Hamming. La distance minimale du code est, par définition,
d(C) = min(w(a), a ∈ C \{0}). Comme C est un espace vectoriel, w(a−b) d(C)
pour deux mots distincts a et b du code. Le lecteur vérifiera facilement que
d(a, b) = w(a − b) définit une véritable distance sur les mots de F n
q , au sens
des espaces métriques. Par exemple, le code de répétition pure C = {(a, a, a) ∈
F 192
2 , a ∈ F 64
2 } possède une distance minimale d(C) = 3.
Un mot reçu m est décodé en c ∈ C tel que w(c−m ) soit minimal. Comme les
probabilités vont dans ce sens, on parle de décodage selon le principe du maximum
de vraisemblance. On voit facilement que le message est décodé correctement si
le nombre t d’erreurs commises vérifie d(c) 2t + 1. On dit que le code est tcorrecteur, où t désigne la partie entière de (d(C) − 1)/2 : le code peut corriger t
erreurs.
Expliquons maintenant le fonctionnement des codes BCH(q, n, δ), qui constituent une classe populaire de codes introduite par Bose, Ray-Chaudhuri et
Hocquenghem.
Définition 2. Soit β une racine primitive n-ième de l’unité dans F q , pour n
un entier premier avec q et g le ppcm (unitaire) des polynômes minimaux de
β, . . . , β δ−1 . L’espace vectoriel
C =
0i
i ¯
g · F q ⊂ F q [x]/(x
n
− 1) = A F
n
q ,
où ¯
g ∈ A désigne la classe de g modulo x n − 1, est appelé code BCH et noté
BCH(q, n, δ). Il est de longueur n et dimension k = n − deg g. On dit que g
est son polynôme générateur, car C est l’idéal de A engendré par g.
(1) La norme American Standard Code for Information Interchange est la norme de codage de
caractères la plus connue en informatique.
393
L’algèbre fournit des codes très utiles. Un code linéaire sur F q , de dimension
k et longueur n, est un sous-espace C de dimension k de F n
q . Le choix d’une base
définit une application d’encodage E : F k
q → F n
q dont l’image est C.
Afin de transmettre un message, on commence par l’identifier à un élément de
F k
q . Si l’on prend, par exemple, q = 2 et k = 64, et si l’on désire transmettre un
message rédigé en ASCII (1) , alors chaque lettre ASCII peut être identifiée à un
octet et un bloc de 8 lettres à un « mot » de F 64
2 .
Pour chaque mot a = (a 1 , . . . , a 64 ) ∈ F n
q , on note
w(a) = Card({i, a i = 0})
son poids de Hamming. La distance minimale du code est, par définition,
d(C) = min(w(a), a ∈ C \{0}). Comme C est un espace vectoriel, w(a−b) d(C)
pour deux mots distincts a et b du code. Le lecteur vérifiera facilement que
d(a, b) = w(a − b) définit une véritable distance sur les mots de F n
q , au sens
des espaces métriques. Par exemple, le code de répétition pure C = {(a, a, a) ∈
F 192
2 , a ∈ F 64
2 } possède une distance minimale d(C) = 3.
Un mot reçu m est décodé en c ∈ C tel que w(c−m ) soit minimal. Comme les
probabilités vont dans ce sens, on parle de décodage selon le principe du maximum
de vraisemblance. On voit facilement que le message est décodé correctement si
le nombre t d’erreurs commises vérifie d(c) 2t + 1. On dit que le code est tcorrecteur, où t désigne la partie entière de (d(C) − 1)/2 : le code peut corriger t
erreurs.
Expliquons maintenant le fonctionnement des codes BCH(q, n, δ), qui constituent une classe populaire de codes introduite par Bose, Ray-Chaudhuri et
Hocquenghem.
Définition 2. Soit β une racine primitive n-ième de l’unité dans F q , pour n
un entier premier avec q et g le ppcm (unitaire) des polynômes minimaux de
β, . . . , β δ−1 . L’espace vectoriel
C =
0i
i ¯
g · F q ⊂ F q [x]/(x
n
− 1) = A F
n
q ,
où ¯
g ∈ A désigne la classe de g modulo x n − 1, est appelé code BCH et noté
BCH(q, n, δ). Il est de longueur n et dimension k = n − deg g. On dit que g
est son polynôme générateur, car C est l’idéal de A engendré par g.
(1) La norme American Standard Code for Information Interchange est la norme de codage de
caractères la plus connue en informatique.
393