jakewilliami/codingtheory.jl

Pure Julia implementation of tools used in Coding Theory

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.

codingtheory.jl's Issues

Remove multiple `include`s

Refine code-word finding capabilities

• Do NOT load into memory all codewords. Completed in 9a58d23, by @dmipeck.¹ Redone using Iterators.product in 993ec21.
• Define a cleverer algorithm for random searching.²
• Refine code for performance consideration.³

¹ Edited and refined in 02d911c, 2f6e6c5, 3fff9d6, and 6546206.
² The current plan is to have a kind of mutating code. The problem with the random "algorithm" (as it were) is to balance it with the first point in this issue; we do not want to load the universe into memory. See below.
³ After the bad performance with the memory efficient iterator method, we should work as much on performance (regarding time) as we can. This does not mean we need to change the algorithm, it just means we need to be careful. Edited and refined in cebcd76, a5b8d4a, 77ee159, 37f6886, 70dbc29, and 267f501. See below.

add docs

Rename src/ files

The files in src are currently not very well named. For example, fields.jl has only polynomial fields in it, where messages.jl uses a lot of concepts from linear fields.

Add docstrings

TagBot trigger issue

This issue is used to trigger TagBot; feel free to unsubscribe.

If you haven't already, you should update your TagBot.yml to include issue comment triggers.
Please see this post on Discourse for instructions and more details.