# 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 _{1}w_{2}...w_{n}* is such a word, then

*n*is its

**length**. We use

*Σ*to denote the set of words with length

^{n}*n*using symbols in

*Σ*. In general, the number of words in

*Σ*is

^{n}
|Σ^{n}| = q^{n}.

**Block codes** are codes in which Alice transmits words of a preditermined and fixed length. A **code** is a subset *C ⊆ Σ ^{n}*. 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 : Σ^{n} ⟶ 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.