# How to write your own classes for coding theory¶

*Author: David Lucas*

This tutorial, designed for advanced users who want to build their own classes, will explain step by step what you need to do to write code which integrates well in the framework of coding theory. During this tutorial, we will cover the following parts:

- how to write a new
**code family** - how to write a new
**encoder** - how to write a new
**decoder** - how to write a new
**channel**

Through all this tutorial, we will follow the same example, namely the implementation of repetition code. At the end of each part, we will summarize every important step of the implementation. If one just wants a quick access to the implementation of one of the objects cited above, one can jump directly to the end of related part, which presents a summary of what to do.

Table of contents

## I. The repetition code¶

We want to implement in Sage the well-known repetition code. Its definition follows:

the \((n, 1)\)-repetition code over \(\GF{q}\) is the code formed by all the vectors of \(\GF{q}^{n}\) of the form \((i, i, i, \dots, i)\) for all \(i \in \GF{q}\).

For example, the \((3, 1)\)-repetition code over \(\GF{2}\) is: \(C = \{(0, 0, 0), (1, 1, 1)\}\).

The encoding is very simple, it only consists in repeating \(n\) times the input symbol and pick the vector thus formed.

The decoding uses majority voting to select the right symbol (over \(\GF{2}\)). If we receive the word \((1, 0, 1)\) (example cont’d), we deduce that the original word was \((1)\). It can correct up to \(\left\lceil \frac{n-1}{2} \right\rceil\) errors.

Through all this tutorial, we will illustrate the implementation of the \((n, 1)\)-repetition code over \(\GF{2}\).

## II. Write a new code class¶

The first thing to do to write a new code class is to identify the following elements:

- the length of the code,
- the base field of the code,
- the default encoder for the code,
- the default decoder for the code and
- any other useful argument we want to set at construction time.

For our code, we know its length, its dimension, its base field, one encoder and one decoder.

Now we isolated the parameters of the code, we can write the
constructor of our class.
Every linear code class must inherit from
`sage.coding.linear_code.AbstractLinearCode`

.
This class provide a lot of useful methods and, as we illustrate thereafter,
a default constructor which sets the *length*, the *base field*,
the *default encoder* and the *default decoder* as class parameters.
We also need to create the dictionary of known encoders and decoders
for the class.

Let us now write the constructor for our code class,
that we store in some file called `repetition_code.py`

:

```
sage: from sage.coding.linear_code import AbstractLinearCode
sage: from sage.rings.finite_rings.finite_field_constructor import FiniteField as GF
sage: class BinaryRepetitionCode(AbstractLinearCode):
....: _registered_encoders = {}
....: _registered_decoders = {}
....: def __init__(self, length):
....: super(BinaryRepetitionCode, self).__init__(GF(2), length,
....: "RepetitionGeneratorMatrixEncoder", "MajorityVoteDecoder")
....: self._dimension = 1
```

As you notice, the constructor is really simple. Most of the work is indeed
managed by the topclass through the `super`

statement.
Note that the dimension is not set by the abstract class, because for some
code families the exact dimension is hard to compute.
If the exact dimension is known, set it using `_dimension`

as a class parameter.

We can now write representation methods for our code class:

```
sage: def _repr_(self):
....: return "Binary repetition code of length %s" % self.length()
sage: def _latex_(self):
....: return "\textnormal{Binary repetition code of length } %s" % self.length()
```

We also write a method to check equality:

```
sage: def __eq__(self, other):
....: return (isinstance(other, BinaryRepetitionCode)
....: and self.length() == other.length()
....: and self.dimension() == other.dimension())
```

After these examples, you probably noticed that we use two methods,
namely `length()`

and `dimension()`

without defining them.
That is because their implementation is provided in
`sage.coding.linear_code.AbstractLinearCode`

.
The abstract class provides a default implementation of the
following getter methods:

`sage.coding.linear_code.AbstractLinearCode.dimension()`

`sage.coding.linear_code.AbstractLinearCode.length()`

,`sage.coding.linear_code.AbstractLinearCode.base_field()`

and`sage.coding.linear_code.AbstractLinearCode.ambient_space()`

.

