TP3 : codes hermitiens

Le but de ce TP est de construire la matrice génératrice d'un code hermitien, puis d'en implanter un algorithme de décodage.

On fixe un corps fini $\mathbb{F}_{q^2}$ dont le cardinal est un carré. On rappelle que l'ensemble des points affines de la courbe hermitienne $H_q$ (définie sur $\mathbb{F}_{q^2}$) sont alors :

$$ \{ (x,y) \in \mathbb{F}_{q^2} \mid y^{q+1} + x^q + x = 0 \}. $$

On rappelle également que la courbe hermitienne a pour genre $g = q(q-1)/2$.

Exercice 1.

Question 1 : Implanter une fonction rational_points(q) qui retourne la liste de l'ensemble des points affines de la courbe $H_q$. (indication : si on le souhaite, on pourra créer cette liste par "recherche exhaustive")

In [373]:
def rational_points(q):
    pass

On note $P_\infty$ le point à l'infini de la courbe $H_q$. Pour un certain $m \ge 0$, on note $L(mP_\infty)$ l'espace de Riemann-Roch associé au diviseur $mP_\infty$. On admet que si $2g-2 \lt m \lt q^3$, alors cet espace a pour base

$$ \{ x^i y^j \mid 0 \le i, 0 \le j \le q,\; (q+1)i + qj \le m \}, $$

où $x$ et $y$ sont les fonctions "coordonnées", qui à un point affine $P = (x_0,y_0)$ associent respectivement $x_0$ et $y_0$.

Question 2 : Implanter une fonction exponents(m, q) qui calcule la liste des couples d'entiers $(i,j)$ tels que $(q+1)i + qj \le m$.

In [374]:
def exponents(q, m):
    pass

Le code hermitien $\mathcal{C}(m)$ est le code géométrique dont les points d'évaluation sont l'ensemble des points affines de $H_q$, et dont le diviseur est $m P_\infty$.

Question 3 : Implanter une fonction generator_matrix(q, m, L=None) qui calcule une matrice génératrice du code $\mathcal{C}(m)$. Le paramètre L=None représente le fait que l'on peut passer optionnellement en paramètre la liste des points d'évaluation (pour éviter de la recalculer).

In [375]:
def generator_matrix(q, m, L=None):
    pass

Question 4 : Vérifier que pour $2g-2 \lt m \lt q^3$, la matrice obtenue à la question précédente est de rang plein et admet $q^3$ colonnes et $m + 1 - q(q-1)/2$ lignes.

In [ ]:

Question 5 : Vérifier expérimentalement (avec une petite valeur de $q$) que pour tout $0 \le m \le q^3+q^2-q-2$, les codes $\mathcal{C}(m)$ et $\mathcal{C}(q^3+q^2-q-2-m)$ sont duaux l'un de l'autre.

In [ ]:

Exercice 2.

Soient $q$ et $m$ des paramètres qui définissent le code hermitien $\mathcal{C}(m)$ de diviseur $m P_\infty$.

On suppose maintenant que l'on connaît une matrice de parité $H$ du code $\mathcal{C}(m)$. On considère alors l'algorithme de décodage suivant.

  • Entrée : un entier $t$ et un mot corrompu $y$, tel que $y = c + e$ avec $c \in \mathcal{C}$ et $\mathrm{wt}(e) = t$
  • Sortie : le mot de code $c$
  1. Définir $m' = q^3+q^2-q-2-m$ et $\ell = max(m'-t-2g+1, t+g)$.
  2. Calculer $M$, la matrice génératrice d'un code hermitien $\mathcal{A}$ de diviseur $\ell P_\infty$.
  3. Calculer $N$, la matrice génératrice d'un code hermitien $\mathcal{B}$ de diviseur $(m'-\ell) P_\infty$.
  4. Calculer $\mathcal{K}$, l'ensemble des mots $u \in \mathcal{A}$ tels que pour tout $v \in \mathcal{B}$, $\sum_{i=1}^n y_i u_i v_i = 0$. Pour cela, on peut s'aider des matrices $M$ et $N$.
  5. Choisir aléatoirement un élément non-nul $u \in \mathcal{K}$.
  6. Calculer $J = \{ j \in [1,n] \mid u_i \ne 0 \}$.
  7. Résoudre le système d'inconnue $e$ : $$ \left\{ \begin{array}{l} H e^\top = H y^\top \\ x_{|J} = 0 \end{array}\right. $$
  8. Retourner $y - e$

On admet que l'algorithme décrit ci-dessus corrige $t$ erreurs sur un mot du code hermitien $\mathcal{C}(m)$, pour tout entier $t$ tel que $t \le (d-1-g)/2$.

Question 1 : Implanter l'algorithme de décodage d'un code hermitien.

In [376]:
def decode(y, t, L, q, m):
    pass

Question 2 : Réécrire (à partir des TP précédents) les fonctions :

  • random_codeword(G) qui calcule un mot de code aléatoire à partir d'une matrice génératrice $G$ du code,
  • random_error(F, t) qui retourne un mot de poids de Hamming $t$ sur le corps fini $F$,
  • corrupt(c, t) qui corrompt le mot $c$ avec $t$ erreurs.
In [377]:
def random_codeword(G):
    pass
In [378]:
def random_error(F, t, n):
    pass
In [379]:
def corrupt(c, t):
    pass

Question 3 : Écrire un script qui permet de vérifier que l'algorithme est valide.

In [ ]:

Exercice 3 (optionnel) :

Répéter les exercices précédents avec un code elliptique (on prendra également comme points d'évaluation les points affines d'une courbe elliptique, et comme diviseur $m P_\infty$).