TP: Codage et décodage

TP: Codage et décodage#

Exercice préliminaire#

  1. Sage contient de nombreuses fonctionalités autour du codage. Un point d’entrée est codes? ainsi que le tutoriel thématique coding theory. Y jeter un coup d’oeil.

  2. Essayer l’exemple suivant et consulter la documentation de @interact:

@interact
def f(x=slider(default=3,vmin=1,vmax=10)):
    return x^2

Variante en pur Python:

from ipywidgets import IntSlider

@interact
def f(x=IntSlider(value=3,min=1,max=10)):
    return x^2

Exercice: illustrer un cours sur le codage#

Mettre au point une illustration sur ordinateur d’un point d’un cours sur le codage. On pourra par exemple:

  1. Illustrez visuellement les liens entre distance, capacité de correction et de détection, ainsi que les notions de distance de Hamming, boules, …

  2. Déterminez en quelles (petites) dimensions on peut espérer l’existence de codes parfaits non triviaux?

    Indications:

    • implantez une fonction pour calculer la borne de Hamming

    • utilisez @interact pour explorer rapidement les valeurs qu’elle prend en fonction de \(q\), \(n\), \(e\).

  3. Déterminez empiriquement quels paramètres de code (dimension, distance, …) seraient souhaitables pour différentes applications (par ex. transmission satellite depuis Voyager). On pourra par exemple calculer, en fonction de la dimension, de la capacité de correction, et du taux d’erreur, la probabilité qu’un message erroné ne soit pas détecté ou pas corrigé. Puis jouer avec les paramètres jusqu’à trouver des paramètres potentiels plausibles.

    Indication: comme ci-dessus

  4. Simulez, avec les outils existant dans Sage une chaîne complète: codage, transmission, détection. Estimer empiriquement la probabilité qu’un message soit transmis incorrectement et non détecté. Comparer avec la théorie.

  5. Implantez toute la chaîne: codage, transmission, détection, correction, décodage.

  6. Implantez des fonctions de calcul de distance et test de perfection.

Pour ces derniers points, on pourra considérer des codes:

  1. décrits par une liste exhaustive de mots

  2. linéaires

  3. cycliques (voir ci-dessous)

  4. par interpolation

  5. code à deux étages avec entrelacement, comme le code CIRC utilisé dans les CDs.

Exercice: codes cycliques#

On oubliera ici que les codes cycliques sont naturellement représentés par des idéaux dans \(A[X]/(X^n-1)\), et on ne fera que de l’algèbre linéaire.

Soit \(E\) un espace vectoriel sur un corps fini; typiquement:

F2 = GF(2)
E = F2^7; E

On considère l’opération cycle(v) qui prend un vecteur et décale ses coordonnées d’un cran vers la droite (modulo \(n\)). On rappelle qu’un code cyclique est un sous-espace vectoriel de \(E\) qui est stable par l’opération cycle.

  1. Définissez l’opération cycle.

  2. Définissez une fonction code_cyclique(v) qui renvoie une matrice génératrice G du plus petit code cyclique \(C(v)\) contenant \(v\), c’est à dire une matrice dont les lignes forment une base de \(C(v)\).
    Indication: voir les méthodes row_space d’une matrice et basis_matrix d’un sous espace vectoriel.

  3. Tirez des vecteurs v aléatoires et explorez les propriétés des codes \(C(v)\) obtenus. Lorsque ces codes sont intéressants, essayez de retrouver le polynôme générateur.

  4. Définissez une fonction qui renvoie une matrice de contrôle H du code \(C(v)\), c’est à dire une matrice \(H\) telle que \(vH=0\) si et seulement si \(v\) est dans \(C(V)\).

  5. Implantez le décodage par syndrome pour le code cyclique \(C(V)\).

Exercice: Un tour de magie#

Implantez le tour de prestidigitation du texte Codes Correcteurs d’Erreurs, Agreg 2005.

Un petit exemple d’utilisation des composants visuels interactifs de Sage:

@interact
def magie(step=slider([1..5])):
    return matrix(4,4,[i for i in srange(0,32) if i.digits(base=2,padto=6)[5-step]])

Textes connexes#