Sauter au contenu
Logo image

Algèbre abstraite Théorie et applications

Thomas W. Judson

Section 8.3 Matrices de contrôle de parité et matrices génératrices

Nous avons besoin de trouver un moyen systématique de générer des codes linéaires ainsi que des méthodes rapides de décodage. En examinant les propriétés d’une matrice \(H\) et en choisissant soigneusement \(H\text{,}\) il est possible de développer des méthodes très efficaces d’encodage et de décodage des messages. À cette fin, nous allons introduire les matrices génératrices standard et les matrices de contrôle de parité canoniques.
🔗
Supposons que \(H\) est une matrice \(m \times n\) à entrées dans \({\mathbb Z}_2\) et \(n \gt m\text{.}\) Si les \(m\) dernières colonnes de la matrice forment la matrice identité \(m \times m\text{,}\) \(I_m\text{,}\) alors la matrice est une matrice de contrôle de parité canonique. Plus précisément, \(H= (A \mid I_m)\text{,}\) où \(A\) est la matrice \(m \times (n-m)\)
\begin{equation*} \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1,n-m} \\ a_{21} & a_{22} & \cdots & a_{2,n-m} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{m,n-m} \end{pmatrix} \end{equation*}
et \(I_m\) est la matrice identité \(m \times m\)
\begin{equation*} \begin{pmatrix} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{pmatrix}\text{.} \end{equation*}
À chaque matrice de contrôle de parité canonique nous pouvons associer une matrice génératrice standard \(n \times (n-m)\)
\begin{equation*} G = \left( \frac{I_{n-m}}{A} \right)\text{.} \end{equation*}
Notre objectif sera de montrer qu’un \(\mathbf x\) satisfaisant \(G {\mathbf x} = {\mathbf y}\) existe si et seulement si \(H{\mathbf y} = {\mathbf 0}\text{.}\) Étant donné un bloc de message \({\mathbf x}\) à encoder, la matrice \(G\) nous permettra de l’encoder rapidement en un mot de code linéaire \({\mathbf y}\text{.}\)
🔗

Exemple 8.3.1.

Supposons que nous avons les huit mots suivants à encoder :
\begin{equation*} (000), (001), (010), \ldots, (111)\text{.} \end{equation*}
Pour
\begin{equation*} A = \begin{pmatrix} 0 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{pmatrix}\text{,} \end{equation*}
la matrice génératrice standard associée et la matrice de contrôle de parité canonique sont
\begin{equation*} G= \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{pmatrix} \end{equation*}
et
\begin{equation*} H = \begin{pmatrix} 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1 \end{pmatrix}\text{,} \end{equation*}
respectivement.
🔗
Observez que les lignes de \(H\) représentent les contrôles de parité sur certaines positions de bits dans un \(6\)-uplet. Les \(1\)s dans la matrice identité servent de contrôles de parité pour les \(1\)s dans la même ligne. Si \({\mathbf x} = (x_1, x_2, x_3, x_4, x_5, x_6)\text{,}\) alors
\begin{equation*} {\mathbf 0} = H{\mathbf x} = \begin{pmatrix} x_2 + x_3 + x_4 \\ x_1 + x_2 + x_5\\ x_1 + x_3 + x_6 \end{pmatrix}\text{,} \end{equation*}
ce qui donne un système d’équations :
\begin{align*} x_2 + x_3 + x_4 & = 0\\ x_1 + x_2 + x_5 & = 0\\ x_1 + x_3 + x_6 & = 0\text{.} \end{align*}
Ici \(x_4\) sert de bit de contrôle pour \(x_2\) et \(x_3\) ; \(x_5\) est un bit de contrôle pour \(x_1\) et \(x_2\) ; et \(x_6\) est un bit de contrôle pour \(x_1\) et \(x_3\text{.}\) La matrice identité évite que \(x_4\text{,}\) \(x_5\) et \(x_6\) aient à se contrôler mutuellement. Ainsi, \(x_1\text{,}\) \(x_2\text{,}\) et \(x_3\) peuvent être arbitraires, mais \(x_4\text{,}\) \(x_5\) et \(x_6\) doivent être choisis pour assurer la parité. Le noyau de \(H\) se calcule facilement :
\begin{equation*} \begin{array}{cccc} (000000) & (001101) & (010110) & (011011) \\ (100011) & (101110) & (110101) & (111000). \end{array} \end{equation*}
Un moyen encore plus facile de calculer le noyau est avec la matrice génératrice \(G\) (Table 8.3.2).
🔗
🔗
Table 8.3.2. Un code généré par une matrice
🔗
Mot de message \(\mathbf x\) Mot de code \(G \mathbf x\)
\(000\) \(000000\)
\(001\) \(001101\)
\(010\) \(010110\)
\(011\) \(011011\)
\(100\) \(100011\)
\(101\) \(101110\)
\(110\) \(110101\)
\(111\) \(111000\)
Nous laissons la démonstration de ce théorème en exercice. À la lumière du théorème, les premiers \(n - m\) bits de \({\mathbf x}\) sont appelés bits d’information et les derniers \(m\) bits sont appelés bits de contrôle. Dans Exemple 8.3.1, les trois premiers bits sont les bits d’information et les trois derniers sont les bits de contrôle.
🔗

