Exercices 22.5 Exercices supplémentaires : Correction d’erreurs pour les codes BCH
Les codes BCH possèdent des algorithmes de correction d’erreurs très attractifs. Soit \(C\) un code BCH dans \(R_n\text{,}\) et supposons qu’un polynôme-code \(c(t) = c_0 + c_1 t + \cdots + c_{n-1} t^{n-1}\) soit transmis. Soit \(w(t) = w_0 + w_1 t + \cdots w_{n-1} t^{n-1}\) le polynôme de \(R_n\) reçu. Si des erreurs se sont produites dans les bits \(a_1, \ldots, a_k\text{,}\) alors \(w(t) = c(t) + e(t)\text{,}\) où \(e(t) = t^{a_1} + t^{a_2} + \cdots + t^{a_k}\) est le polynôme d’erreur. Le décodeur doit déterminer les entiers \(a_i\) puis retrouver \(c(t)\) à partir de \(w(t)\) en inversant le \(a_i\)-ième bit. À partir de \(w(t)\) on peut calculer \(w( \omega^i ) = s_i\) pour \(i = 1, \ldots, 2r\text{,}\) où \(\omega\) est une racine primitive \(n\)-ième de l’unité sur \({\mathbb Z}_2\text{.}\) Nous appelons le syndrome de \(w(t)\) la suite \(s_1, \ldots, s_{2r}\text{.}\)
2.
Montrez que
\begin{equation*}
s_i = w( \omega^i) = e( \omega^i) = \omega^{i a_1} + \omega^{i a_2} + \cdots + \omega^{i a_k}
\end{equation*}
pour \(i = 1, \ldots, 2r\text{.}\) Le polynôme localisateur d’erreurs est défini par
\begin{equation*}
s(x) = (x + \omega^{a_1})(x + \omega^{a_2}) \cdots (x + \omega^{a_k})\text{.}
\end{equation*}
3.
Rappelons le code BCH en blocs \((15,7)\) de l’Exemple 22.2.6. Par le Théorème 8.1.13, ce code est capable de corriger deux erreurs. Supposons que ces erreurs se produisent dans les bits \(a_1\) et \(a_2\text{.}\) Le polynôme localisateur d’erreurs est \(s(x) = (x + \omega^{a_1})(x + \omega^{a_2})\text{.}\) Montrez que
\begin{equation*}
s(x) = x^2 + s_1 x + \left( s_1^2 + \frac{s_3}{s_1} \right)\text{.}
\end{equation*}
4.
Soit \(w(t) = 1 + t^2 +t^4 + t^5 + t^7 + t^{12} + t^{13}\text{.}\) Déterminez quel était le polynôme-code transmis à l’origine.