It also provides an implementation of `__ne__`

which returns the inverse
of `__eq__`

and several other very useful methods, like `__contains__`

.
Note that a lot of these other methods rely on the computation of a generator
matrix. It is thus highly recommended to set an encoder which
knows how to compute such a matrix as default encoder.
As default encoder will be used by all these methods which expect a
generator matrix, if one provides a default encoder which does not have a
`generator_matrix`

method, a lot of generic methods will fail.

As our code family is really simple, we do not need anything else, and the code provided above is enough to describe properly a repetition code.

### Summary of the implementation for linear codes¶

Inherit from

`sage.coding.linear_code.AbstractLinearCode`

.Add

`_registered_encoders = {}`

and`_registered_decoders = {}`

as class variables.Add this line in the class’ constructor:

super(ClassName, self).__init__(base_field, length, "DefaultEncoder", "DefaultDecoder")

Implement representation methods (not mandatory, but highly advised)

`_repr_`

and`_latex_`

.Implement

`__eq__`

.`__ne__`

,`length`

and`dimension`

come with the abstract class.

Please note that `dimension`

will not work is there is no field
`_dimension`

as class parameter.

We now know how to write a new code class. Let us see how to write a new encoder and a new decoder.

## III. Write a new encoder class¶

Let us continue our example. We ask the same question as before:
what do we need to describe the encoder?
For most of the cases (this one included), we only need the associated code.
In that case, writing the constructor is really straightforward
(we store the code in the same `.py`

file as the code class):

```
sage: from sage.coding.encoder import Encoder
sage: class BinaryRepetitionCodeGeneratorMatrixEncoder(Encoder):
....: def __init__(self, code):
....: super(BinaryRepetitionCodeGeneratorMatrixEncoder, self).__init__(code)
```

Same thing as before, as an encoder always needs to know its associated code,
the work can be done by the base class.
Remember to inherit from `sage.coding.encoder.Encoder`

!

We also want to override representation methods `_repr_`

and `_latex_`

:

```
sage: def _repr_(self):
....: return "Binary repetition encoder for the %s" % self.code()
sage: def _latex_(self):
....: return "\textnormal{Binary repetition encoder for the } %s" % self.code()
```

And we want to have an equality check too:

```
sage: def __eq__(self, other):
....: return (isinstance(other, BinaryRepetitionCodeGeneratorMatrixEncoder)
....: and self.code() == other.code())
```

As before, default getter method is provided by the topclass,
namely `sage.coding.encoder.Encoder.code()`

.

All we have to do is to implement the methods related to the encoding. This implementation changes quite a lot whether we have a generator matrix or not.

### We have a generator matrix¶

In that case, the message space is a vector space, and it is especially easy:
the only method you need to implement is `generator_matrix`

.

Continuing our example, it will be:

```
sage: def generator_matrix(self):
....: n = self.code().length()
....: return Matrix(GF(2), 1, n, [GF(2).one()] * n)
```

As the topclass provides default implementation for encode and the inverse
operation, that we call *unencode*
(see: `sage.coding.encoder.Encoder.encode()`

and
`sage.coding.encoder.Encoder.unencode()`

), alongside
with a default implementation of
`sage.coding.encoder.Encoder.message_space()`

, our work here is done.

Note

Default `encode`

method multiplies the provide word by the generator
matrix, while default `unencode`

computes an information set for
the generator matrix, inverses it and performs a matrix-vector
multiplication to recover the original message.
If one has a better implementation for one’s specific code family,
one should obviously override the default `encode`

and `unencode`

.

### We do not have any generator matrix¶

In that case, we need to override several methods, namely `encode`

,
`unencode_nocheck`

and probably `message_space`

(in the case where
the message space is not a vector space). Note that the default
implementation of `sage.coding.encoder.Encoder.unencode()`

relies on
`unencode_nocheck`

, so reimplementing the former is not necessary.

In our example, it is easy to create an encoder which does not need a generator matrix to perform the encoding and the unencoding. We propose the following implementation:

```
sage: def encode(self, message):
....: return vector(GF(2), [message] * self.code().length())
sage: def unencode_nocheck(self, word):
....: return word[0]
sage: def message_space(self):
....: return GF(2)
```