Démonstration.

Soient \(G {\mathbf x}_1 = {\mathbf y}_1\) et \(G {\mathbf x}_2 ={\mathbf y}_2\) deux mots de code. Alors \({\mathbf y}_1 + {\mathbf y}_2\) est dans \(C\) puisque
\begin{equation*} G( {\mathbf x}_1 + {\mathbf x}_2) = G {\mathbf x}_1 + G {\mathbf x}_2 = {\mathbf y}_1 + {\mathbf y}_2\text{.} \end{equation*}
Nous devons également montrer que deux blocs de messages ne peuvent pas être encodés dans le même mot de code. C’est-à-dire, nous devons montrer que si \(G {\mathbf x} = G {\mathbf y}\text{,}\) alors \({\mathbf x} = {\mathbf y}\text{.}\) Supposons que \(G {\mathbf x} = G {\mathbf y}\text{.}\) Alors
\begin{equation*} G {\mathbf x} - G {\mathbf y} = G( {\mathbf x} - {\mathbf y}) = {\mathbf 0}\text{.} \end{equation*}
Cependant, les premiers \(k\) coordonnées de \(G( {\mathbf x} - {\mathbf y})\) sont exactement \(x_1 -y_1, \ldots, x_k - y_k\text{,}\) puisqu’elles sont déterminées par la matrice identité, \(I_k\text{,}\) partie de \(G\text{.}\) Par conséquent, \(G( {\mathbf x} - {\mathbf y}) = {\mathbf 0}\) exactement quand \({\mathbf x} = {\mathbf y}\text{.}\)
🔗
🔗
Avant de pouvoir démontrer la relation entre les matrices de contrôle de parité canoniques et les matrices génératrices standard, nous devons démontrer un lemme.
🔗

Démonstration.

Soit \(C = HG\text{.}\) Le coefficient d’indice \(ij\) de \(C\) est
\begin{align*} c_{ij} & = \sum_{k=1}^n h_{ik} g_{kj}\\ & = \sum_{k=1}^{n-m} h_{ik} g_{kj} + \sum_{k=n-m+1}^n h_{ik} g_{kj}\\ & = \sum_{k=1}^{n-m} a_{ik} \delta_{kj} + \sum_{k=n-m+1}^n \delta_{i-(m-n),k} a_{kj}\\ & = a_{ij} + a_{ij}\\ & = 0\text{,} \end{align*}
où
\begin{equation*} \delta_{ij} = \begin{cases} 1 & i = j \\ 0 & i \neq j \end{cases} \end{equation*}
est le delta de Kronecker.
🔗
🔗

Démonstration.

