Coding Theory

Coding theory is the mathematical theory for algebraic and combinatorial codes used for forward error correction in communications theory. Sage provides an extensive library of objects and algorithms in coding theory.

Basic objects in coding theory are codes, channels, encoders, and decoders. The following modules provide the base classes defining them.

Catalogs for available constructions of the basic objects and for bounds on the parameters of linear codes are provided.

Linear Codes

The following module is a base class for linear code objects regardless their metric.

There is a number of representatives of linear codes over a specific metric.

Families of Linear Codes

Famous families of codes, listed below, are represented in Sage by their own classes. For some of them, implementations of special decoding algorithms or computations for structural invariants are available.

In contrast, for some code families Sage can only construct their generator matrix and has no other a priori knowledge on them:

Derived Code Constructions

Sage supports the following derived code constructions. If the constituent code is from a special code family, the derived codes inherit structural properties like decoding radius or minimum distance:

Other derived constructions that simply produce the modified generator matrix can be found among the methods of a constructed code.

Decoding

Information-set decoding for linear codes:

Guruswami-Sudan interpolation-based list decoding for Reed-Solomon codes:

Miscellaneous Modules

There is at least one module in Sage for source coding in communications theory:

Finally an experimental module used for code constructions:

Indices and Tables