Coding Theory in Sage

Author: David Joyner and Robert Miller (2008), edited by Ralf Stephan for the initial version. David Lucas (2016) for this version.

This tutorial, designed for beginners who want to discover how to use Sage for their work (research, experimentation, teaching) on coding theory, will present several key features of Sage’s coding theory library and explain how to find classes and methods you look for.

During this tutorial, we will cover the following parts:

  • what can you do with generic linear codes and associated methods,
  • what can you do with structured code families,
  • what can you do to encode and recover messages, correct errors and
  • what can you do to easily add errors to codewords.

The goal of this tutorial is to give a quick overview of what can be done with the library and how to use the main functionalities. It is neither a comprehensive description of all methods nor of specific classes. If one needs some specific information on the behaviour of a class/method related to coding theory, one should check the documentation for this class/method.

I. Generic Linear codes and associated methods

Let us start with the most generic code one can build: a generic linear code without any specific structure.

To build such a code, one just need to provide its generator matrix, as follows:

sage: G = matrix(GF(3), [[1, 0, 0, 0, 1, 2, 1],
....:                    [0, 1, 0, 0, 2, 1, 0],
....:                    [0, 0, 1, 2, 2, 2, 2]])
sage: C = LinearCode(G)

With these lines, you just created a linear code, congratulations! Note that if you pass a matrix which is not full rank, Sage will turn it into a full-rank matrix before building the code, as illustrated in the following example:

sage: G = matrix(GF(3), [[1, 0, 0, 0, 1, 2, 1],
....:                    [0, 1, 0, 0, 2, 1, 0],
....:                    [0, 0, 1, 2, 2, 2, 2],
....:                    [1, 0, 1, 2, 0, 1, 0]]) #r3 = r0 + r2
sage: C = LinearCode(G)
sage: C.generator_matrix()
[1 0 0 0 1 2 1]
[0 1 0 0 2 1 0]
[0 0 1 2 2 2 2]

We now have a linear code… What can we do with it? As we can a lot of things, let us start with the basic functionalities.

In the example just above, we already asked for the code’s generator matrix. It is also possible to ask the code for its basic parameters: its length and dimension as illustrated therafter:

sage: C.length()
7
sage: C.dimension()
3

It is also possible to ask for our code’s minimum distance:

sage: C.minimum_distance()
3

Of course, as C is a generic linear code, an exhaustive search algorithm is run to find the minimum distance, which will be slower and slower as the code grows.

By just typing the name of our code, we get a sentence which briefly describes it and gives its parameters:

sage: C
[7, 3] linear code over GF(3)

As the aim of this tutorial is not to give a comprehensive view of the methods, we won’t describe any other methods.

If one wants to get all methods that can be run on a linear code, one can:

  • either check the manual page of the file Linear codes

  • or type:

    C.<tab>

    in Sage to get a list of all available methods for C. Afterwards, typing:

    C.method?

    will show the manual page for method.

Note

Some generic methods require the installation of the optional package Guava for Gap. While some work is done to always propose a default implementation which does not require an optional package, there exist some methods which are not up to date - yet. If you’re receiving an error message related to Gap, please check the documentation of the method to verify if Guava has to be installed.

II. Structured code families and an overview of the encoding and decoding system

II.1 Create specific codes in Sage

Now that we know how to create generic linear codes, we want to go deeper and create specific code families. In Sage, all codes families can be accessed by typing:

codes.<tab>

Doing so, you will get the comprehensive list of all code families Sage can build.

For the rest of this section, we will illustrate specific functionalities of these code families by manipulating sage.coding.grs_code.GeneralizedReedSolomonCode.

So, for starters, we want to create a Generalized Reed-Solomon (GRS) code.

By clicking on the link provided above, or typing:

codes.GeneralizedReedSolomonCode?

one can access the documentation page for GRS codes, find a definition of these and learn what is needed to build one in Sage.

Here we choose to build a [12, 6] GRS code over \(\GF{13}\). To do this, we need up to three elements:

  • The list of evaluation points,
  • the dimension of the code, and
  • optionally, the list of column multipliers.

We build our code as follows:

sage: F = GF(13)
sage: length, dimension = 12, 6
sage: evaluation_pts = F.list()[:length]
sage: column_mults = F.list()[1:length+1]
sage: C = codes.GeneralizedReedSolomonCode(evaluation_pts, dimension, column_mults)

Our GRS code is now created. We can ask for its parameters, as we did in the previous section:

sage: C.length()
12
sage: C.dimension()
6
sage: C.base_ring()
Finite Field of size 13