Supposons d’abord que \({\mathbf y} \in C\text{.}\) Alors \(G {\mathbf x} = {\mathbf y}\) pour un certain \({\mathbf x} \in {\mathbb Z}_2^m\text{.}\) Par Lemme 8.3.5, \(H {\mathbf y} = HG {\mathbf x} = {\mathbf 0}\text{.}\)
🔗
Réciproquement, supposons que \({\mathbf y} = (y_1, \ldots, y_n)^\transpose\) est dans le noyau de \(H\text{.}\) Nous devons trouver un \({\mathbf x}\) dans \({\mathbb Z}_2^{n-m}\) tel que \(G {\mathbf x}^\transpose = {\mathbf y}\text{.}\) Puisque \(H {\mathbf y} = {\mathbf 0}\text{,}\) le système d’équations suivant doit être satisfait :
\begin{align*} a_{11} y_1 + a_{12} y_2 + \cdots + a_{1, n-m} y_{n-m} + y_{n-m+1} & = 0\\ a_{21} y_1 + a_{22} y_2 + \cdots + a_{2, n-m} y_{n-m} + y_{n-m+2} & = 0\\ & \vdots\\ a_{m1} y_1 + a_{m2} y_2 + \cdots + a_{m, n-m} y_{n-m} + y_{n-m+m} & = 0\text{.} \end{align*}
Autrement dit, \(y_{n-m+1}, \ldots, y_n\) sont déterminés par \(y_1, \ldots, y_{n-m}\) :
\begin{align*} y_{n-m+1} & = a_{11} y_1 + a_{12} y_2 + \cdots + a_{1, n-m} y_{n-m}\\ y_{n-m+2} & = a_{21} y_1 + a_{22} y_2 + \cdots + a_{2, n-m} y_{n-m}\\ & \vdots\\ y_{n} & = a_{m1} y_1 + a_{m2} y_2 + \cdots + a_{m, n-m} y_{n-m}\text{.} \end{align*}
Par conséquent, nous pouvons poser \(x_i = y_i\) pour \(i= 1, \ldots, n - m\text{.}\)
🔗
🔗
Il serait utile de pouvoir calculer la distance minimale d’un code linéaire directement à partir de sa matrice \(H\) afin de déterminer les capacités de détection et de correction d’erreurs du code. Supposons que
\begin{align*} {\mathbf e}_1 & = (100 \cdots 00)^\transpose\\ {\mathbf e}_2 & = (010 \cdots 00)^\transpose\\ & \vdots\\ {\mathbf e}_n & = (000 \cdots 01)^\transpose \end{align*}
sont les \(n\)-uplets de \({\mathbb Z}_2^n\) de poids \(1\text{.}\) Pour une matrice binaire \(m \times n\) \(H\text{,}\) \(H{\mathbf e}_i\) est exactement la \(i\)-ème colonne de la matrice \(H\text{.}\)
🔗

Exemple 8.3.7.

Observons que
\begin{equation*} \begin{pmatrix} 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \\ 0 \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix}\text{.} \end{equation*}
🔗
🔗
Nous énonçons ce résultat dans la proposition suivante et laissons la démonstration en exercice.
🔗

Démonstration.

Supposons que \(\Null(H)\) est un code de détection d’erreur simple. Alors la distance minimale du code doit être au moins \(2\text{.}\) Puisque le noyau est un code de groupe, il suffit d’exiger que le code ne contienne aucun mot de code de poids inférieur à \(2\) autre que le mot de code nul. C’est-à-dire que \({\mathbf e}_i\) ne doit pas être un mot de code pour \(i = 1, \ldots, n\text{.}\) Puisque \(H{\mathbf e}_i\) est la \(i\)-ème colonne de \(H\text{,}\) la seule façon dont \({\mathbf e}_i\) pourrait être dans le noyau de \(H\) serait si la \(i\)-ème colonne était entièrement nulle, ce qui est impossible ; par conséquent, le code doit avoir la capacité de détecter au moins les erreurs simples.
🔗
Réciproquement, supposons qu’aucune colonne de \(H\) n’est la colonne nulle. Par Proposition 8.3.8, \(H{\mathbf e}_i \neq {\mathbf 0}\text{.}\)
🔗
🔗

