Implementation of Power decoding with Multiplicities

This is a publically available repository of an implementation which is
connected with the following publication:

Power Decoding Reed--Solomon Codes Up to the Johnson Radius

by Johan Rosenkilde

Accepted for Advances in Mathematics of Communication

The code is written by me, Johan Rosenkilde

The code is documented in a self-contained fashion, but it should be
understandable for someone with the article at hand.

The repository contains the following files

  • power_mults.sheet: Examples of how to call the decoder from Codinglib (see
    below) as well as computation of failure probability bound, and the examples
    on the (lack of) relation to list-decoding from the paper.

  • failure_rate_powermults.sage: Script taking specific code and decoder
    parameters and performs a specified number of decoding attempts with random
    errors. Outputs to standard out.

  • failure_rate_simulation.sage: Script for orchestrating the large-scale
    simulation whose results are given in the paper. The actual simulation is
    carried out in parallel on multiple machines using SSH and
    failure_rate_powermults.sage. The results are saved in many files (it is
    assumed that all the machines share the same file system).

  • find_code_examples.sheet: Helper-functions for identifying code and decoder
    parameters that make for good examples under various constraints.

  • simulation_results.sage: Print the simulation results obtained using

  • From the complete simulation results, extract only
    those received words where behaviour was surprising.

  • interesting_results/: Contains the received words with surprising decoding
    behaviour observed during the simulation documented in the paper.

The code is written in Sage, and will require this to run.
The source file(s) mention the latest version of Sage for which I have verified
they work. The code also requires installation of Codinglib, my library of
functions and algorithms for algebraic coding theory. In fact, the bulk of the
algorithm and work might well be done by Codinglib, and as such, the
implementation here can be seen as calling examples of the
library. Before running the code in the files of this repository, one needs to
import Codinglib into the running Sage process:

from codinglib import *

The code here is structured into .sheet-files. They are clear-text analogues
of the Sage Notebook's worksheets. Such a file is not meant to be imported as a
whole, but rather evaluated block by block in a Sage process. In a sheet file,
the blocks are delimited by lines starting with ###, usually followed by a
one-line description of their contents. Possibly, the file is further
sub-structured by visibly larger whitespace. Usually, the first few blocks will
contain definitions, implementing the algorithms and helper functions. The
latter blocks then set up examples and objects for input in the algorithms.

The latter blocks of the sheet might also contain code for creating plots or
running the simulations included in the paper.

If you are using Emacs, then working with .sheet-files can be conveniently
accomplished using sage-mode, where the file sage-blocks.el
contains block-specific functionality.

This code is released under the GPL v3 or later to conform with Sage's

You are welcome to contact me for questions on the implementation or its usage,
or, of course, a discussion of the paper.

Johan Rosenkilde