It is also possible to ask for the evaluation points and the column multipliers by calling sage.coding.grs_code.GeneralizedReedSolomonCode.evaluation_points() and sage.coding.grs_code.GeneralizedReedSolomonCode.column_multipliers().

Now, if you know some theory for GRS codes, you know that it’s especially easy to compute their minimum distance, which is: \(d = n - k + 1\), where \(n\) is the length of the code and \(k\) is the dimension of the code.

Because Sage knows C is a GRS code, it will not run the exhaustive search algorithm presented in section I to find C’s minimum distance but use the operation introduced above. And you instantly get:

sage: C.minimum_distance()
7

All these parameters are summarized inside the string representation of our code:

sage: C
[12, 6, 7] Generalized Reed-Solomon Code over GF(13)

Note

Writing proper classes for code families is a work in progress. Some constructions under codes.<tab> might thus be functions which build a generic linear code, and in that case are only able to use generic algorithms. Please refer to the documentation of a construction to check if it is a function or a class.

II.2 Encode and decode in Sage

In the previous part, we learnt how to find specific code families in Sage and create instances of these families.

In this part, we will learn how to encode and decode.

First of all, we want to generate a codeword to play with. There is two different ways to do that:

  • It is possible to just generate a random element of our code, as follows:

    sage: c = C.random_element()
sage: c in C
True

  • Alternatively, we can create a message and then encode it into a codeword:

    sage: msg = random_vector(C.base_field(), C.dimension())
sage: c = C.encode(msg)
sage: c in C
True

Either way, we obtained a codeword. So, we might want to put some errors in it, and try to correct these errors afterwards. We can obviously do it by changing the values at some random positions of our codeword, but we propose here something more general: communication channels. sage.coding.channel.Channel objects are meant as abstractions for communication channels and for manipulation of data representation. In this case, we want to emulate a communication channel which adds some, but not too many, errors to a transmitted word:

sage: err = 3
sage: Chan = channels.StaticErrorRateChannel(C.ambient_space(), err)
sage: Chan
Static error rate channel creating 3 errors, of input and output space Vector space of dimension 12 over Finite Field of size 13
sage: r = Chan.transmit(c)
sage: len((c-r).nonzero_positions())
3

If you want to learn more on Channels, please refer to section IV of this tutorial.

