TP: Coding and decoding
TP: Coding and decoding#
Sage contains many features around coding. An entry point is
codes?and the thematic tutorial coding theory. Take a look at it.
Try the following example and see the
@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
Exercise: illustrating a course on coding theory#
Develop a computer-based illustration of a point from a course on coding. For example:
To visually illustrate the links between distance, capacity correction and detection, as well as the notions of distance of Hamming, spheres, etc.
Determine in which (small) dimensions one can expect the existence of non-trivial perfect codes?
implement a function to calculate the Hamming bound
@interactto quickly explore the values which it takes according to \(q\), \(n\), \(e\).
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
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.
Implement the whole chain: coding, transmission, detection, correction, decoding.
Implement distance calculation and perfection test functions.
For these last points, codes may be considered:
described by an exhaustive list of words
cyclic (see below)
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
Implement the operation
Implement a function
code_cyclique(v)that returns a base of the smallest cyclic code \(C\) containing \(v\).
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\).
Implementing syndrome decoding for the generated cyclic code by \(v\).
Exercise: A magic trick#
Implementing the text conjuring trick 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]])