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(1,10,1)):
    return x^2

Choisir à la carte parmi les exercices suivants.

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. Illustrer visuellement les liens entre distance, capacité de correction et de détection, ainsi que les notions de distance de Hamming, boules, …

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

    Indications:

    • implanter une fonction pour calculer la borne de Hamming

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

  3. Déterminer 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. Simuler, 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. Implanter toute la chaîne: codage, transmission, détection, correction, décodage.

  6. Implanter 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
    Vector space of dimension 7 over Finite Field of size 2

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. Implanter l’opération cycle.

  2. Implanter une fonction code_cyclique(v) qui renvoie une base du plus petit code cyclique \(C\) contenant \(v\).

  3. Implanter une fonction qui renvoie la matrice de contrôle du code \(C\), c’est à dire une matrice \(M\) telle que \(Mv=0\) si et seulement si \(v\) est dans \(C\).

  4. Implanter le décodage par syndrome pour le code cyclique engendré par \(v\).

Exercice: Un tour de magie#

Implanter 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#