Thanks to our channel, we got a “received word`, r, as a codeword with errors on it. We can try to correct the errors and recover the original codeword:

sage: c_dec = C.decode_to_code(r)
sage: c_dec == c
True

Perhaps we want the original message back rather than the codeword. All we have to do then is to unencode it back to the message space:

sage: m_unenc = C.unencode(c_dec)
sage: m_unenc == msg
True

It is also possible to perform the two previous operations (correct the errors and recover the original message) in one line, as illustrated below:

sage: m_unenc2 = C.decode_to_message(r)
sage: m_unenc2 == msg
True

III. A deeper view of the Encoder and Decoder structure

In the previous section, we saw that encoding, decoding and unencoding a vector can be easily done using methods directly on the code object. These methods are actually shortcuts, added for usability, for when one does not care more specifically about how encoding and decoding takes place. At some point, however, one might need more control.

This section will thus go into details on the mechanism of Encoders and Decoders.

At the core, the three mentioned operations are handled by sage.coding.encoder.Encoder and sage.coding.decoder.Decoder. These objects possess their own methods to operate on words. When one calls (as seen above):

C.encode(msg)

one actually calls the method sage.coding.encoder.Encoder.encode() on the default encoder of C. Every code object possess a list of encoders and decoders it can use. Let us see how one can explore this:

sage: C = codes.GeneralizedReedSolomonCode(GF(59).list()[:40], 12, GF(59).list()[1:41])
sage: C.encoders_available()
['EvaluationPolynomial', 'EvaluationVector', 'Systematic']
sage: C.decoders_available()
['BerlekampWelch',
 'ErrorErasure',
 'Gao',
 'GuruswamiSudan',
 'InformationSet',
 'KeyEquationSyndrome',
 'NearestNeighbor',
 'Syndrome']

We got a list of the available encoders and decoders for our GRS code. Rather than using the default ones as we did before, we can now ask for specific encoder and decoder:

sage: Evect = C.encoder("EvaluationVector")
sage: Evect
Evaluation vector-style encoder for [40, 12, 29] Generalized Reed-Solomon Code over GF(59)
sage: type(Evect)
<class 'sage.coding.grs_code.GRSEvaluationVectorEncoder'>
sage: msg = random_vector(GF(59), C.dimension()) #random
sage: c = Evect.encode(msg)
sage: NN = C.decoder("NearestNeighbor")
sage: NN
Nearest neighbor decoder for [40, 12, 29] Generalized Reed-Solomon Code over GF(59)

Calling:

C.encoder(encoder_name)

is actually a short-hand for constructing the encoder manually, by calling the constructor for sage.coding.grs_code.EncoderGRSEvaluationVector yourself. If you don’t supply encoder_name to sage.coding.linear_code.AbstractLinearCode.encoder() you get the default encoder for the code. sage.coding.linear_code.AbstractLinearCode.encoder() also has an important side-effect: it caches the constructed encoder before returning it. This means that each time one will access the same EvaluationVector encoder for C, which saves construction time.

All the above things are similar for Decoders. This reinforces that Encoders and Decoders are rarely constructed but used many times, which allows them to perform expensive precomputation at construction or first use, for the benefit of future use.

This gives a good idea of how the elements work internally. Let us now go a bit more into details on specific points.

III.1 Message spaces

The point of an Encoder is to encode messages into the code. These messages are often just vectors over the base field of the code and whose length matches the code’s dimension. But it could be anything: vectors over other fields, polynomials, or even something quite different. Therefore, each Encoder has a sage.coding.encoder.Encoder.message_space(). For instance, we saw earlier that our GRS code has two possible encoders; let us investigate the one we left behind in the part just before:

sage: Epoly = C.encoder("EvaluationPolynomial")
sage: Epoly
Evaluation polynomial-style encoder for [40, 12, 29] Generalized Reed-Solomon Code over GF(59)
sage: Epoly.message_space()
Univariate Polynomial Ring in x over Finite Field of size 59
sage: msg_p = Epoly.message_space().random_element(degree=C.dimension()-1); msg_p #random
31*x^11 + 49*x^10 + 56*x^9 + 31*x^8 + 36*x^6 + 58*x^5 + 9*x^4 + 17*x^3 + 29*x^2 + 50*x + 46

Epoly reflects that GRS codes are often constructed as evaluations of polynomials, and that a natural way to consider their messages is as polynomials of degree at most \(k-1\), where \(k\) is the dimension of the code. Notice that the message space of Epoly is all univariate polynomials: message_space is the ambient space of the messages, and sometimes an Encoder demands that the messages are actually picked from a subspace hereof.

The default encoder of a code always has a vector space as message space, so when we call sage.coding.linear_code.AbstractLinearCode.decode_to_message() or sage.coding.linear_code.AbstractLinearCode.unencode() on the code itself, as illustrated on the first example, this will always return vectors whose length is the dimension of the code.

III.2 Generator matrices

Whenever the message space of an Encoder is a vector space and it encodes using a linear map, the Encoder will possess a generator matrix (note that this notion does not make sense for other types of encoders), which specifies that linear map.

Generator matrices have been placed on Encoder objects since a code has many generator matrices, and each of these will encode messages differently. One will also find sage.coding.linear_code.AbstractLinearCode.generator_matrix() on code objects, but this is again simply a convenience method which forwards the query to the default encoder.

Let us see this in Sage, using the first encoder we constructed:

sage: Evect.message_space()
Vector space of dimension 12 over Finite Field of size 59
sage: G = Evect.generator_matrix()
sage: G == C.generator_matrix()
True

III.3 Decoders and messages

As we saw before, any code has two generic methods for decoding, called decode_to_codeword and decode_to_message. Every Decoder also has these two methods, and the methods on the code simply forward the calls to the default decoder of this code.

There are two reasons for having these two methods: convenience and speed. Convenience is clear: having both methods provides a useful shortcut depending on the user’s needs. Concerning speed, some decoders naturally decode directly to a codeword, while others directly to a message space. Supporting both methods therefore avoids unnecessary work in encoding and unencoding.

However, decode_to_message implies that there is a message space and an encoding from that space to the code behind the scenes. A Decoder has methods message_space and connected_encoder to inform the user about this. Let us illustrate that by a long example:

sage: C = codes.GeneralizedReedSolomonCode(GF(59).list()[1:41], 3, GF(59).list()[1:41])
sage: c = C.random_element()
sage: c in C
True

#Create two decoders: Syndrome and Gao
sage: Syn = C.decoder("KeyEquationSyndrome")
sage: Gao = C.decoder("Gao")

#Check their message spaces
sage: Syn.message_space()
Vector space of dimension 3 over Finite Field of size 59
sage: Gao.message_space()
Univariate Polynomial Ring in x over Finite Field of size 59

#and now we unencode
sage: Syn.decode_to_message(c) #random
(55,9,43)

sage: Gao.decode_to_message(c) #random
43*x^2 + 9*x + 55

IV. A deeper look at channels

In Section II, we briefly introduced the Channel objects as a way to put errors in a word. In this section, we will look deeper at their functionality and introduce a second Channel.

Note

Once again, we chose a specific class as a running example through all this section, as we do not want to make an exhaustive catalog of all channels. If one wants to get this list, one can access it by typing:

channels.<tab>

in Sage.

Consider again the sage.coding.channel.ChannelStaticErrorRate() from before. This is a channel that places errors in the transmitted vector but within controlled boundaries. We can describe these boundaries in two ways:

  • The first one was illustrated in Section II and consists in passing an integer, as shown below:

    sage: C = codes.GeneralizedReedSolomonCode(GF(59).list()[:40], 12)
sage: t = 14
sage: Chan = channels.StaticErrorRateChannel(C.ambient_space(), t)
sage: Chan
Static error rate channel creating 14 errors, of input and output space Vector space of dimension 40 over Finite Field of size 59

  • We can also pass a tuple of two integers, the first smaller than the second. Then each time a word is transmitted, a random number of errors between these two integers will be added:

    sage: t = (1, 14)
sage: Chan = channels.StaticErrorRateChannel(C.ambient_space(), t)
sage: Chan
Static error rate channel creating between 1 and 14 errors, of input and output space Vector space of dimension 40 over Finite Field of size 59

We already know that a channel has a sage.coding.channel.Channel.transmit() method which will perform transmission over the channel; in this case it will return the transmitted word with some errors in it. This method will always check if the provided word belongs to the input space of the channel. In a case one is absolutely certain that one’s word is in the input space, one might want to avoid this check, which is time consuming - especially if one is simulating millions of transmissions. For this usage there is sage.coding.channel.Channel.transmit_unsafe() which does the same as sage.coding.channel.Channel.transmit() but without checking the input, as illustrated thereafter:

sage: c = C.random_element()
sage: c in C
True
sage: c_trans = Chan.transmit_unsafe(c)
sage: c_trans in C
False

Note there exists a useful shortcut for sage.coding.channel.Channel.transmit()

sage: r = Chan(c)
sage: r in C
False

A channel for errors and erasures

Let us introduce a new Channel object which adds errors and erasures. When it transmits a word, it both adds some errors as well as it erases some positions:

sage: Chan = channels.ErrorErasureChannel(C.ambient_space(), 3, 4)
sage: Chan
Error-and-erasure channel creating 3 errors and 4 erasures of input space Vector space of dimension 40 over Finite Field of size 59 and output space The Cartesian product of (Vector space of dimension 40 over Finite Field of size 59, Vector space of dimension 40 over Finite Field of size 2)

The first parameter is the input space of the channel. The next two are (respectively) the number of errors and the number or erasures. Each of these can be tuples too, just as it was with sage.coding.channel.StaticErrorRateChannel. As opposed to this channel though, the output of sage.coding.channel.ErrorErasureChannel is not the same as its input space, i.e. the ambient space of C. Rather, it will return two vectors: the first is the transmitted word with the errors added and erased positions set to 0. The second one is the erasure vector whose erased positions contain ones. This is reflected in sage.coding.channel.output_space():

sage: C = codes.random_linear_code(GF(7), 10, 5)
sage: Chan.output_space()
The Cartesian product of (Vector space of dimension 40 over Finite Field of size 59, Vector space of dimension 40 over Finite Field of size 2)
sage: Chan(c) # random
((0, 3, 6, 4, 4, 0, 1, 0, 0, 1),
 (1, 0, 0, 0, 0, 1, 0, 0, 1, 0))

Note it is guaranteed by construction that errors and erasures will never overlap, so when you ask for e errors and t erasures, you will always receive a vector with e errors and t erased positions.

V. Conclusion - Afterword

This last section concludes our tutorial on coding theory.

After reading this, you should know enough to create and manipulate codes in Sage!

We did not illustrate all the content of the library in this tutorial. For instance, we did not mention how Sage manages bounds on codes.

All objects, constructions and methods related to coding theory are hidden under the prefix codes in Sage.

For instance, it is possible to find all encoders you can build by typing:

codes.encoders.<tab>

So, if you are looking for a specific object related to code, you should always type:

codes.<tab>

and check if there’s a subcategory which matches your needs.

Despite all the hard work we put on it, there’s always much to do!

Maybe at some point you might want to create your own codes for Sage. If it’s the case and if you don’t know how to do that, don’t panic! We also wrote a tutorial for this specific case, which you can find here: How to write your own classes for coding theory.