Pour mieux connaître un code particulier et développer des techniques plus efficaces d’encodage, de décodage et de détection d’erreurs, nous devons ajouter une structure supplémentaire à nos codes. Une façon d’y parvenir est d’exiger que le code soit également un groupe. Un code de groupe est un code qui est également un sous-groupe de \({\mathbb Z}_2^n\text{.}\)
Pour vérifier qu’un code est un code de groupe, il suffit de vérifier une seule chose. Si nous additionnons deux éléments quelconques du code, le résultat doit être un \(n\)-uplet qui est à nouveau dans le code. Il n’est pas nécessaire de vérifier que l’inverse du \(n\)-uplet est dans le code, puisque chaque mot de code est son propre inverse, et il n’est pas non plus nécessaire de vérifier que \({\mathbf 0}\) est un mot de code. Par exemple,
C’est une tâche directe bien que fastidieuse de vérifier que ce code est également un sous-groupe de \({\mathbb Z}_2^7\) et, par conséquent, un code de groupe. Ce code est un code de détection et de correction d’erreur simple, mais c’est un processus long et fastidieux de calculer toutes les distances entre les paires de mots de code pour déterminer que \(d_{\min} = 3\text{.}\) Il est beaucoup plus facile de voir que le poids minimum de tous les mots de code non nuls est \(3\text{.}\) Comme nous le verrons bientôt, ce n’est pas une coïncidence. Cependant, la relation entre les poids et les distances dans un code particulier dépend fortement du fait que le code est un groupe.
Supposons que \({\mathbf x}\) et \({\mathbf y}\) sont des \(n\)-uplets binaires. Alors la distance entre \({\mathbf x}\) et \({\mathbf y}\) est exactement le nombre de positions dans lesquelles \({\mathbf x}\) et \({\mathbf y}\) diffèrent. Mais \({\mathbf x}\) et \({\mathbf y}\) diffèrent dans une coordonnée particulière exactement quand la somme dans cette coordonnée est \(1\text{,}\) puisque
Soit \(d_{\min}\) la distance minimale pour un code de groupe \(C\text{.}\) Alors \(d_{\min}\) est le poids minimum de tous les mots de code non nuls dans \(C\text{.}\) C’est-à-dire,
À partir de Exemple 8.2.1, il est maintenant facile de vérifier que le poids minimal non nul est \(3\) ; par conséquent, le code détecte et corrige bien toutes les erreurs simples. Nous avons maintenant réduit le problème de trouver de « bons » codes à celui de générer des codes de groupe. Un moyen facile de générer des codes de groupe est d’utiliser un peu de théorie matricielle.
où \({\mathbf x} = (x_1, x_2, \ldots,
x_n)^\transpose\) et \({\mathbf y} = (y_1, y_2, \ldots,
y_n)^\transpose\) sont des vecteurs colonnes. 1
Puisque nous travaillerons avec des matrices, nous écrirons les \(n\)-uplets binaires comme vecteurs colonnes pour le reste de ce chapitre.
Par exemple, si \({\mathbf x} = (011001)^\transpose\) et \({\mathbf y} = (110101)^\transpose\text{,}\) alors \({\mathbf x} \cdot {\mathbf y} = 0\text{.}\) Nous pouvons également considérer un produit scalaire comme le produit d’une matrice ligne par une matrice colonne ; c’est-à-dire,
Supposons que les mots à encoder consistent en tous les \(3\)-uplets binaires et que notre schéma d’encodage est la parité paire. Pour encoder un \(3\)-uplet arbitraire, nous ajoutons un quatrième bit pour obtenir un nombre pair de \(1\)s. Remarquez qu’un \(n\)-uplet arbitraire \({\mathbf x} = (x_1, x_2, \ldots,
x_n)^\transpose\) a un nombre pair de \(1\)s exactement quand \(x_1 + x_2 + \cdots + x_n = 0\) ; par conséquent, un \(4\)-uplet \({\mathbf x} = (x_1, x_2, x_3, x_4)^\transpose\) a un nombre pair de \(1\)s si \(x_1+ x_2+ x_3+ x_4 = 0\text{,}\) ou
Soit \({\mathbb M}_{m \times n}({\mathbb Z}_2)\) l’ensemble de toutes les matrices \(m \times n\) à entrées dans \({\mathbb Z}_2\text{.}\) Nous effectuons les opérations matricielles comme d’habitude sauf que toutes nos opérations d’addition et de multiplication se produisent dans \({\mathbb Z}_2\text{.}\) Définissons le noyau d’une matrice \(H \in {\mathbb M}_{m \times n}({\mathbb Z}_2)\) comme l’ensemble de tous les \(n\)-uplets binaires \({\mathbf x}\) tels que \(H{\mathbf x} = {\mathbf 0}\text{.}\) Nous notons le noyau d’une matrice \(H\) par \(\Null(H)\text{.}\)
Pour qu’un \(5\)-uplet \({\mathbf x} = (x_1, x_2, x_3, x_4, x_5)^\transpose\) soit dans le noyau de \(H\text{,}\) il faut que \(H{\mathbf x} = {\mathbf 0}\text{.}\) Autrement dit, le système d’équations suivant doit être satisfait :
Puisque chaque élément de \({\mathbb Z}_2^n\) est son propre inverse, la seule chose qu’il est vraiment nécessaire de vérifier ici est la clôture. Soient \({\mathbf x}, {\mathbf y} \in \Null(H)\) pour une matrice \(H\) dans \({\mathbb M}_{m \times n}({\mathbb Z}_2)\text{.}\) Alors \(H{\mathbf x} = {\mathbf 0}\) et \(H{\mathbf y} = {\mathbf 0}\text{.}\) Donc
Supposons que le \(6\)-uplet \({\mathbf x} = (010011)^\transpose\) est reçu. C’est une simple multiplication matricielle de déterminer si \({\mathbf x}\) est ou non un mot de code. Puisque
