New encoding structure for linear codes #18376
Description
For now, linear codes don't have a proper structure for encoding, "encoding" meaning handle the bijection between a message space of the code and its ambient space.
We propose in this ticket a new structure, designed to handle message -> codeword and codeword -> message transformations. The former operation is designated as encoding, the latter as unencoding.
We provide the following:
-
An abstract class
Encoder, for inheritances purposes. Every Encoder will inherit from this class. It contains:- a default constructor;
- both
encodeandunencodemethods. They come with a default implementations for encoders
whose message space is a vectorial space; - several methods to get information on the instance of the class;
generator_matrixmethod (see Design) and- explanations on what to do to create a new encoder subclass.
-
An exception class
EncodingFailure, for errors related to encoding or unencoding. -
Methods for encoding and unencoding handling in
AbstractLinearCode(see Design)
Design
Some codes families might have different message spaces. In the case of -for instance- Reed-Solomon codes, it is possible to transform elements of a Polynomial Ring into codewords, as well as elements of a vectorial space.
We wanted to be able to support encoding over all possible message spaces, which is here represented by Encoder subclasses. Continuing the Reed-Solomon example, we will have a PolynomialEncoder and a VectorialEncoder.
Considering this particularity, we chose to let encoders deal with generator matrix computation, as it
depends on the message space.
Of course, this multiplicity of objects and spaces might be confusing for people who just want to encode
elements without being bothered by all these messages spaces. So, we created a set of methods to directly
perform encoding operations on the code itself. We added a new field in AbstractLinearCode, called
default_encoder. This field indicates to the program which encoder it should use if none is specified. For instance, with a code C and a message m, one can directly call C.encode(m). In that case, the default encoder will be used to perform the encoding operation. This works for every encoder-related method, like unencode(), or generator_matrix.
As there might be numerous encoders for a same code family, we chose to maintain a dictionary of known encoders for every code family. In this ticket, only one encoder is provided, called LinearCodeGeneratorMatrixEncoder. If one wants to create an instance of this encoder for a code C, he can of course call
E = LinearCodeGeneratorMatrixEncoder(C)
but we propose something better. While calling the method C.encoders_available(), one will get a list of all known encoders for C. For any linear code, he will get ['GeneratorMatrix']. After that, he can call
E = C.encoder('GeneratorMatrix')
which will also instantiate LinearCodeGeneratorMatrixEncoder for C and cache the result as well.
So, any further call (for instance, C.encode(m, 'GeneratorMatrix')) to this encoder will be fast, and will guarantee that the same LinearCodeGeneratorMatrixEncoder will be used every time.
The dictionary of available encoders for every code family is filled in __init__.py, as any instance of a subclass has to know some specific encoders. Furthermore, it is possible to add an encoder subclass for a specific instance of a code using the method add_encoder.
With this design, we are able to satisfy specific experimentation which requires specific encoders as well as generic experimentation for which any encoder will be fine.
Users will probably most often use and expect the message space F^k,
where k is the dimension of the code, and F the field. For this reason,
the default encoder should be an encoder with this message space, such
that C.encode(m) expects m from F^k and C.unencode(c) returns an
element of F^k.
We also now have a default implementation of generator_matrix in AbstractLinearCode which calls the generator_matrix method of the selected encoder.
CC: @johanrosenkilde @jpflori @videlec @defeo @sagetrac-danielaugot @ClementPernet
Component: coding theory
Author: David Lucas
Branch/Commit: 09cff05
Reviewer: Johan Sebastian Rosenkilde Nielsen
Issue created by migration from https://trac.sagemath.org/ticket/18376