Our work here is done.

We need to do one extra thing: set this encoder in the dictionary of known encoders for the associated code class. To do that, just add the following line at the end of your file:

```
BinaryRepetitionCode._registered_encoders["RepetitionGeneratorMatrixEncoder"] = BinaryRepetitionCodeGeneratorMatrixEncoder
```

Note

In case you are implementing a generic encoder (an encoder which works
with any family of linear codes), please add the following statement in
`AbstractLinearCode`

’s constructor instead:
`self._registered_encoders["EncName"] = MyGenericEncoder`

.
This will make it immediately available to any code
class which inherits from \(AbstractLinearCode\).

### Summary of the implementation for encoders¶

Inherit from

`sage.coding.encoder.Encoder`

.Add this line in the class’ constructor:

super(ClassName, self).__init__(associated_code)

Implement representation methods (not mandatory)

`_repr_`

and`_latex_`

.Implement

`__eq__`

`__ne__`

,`code`

come with the abstract class.If a generator matrix is known, override

`generator_matrix`

.Else override

`encode`

,`unencode_nocheck`

and if needed`message_space`

.Add the encoder to

`CodeClass._registered_encoders`

.

## IV. Write a new decoder class¶

Let us continue by writing a decoder. As before, we need to know what is
required to describe a decoder. We need of course the associated code of
the decoder. We also want to know which `Encoder`

we should use when we
try to recover the original message from a received word containing errors.
We call this encoder `connected_encoder`

.
As different decoding algorithms do not have the same behaviour
(e.g. probabilistic decoding vs deterministic), we would like to give a few
clues about the type of a decoder. So we can store a list of keywords in the
class parameter `_decoder_type`

.
Eventually, we also need to know the input space of the decoder.
As usual, initializing these parameters can be delegated to the topclass,
and our constructor looks like that:

```
sage: from sage.coding.decoder import Decoder
sage: class BinaryRepetitionCodeMajorityVoteDecoder(Decoder):
....: def __init__(self, code):
....: super((BinaryRepetitionCodeMajorityVoteDecoder, self).__init__(code,
....: code.ambient_space(), "RepetitionGeneratorMatrixEncoder"))
```

Remember to inherit from `sage.coding.decoder.Decoder`

!

As `_decoder_type`

is actually a class parameter, one should set it
in the file itself, outside of any method.
For readability, we suggest to add this statement at the bottom of the file.
We’ll get back to this in a moment.

We also want to override representation methods `_repr_`

and `_latex_`

:

```
sage: def _repr_(self):
....: return "Majority vote-based decoder for the %s" % self.code()
sage: def _latex_(self):
....: return "\textnormal{Majority vote based-decoder for the } %s" % self.code()
```

And we want to have an equality check too:

```
sage: def __eq__(self, other):
....: return isinstance((other, BinaryRepetitionCodeMajorityVoteDecoder)
....: and self.code() == other.code())
```

As before, default getter methods are provided by the topclass, namely
`sage.coding.decoder.Decoder.code()`

,
`sage.coding.decoder.Decoder.input_space()`

,
`sage.coding.decoder.Decoder.decoder_type()`

and
`sage.coding.decoder.Decoder.connected_encoder()`

.

All we have to do know is to implement the methods related to the decoding.

There are two methods, namely
`sage.coding.decoder.Decoder.decode_to_code()`

and `sage.coding.decoder.Decoder.decode_to_message()`

.

By the magic of default implementation, these two are linked, as
`decode_to_message`

calls first `decode_to_code`

and then
`unencode`

, while `decode_to_code`

calls successively
`decode_to_message`

and `encode`

.
So we only need to implement one of these two, and we choose
to override `decode_to_code`

:

```
sage: def decode_to_code(self, word):
....: list_word = word.list()
....: count_one = list_word.count(GF(2).one())
....: n = self.code().length()
....: length = len(list_word)
....: F = GF(2)
....: if count_one > length / 2:
....: return vector(F, [F.one()] * n)
....: elif count_one < length / 2:
....: return vector(F, [F.zero()] * n)
....: else:
....: raise DecodingError("impossible to find a majority")
```

