## CodingTheory.jl

Pure Julia implementation of tools used in Coding Theory
Author jakewilliami
Popularity
5 Stars
Updated Last
2 Years Ago
Started In
October 2020

# 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 w1w2...wn is such a word, then n is its length. We use Σn to denote the set of words with length n using symbols in Σ. In general, the number of words in Σn is

n| = qn.

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.

### Required Packages

View all packages

### Used By Packages

No packages found.