Exemple 8.3.10.

Si nous considérons les matrices
\begin{equation*} H_1 = \begin{pmatrix} 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1 \end{pmatrix} \end{equation*}
et
\begin{equation*} H_2 = \begin{pmatrix} 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 \end{pmatrix}\text{,} \end{equation*}
alors le noyau de \(H_1\) est un code de détection d’erreur simple et le noyau de \(H_2\) ne l’est pas.
🔗
🔗
Nous pouvons même faire mieux que Théorème 8.3.9. Ce théorème nous donne des conditions sur une matrice \(H\) qui nous indiquent quand le poids minimal du code formé par le noyau de \(H\) est \(2\text{.}\) Nous pouvons également déterminer quand la distance minimale d’un code linéaire est \(3\) en examinant la matrice correspondante.
🔗

Exemple 8.3.11.

Si nous posons
\begin{equation*} H = \begin{pmatrix} 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 \end{pmatrix} \end{equation*}
et voulons déterminer si \(H\) est ou non la matrice de contrôle de parité canonique d’un code correcteur d’erreurs, il est nécessaire de s’assurer que \(\Null(H)\) ne contient aucun \(4\)-uplet de poids \(2\text{.}\) C’est-à-dire que \((1100)\text{,}\) \((1010)\text{,}\) \((1001)\text{,}\) \((0110)\text{,}\) \((0101)\) et \((0011)\) ne doivent pas être dans \(\Null(H)\text{.}\) Le théorème suivant affirme que nous pouvons effectivement déterminer que le code généré par \(H\) est correcteur d’erreurs en examinant les colonnes de \(H\text{.}\) Remarquez dans cet exemple que non seulement \(H\) n’a pas de colonnes nulles, mais aussi qu’aucune des deux colonnes n’est identique.
🔗
🔗

Démonstration.

Le \(n\)-uplet \({\mathbf e}_{i} +{\mathbf e}_{j}\) a des \(1\)s aux \(i\)-ème et \(j\)-ème entrées et des 0s ailleurs, et \(w( {\mathbf e}_{i} +{\mathbf e}_{j}) = 2\) pour \(i \neq j\text{.}\) Puisque
\begin{equation*} {\mathbf 0} = H({\mathbf e}_{i} +{\mathbf e}_{j}) = H{\mathbf e}_{i} + H{\mathbf e}_{j} \end{equation*}
ne peut se produire que si les \(i\)-ème et \(j\)-ème colonnes sont identiques, le noyau de \(H\) est un code correcteur d’erreur simple.
🔗
🔗
Supposons maintenant que nous avons une matrice de contrôle de parité canonique \(H\) avec trois lignes. Nous pourrions alors nous demander combien de colonnes supplémentaires nous pouvons ajouter à la matrice tout en conservant un noyau qui est un code de détection et de correction d’erreur simple. Puisque chaque colonne a trois entrées, il y a \(2^3 = 8\) colonnes distinctes possibles. Nous ne pouvons pas ajouter les colonnes
\begin{equation*} \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix}, \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix}, \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix}, \begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix}\text{.} \end{equation*}
Donc nous pouvons ajouter jusqu’à quatre colonnes tout en maintenant une distance minimale de \(3\text{.}\)
🔗
En général, si \(H\) est une matrice de contrôle de parité canonique \(m \times n\text{,}\) alors il y a \(n-m\) positions d’information dans chaque mot de code. Chaque colonne a \(m\) bits, donc il y a \(2^m\) colonnes distinctes possibles. Il est nécessaire que les colonnes \({\mathbf 0}, {\mathbf e}_1, \ldots, {\mathbf e}_m\) soient exclues, laissant \(2^m - (1 + m)\) colonnes restantes pour l’information si nous voulons maintenir la capacité non seulement de détecter mais aussi de corriger les erreurs simples.
🔗
🔗
PrécédentTopSuivant