Note

One notices that if default `decode_to_code`

calls default
`decode_to_message`

and default `decode_to_message`

calls default
`decode_to_code`

, if none is overriden and one is called,
it will end up stuck in an infinite loop. We added a trigger guard
against this, so if none is overriden and one is called,
an exception will be raised.

Only one method is missing: one to provide to the user the number of
errors our decoder can decode.
This is the method `sage.coding.decoder.Decoder.decoding_radius()`

,
which we override:

```
sage: def decoding_radius(self):
....: return (self.code().length()-1) // 2
```

As for some cases, the decoding might not be precisely known, its
implementation is not mandatory in `sage.coding.decoder.Decoder`

’s
subclasses.

We need to do one extra thing: set this encoder in the dictionary of known decoders for the associated code class. To do that, just add the following line at the end of your file:

```
BinaryRepetitionCode._registered_decoders["MajorityVoteDecoder"] = BinaryRepetitionCodeMajorityVoteDecoder
```

Also put this line to set `decoder_type`

:

```
BinaryRepetitionCode._decoder_type = {"hard-decision", "unique"}
```

Note

In case you are implementing a generic decoder (a decoder which works
with any family of linear codes), please add the following statement in
`AbstractLinearCode`

’s constructor instead:
`self._registered_decoders["DecName"] = MyGenericDecoder`

.
This will make it immediately available to any code
class which inherits from \(AbstractLinearCode\).

### Summary of the implementation for decoders¶

Inherit from

`sage.coding.decoder.Decoder`

.Add this line in the class’ constructor:

super(ClassName, self).__init__(associated_code, input_space, connected_encoder_name, decoder_type)

Implement representation methods (not mandatory)

`_repr_`

and`_latex_`

.Implement

`__eq__`

.`__ne__`

,`code`

,`connected_encoder`

,`decoder_type`

come with the abstract class.Override

`decode_to_code`

or`decode_to_message`

and`decoding_radius`

.Add the encoder to

`CodeClass._registered_decoders`

.

## V. Write a new channel class¶

Alongside all these new structures directly related to codes, we also propose a whole new and shiny structure to experiment on codes, and more specifically on their decoding.

Indeed, we implemented a structure to emulate real-world communication channels.

I’ll propose here a step-by-step implementation of a dummy channel for example’s sake.

We will implement a very naive channel which works only for words over \(\GF{2}\) and flips as many bits as requested by the user.

As channels are not directly related to code families, but more to
vectors and words, we have a specific file, `channel_constructions.py`

to store them.

So we will just add our new class in this file.

For starters, we ask ourselves the eternal question: What do we need to
describe a channel?
Well, we mandatorily need its `input_space`

and its `output_space`

.
Of course, in most of the cases, the user will be able to provide some extra
information on the channel’s behaviour.
In our case, it will be the number of bits to flip (aka the number of errors).

As you might have guess, there is an abstract class to take care of the mandatory arguments! Plus, in our case, as this channel only works for vectors over \(\GF{2}\), the input and output spaces are the same. Let us write the constructor of our new channel class:

```
sage: from sage.coding.channel_constructions import Channel
sage: class BinaryStaticErrorRateChannel(Channel):
....: def __init__(self, space, number_errors):
....: if space.base_ring() is not GF(2):
....: raise ValueError("Provided space must be a vector space over GF(2)")
....: if number_errors > space.dimension():
....: raise ValueErrors("number_errors cannot be bigger than input space's dimension")
....: super(BinaryStaticErrorRateChannel, self).__init__(space, space)
....: self._number_errors = number_errors
```

Remember to inherit from `sage.coding.channel_constructions.Channel`

!

We also want to override representation methods `_repr_`

and `_latex_`

:

```
sage: def _repr_(self):
....: return ("Binary static error rate channel creating %s errors, of input and output space %s"
....: % (format_interval(no_err), self.input_space()))
sage: def _latex_(self):
....: return ("\\textnormal{Static error rate channel creating %s errors, of input and output space %s}"
....: % (format_interval(no_err), self.input_space()))
```

