CodingTheory.jl

This is a minimal package for a pure Julia implementation of tools used in Coding Theory. This is the science of accurately transmitting information through a noisy channel.

Background

We assume that Alice and Bob communicate by sending sequences of symbols from a finite set Σ, which we call the alphabet. We always use q to stand for the size of the set of symbols, |Σ|. A word is a sequence of symbols from the alphabet Σ. If w₁w₂...w_n is such a word, then n is its length. We use Σⁿ to denote the set of words with length n using symbols in Σ. In general, the number of words in Σⁿ is

|Σⁿ| = qⁿ.

Block codes are codes in which Alice transmits words of a preditermined and fixed length. A code is a subset C ⊆ Σⁿ. The words in C are called code words. We say that n is the block length. We use M to stand for |C|, the number of code words. Alice has a set ℳ, some of which she wants to send to Bob, so she has the bijective encoding function

E : ℳ ⟶ C.

Similarly, Bob has a decoding function

D : Σⁿ ⟶ C ∪ {?},

Where Bob uses the ? symbol when he cannot confidently decode. So if Alice wishes to communicate a message, she transmits a code word w = E(M). w may be corrupted to w' ≠ w. Then Bob can decode w' as E^-1(D(w)). If Bob is not certain how to decode, then D(w') may be '?', which means that Bob can tell an error has occurred but is not certain what that error is.

If ℳ ⊆ Σ^k is the set of messages, then k is the message length.

A note on the number of codewords in a code

We have some algorithms brute-force searching for the codewords in a [q, n, d]-code. These algorithms are brute-force as they do not assume that q is a prime power. Therefore, they go through all possible codewords of a [q, n]-code, and narrow down the code based on d. There algorithms are namely get_codewords_greedy and get_codewords_random, both of which using get_all_codewords. The get_codewords function iterates through possibilities of get_codeword_random and chooses the maximum of those iterations or the get_codeword_greedy length. Despite the name, get_codewords is only a probably candidate. Increate the keyword argument m to decrease the likelihood that there is a code with more codewords while maintaining the bound of the distance. Furthermore, there is a get_codewords method that lists all linear combinations of rows of a generator matrix.

Similar Projects

• Eric Sabo's CodingTheory may offer more comprehensive support for coding theory computation
• Claus Fieker, William Hart, Tommy Hofmann, and Fredrik Johansson's Nemo/Hecke provides useful computer algebra and number theory implementations within Julia that are used throughout within this package.

Citation

If your research depends on CodingTheory.jl, please consider giving us a formal citation: citation.bib.