TP1 : codes de Reed-Solomon

Ce TP a pour but d'implanter effectivement un code de Reed-Solomon et son algorithme de décodage.

Exercice 1 : Fonctions de base

Question : Implanter une fonction random_message(F, k) qui retourne un vecteur aléatoire tiré uniformément dans l'esspace vectoriel sur F de dimentsion k.

In [1]:
def random_message(F, k):
    pass

Question : Implanter une fonction random_error(F, n, t) qui retourne un vecteur d'erreur de poids t et de longueur n sur le corps fini F. (on pourra supposer que le nombre d'erreurs est assez faible comparé à la longueur, typiquement $t \le n$)

In [2]:
def random_error(F, n, t):
    pass

Question : En déduire une fonction corrupt(c, t) qui ajoute une erreur de poids t à un mot c.

In [3]:
def corrupt(c, t):
    pass

Question : Implanter une fonction parity_check_matrix(G) qui retourne une matrice de parité du code engendré par la matrice génératrice G.

In [4]:
def parity_check_matrix(G):
    pass
In [5]:
def TEST_PARITY_CHECK_MATRIX():
    r, k, n = 0, 6, 10
    G = random_matrix(GF(7), k, n)
    print(G * parity_check_matrix(G).transpose() == 0)

Question : Implanter une fonction systematic_form(G) qui retourne :

  • une matrice génératrice $G'$ sous forme systématique du code engendré par la matrice G
  • les indices des colonnes de $G'$ sur lequelles $G'$ est égale à l'identité
In [6]:
def systematic_form(G):
    pass
In [7]:
def TEST_SYSTEMATIC_FORM():
    r, k, n = 0, 6, 10
    while r != k:
        G = random_matrix(GF(7), k, n)
        r = G.rank()
    Gp, I = systematic_form(G)
    print(G.row_space() == Gp.row_space() and Gp[:,I] == identity_matrix(GF(7), k))

Question : Implanter une fonction uncode(G, c) qui prend en entrée une matrice génératrice G d'un code $\mathcal{C}$ et un mot c de $\mathcal{C}$, et qui retourne le message associé au mot c.

In [8]:
def uncode(G, c):
    pass
In [9]:
def TEST_UNCODE():
    r, k, n = 0, 6, 10
    while r != k:
        G = random_matrix(GF(7), k, n)
        r = G.rank()
    m = random_message(GF(7), k)
    c = m * G
    print(uncode(G, c) == m)

Exercice 2 : Codes de Reed--Solomon

Question : Implanter une fonction generator_matrix_reed_solomon(x, k) qui prend en entrée un vecteur x de points d'évaluation et un entier k, et qui retourne une matrice génératrice du code de Reed--Solomon $\mathrm{RS}_k(\mathbf{x})$.

In [10]:
def generator_matrix_reed_solomon(x, k):
    pass

Question : Implanter une fonction random_evaluation_points(F, n) qui prend en entrée un corps fini F (de cardinal $q$) et un entier n ($\le q$), et qui retourne un vecteur aléatoire de longueur n formé d'éléments de F deux à deux distincts.

In [11]:
def random_evaluation_points(F, n):
    pass

Question : Implanter une fonction get_evaluation_vector(P, x) qui prend en entrée un polynôme P et des points d'évaluation xet qui retourne le vecteur d'évaluation de P sur x.

In [12]:
def get_evaluation_vector(P, x):
    pass

Exercice 3 : Décodage de Gao

Question : Implanter une fonction interpolate(x, y) qui prend en entrée un vecteur de points d'évaluation x et un vecteur y de même longueur, et qui retourne le polynôme $P$ de plus petit degré tel que $P(x_i) = y_i$ pour tout $i$.

In [13]:
def interpolate(x, y):
    pass

Question : Implanter une fonction partial_xgcd(A, B, s) qui prend en entrée deux polynômes A et B, qui effectue l'algorithme d'Euclide étendu jusque ce que le degré du reste soit $<s$, puis qui retourne les coefficients de Bezout et le reste associé.

In [14]:
def partial_xgcd(A, B, s):
    pass

Question : Implanter l'algorithme de Gao tel que vu en TD. La fonction à implanter sera notée gao_decoding(y, x, k), et retournera un message sous la forme d'un vecteur $\mathbf{m} = (m_0, \dots, m_{k-1})$ tel que y est le mot le plus proche de get_evaluation_vector(P, x) où $P(X) = \sum_{i=0}^{k-1} m_i X^i$.

In [15]:
def gao_decoding(y, x, k):
    pass

Question : Tester votre algorithme avec la fonction suivante :

In [16]:
def TEST_GAO():
    q, n, k = 31, 26, 12
    t = (n-k)//2
    F = GF(q)
    x = random_evaluation_points(F, n)
    G = generator_matrix_reed_solomon(x, k)
    m = random_message(F, k)
    c = m * G
    y = corrupt(c, t)
    m_dec = gao_decoding(y, x, k)
    print(m == m_dec)