We don’t really see any use case for equality methods
(`__eq__`

and `__ne__`

) so do not provide any default implementation.
If one needs these, one can of course override Python’s default methods.

We of course want getter methods.
There is a provided default implementation for `input_space`

and
`output_space`

, so we only need one for `number_errors`

:

```
sage: def number_errors(self):
....: return self._number_errors
```

So, now we want a method to actually add errors to words.
As it is the same thing as transmitting messages over a real-world channel,
we propose two methods, `transmit`

and `transmit_unsafe`

.
As you can guess, `transmit_unsafe`

tries to transmit the message
without checking if it is in the input space or not, while `transmit`

checks
this before the transmission… Which means that `transmit`

has a default
implementation which calls `transmit_unsafe`

.
So we only need to override `transmit_unsafe`

! Let us do it:

```
sage: def transmit_unsafe(self, message):
....: w = copy(message)
....: number_err = self.number_errors()
....: V = self.input_space()
....: F = GF(2)
....: for i in sample(xrange(V.dimension()), number_err):
....: w[i] += F.one()
....: return w
```

That is it, we now have our new channel class ready to use!

### Summary of the implementation for channels¶

Inherit from

`sage.coding.channel_constructions.Channel`

.Add this line in the class’ constructor:

super(ClassName, self).__init__(input_space, output_space)

Implement representation methods (not mandatory)

`_repr_`

and`_latex_`

.`input_space`

and`output_space`

getter methods come with the abstract class.Override

`transmit_unsafe`

.

## VI. Sort our new elements¶

As there is many code families and channels in the coding theory library, we do not wish to store all our classes directly in Sage’s global namespace.

We propose several catalog files to store our constructions, namely:

`codes_catalog.py`

,`encoders_catalog.py`

,`decoders_catalog.py`

and`channels_catalog.py`

.

Everytime one creates a new object, it should be added in the dedicated
catalog file instead of coding theory folder’s `all.py`

.

Here it means the following:

add the following in

`codes_catalog.py`

:from sage.coding.repetition_code import BinaryRepetitionCode

add the following in

`encoders_catalog.py`

:from sage.coding.repetition_code import BinaryRepetitionCodeGeneratorMatrixEncoder

add the following in

`decoders_catalog.py`

:from sage.coding.repetition_code import BinaryRepetitionCodeMajorityVoteDecoder

add the following in

`channels_catalog.py`

:from sage.coding.channel_constructions import BinaryStaticErrorRateChannel

## VII. Complete code of this tutorial¶

If you need some base code to start from, feel free to copy-paste and derive from the one that follows.

`repetition_code.py`

(with two encoders):

