Grâce à notre connaissance des anneaux de polynômes et des corps finis, il est maintenant possible de dériver des codes plus sophistiqués que ceux du
Chapitre 8. Rappelons d’abord qu’un code en blocs
\((n, k)\) consiste en une fonction d’encodage injective
\(E:{\mathbb Z}^{k}_{2} \rightarrow {\mathbb Z}^{n}_{2}\) et une fonction de décodage
\(D:{\mathbb Z}^{n}_{2} \rightarrow {\mathbb Z}^{k}_{2}\text{.}\) Le code est correcteur d’erreurs si
\(D\) est surjective. Un code est un code linéaire s’il est le noyau d’une matrice
\(H \in {\mathbb M}_{k \times n}({\mathbb Z}_2)\text{.}\)
Nous nous intéressons à une classe de codes appelés
codes cycliques. Soit
\(\phi : {\mathbb Z}_2^k \rightarrow {\mathbb Z}_2^n\) un code en blocs binaire
\((n,k)\text{.}\) Alors
\(\phi\) est un
code cyclique si pour tout mot de code
\((a_1, a_2, \ldots, a_n )\text{,}\) le
\(n\)-uplet cycliquement décalé
\((a_n, a_1, a_2, \ldots,
a_{n - 1} )\) est aussi un mot de code. Les codes cycliques sont particulièrement faciles à implémenter sur un ordinateur à l’aide de registres à décalage [2, 3].
Exemple 22.2.1.
Considérons les codes linéaires \((6,3)\) engendrés par les deux matrices
\begin{equation*}
G_1
=
\begin{pmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1 \\
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1
\end{pmatrix}
\quad
\text{et}
\quad
G_2 =
\begin{pmatrix}
1 & 0 & 0 \\
1 & 1 & 0 \\
1 & 1 & 1 \\
1 & 1 & 1 \\
0 & 1 & 1 \\
0 & 0 & 1
\end{pmatrix}\text{.}
\end{equation*}
Les messages dans le premier code sont encodés comme suit :
\begin{equation*}
\begin{array}{rclccrcl}
(000) & \mapsto & (000000) & & & (100) & \mapsto & (100100) \\
(001) & \mapsto & (001001) & & & (101) & \mapsto & (101101) \\
(010) & \mapsto & (010010) & & & (110) & \mapsto & (110110) \\
(011) & \mapsto & (011011) & & & (111) & \mapsto & (111111).
\end{array}
\end{equation*}
Il est facile de voir que les mots de code forment un code cyclique. Dans le second code, les 3-uplets sont encodés de la manière suivante :
\begin{equation*}
\begin{array}{rclccrcl}
(000) & \mapsto & (000000) & & & (100) & \mapsto & (111100) \\
(001) & \mapsto & (001111) & & & (101) & \mapsto & (110011) \\
(010) & \mapsto & (011110) & & & (110) & \mapsto & (100010) \\
(011) & \mapsto & (010001) & & & (111) & \mapsto & (101101).
\end{array}
\end{equation*}
Ce code ne peut pas être cyclique, puisque \((101101)\) est un mot de code mais \((011011)\) ne l’est pas.
Sous-section 22.2.1 Codes polynomiaux
Nous souhaitons trouver une méthode simple pour obtenir des codes linéaires cycliques. Pour ce faire, nous pouvons utiliser notre connaissance des corps finis et des anneaux de polynômes sur \({\mathbb Z}_2\text{.}\) Tout \(n\)-uplet binaire peut être interprété comme un polynôme dans \({\mathbb Z}_2[x]\text{.}\) Autrement dit, le \(n\)-uplet \((a_0, a_1, \ldots,
a_{n - 1} )\) correspond au polynôme
\begin{equation*}
f(x) = a_0 + a_1 x + \cdots + a_{n-1} x^{n - 1}\text{,}
\end{equation*}
où le degré de \(f(x)\) est au plus \(n - 1\text{.}\) Par exemple, le polynôme correspondant au \(5\)-uplet \((10011)\) est
\begin{equation*}
1 + 0 x + 0 x^2 + 1 x^3 + 1 x^4 = 1 + x^3 + x^4\text{.}
\end{equation*}
Réciproquement, à tout polynôme \(f(x) \in {\mathbb Z}_2[x]\) avec \(\deg f(x) \lt n\) on peut associer un \(n\)-uplet binaire. Le polynôme \(x + x^2 + x^4\) correspond au \(5\)-uplet \((01101)\text{.}\)
Fixons un polynôme non constant
\(g(x)\) dans
\({\mathbb Z}_2[x]\) de degré
\(n - k\text{.}\) Nous pouvons définir un code
\((n,k)\) \(C\) de la manière suivante. Si
\((a_0, \ldots, a_{k - 1})\) est un
\(k\)-uplet à encoder, alors
\(f(x) = a_0 + a_1 x + \cdots + a_{k - 1} x^{k - 1}\) est le polynôme correspondant dans
\({\mathbb Z}_2[x]\text{.}\) Pour encoder
\(f(x)\text{,}\) on le multiplie par
\(g(x)\text{.}\) Les mots de code dans
\(C\) sont tous les polynômes de
\({\mathbb Z}_2[x]\) de degré inférieur à
\(n\) qui sont divisibles par
\(g(x)\text{.}\) Les codes ainsi obtenus sont appelés
codes polynomiaux.
Exemple 22.2.2.
Si l’on pose
\(g(x)= 1 + x^3\text{,}\) on peut définir un code
\((6,3)\) \(C\) comme suit. Pour encoder un
\(3\)-uplet
\(( a_0, a_1, a_2 )\text{,}\) on multiplie le polynôme correspondant
\(f(x) = a_0 + a_1 x + a_2 x^2\) par
\(1 + x^3\text{.}\) Nous définissons une application
\(\phi : {\mathbb Z}_2^3 \rightarrow {\mathbb Z}_2^6\) par
\(\phi : f(x) \mapsto g(x) f(x)\text{.}\) Il est facile de vérifier que cette application est un homomorphisme de groupes. En fait, si l’on considère
\({\mathbb Z}_2^n\) comme espace vectoriel sur
\({\mathbb Z}_2\text{,}\) \(\phi\) est une transformation linéaire d’espaces vectoriels (voir
Exercice 20.5.15,
Chapitre 20). Calculons le noyau de
\(\phi\text{.}\) Observons que
\(\phi ( a_0, a_1, a_2 ) = (000000)\) exactement quand
\begin{align*}
0 + 0x + 0x^2 + 0x^3 + 0x^4 + 0 x^5 & = (1 + x^3) ( a_0 + a_1 x + a_2 x^2 )\\
& = a_0 + a_1 x + a_2 x^2 + a_0 x^3 + a_1 x^4 + a_2 x^5\text{.}
\end{align*}
Puisque les polynômes sur un corps forment un domaine intègre, \(a_0 + a_1 x + a_2 x^2\) doit être le polynôme nul. Donc \(\ker \phi = \{ (000) \}\) et \(\phi\) est injective.
Pour calculer une matrice génératrice pour \(C\text{,}\) il suffit d’examiner la façon dont les polynômes \(1\text{,}\) \(x\) et \(x^2\) sont encodés :
\begin{align*}
(1 + x^3) \cdot 1 & = 1 + x^3\\
(1 + x^3)x & = x + x^4\\
(1 + x^3)x^2 & = x^2 + x^5\text{.}
\end{align*}
Nous obtenons le code correspondant à la matrice génératrice
\(G_1\) de l’
Exemple 22.2.1. La matrice de contrôle de parité pour ce code est
\begin{equation*}
H
=
\begin{pmatrix}
1 & 0 & 0 & 1 & 0 & 0 \\
0 & 1 & 0 & 0 & 1 & 0 \\
0 & 0 & 1 & 0 & 0 & 1
\end{pmatrix}\text{.}
\end{equation*}
Puisque le plus petit poids d’un mot de code non nul est \(2\text{,}\) ce code est capable de détecter toutes les erreurs simples.
Les anneaux de polynômes possèdent une grande richesse de structure ; notre objectif immédiat est donc d’établir un lien entre les codes polynomiaux et la théorie des anneaux. Rappelons que \(x^n - 1 = (x - 1)( x^{n - 1} + \cdots + x + 1)\text{.}\) L’anneau quotient
\begin{equation*}
R_n = {\mathbb Z}_2[x]/ \langle x^n - 1 \rangle
\end{equation*}
peut être considéré comme l’anneau des polynômes de la forme
\begin{equation*}
f(t) = a_0 + a_1 t + \cdots + a_{n - 1} t^{n - 1}
\end{equation*}
satisfaisant la condition \(t^n = 1\text{.}\) Il est facile de montrer que \({\mathbb Z}_2^n\) et \(R_n\) sont isomorphes en tant qu’espaces vectoriels. Nous identifierons souvent les éléments de \({\mathbb Z}_2^n\) avec les éléments de \({\mathbb Z}[x] / \langle x^n - 1 \rangle\text{.}\) De cette façon, nous pouvons interpréter un code linéaire comme un sous-ensemble de \({\mathbb Z}[x] / \langle x^n - 1 \rangle\text{.}\)
La structure d’anneau supplémentaire des codes polynomiaux est très puissante pour décrire les codes cycliques. Un décalage cyclique d’un \(n\)-uplet peut être décrit par une multiplication de polynômes. Si \(f(t) = a_0 + a_1 t + \cdots + a_{n - 1} t^{n - 1}\) est un polynôme-code dans \(R_n\text{,}\) alors
\begin{equation*}
tf(t) = a_{n - 1} + a_0 t + \cdots + a_{n - 2} t^{n - 1}
\end{equation*}
est le mot cycliquement décalé obtenu en multipliant \(f(t)\) par \(t\text{.}\) Le théorème suivant donne une belle classification des codes cycliques en termes d’idéaux de \(R_n\text{.}\)
Théorème 22.2.3.
Un code linéaire
\(C\) dans
\({\mathbb Z}_2^n\) est cyclique si et seulement si c’est un idéal de
\(R_n = {\mathbb Z}[x] / \langle x^n - 1 \rangle\text{.}\)
Démonstration.
Soit
\(C\) un code linéaire cyclique et supposons que
\(f(t)\) soit dans
\(C\text{.}\) Alors
\(t f(t)\) doit aussi être dans
\(C\text{.}\) Par conséquent,
\(t^k f(t)\) est dans
\(C\) pour tout
\(k \in {\mathbb N}\text{.}\) Puisque
\(C\) est un code linéaire, toute combinaison linéaire des mots de code
\(f(t), tf(t),
t^2f(t), \ldots, t^{n-1}f(t)\) est aussi un mot de code ; donc, pour tout polynôme
\(p(t)\text{,}\) \(p(t)f(t)\) est dans
\(C\text{.}\) Ainsi,
\(C\) est un idéal.
Réciproquement, soit
\(C\) un idéal de
\({\mathbb Z}_2[x]/\langle x^n + 1\rangle\text{.}\) Supposons que
\(f(t) = a_0 + a_1 t + \cdots + a_{n - 1} t^{n - 1}\) soit un mot de code dans
\(C\text{.}\) Alors
\(t f(t)\) est un mot de code dans
\(C\) ; c’est-à-dire que
\((a_1, \ldots, a_{n-1}, a_0)\) est dans
\(C\text{.}\)
Le
Théorème 22.2.3 nous dit que connaître les idéaux de
\(R_n\) équivaut à connaître les codes linéaires cycliques de
\({\mathbb Z}_2^n\text{.}\) Heureusement, les idéaux de
\(R_n\) sont faciles à décrire. L’homomorphisme d’anneaux naturel
\(\phi : {\mathbb Z}_2[x] \rightarrow R_n\) défini par
\(\phi[f(x)] = f(t)\) est un homomorphisme surjectif. Le noyau de
\(\phi\) est l’idéal engendré par
\(x^n - 1\text{.}\) Par le
Théorème 16.3.15, tout idéal
\(C\) de
\(R_n\) est de la forme
\(\phi(I)\text{,}\) où
\(I\) est un idéal de
\({\mathbb Z}_2[x]\) contenant
\(\langle x^n - 1 \rangle\text{.}\) Par le
Théorème 17.3.10, tout idéal
\(I\) de
\({\mathbb Z}_2[x]\) est un idéal principal, puisque
\({\mathbb Z}_2\) est un corps. Donc
\(I = \langle g(x) \rangle\) pour un unique polynôme unitaire de
\({\mathbb Z}_2[x]\text{.}\) Puisque
\(\langle x^n - 1 \rangle\) est contenu dans
\(I\text{,}\) \(g(x)\) divise nécessairement
\(x^n - 1\text{.}\) Par conséquent, tout idéal
\(C\) de
\(R_n\) est de la forme
\begin{equation*}
C = \langle g(t) \rangle = \{ f(t)g(t) : f(t) \in R_n \text{ et } g(x) \mid (x^n - 1) \text{ dans } {\mathbb Z}_2[x] \}\text{.}
\end{equation*}
L’unique polynôme unitaire de plus petit degré qui engendre \(C\) est appelé le polynôme générateur minimal de \(C\text{.}\)
Exemple 22.2.4.
Si l’on factorise \(x^7 - 1\) en composantes irréductibles, on obtient
\begin{equation*}
x^7 - 1 = (1 + x)(1 + x + x^3)(1+ x^2 + x^3)\text{.}
\end{equation*}
Nous voyons que
\(g(t) = (1 + t + t^3)\) engendre un idéal
\(C\) dans
\(R_7\text{.}\) Ce code est un code en blocs
\((7, 4)\text{.}\) Comme dans l’
Exemple 22.2.2, il est facile de calculer une matrice génératrice en examinant ce que
\(g(t)\) fait aux polynômes 1,
\(t\text{,}\) \(t^2\) et
\(t^3\text{.}\) Une matrice génératrice pour
\(C\) est
\begin{equation*}
G =
\begin{pmatrix}
1 & 0 & 0 & 0 \\
1 & 1 & 0 & 0 \\
0 & 1 & 1 & 0 \\
1 & 0 & 1 & 1 \\
0 & 1 & 0 & 1 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1
\end{pmatrix}\text{.}
\end{equation*}
En général, nous pouvons déterminer une matrice génératrice pour un code \((n, k)\) \(C\) en examinant la façon dont les éléments \(t^k\) sont encodés. Soit \(x^n - 1 = g(x) h(x)\) dans \({\mathbb Z}_2[x]\text{.}\) Si \(g(x) = g_0 + g_1 x + \cdots + g_{n-k} x^{n-k}\) et \(h(x) = h_0 + h_1 x + \cdots + h_k x^k\text{,}\) alors la matrice \(n \times k\)
\begin{equation*}
G =
\begin{pmatrix}
g_0 & 0 & \cdots & 0 \\
g_1 & g_0 & \cdots & 0 \\
\vdots & \vdots &\ddots & \vdots \\
g_{n-k} & g_{n-k-1} & \cdots & g_0 \\
0 & g_{n-k} & \cdots & g_{1} \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & g_{n-k}
\end{pmatrix}
\end{equation*}
est une matrice génératrice pour le code \(C\) de polynôme générateur \(g(t)\text{.}\) La matrice de contrôle de parité pour \(C\) est la matrice \((n - k) \times n\)
\begin{equation*}
H =
\begin{pmatrix}
0 & \cdots & 0 & 0 & h_k & \cdots & h_0 \\
0 & \cdots & 0 & h_k & \cdots & h_0 & 0 \\
\cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots \\
h_k & \cdots & h_0 & 0 & 0 & \cdots & 0
\end{pmatrix}\text{.}
\end{equation*}
Nous laisserons les détails de la preuve de la proposition suivante en exercice.
Proposition 22.2.5.
Soit
\(C = \langle g(t) \rangle\) un code cyclique dans
\(R_n\) et supposons que
\(x^n - 1 = g(x) h(x)\text{.}\) Alors
\(G\) et
\(H\) sont respectivement des matrices génératrice et de contrôle de parité pour
\(C\text{.}\) De plus,
\(HG = 0\text{.}\)
Exemple 22.2.6.
\begin{equation*}
x^7 - 1 = g(x) h(x) = (1 + x + x^3)(1 + x + x^2 + x^4)\text{.}
\end{equation*}
Donc une matrice de contrôle de parité pour ce code est
\begin{equation*}
H =
\begin{pmatrix}
0 & 0 & 1 & 0 & 1 & 1 & 1 \\
0 & 1 & 0 & 1 & 1 & 1 & 0 \\
1 & 0 & 1 & 1 & 1 & 0 & 0
\end{pmatrix}\text{.}
\end{equation*}
Pour déterminer les capacités de détection et de correction d’erreurs d’un code cyclique, nous avons besoin de connaître quelques propriétés des déterminants. Si \(\alpha_1, \ldots, \alpha_n\) sont des éléments d’un corps \(F\text{,}\) alors la matrice \(n \times n\)
\begin{equation*}
\begin{pmatrix}
1 & 1 & \cdots & 1 \\
\alpha_1 & \alpha_2 & \cdots & \alpha_n \\
\alpha_1^2 & \alpha_2^2 & \cdots & \alpha_n^2 \\
\vdots & \vdots & \ddots & \vdots \\
\alpha_1^{n-1} & \alpha_2^{n-1} & \cdots & \alpha_n^{n-1}
\end{pmatrix}
\end{equation*}
est appelée la matrice de Vandermonde. Le déterminant de cette matrice est appelé le déterminant de Vandermonde. Nous aurons besoin du lemme suivant dans notre étude des codes cycliques.
Lemme 22.2.7.
Soient \(\alpha_1, \ldots, \alpha_n\) des éléments d’un corps \(F\) avec \(n \geq 2\text{.}\) Alors
\begin{equation*}
\det
\begin{pmatrix}
1 & 1 & \cdots & 1 \\
\alpha_1 & \alpha_2 & \cdots & \alpha_n \\
\alpha_1^2 & \alpha_2^2 & \cdots & \alpha_n^2 \\
\vdots & \vdots & \ddots & \vdots \\
\alpha_1^{n-1} & \alpha_2^{n-1} & \cdots & \alpha_n^{n-1}
\end{pmatrix}
= \prod_{1 \leq j \lt i \leq n} (\alpha_i - \alpha_j)\text{.}
\end{equation*}
En particulier, si les \(\alpha_i\) sont distincts, alors le déterminant est non nul.
Démonstration.
Nous allons procéder par récurrence sur \(n\text{.}\) Si \(n = 2\text{,}\) alors le déterminant est \(\alpha_2 - \alpha_1\text{.}\) Supposons le résultat vrai pour \(n - 1\) et considérons le polynôme \(p(x)\) défini par
\begin{equation*}
p(x) = \det
\begin{pmatrix}
1 & 1 & \cdots & 1 & 1 \\
\alpha_1 & \alpha_2 & \cdots & \alpha_{n-1} & x \\
\alpha_1^2 & \alpha_2^2 & \cdots & \alpha_{n-1}^2 & x^2 \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
\alpha_1^{n-1} & \alpha_2^{n-1} & \cdots & \alpha_{n-1}^{n-1} & x^{n-1}
\end{pmatrix}\text{.}
\end{equation*}
En développant ce déterminant par cofacteurs sur la dernière colonne, on voit que \(p(x)\) est un polynôme de degré au plus \(n-1\text{.}\) De plus, les racines de \(p(x)\) sont \(\alpha_1, \ldots, \alpha_{n-1}\text{,}\) car la substitution de l’un quelconque de ces éléments dans la dernière colonne produira une colonne identique à la dernière colonne de la matrice. Rappelons que le déterminant d’une matrice est nul si elle a deux colonnes identiques. Donc,
\begin{equation*}
p(x) = (x - \alpha_1)(x - \alpha_2) \cdots (x - \alpha_{n-1}) \beta\text{,}
\end{equation*}
où
\begin{equation*}
\beta = (-1)^{n + n} \det
\begin{pmatrix}
1 & 1 & \cdots & 1 \\
\alpha_1 & \alpha_2 & \cdots & \alpha_{n-1} \\
\alpha_1^2 & \alpha_2^2 & \cdots & \alpha_{n-1}^2 \\
\vdots & \vdots & \ddots & \vdots \\
\alpha_1^{n-2} & \alpha_2^{n-2} & \cdots & \alpha_{n-1}^{n-2}
\end{pmatrix}\text{.}
\end{equation*}
Par hypothèse de récurrence,
\begin{equation*}
\beta = (-1)^{n+n} \prod_{1 \leq j \lt i \leq n - 1} (\alpha_i - \alpha_j)\text{.}
\end{equation*}
En posant \(x = \alpha_n\text{,}\) le résultat s’ensuit immédiatement.
Le théorème suivant nous donne une estimation des capacités de détection et de correction d’erreurs pour un polynôme générateur particulier.
Théorème 22.2.8.
Soit
\(C = \langle g(t) \rangle\) un code cyclique dans
\(R_n\) et supposons que
\(\omega\) est une racine primitive
\(n\)-ième de l’unité sur
\({\mathbb Z}_2\text{.}\) Si
\(s\) puissances consécutives de
\(\omega\) sont des racines de
\(g(x)\text{,}\) alors la distance minimale de
\(C\) est au moins
\(s + 1\text{.}\)
Démonstration.
Supposons que
\begin{equation*}
g( \omega^r) = g(\omega^{r + 1}) = \cdots = g( \omega^{r + s - 1}) = 0\text{.}
\end{equation*}
Soit \(f(x)\) un polynôme de \(C\) ayant \(s\) coefficients non nuls ou moins. On peut supposer que
\begin{equation*}
f(x) = a_{i_0} x^{i_0} + a_{i_1} x^{i_1} + \cdots + a_{i_{s - 1}} x^{i_{s - 1}}
\end{equation*}
est un polynôme de \(C\text{.}\) Il suffira de montrer que tous les \(a_i\) sont nuls. Puisque
\begin{equation*}
g( \omega^r) = g(\omega^{r + 1}) = \cdots = g( \omega^{r + s - 1}) = 0
\end{equation*}
et que \(g(x)\) divise \(f(x)\text{,}\)
\begin{equation*}
f( \omega^r) = f(\omega^{r + 1}) = \cdots = f( \omega^{r + s - 1}) = 0\text{.}
\end{equation*}
De manière équivalente, nous avons le système d’équations suivant :
\begin{align*}
a_{i_0} (\omega^r)^{i_0} + a_{i_1} (\omega^r)^{i_1} + \cdots + a_{i_{s - 1}} (\omega^r)^{i_{s - 1}} & = 0\\
a_{i_0} (\omega^{r + 1})^{i_0} + a_{i_1} (\omega^{r + 1})^{i_2} + \cdots + a_{i_{s-1}} (\omega^{r+1})^{i_{s-1}} & = 0\\
& \vdots\\
a_{i_0} (\omega^{r + s - 1})^{i_0} + a_{i_1} (\omega^{r + s - 1})^{i_1} + \cdots + a_{i_{s - 1}} (\omega^{r + s - 1})^{i_{s - 1}} & = 0\text{.}
\end{align*}
Donc \((a_{i_0}, a_{i_1}, \ldots,
a_{i_{s - 1}})\) est une solution du système homogène d’équations linéaires
\begin{align*}
(\omega^{i_0})^r x_0 + (\omega^{i_1})^r x_1 + \cdots + (\omega^{i_{s - 1}})^r x_{n - 1} & = 0\\
(\omega^{i_0})^{r + 1} x_0 + (\omega^{i_1})^{r + 1} x_1 + \cdots + (\omega^{i_{s - 1}})^{r + 1} x_{n - 1} & = 0\\
& \vdots\\
(\omega^{i_0})^{r + s - 1} x_0 + (\omega^{i_1})^{r + s - 1} x_1 + \cdots + (\omega^{i_{s - 1}})^{r + s - 1} x_{n - 1} & = 0\text{.}
\end{align*}
Or ce système a une solution unique, car le déterminant de la matrice
\begin{equation*}
\begin{pmatrix}
(\omega^{i_0})^r & (\omega^{i_1})^r & \cdots & (\omega^{i_{s-1}})^r \\
(\omega^{i_0})^{r+1} & (\omega^{i_1})^{r+1} & \cdots &
(\omega^{i_{s-1}})^{r+1} \\
\vdots & \vdots & \ddots & \vdots \\
(\omega^{i_0})^{r+s-1} & (\omega^{i_1})^{r+s-1} & \cdots &
(\omega^{i_{s-1}})^{r+s-1}
\end{pmatrix}
\end{equation*}
peut être montré non nul grâce au
Lemme 22.2.7 et aux propriétés fondamentales des déterminants (Exercice). Donc cette solution doit être
\(a_{i_0} = a_{i_1} = \cdots = a_{i_{s - 1}} = 0\text{.}\)
Sous-section 22.2.2 Codes BCH
Parmi les codes les plus importants, découverts indépendamment par A. Hocquenghem en 1959 et par R. C. Bose et D. V. Ray-Chaudhuri en 1960, figurent les codes
BCH. Les systèmes de communication européens et transatlantiques utilisent tous deux des codes
BCH. Les mots d’information à encoder sont de longueur
\(231\text{,}\) et un polynôme de degré
\(24\) est utilisé pour engendrer le code. Puisque
\(231 + 24 = 255 = 2^8-1\text{,}\) nous avons affaire à un code en blocs
\((255, 231)\text{.}\) Ce code
BCH détecte six erreurs et a un taux d’échec de
\(1\) sur
\(16\) millions. Un avantage des codes
BCH est qu’il existe des algorithmes de correction d’erreurs efficaces pour eux.
L’idée derrière les codes
BCH est de choisir un polynôme générateur de plus petit degré ayant les plus grandes capacités de détection et de correction d’erreurs. Soit
\(d = 2r + 1\) pour un certain
\(r \geq 0\text{.}\) Supposons que
\(\omega\) soit une racine primitive
\(n\)-ième de l’unité sur
\({\mathbb Z}_2\text{,}\) et soit
\(m_i(x)\) le polynôme minimal sur
\({\mathbb Z}_2\) de
\(\omega^i\text{.}\) Si
\begin{equation*}
g(x) = \lcm[ m_1(x), m_{2}(x), \ldots, m_{2r}(x)]\text{,}
\end{equation*}
alors le code cyclique
\(\langle g(t) \rangle\) dans
\(R_n\) est appelé le
code BCH de longueur \(n\) et de distance \(d\text{.}\) Par le
Théorème 22.2.8, la distance minimale de
\(C\) est au moins
\(d\text{.}\)
Théorème 22.2.9.
Soit \(C = \langle g(t) \rangle\) un code cyclique dans \(R_n\text{.}\) Les énoncés suivants sont équivalents.
-
Le code
\(C\) est un code
BCH dont la distance minimale est au moins
\(d\text{.}\)
-
Un polynôme-code
\(f(t)\) est dans
\(C\) si et seulement si
\(f( \omega^i) = 0\) pour
\(1 \leq i \lt d\text{.}\)
-
La matrice
\begin{equation*}
H =
\begin{pmatrix}
1 & \omega & \omega^2 & \cdots & \omega^{n-1}\\
1 & \omega^2 & \omega^{4} & \cdots & \omega^{(n-1)(2)} \\
1 & \omega^3 & \omega^{6} & \cdots & \omega^{(n-1)(3)} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
1 & \omega^{2r} & \omega^{4r} & \cdots & \omega^{(n-1)(2r)}
\end{pmatrix}
\end{equation*}
est une matrice de contrôle de parité pour \(C\text{.}\)
Démonstration.
(1)
\(\Rightarrow\) (2). Si
\(f(t)\) est dans
\(C\text{,}\) alors
\(g(x) \mid f(x)\) dans
\({\mathbb Z}_2[x]\text{.}\) Donc, pour
\(i = 1, \ldots, 2r\text{,}\) \(f( \omega^i) = 0\) puisque
\(g( \omega^i ) = 0\text{.}\) Réciproquement, supposons que
\(f( \omega^i) = 0\) pour
\(1 \leq i \leq d\text{.}\) Alors
\(f(x)\) est divisible par chaque
\(m_i(x)\text{,}\) puisque
\(m_i(x)\) est le polynôme minimal de
\(\omega^i\text{.}\) Donc
\(g(x) \mid f(x)\) par définition de
\(g(x)\text{.}\) Par conséquent,
\(f(x)\) est un mot de code.
(2) \(\Rightarrow\) (3). Soit \(f(t) = a_0 + a_1 t + \cdots + a_{n - 1}v t^{n - 1}\) dans \(R_n\text{.}\) Le \(n\)-uplet correspondant dans \({\mathbb Z}_2^n\) est \({\mathbf x} = (a_0 a_1 \cdots a_{n - 1})^\transpose\text{.}\) Par (2),
\begin{equation*}
H {\mathbf x} =
\begin{pmatrix}
a_0 + a_1 \omega + \cdots + a_{n-1} \omega^{n-1} \\
a_0 + a_1 \omega^2 + \cdots + a_{n-1} (\omega^2)^{n-1} \\
\vdots \\
a_0 + a_1 \omega^{2r} + \cdots + a_{n-1} (\omega^{2r})^{n-1}
\end{pmatrix}
=
\begin{pmatrix}
f(\omega) \\
f(\omega^2) \\
\vdots \\
f(\omega^{2r})
\end{pmatrix}
= 0
\end{equation*}
exactement quand \(f(t)\) est dans \(C\text{.}\) Ainsi, \(H\) est une matrice de contrôle de parité pour \(C\text{.}\)
(3)
\(\Rightarrow\) (1). Par (3), un polynôme-code
\(f(t) = a_0 + a_1 t + \cdots + a_{n - 1} t^{n - 1}\) est dans
\(C\) exactement quand
\(f(\omega^i) = 0\) pour
\(i = 1, \ldots, 2r\text{.}\) Le plus petit tel polynôme est
\(g(t) = \lcm[ m_1(t),\ldots,
m_{2r}(t)]\text{.}\) Donc
\(C = \langle g(t) \rangle\text{.}\)
Exemple 22.2.10.
Il est facile de vérifier que \(x^{15} - 1 \in {\mathbb Z}_2[x]\) admet la factorisation
\begin{equation*}
x^{15} - 1 = (x + 1)(x^2 + x + 1)(x^4 + x + 1)(x^4 + x^3 + 1)(x^4 + x^3 + x^2 + x + 1)\text{,}
\end{equation*}
où chacun des facteurs est un polynôme irréductible. Soit \(\omega\) une racine de \(1 + x + x^4\text{.}\) Le corps de Galois \(\gf(2^4)\) est
\begin{equation*}
\{ a_0 + a_1 \omega + a_2 \omega^2 + a_3 \omega^3 : a_i \in {\mathbb Z}_2 \text{ et } 1 + \omega + \omega^4 = 0 \}\text{.}
\end{equation*}
Par l’
Exemple 22.1.8,
\(\omega\) est une racine primitive
\(15\)-ième de l’unité. Le polynôme minimal de
\(\omega\) est
\(m_1(x) = 1 + x + x^4\text{.}\) Il est facile de voir que
\(\omega^2\) et
\(\omega^4\) sont aussi des racines de
\(m_1(x)\text{.}\) Le polynôme minimal de
\(\omega^3\) est
\(m_2(x) = 1 + x + x^2 + x^3 + x^4\text{.}\) Donc,
\begin{equation*}
g(x) = m_1(x) m_2(x) = 1 + x^4 + x^6 + x^7 + x^8
\end{equation*}
a pour racines
\(\omega\text{,}\) \(\omega^2\text{,}\) \(\omega^3\text{,}\) \(\omega^4\text{.}\) Puisque
\(m_1(x)\) et
\(m_2(x)\) divisent tous deux
\(x^{15} - 1\text{,}\) le code
BCH est un code
\((15, 7)\text{.}\) Si
\(x^{15} -1 = g(x)h(x)\text{,}\) alors
\(h(x) = 1 + x^4 + x^6 + x^7\) ; donc une matrice de contrôle de parité pour ce code est
\begin{equation*}
\left(
\begin{array}{ccccccccccccccc}
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0
\end{array}
\right)\text{.}
\end{equation*}
