TP: Coding and decoding

TP: Coding and decoding#

Preliminary exercise#

  1. Sage contains many features around coding. An entry point is codes? and the thematic tutorial coding theory. Take a look at it.

  2. Try the following example and see the @interact documentation:

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

Pure Python variation:

from ipywidgets import IntSlider

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

Today’s menu of the chef#

Choose from the following a la carte exercises, and prepare a brief illustration.

Exercise: illustrating a course on coding theory#

Develop a computer-based illustration of a point from a course on coding. For example:

  1. To visually illustrate the links between distance, capacity correction and detection, as well as the notions of distance of Hamming, spheres, etc.

  2. Determine in which (small) dimensions one can expect the existence of non-trivial perfect codes?

    Indications:

    • implement a function to calculate the Hamming bound

    • use @interact to quickly explore the values which it takes according to \(q\), \(n\), \(e\).

  3. Determine empirically which code parameters (dimension, (e.g. remote control, …) would be desirable for different applications (e.g. satellite transmission from Voyager). For example, it will be possible to calculate, based on the size, the correction capacity and the error rate, the probability that an erroneous message will not be detected or not be corrected. Then play with the parameters until plausible potential parameters are found.

    Note: as above

  4. Simulate, with the existing tools in Sage, a complete chain: coding, transmission, detection. Empirically estimate the probability of a message being transmitted incorrectly and not being detected. Compare with the theory.

  5. Implement the whole chain: coding, transmission, detection, correction, decoding.

  6. Implement distance calculation and perfection test functions.

For these last points, codes may be considered:

  1. described by an exhaustive list of words

  2. linear

  3. cyclic (see below)

  4. by interpolation

  5. two-stage code with interleaving, like the CIRC code used in the CDs.

Exercise: cyclic codes#

We will forget here that cyclic codes are naturally represented by ideals in \(A[X] / X^n-1\), and we will only do linear algebra.

Let \(E\) be a vector space over a finite field; typically:

F2 = GF(2)
E = F2^7; E
    Vector space of dimension 7 over Finite Field of size 2

Consider the operation cycle(v) which takes a vector and shifts its coordinates one step to the right (modulo \(n\)). We recall that a cyclic code is a vector subspace of \(E\) which is stable by the operation cycle.

  1. Implement the operation cycle.

  2. Implement a function code_cyclique(v) that returns a basis of the smallest cyclic code \(C\) containing \(v\).

  3. Implement a function that returns the control matrix of the code \(C\) i.e. a matrix \(M\) such that \(Mv=0\) if and only if \(v\) is in \(C\).

  4. Implement syndrome decoding for the generated cyclic code by \(v\).

Exercise: A magic trick#

Implementing the text Error correcting codes, Agreg 2005.

A small example of using the interactive visual components of interactive visual components:

@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]])