```
from sage.coding.linear_code import AbstractLinearCode
from sage.coding.encoder import Encoder
from sage.coding.decoder import Decoder
from sage.rings.finite_rings.finite_field_constructor import FiniteField as GF
class BinaryRepetitionCode(AbstractLinearCode):
_registered_encoders = {}
_registered_decoders = {}
def __init__(self, length):
super(BinaryRepetitionCode, self).__init__(GF(2), length, "RepetitionGeneratorMatrixEncoder", "MajorityVoteDecoder")
self._dimension = 1
def _repr_(self):
return "Binary repetition code of length %s" % self.length()
def _latex_(self):
return "\textnormal{Binary repetition code of length } %s" % self.length()
def __eq__(self, other):
return (isinstance(other, BinaryRepetitionCode)
and self.length() == other.length()
and self.dimension() == other.dimension())
class BinaryRepetitionCodeGeneratorMatrixEncoder(Encoder):
def __init__(self, code):
super(BinaryRepetitionCodeGeneratorMatrixEncoder, self).__init__(code)
def _repr_(self):
return "Binary repetition encoder for the %s" % self.code()
def _latex_(self):
return "\textnormal{Binary repetition encoder for the } %s" % self.code()
def __eq__(self, other):
return (isinstance(other, BinaryRepetitionCodeGeneratorMatrixEncoder)
and self.code() == other.code())
def generator_matrix(self):
n = self.code().length()
return Matrix(GF(2), 1, n, [GF(2).one()] * n)
class BinaryRepetitionCodeStraightforwardEncoder(Encoder):
def __init__(self, code):
super(BinaryRepetitionCodeStraightforwardEncoder, self).__init__(code)
def _repr_(self):
return "Binary repetition encoder for the %s" % self.code()
def _latex_(self):
return "\textnormal{Binary repetition encoder for the } %s" % self.code()
def __eq__(self, other):
return (isinstance(other, BinaryRepetitionCodeStraightforwardEncoder)
and self.code() == other.code())
def encode(self, message):
return vector(GF(2), [message] * self.code().length())
def unencode_nocheck(self, word):
return word[0]
def message_space(self):
return GF(2)
class BinaryRepetitionCodeMajorityVoteDecoder(Decoder):
def __init__(self, code):
super(BinaryRepetitionCodeMajorityVoteDecoder, self).__init__(code, code.ambient_space(),
"RepetitionGeneratorMatrixEncoder")
def _repr_(self):
return "Majority vote-based decoder for the %s" % self.code()
def _latex_(self):
return "\textnormal{Majority vote based-decoder for the } %s" % self.code()
def __eq__(self, other):
return (isinstance(other, BinaryRepetitionCodeMajorityVoteDecoder)
and self.code() == other.code())
def decode_to_code(self, word):
list_word = word.list()
count_one = list_word.count(GF(2).one())
n = self.code().length()
length = len(list_word)
F = GF(2)
if count_one > length / 2:
return vector(F, [F.one()] * n)
elif count_one < length / 2:
return vector(F, [F.zero()] * n)
else:
raise DecodingError("impossible to find a majority")
def decoding_radius(self):
return (self.code().length()-1) // 2
BinaryRepetitionCode._registered_encoders["RepetitionGeneratorMatrixEncoder"] = BinaryRepetitionCodeGeneratorMatrixEncoder
BinaryRepetitionCode._registered_encoders["RepetitionStraightforwardEncoder"] = BinaryRepetitionCodeStraightforwardEncoder
BinaryRepetitionCode._registered_decoders["MajorityVoteDecoder"] = BinaryRepetitionCodeMajorityVoteDecoder
BinaryRepetitionCodeMajorityVoteDecoder._decoder_type = {"hard-decision", "unique"}
```

`channel_constructions.py`

(continued):

```
class BinaryStaticErrorRateChannel(Channel):
def __init__(self, space, number_errors):
if space.base_ring() is not GF(2):
raise ValueError("Provided space must be a vector space over GF(2)")
if number_errors > space.dimension():
raise ValueErrors("number_errors cannot be bigger than input space's dimension")
super(BinaryStaticErrorRateChannel, self).__init__(space, space)
self._number_errors = number_errors
def _repr_(self):
return ("Binary static error rate channel creating %s errors, of input and output space %s"
% (format_interval(no_err), self.input_space()))
def _latex_(self):
return ("\\textnormal{Static error rate channel creating %s errors, of input and output space %s}"
% (format_interval(no_err), self.input_space()))
def number_errors(self):
return self._number_errors
def transmit_unsafe(self, message):
w = copy(message)
number_err = self.number_errors()
V = self.input_space()
F = GF(2)
for i in sample(xrange(V.dimension()), number_err):
w[i] += F.one()
return w
```

`codes_catalog.py`

(continued):

```
:class:`sage.coding.repetition_code.BinaryRepetitionCode <sage.coding.repetition_code.BinaryRepetitionCode>`
#the line above creates a link to the class in the html documentation of coding theory library
from sage.coding.repetition_code import BinaryRepetitionCode
```

`encoders_catalog.py`

(continued):

```
from sage.coding.repetition_code import (BinaryRepetitionCodeGeneratorMatrixEncoder, BinaryRepetitionCodeStraightforwardEncoder)
```

`decoders_catalog.py`

(continued):

```
from sage.coding.repetition_code import BinaryRepetitionCodeMajorityVoteDecoder
```

`channels_catalog.py`

(continued):

```
from sage.coding.channel_constructions import (ErrorErasureChannel, StaticErrorRateChannel, BinaryStaticErrorRateChannel)
```