a) Un mot de code c ∈ C ⊂ { 0, 1}n est par définition donné par c = Gx, où G est la matrice génératrice
du code, de dimensions n × k, et x est un vecteur quelconque dans {0, 1}k. Ici,
Pour montrer que H = (A In−k) est une matrice de parité pour le code C, il faut donc vérifier que
tout mot de code c de la forme ci-dessus satisfait l'equation H c = 0. En effet, on vérifie que
en se rappelant qu’avec l’addition sur {0, 1}, a + a = 0 pour tout a.
NB: Il est également possible de montrer que si c ∈ {0, 1}n satisfait l'equation H c = 0, alors il existe x ∈ {0, 1}k tel que c = Gx.
b) Rappelons tout d'abord que la dimension d'un code C est égale au nombre de colonnes linéairement
indépendantes de sa matrice génératrice G, autrement dit à son rang. Vu que G est de dimensions
n × k et que k ≤ n, son rang ne peut être plus grand que k. D'un autre côté, vu que la partie supérieure
de G est composée ici de la matrice identité Ik, ses k colonnes sont linéairement indépendantes, et
donc dim(C) = rang(G) = k.
c) et d) Pour ces deux exemples, il est bon de rappeler ici que la distance minimale d d'un code C est égale au nombre minimum de colonnes linéairement dépendantes de H (proposition 7.7).
Dans l'exemple 1 (partie c), on a
On voit en particulier que toutes les colonnes sont différentes et non-nulles, donc que d ≥ 3 (remarque
7.8). Par contre, on voit que les colonnes 1, 5 et 8 sont linéairement dépendantes, car leur somme est
nulle. Donc d = 3. D'autre part, n = 8 et k = 4, donc 4 = k < n − d + 1 = 6: la borne de Singleton
n'est pas atteinte.
Dans l'exemple 2 (partie d), on a
A nouveau, toutes les colonnes sont différentes et non-nulles, donc d ≥ 3. Mais ici, on voit de plus,
après exploration de toutes les possibilites, qu'il n'est pas possible de trouver 3 colonnes linéairement
dépendantes (i.e., dont la somme soit nulle). Par contre, la somme des colonnes 1, 5, 7 et 8 est
nulle. Donc d = 4. On veri e que la borne de Singleton n'est pas atteinte dans ce cas non-plus:
4 = k < n − d + 1 = 5.
La matrice de paritée du code du paragraphe 7.3.4 est donnée par:
Noter que H est ici sous la forme systématique de l'exercice 7.8.1, avec
n = 6 et k = 6 − 2 = 4. La matrice génératrice du code s'écrit donc
avec x ∈ {0, 1}4 . La dimension du code vaut k = 4, et vu que deux colonnes de la matrice de parité
H sont identiques (mais qu'aucune colonne n'est identiquement nulle), on obtient par la remarque 7.8
que la distance minimale du code vaut d = 2. De façon équivalente, on vérifie que tout mot de code
généré par la matrix G a au moins deux composantes non-nulles, et qu'il existe un mot de code avec
exactement deux composantes non-nulles (p. ex., c = (1, 0, 0, 0, 1, 0)).
La matrice de parité du code de Hamming (paragraphe 7.3.5) est donnée par:
donc n = 7 et k = 7 − 3 = 4 est la dimension du code. Tout mot de code c ∈ {0, 1}7 satisfait aux
relations:
c4 + c5 + c6 + c7 = 0
c2 + c3 + c6 + c7 = 0
c1 + c3 + c5 + c7 = 0
Pour trouver les mots de ce code et sa matrice génératrice G (remarquer que cette fois, la matrice H
n'est pas sous la forme systématique de l'exercice 7.8.1), on essaye de poser
c1 = x1, c2 = x2, c3 = x3, c4 = x4
ce qui implique, en considérant les relations ci-dessus:
c5 + c6 + c7 = x4
c6 + c7 = x2 + x3
c5 + c7 = x1 + x3
En résolvant ce systeme linéaire pour c5, c6, c7, on trouve:
c5 = x2 + x3 + x4
c6 = x1 + x3 + x4 (1)
c7 = x1 + x2 + x4
Finalement, une matrice génératrice possible G pour ce code est donnée par:
La distance minimale du code est quant à elle égale à d = 3, car toutes les colonnes de H sont différentes et non-nulles, donc d ≥ 3 par la remarque 7.8, et la somme des colonnes 1, 2 et 3 de cette même matrice H est nulle. De manière équivalente, on vérifie qu'aucun mot de code c satisfaisant aux relations (1) n'a moins de 3 composantes non-nulles et que c = (1, 0, 0, 0, 0, 1, 1) en a exactement 3.
Remarque: Noter que la borne de Singleton k = n − d + 1 n'est atteinte par aucun des deux codes
ci-desssus.
Pour rappel, la matrice génératrice du code de Hadamard (paragraphe 7.3.6) est donnée par:
donc n = 8 et k = 3 est la dimension du code (effectivement, rang(G) = 3). D'autre part, la distance
minimale de ce code vaut d = 4, car on peut vérifier que tous les mots de code générés par G ont
exactement 4 composantes non-nulles. Encore une fois, la borne de Singleton n'est donc pas atteinte.
Pour trouver une matrice de parité pour ce code, il faut trouver toutes les relations satisfaites par une
colonne c quelconque de la matrice G. On observe que dans tous les cas, on a:
c1 = 0
c1 + c2 + c3 + c4 = 0
c1 + c2 + c5 + c6 = 0
c1 + c3 + c5 + c7 = 0
c1 + c2 + c3 + c4 + c5 + c6 + c7 + c8 = 0
Une matrice de parité possible pour ce code est donc:
et on peut vérifier que le nombre minimum de colonnes dépendantes de H vaut bien d = 4.