1.
Pourquoi le schéma d’encodage suivant n’est-il pas acceptable ?
| Information | \(0\) | \(1\) | \(2\) | \(3\) | \(4\) | \(5\) | \(6\) | \(7\) | \(8\) |
| Mot de code | \(000\) | \(001\) | \(010\) | \(011\) | \(101\) | \(110\) | \(111\) | \(000\) | \(001\) |
Exercices 8.6 Exercices
2.
Sans effectuer d’addition, expliquez pourquoi l’ensemble suivant de \(4\)-uplets dans \({\mathbb Z}_2^4\) ne peut pas être un code de groupe.
\begin{equation*}
(0110) \quad (1001) \quad (1010) \quad (1100)
\end{equation*}
3.
Calculez les distances de Hamming entre les paires suivantes de \(n\)-uplets.
-
\(\displaystyle (011010), (011100)\)
-
\(\displaystyle (11110101), (01010100)\)
-
\(\displaystyle (00110), (01111)\)
-
\(\displaystyle (1001), (0111)\)
4.
Calculez les poids des \(n\)-uplets suivants.
-
\(\displaystyle (011010)\)
-
\(\displaystyle (11110101)\)
-
\(\displaystyle (01111)\)
-
\(\displaystyle (1011)\)
5.
Supposons qu’un code linéaire \(C\) a un poids minimal de \(7\text{.}\) Quelles sont les capacités de détection et de correction d’erreurs de \(C\) ?
6.
Dans chacun des codes suivants, quelle est la distance minimale du code ? Quelle est la meilleure situation que nous pourrions espérer en matière de détection et de correction d’erreurs ?
-
\(\displaystyle (011010) \; (011100) \; (110111) \; (110000)\)
-
\(\displaystyle (011100) \; (011011) \; (111011) \; (100011) \\ (000000) \; (010101) \; (110100) \; (110011)\)
-
\(\displaystyle (000000) \; (011100) \; (110101) \; (110001)\)
-
\(\displaystyle (0110110) \; (0111100) \; (1110000) \; (1111111) \\ (1001001) \; (1000011) \; (0001111) \; (0000000)\)
7.
Calculez le noyau de chacune des matrices suivantes. De quel type de codes en blocs \((n,k)\) sont les noyaux ? Pouvez-vous trouver une matrice (pas nécessairement une matrice génératrice standard) qui génère chaque code ? Vos matrices génératrices sont-elles uniques ?
-
\begin{equation*} \begin{pmatrix} 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 \end{pmatrix} \end{equation*}
-
\begin{equation*} \begin{pmatrix} 1 & 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 1 \end{pmatrix} \end{equation*}
-
\begin{equation*} \begin{pmatrix} 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 \end{pmatrix} \end{equation*}
-
\begin{equation*} \begin{pmatrix} 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \end{pmatrix} \end{equation*}
Indication.
-
\((00000), (00101), (10011), (10110)\)\begin{equation*} G = \begin{pmatrix} 0 & 1 \\ 0 & 0 \\ 1 & 0 \\ 0 & 1 \\ 1 & 1 \end{pmatrix} \end{equation*}
-
\((000000), (010111), (101101), (111010)\)\begin{equation*} G = \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ 1 & 0 \\ 1 & 1 \\ 0 & 1 \\ 1 & 1 \end{pmatrix} \end{equation*}
8.
Construisez un code en blocs \((5,2)\text{.}\) Discutez des capacités de détection et de correction d’erreurs de votre code.
9.
Soit \(C\) le code obtenu à partir du noyau de la matrice
\begin{equation*}
H =
\begin{pmatrix}
0 & 1 & 0 & 0 & 1 \\
1 & 0 & 1 & 0 & 1 \\
0 & 0 & 1 & 1 & 1
\end{pmatrix}\text{.}
\end{equation*}
Décodez le message
\begin{equation*}
01111 \quad 10101 \quad 01110 \quad 00011
\end{equation*}
si possible.
10.
Supposons qu’un message binaire de \(1000\) bits est transmis. Supposons que la probabilité d’une erreur simple est \(p\) et que les erreurs se produisant dans différents bits sont indépendantes les unes des autres. Si \(p = 0.01\text{,}\) quelle est la probabilité que plus d’une erreur se produise ? Quelle est la probabilité qu’exactement deux erreurs se produisent ? Répétez ce problème pour \(p = 0.0001\text{.}\)
11.
Quelles matrices sont des matrices de contrôle de parité canoniques ? Pour les matrices qui sont des matrices de contrôle de parité canoniques, quelles sont les matrices génératrices standard correspondantes ? Quelles sont les capacités de détection et de correction d’erreurs du code généré par chacune de ces matrices ?
-
\begin{equation*} \begin{pmatrix} 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 \end{pmatrix} \end{equation*}
-
\begin{equation*} \begin{pmatrix} 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 1 \end{pmatrix} \end{equation*}
-
\begin{equation*} \begin{pmatrix} 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \end{pmatrix} \end{equation*}
-
\begin{equation*} \begin{pmatrix} 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 & 1 \end{pmatrix} \end{equation*}
Indication.
(a) Une matrice de contrôle de parité canonique avec la matrice génératrice standard
\begin{equation*}
G =
\begin{pmatrix}
1 \\ 1 \\ 0 \\ 0 \\ 1
\end{pmatrix}\text{.}
\end{equation*}
(c) Une matrice de contrôle de parité canonique avec la matrice génératrice standard
\begin{equation*}
G =
\begin{pmatrix}
1 & 0 \\
0 & 1 \\
1 & 1 \\
1 & 0
\end{pmatrix}\text{.}
\end{equation*}
12.
Listez tous les syndromes possibles pour les codes générés par chacune des matrices de Exercice 8.6.11.
13.
Soit
\begin{equation*}
H =
\begin{pmatrix}
0 & 1 & 1 & 1 & 1 \\
0 & 0 & 0 & 1 & 1 \\
1 & 0 & 1 & 0 & 1
\end{pmatrix}\text{.}
\end{equation*}
Calculez le syndrome causé par chacune des erreurs de transmission suivantes.
-
Une erreur dans le premier bit.
-
Une erreur dans le troisième bit.
-
Une erreur dans le dernier bit.
-
Des erreurs dans les troisième et quatrième bits.
14.
Soit \(C\) le code de groupe dans \({\mathbb Z}_2^3\) défini par les mots de code \((000)\) et \((111)\text{.}\) Calculez les classes latérales de \(C\) dans \({\mathbb Z}_2^3\text{.}\) Pourquoi n’a-t-il pas été nécessaire de préciser s’il s’agissait de classes latérales gauches ou droites ? Donnez l’erreur de transmission simple, le cas échéant, à laquelle correspond chaque classe latérale.
15.
Pour chacune des matrices suivantes, trouvez les classes latérales du code \(C\) correspondant. Donnez une table de décodage pour chaque code si possible.
-
\begin{equation*} \begin{pmatrix} 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 \end{pmatrix} \end{equation*}
-
\begin{equation*} \begin{pmatrix} 0 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1 \end{pmatrix} \end{equation*}
-
\begin{equation*} \begin{pmatrix} 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 \end{pmatrix} \end{equation*}
-
\begin{equation*} \begin{pmatrix} 1 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 1 & 0 \end{pmatrix} \end{equation*}
Indication.
16.
Soient \({\mathbf x}\text{,}\) \({\mathbf y}\text{,}\) et \({\mathbf z}\) des \(n\)-uplets binaires. Démontrez chacune des affirmations suivantes.
-
\(\displaystyle w({\mathbf x}) = d( {\mathbf x}, {\mathbf 0})\)
-
\(\displaystyle d( {\mathbf x}, {\mathbf y}) = d( {\mathbf x} + {\mathbf z}, {\mathbf y} + {\mathbf z} )\)
-
\(\displaystyle d({\mathbf x}, {\mathbf y}) = w({\mathbf x}- {\mathbf y})\)
17.
Une métrique sur un ensemble \(X\) est une application \(d: X \times X \rightarrow {\mathbb R}\) satisfaisant les conditions suivantes.
-
\(d( {\mathbf x}, {\mathbf y})= d( {\mathbf y}, {\mathbf x})\) ;
-
\(d( {\mathbf x}, {\mathbf y}) \leq d( {\mathbf x}, {\mathbf z}) + d( {\mathbf z}, {\mathbf y})\text{.}\)
En d’autres termes, une métrique est simplement une généralisation de la notion de distance. Démontrez que la distance de Hamming est une métrique sur \({\mathbb Z}_2^n\text{.}\) Le décodage d’un message se réduit en fait à décider quel est le mot de code le plus proche en termes de distance.
18.
Soit \(C\) un code linéaire. Montrez que soit les \(i\)-èmes coordonnées des mots de code de \(C\) sont toutes nulles, soit exactement la moitié d’entre elles sont nulles.
19.
Soit \(C\) un code linéaire. Montrez que soit tout mot de code a un poids pair, soit exactement la moitié des mots de code ont un poids pair.
20.
Montrez que les mots de code de poids pair dans un code linéaire \(C\) forment également un code linéaire.
21.
Si nous devons utiliser un code linéaire correcteur d’erreurs pour transmettre les 128 caractères ASCII, quelle taille de matrice doit être utilisée ? Quelle taille de matrice doit être utilisée pour transmettre le jeu de caractères ASCII étendu de 256 caractères ? Et si nous n’exigeons que la détection d’erreurs dans les deux cas ?
22.
Trouvez la matrice de contrôle de parité canonique qui donne le code à bit de parité paire avec trois positions d’information. Quelle est la matrice pour sept positions d’information ? Quelles sont les matrices génératrices standard correspondantes ?
23.
Combien de positions de contrôle sont nécessaires pour un code correcteur d’erreur simple avec 20 positions d’information ? Avec 32 positions d’information ?
24.
Soit \({\mathbf e}_i\) le \(n\)-uplet binaire avec un \(1\) en \(i\)-ème coordonnée et des \(0\) ailleurs, et supposons que \(H \in {\mathbb M}_{m \times n}({\mathbb Z}_2)\text{.}\) Montrez que \(H{\mathbf e}_i\) est la \(i\)-ème colonne de la matrice \(H\text{.}\)
25.
Soit \(C\) un code linéaire \((n,k)\text{.}\) Définissons le code dual ou orthogonal de \(C\) par
\begin{equation*}
C^\perp = \{ {\mathbf x} \in {\mathbb Z}_2^n : {\mathbf x} \cdot {\mathbf y} = 0 \text{ pour tout } {\mathbf y} \in C \}\text{.}
\end{equation*}
-
Trouvez le code dual du code linéaire \(C\) où \(C\) est donné par la matrice\begin{equation*} \begin{pmatrix} 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 \end{pmatrix}\text{.} \end{equation*}
-
Trouvez les matrices génératrices standard et de contrôle de parité de \(C\) et \(C^\perp\text{.}\) Que se passe-t-il en général ? Prouvez votre conjecture.
26.
Soit \(H\) une matrice \(m \times n\) sur \({\mathbb Z}_2\text{,}\) où la \(i\)-ème colonne est le nombre \(i\) écrit en binaire avec \(m\) bits. Le noyau d’une telle matrice est appelé un code de Hamming.
-
Montrez que la matrice\begin{equation*} H = \begin{pmatrix} 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 \end{pmatrix} \end{equation*}génère un code de Hamming. Quelles sont les propriétés correctrices d’erreurs d’un code de Hamming ?
-
La colonne correspondant au syndrome indique également le bit qui était erroné ; c’est-à-dire que la \(i\)-ème colonne de la matrice est \(i\) écrit comme nombre binaire, et le syndrome nous indique immédiatement quel bit est erroné. Si le mot reçu est \((101011)\text{,}\) calculez le syndrome. Dans quel bit l’erreur s’est-elle produite dans ce cas, et quel mot de code a été transmis à l’origine ?
-
Donnez une matrice binaire \(H\) pour le code de Hamming avec six positions d’information et quatre positions de contrôle. Quelles sont les positions de contrôle et quelles sont les positions d’information ? Encodez les messages \((101101)\) et \((001001)\text{.}\) Décodez les mots reçus \((0010000101)\) et \((0000101100)\text{.}\) Quels sont les syndromes possibles pour ce code ?
-
Quel est le nombre de bits de contrôle et le nombre de bits d’information dans un code de Hamming en blocs \((m,n)\) ? Donnez une borne supérieure et une borne inférieure sur le nombre de bits d’information en fonction du nombre de bits de contrôle. Les codes de Hamming ayant le nombre maximal possible de bits d’information avec \(k\) bits de contrôle sont appelés parfaits. Chaque syndrome possible sauf \({\mathbf 0}\) apparaît comme colonne. Si le nombre de bits d’information est inférieur au maximum, alors le code est dit raccourci. Dans ce cas, donnez un exemple montrant que certains syndromes peuvent représenter des erreurs multiples.
