Nous pouvons utiliser la théorie des groupes pour obtenir une autre méthode de décodage des messages. Un code linéaire
\(C\) est un sous-groupe de
\({\mathbb Z}_2^n\text{.}\) Le
décodage par classes latérales ou
décodage standard utilise les classes latérales de
\(C\) dans
\({\mathbb Z}_2^n\) pour mettre en œuvre le décodage par maximum de vraisemblance. Supposons que
\(C\) est un code linéaire
\((n,m)\text{.}\) Une classe latérale de
\(C\) dans
\({\mathbb Z}_2^n\) s’écrit sous la forme
\({\mathbf x} + C\text{,}\) où
\({\mathbf x} \in {\mathbb Z}_2^n\text{.}\) Par le théorème de Lagrange (
Théorème 6.2.2), il y a
\(2^{n - (n - m)} = 2^m\) classes latérales distinctes de
\(C\) dans
\({\mathbb Z}_2^n\text{.}\)
Exemple 8.4.5.
Soit \(C\) le code linéaire \((5,3)\) donné par la matrice de contrôle de parité
\begin{equation*}
H =
\begin{pmatrix}
0 & 1 & 1 & 0 & 0 \\
1 & 0 & 0 & 1 & 0 \\
1 & 1 & 0 & 0 & 1
\end{pmatrix}\text{.}
\end{equation*}
Le code est constitué des mots de code
\begin{equation*}
(00000) \quad (01101) \quad (10011) \quad (11110)\text{.}
\end{equation*}
Il y a
\(2^{5-2} = 2^3\) classes latérales de
\(C\) dans
\({\mathbb Z}_2^5\text{,}\) chacune d’ordre
\(2^2 =4\text{.}\) Ces classes latérales sont listées dans
Table 8.4.6.
Notre tâche est de comprendre comment la connaissance des classes latérales peut nous aider à décoder un message. Supposons que
\({\mathbf x}\) était le mot de code original envoyé et que
\({\mathbf r}\) est le
\(n\)-uplet reçu. Si
\({\mathbf e}\) est l’erreur de transmission, alors
\({\mathbf r} = {\mathbf e} + {\mathbf x}\) ou, de façon équivalente,
\({\mathbf x} = {\mathbf e} + {\mathbf r}\text{.}\) Cependant, cela revient exactement à dire que
\({\mathbf r}\) est un élément de la classe latérale
\({\mathbf e} + C\text{.}\) Dans le décodage par maximum de vraisemblance, nous attendons que l’erreur
\({\mathbf e}\) soit aussi petite que possible ; c’est-à-dire que
\({\mathbf e}\) aura le poids le plus faible. Un
\(n\)-uplet de poids minimal dans une classe latérale est appelé un
représentant minimal de la classe latérale. Une fois que nous avons déterminé un représentant minimal pour chaque classe latérale, le processus de décodage devient une tâche de calcul de
\({\mathbf r} + {\mathbf e}\) pour obtenir
\({\mathbf x}\text{.}\)
Exemple 8.4.7.
Dans
Table 8.4.6, remarquez que nous avons choisi un représentant du poids le plus faible possible pour chaque classe latérale. Ces représentants sont les représentants minimaux des classes latérales. Supposons maintenant que
\({\mathbf r} = (01111)\) est le mot reçu. Pour décoder
\({\mathbf r}\text{,}\) nous trouvons qu’il est dans la classe latérale
\((00010) + C\) ; par conséquent, le mot de code transmis à l’origine devait être
\((01101) = (01111) + (00010)\text{.}\)
Un problème potentiel avec cette méthode de décodage est que nous pourrions avoir à examiner chaque classe latérale pour le mot de code reçu. La proposition suivante donne une méthode pour mettre en œuvre le décodage par classes latérales. Elle affirme que nous pouvons associer un syndrome à chaque classe latérale ; par conséquent, nous pouvons établir un tableau qui désigne un représentant minimal correspondant à chaque syndrome. Une telle liste est appelée une
table de décodage.
Étant donné un code en blocs
\((n,k)\text{,}\) la question se pose de savoir si le décodage par classes latérales est un schéma gérable. Une table de décodage nécessite une liste de classes latérales et de syndromes, une pour chacune des
\(2^{n - k}\) classes latérales de
\(C\text{.}\) Supposons que nous avons un code en blocs
\((32, 24)\text{.}\) Nous avons un nombre énorme de mots de code,
\(2^{24}\text{,}\) mais il n’y a que
\(2^{32 - 24} = 2^{8} = 256\) classes latérales.
