6.7 Appendice : le produit scalaire et les corps finis
203
m = 8, le nombre k de lettres est born´ e par 2
m
− 2 = 254. Supposons maintenant que
le canal de transmission soit assez fiable et qu’il soit pratiquement toujours suffisant
de pouvoir corriger deux lettres. Puisque le nombre d’erreurs corrigibles s est ´ egal `
a
[
1
2 (2
m
− k − 1)], il faut donc que (2
m
− k − 1) soit sup´ erieur ou ´ egal `
a 2s = 4. Nous
pouvons donc transmettre le texte par blocs de k = 2
8
− 4 − 1 = 251 lettres. Notons
qu’il pourrait y avoir plus d’un bit erron´ e au sein de chaque lettre transmise. Le code
de Reed–Solomon corrige les lettres (et non les bits individuels).
La technologie du disque compact ne transmet pas des caract` eres latins, mais bien
sˆ ur un signal musical num´ eris´ e. Elle utilise malgr´ e tout le code de Reed–Solomon avec
les param` etres que nous venons d’´ etudier, soit m = 8 et un maximum de deux erreurs.
Notons enfin qu’il existe des algorithmes efficaces de d´ ecodage qui ´ evitent la solution
de
2
m −1
k
syst` emes lin´ eaires de k ´ equations en k inconnues [2, 8]. Ces algorithmes
acc´ el` erent consid´ erablement le d´ ecodage.
6.7 Appendice : le produit scalaire et les corps finis
Il est fort probable que votre cours d’alg` ebre lin´ eaire ait d´ efini le produit scalaire
sur un espace vectoriel V sur le corps R comme une fonction not´ ee (·, ·) qui associe ` a
une paire d’´ el´ ements de V un nombre r´ eel et telle que
(i) (x, y) = (y, x), pour tout x, y ∈ V ;
(ii) (x + y, z) = (x, z) + (y, z) pour tout x, y, z ∈ V ;
(iii) (cx, y) = c(x, y) pour tout x, y ∈ V et c ∈ R ;
(iv) (x, x) ≥ 0 et (x, x) = 0 seulement pour x = 0.
Si le corps R des nombres r´ eels est remplac´ e par un corps fini, cette d´ efinition est
conserv´ ee ` a l’exception de la derni` ere exigence qui devient
(iv) fini si (x, y) = 0 pour tout y ∈ V , alors x = 0.
C’est donc avec cette modification que le produit scalaire est utilis´ e dans le pr´ esent
chapitre. Notons que la condition (iv) originale n’a pas de sens dans un corps fini, car
il n’y a pas de relation d’ordre (« < ») pr´ eserv´ ee par l’addition. Par exemple, dans F 2 ,
nous pourrions proposer que 0 < 1. Cependant, cette in´ egalit´ e ne peut ˆ etre r´ econcili´ ee
avec l’affirmation usuelle dans les r´ eels qui dit que, si a < b, alors a + c < b + c pour
tout nombre c. En effet, si le nombre 1 ∈ F 2 est ajout´ e aux deux membres de 0 < 1,
nous obtenons 0 + 1 < 1 + 1, c’est-` a-dire 1 < 0, ce qui contredit clairement 0 < 1 !
La d´ efinition de compl´ ement orthogonal demeure la mˆ eme pour le produit scalaire
avec (iv) fini . Nous la rappelons.
D´ efinition 6.23 Si W ⊂ V est un sous-ensemble de V , alors le compl´ ement orthogonal
W
⊥ est d´ efini par W
⊥ = {v ∈ V |(v, w) = 0 pour tout w ∈ W }.
203
m = 8, le nombre k de lettres est born´ e par 2
m
− 2 = 254. Supposons maintenant que
le canal de transmission soit assez fiable et qu’il soit pratiquement toujours suffisant
de pouvoir corriger deux lettres. Puisque le nombre d’erreurs corrigibles s est ´ egal `
a
[
1
2 (2
m
− k − 1)], il faut donc que (2
m
− k − 1) soit sup´ erieur ou ´ egal `
a 2s = 4. Nous
pouvons donc transmettre le texte par blocs de k = 2
8
− 4 − 1 = 251 lettres. Notons
qu’il pourrait y avoir plus d’un bit erron´ e au sein de chaque lettre transmise. Le code
de Reed–Solomon corrige les lettres (et non les bits individuels).
La technologie du disque compact ne transmet pas des caract` eres latins, mais bien
sˆ ur un signal musical num´ eris´ e. Elle utilise malgr´ e tout le code de Reed–Solomon avec
les param` etres que nous venons d’´ etudier, soit m = 8 et un maximum de deux erreurs.
Notons enfin qu’il existe des algorithmes efficaces de d´ ecodage qui ´ evitent la solution
de
2
m −1
k
syst` emes lin´ eaires de k ´ equations en k inconnues [2, 8]. Ces algorithmes
acc´ el` erent consid´ erablement le d´ ecodage.
6.7 Appendice : le produit scalaire et les corps finis
Il est fort probable que votre cours d’alg` ebre lin´ eaire ait d´ efini le produit scalaire
sur un espace vectoriel V sur le corps R comme une fonction not´ ee (·, ·) qui associe ` a
une paire d’´ el´ ements de V un nombre r´ eel et telle que
(i) (x, y) = (y, x), pour tout x, y ∈ V ;
(ii) (x + y, z) = (x, z) + (y, z) pour tout x, y, z ∈ V ;
(iii) (cx, y) = c(x, y) pour tout x, y ∈ V et c ∈ R ;
(iv) (x, x) ≥ 0 et (x, x) = 0 seulement pour x = 0.
Si le corps R des nombres r´ eels est remplac´ e par un corps fini, cette d´ efinition est
conserv´ ee ` a l’exception de la derni` ere exigence qui devient
(iv) fini si (x, y) = 0 pour tout y ∈ V , alors x = 0.
C’est donc avec cette modification que le produit scalaire est utilis´ e dans le pr´ esent
chapitre. Notons que la condition (iv) originale n’a pas de sens dans un corps fini, car
il n’y a pas de relation d’ordre (« < ») pr´ eserv´ ee par l’addition. Par exemple, dans F 2 ,
nous pourrions proposer que 0 < 1. Cependant, cette in´ egalit´ e ne peut ˆ etre r´ econcili´ ee
avec l’affirmation usuelle dans les r´ eels qui dit que, si a < b, alors a + c < b + c pour
tout nombre c. En effet, si le nombre 1 ∈ F 2 est ajout´ e aux deux membres de 0 < 1,
nous obtenons 0 + 1 < 1 + 1, c’est-` a-dire 1 < 0, ce qui contredit clairement 0 < 1 !
La d´ efinition de compl´ ement orthogonal demeure la mˆ eme pour le produit scalaire
avec (iv) fini . Nous la rappelons.
D´ efinition 6.23 Si W ⊂ V est un sous-ensemble de V , alors le compl´ ement orthogonal
W
⊥ est d´ efini par W
⊥ = {v ∈ V |(v, w) = 0 pour tout w ∈ W }.