TP2 : Décodage générique

Ce TP a pour objectif d'implanter deux algorithmes résolvant le problème de décodage par syndrome.

Le premier, l'algorithme de Prange, est à le fondement d'algorithmes plus avancés dits de "décodage par ensemble d'information", et permet d'obtenir une solution au problème. Le second, dite méthode de Dumer, permet quant à lui d'obtenir un ensemble de solutions au problème, et s'avère donc avantageux lorsque le nombre de solutions à trouver est de grande taille.

Exercice 1 : algorithme de Prange

Question 1. Écrire ou rappeler des fonctions qui permettent de :

  • retourner un vecteur tiré uniformément dans $\mathbb{F}_2^n$
  • calculer le poids de Hamming d'un mot de $\mathbb{F}_2^n$,
  • retourner un vecteur aléatoire de $\mathbb{F}_2^n$ de poids $w$,
  • retourner une matrice aléatoire à $k$ lignes et $n$ colonnes sur $\mathbb{F}_2$, de rang plein,
  • retourner un sous-ensemble aléatoire $I \subset \{1, \dots, n\}$ de cardinal $k$,
  • teste si un ensemble $I$ est un ensemble d'information d'un code de matrice de parité $\mathbf{H}$.
In [21]:
def random_vector(n):
    pass
In [22]:
def weight(x):
    pass
In [23]:
def random_fixed_weight(n, w):
    pass
In [24]:
def random_binary_matrix(k, n):
    pass
In [25]:
def random_subset(n, k):
    pass
In [26]:
def is_information_set(H, I):
    pass

On considère l'algorithme de Prange, comme décrit ci-dessous :

Entrée : une matrice $\mathbf{H} \in \mathbb{F}_2^{(n-k) \times n}$ de rang plein, un entier $w$ et un vecteur $\mathbf{s}$ tel que $\mathbf{s} = \mathbf{H e}$ où $\mathbf{e}$ est de poids de Hamming $w$.

Sortie : un vecteur $\mathbf{x}$ de poids de Hamming $w$ tel que $\mathbf{H x} = \mathbf{s}$.

  1. Choisir aléatoirement un ensemble d'information $I$ du code de matrice de parité $\mathbf{H}$.
  2. Résoudre le système $$ \left\{\begin{array}{l} \mathbf{x}_{|I} = \mathbf{0} \\ \mathbf{H x} = \mathbf{s} \end{array}\right. $$
  3. Si la solution $\mathbf{x}$ obtenue est de poids $w$, alors retourner $\mathbf{x}$.
  4. Sinon, revenir à l'étape 1.

Question 2 : Implanter l'algorithme de Prange.

In [27]:
def prange(H, w, s):
    pass

Question 3 : Tester votre algorithme à l'aide des fonctions écrites à la Question 1.

In [28]:
def TEST_PRANGE():
    pass

Question 4 : Intégrer à votre algorithme de Prange un compteur permettant d'estimer son nombre d'itérations. Puis, donner la complexité expérimentale de l'algorithme de Prange pour les séries de valeurs suivantes :

  • $k = n/2$, $w = \lfloor 0.11 n\rfloor$ et $n$ croissant (par exemple $30$, $32$, $34$, etc.),
  • $k = n/2$, $w$ variant entre $1$ et $n/4$, avec $n$ fixé (à $60$ ou $80$ par exemple).

Remarque importante : il y a une variance importante pour les complexités obtenues. Pour un certain triplet $(n, k, w)$, on considèrera donc la médiane de la complexité obtenue sur quelques dizaines d'échantillons.

In [ ]:

Exercice 2 : méthode de Dumer

La méthode de Dumer est un algorithme permettant de trouver un ensemble de solutions au problème de décodage par syndrome.

Dans l'exercice on suppose que $n$ est pair. Soit $J_1 \cup J_2$ une partition de $\{1, \dots, n\}$ en deux sous-ensembles de même taille. Étant donnée une matrice $\mathbf{H} \in \mathbf{F}_2^{(n-k) \times n}$, on note $\mathbf{H}_i = \mathbf{H}_{|J_i}$.

Enfin, pour $\mathbf{s} \in \mathbb{F}_2^{n-k}$, on définit : $$ \begin{array}{l} L_1 := \{ \mathbf{H_1 x_1} \mid \mathbf{x_1} \in \mathbb{F}_2^{n/2} \text{ et } |\mathbf{x_1}| = w/2 \} \subseteq \mathbf{F}_2^{n-k} \\ L_2 := \{ \mathbf{s} - \mathbf{H_2 x_2} \mid \mathbf{x_2} \in \mathbb{F}_2^{n/2} \text{ et } |\mathbf{x_2}| = w/2 \} \subseteq \mathbf{F}_2^{n-k} \end{array} $$ Ces listes peuvent être de taille importante, en moyenne $\binom{n/2}{w/2}$.

L'idée de la méthode de Dumer est de chercher une collision entre les listes $L_1$ et $L_2$ : si $\mathbf{H_1 x_1} = \mathbf{s} - \mathbf{H_2 x_2}$ et si $\mathbf{x_1}$ et $\mathbf{x_2}$ ont poids $w/2$, alors le vecteur $\mathbf{x} = (\mathbf{x_1}, \mathbf{x_2})$ est solution en poids $w$ du problème de décodage par syndrome.

Bien entendu, l'existence d'une collision entre les listes dépend du bon choix de $J_1$ et $J_2$ (qui, dans un sens, doivent partitionner équitablement l'erreur). Comme pour l'algotihme de Prange, on réitière donc des tirages aléatoires de $J_1$, $J_2$ jusqu'à obtenir une solution convenable.

Méthode de Dumer

Entrée : une matrice $\mathbf{H} \in \mathbb{F}_2^{n-k}$, un entier $w$ et un syndrome $\mathbf{s} = \mathbf{H e}$ où $\mathbf{e}$ est de poids $w$.

Sortie : un ensemble de vecteurs $\mathbf{x}$ de poids $w$ tels que $\mathbf{H x} = \mathbf{s}$.

  1. Choisir aléatoirement $J_1 \cup J_2$ une partition de $\{1, \dots, n\}$.
  2. Construire les dictionnaires associés aux listes $L_1$, $L_2$ comme définies plus haut.
  3. Calculer l'ensemble des préimages $\{ (\mathbf{x_1}, \mathbf{x_2}) \}$ des collisions obtenues.
  4. Si cet ensemble est vide, revenir à 1.
  5. Sinon, retourner les vecteurs $\{ (\mathbf{x} = \mathbf{x_1}, \mathbf{x_2}) \} \subseteq \mathbb{F}_2^n$ issus des collisions.

Question 1. Implanter la méthode de Dumer. On pourra utiliser des fonctions déjà écrites dans l'exercice 1.

In [29]:
def dumer(H, w, s):
    pass

Question 2. Tester votre implantation avec de petits exemples (par exemple $n = 20$, $k = 10$, $w = 8$).

In [30]:
def TEST_DUMER():
    pass