CodingTheory.jl Documentation

AbstractWord{N} = Union{NonStaticAbstractWord{N, T}, MVector{T}} where {T}

NonStaticAbstractWord{N, T} = Union{NTuple{N, T}, AbstractVector{T}, AbstractString} where {N, T}

abstract type AbstractCode end

struct Alphabet <: AbstractCode

Has the parameter Σ, which is the alphabet; a collection of strings, characters, symbols, or Ints.

Alphabet(Σ::AbstractArray)

A constructor method for the struct Alphabet. Takes an array of letters in the alphabet, and attempts to parse them as 64-bit Ints.

Alphabet{N}(Σ::AbstractArray)
Alphabet{N}(Σ::AbstractString)

A constructor method for the struct Alphabet. Takes in a symbols and splits it into constituent characters. Those symbols are the letters in the alphabet. N is the number of letters in the alphabet

struct CodeUniverse <: AbstractCode

Defines a structure for the messages in the code. Parameters are the abstract array of messages 𝒰, and the length of the messages n.

CodeUniverse(𝒰::AbstractArray, Σ::Alphabet)

An inner constructor function on the structure CodeUniverse.

struct CodeUniverseIterator <: AbstractCode

A structure used to iterate through a code universe, with specified universe parameters. E.g.,

for c in CodeUniverseIterator(["a", "b", "c"], 3)
    println(c)
end

Fields:

• 𝒰::UniverseParameters

Methods:

CodeUniverseIterator(𝒰::UniverseParameters)
CodeUniverseIterator(Σ::Union{Alphabet, AbstractArray}, q::Int, n::Int)
CodeUniverseIterator(Σ::Union{Alphabet, AbstractArray}, n::Int)
CodeUniverseIterator(q::Int, n::Int)

Codewords{N} <: AbstractCode

Simply a wrapper type for a vector of abstract words of length N.

abstract type FiniteField end

struct FinitePolynomial <: FiniteField

Has parameters p, which is an abstract polynomial, and n which is the modulus of the field under which the molynomial is defined.

FinitePolynomial(p::AbstractPolynomial, n::Int)

A constructor method for FinitePolynomial. Takes in a polynomial p and a number n, and constructs a polynomial under modulo n.

struct Rounding end

An abstract structure used as a parameter in a non-rounding method of hamming_bound. Use no_round for this; a predefiend variable of the structure Rounding.

struct UniverseParameters <: AbstractCode

Defines a structure for the messages in the code. Parameters are the alphabet Σ, size of alphabet q, and block length n

UniverseParameters(Σ::Alphabet, n::Int)
UniverseParameters(Σ::AbstractArray, n::Int)
UniverseParameters(Σ::Alphabet, q::Int, n::Int)
UniverseParameters(Σ::AbstractArray, q::Int, n::Int)
UniverseParameters(q::Int, n::Int)

An inner constructor function on the structure UniverseParameters.

mutable struct Word{N, T}
Word(w::NTuple{N, T})
Word(w::AbstractVector{T})
Word(w::AbstractString)
Word(i::T...)

A Word is an StaticArrays.MVector which is efficient (like tuple) yet mutable.

Polynomial(A::Union{NTuple{N, T}, Vector{T}}, n::Int) -> Polynomial

Constructs a polynomial under modulo n.

Parameters:

• A::Union{Tuple, AbstractArray}: The polynomial coefficients.
• n::Int: The modulus of the field.

Returns

• Polynomial: A polynomial modulo n.

gensym(q::Int) -> Vector{Symbol}

Generates a vector of unique symbols of length q.

mod(p::Polynomial, n::Int) -> Polynomial

Uses the FinitePolynomial constructor to return a polynomial p under modulus n.

Parameters:

• p::Polynomial: The input polynomial.
• n::Int: The modulus of the field.

Returns

• Polynomial: A polynomial modulo n.

rand(𝒰::UniverseParameters, C::AbstractArray) -> Tuple

Given universe parameters 𝒰 and a code C, return a tuple including

• A random word in C;
• A random letter in the alphabet; and
• A random index in the block length.

_has_identity(M::Matrix, n::Union{T, Base.OneTo{T}, AbstractRange{T}}) where {T <: Integer}

Inner function on has_identity function. Will return a tuple of:

• Whether or not the matrix has an identity;
• Where that identity matrix starts; and
• How big the identity matrix is.

allequal(A) -> Bool
allequal(a, b...) -> Bool

Check that all elements in a list are equal to each other.

allequal_length(A) -> Bool
allequal_length(a, b...) -> Bool

Check that all elements in a list are of equal length.

aredistinct(A) -> Bool
aredistinct(a, b...) -> Bool

Check that all elements in a list are distinct from every other element in the list.

areequalto(x::Number, A::AbstractArray) -> Bool
areequalto(x::Number, a, b...) -> Bool

Check that all elements in a list are equal to a given x.

arelessthan(x::Number, A) -> Bool
arelessthan(x::Number, a, b...) -> Bool

Check that all elements in a list are less than a given x.

code_distance!(C::AbstractArray{T}, w::T) -> Int

A wrapper to get the code distance after pushing a word to the code. This directly changes the matrix M. Use code_distance for a non-mutating version of this function.

Parameters:

• C::AbstractArray: An array of words in the code.
• w: A word to be appended to C.

Returns:

• Int: The code distance after adding w to C.

code_distance(C::AbstractArray) -> Int

Finds the distance of the code. That is, given a code C, finds the minimum distance between any two words in the code, which are not the same. (Find the minimum hamming distance in the code for all unique letters).

Parameters:

• C::AbstractArray: An array of words in the code.

Return:

• Int: the distance of the code.

code_distance(C::AbstractArray{T}, w::T) -> Int

A wrapper to get the code distance after pushing a word to the code.

Parameters:

• C::AbstractArray: An array of words in the code.
• w: A word to be appended to C.

Returns:

• Int: The code distance after adding w to C.

Examples

julia> code_distance([[0,0,0,0,0],[1,0,1,0,1],[0,1,0,1,0],[1,1,1,1,1]]) # gets the minimum distance between two vectors in an array of vectors
2

construct_ham_matrix(r::Int, q::Int) -> Matrix

Construct a Hamming parity-check matrix.

Parameters:

• r::Int: number of rows of a parity check matrix.
• q:::Int: The size of the alphabet of the code.

Returns:

• Matrix: The Hamming matrix, denoted as $\text{Ham}(r, q)$

Examples

julia> construct_ham_matrix(3,2)
3×7 Array{Int64,2}:
 0  0  0  1  1  1  1
 0  1  1  0  0  1  1
 1  0  1  0  1  0  1

deepeltype(a::AbstractArray) -> Type

Returns the type of the inner-most element in a nested array structure.

deepsym(a::AbstractArray)

Convert inner-most elements into symbols

displaymatrix(M::AbstractArray)

Displays a matrix M in a compact form from the terminal.

ensure_symbolic!(Σ) -> typeof(Σ)

Ensures that the inner-most elements of a nested array structure are of the type Symbol. This is a mutating function. Use its twin, non-mutating function, ensure_symbolic, if you need a non-mutating version of this.

ensure_symbolic(Σ) -> typeof(Σ)

Ensures that the inner-most elements of a nested array structure are of the type Symbol.

equivalent_code!(M::AbstractArray{Int}, n::Int) -> Matrix{Int}

Peforms Gauss-Jordan elimination on a matrix M, but allows for column swapping. This constructs an "equivalent" matrix. This directly changes the matrix M. Use equivalent_code for a non-mutating version of this function.

Parameters:

• M::AbstractArray{Int}: A matrix of Ints.
• n::Int: The modulus of the finite field.

Returns:

• Matrix{Int}: A which represents an "equivalent" code to that of the matrix M.

Examples

julia> equivalent_code!([1 2 0 1 2 1 2; 2 2 2 0 1 1 1; 1 0 1 1 2 1 2; 0 1 0 1 1 2 2], 3) # computes rref colswap = true
4×7 Array{Int64,2}:
1  0  0  0  2  2  2
0  1  0  0  2  0  1
0  0  1  0  1  0  2
0  0  0  1  2  2  1

equivalent_code(M::AbstractArray{Int}, n::Int) -> Matrix{Int}

Peforms Gauss-Jordan elimination on a matrix M, but allows for column swapping.

Parameters:

• M::AbstractArray{Int}: A matrix of Ints.
• n::Int: The modulus of the finite field.

Returns:

• Matrix{Int}: A which represents an "equivalent" code to that of the matrix M.

Examples

julia> equivalent_code([1 2 0 1 2 1 2; 2 2 2 0 1 1 1; 1 0 1 1 2 1 2; 0 1 0 1 1 2 2], 3) # computes rref colswap = true
4×7 Array{Int64,2}:
1  0  0  0  2  2  2
0  1  0  0  2  0  1
0  0  1  0  1  0  2
0  0  0  1  2  2  1

find_error_correction_max(C::AbstractArray{T}, modulo::Int) -> Int

Finds the greatest number t such that C is error t error correcting.

Parameters:

• C::AbstractArray: An array of words in the code.
• moldulo::Int: The modulus of the finite field. The upper bound of t.

Returns:

• Int: The maximum number t such that the code is t error correcting.

find_error_detection_max(C::AbstractArray{T}, modulo::Int) -> Int

Finds the greatest number t such that C is error t error detecting.

Parameters:

• C::AbstractArray: An array of words in the code.
• moldulo::Int: The modulus of the finite field. The upper bound of t.

Returns:

• Int: The maximum number t such that the code is t error detecting.

julia> find_error_detection_max([[0, 0, 0, 0], [0, 1, 1, 1], [1, 0, 1, 0], [1, 1, 0, 1]], 2)
1

genalphabet(q::Int)

Generates an alphabet of q unique symbols.

generator!(M::AbstractArray{Int}, n::Int; colswap::Bool = true) -> Matrix{Int}

Constructs a generator matrix of the code, depending on if you allow for column swapping or not. This function uses normal_form! or equivalent_code!. This directly changes the matrix M. Use generator for a non-mutating version of this function.

Parameters:

• M::AbstractArray{Int}: A matrix of Ints.
• n::Int: The modulus of the finite field.
• colswap::Bool (kwarg): A boolean flag indicating whether or not you allow for swapping of columns when constructing the generating matrix.

Returns:

• Matrix{Int}: A generating matrix.

generator(M::AbstractArray{Int}, n::Int; colswap::Bool = true) -> Matrix{Int}

Constructs a generator matrix of the code, depending on if you allow for column swapping or not. This function uses normal_form or equivalent_code.

Parameters:

• M::AbstractArray{Int}: A matrix of Ints.
• n::Int: The modulus of the finite field.
• colswap::Bool (kwarg): A boolean flag indicating whether or not you allow for swapping of columns when constructing the generating matrix.

Returns:

• Matrix{Int}: A generating matrix.

get_all_words(Σ::Alphabet{N}, q::Int, n::Int) -> Codewords{M}
get_all_words(Σ::Alphabet{N}, n::Int) -> Codewords{M}
get_all_words(Σ::AbstractArray, q::Int, n::Int) -> Codewords{M}
get_all_words(Σ::AbstractArray, n::Int) -> Codewords{M}
get_all_words(q::Int, n::Int) -> Codewords{M}

Get the universe of all codewords of a given alphabet. The alphabet will be uniquely generated if none is given.

Parameters:

• Σ::AbstractArray: The alphabet allowed.
• q::Int: The size of the alphabet.
• n::Int: The (fixed) length of the words in the code.
• d::Int: The minimum distance between words in the code.
• 𝒰::AbstractArray: The universe of all codewords of q many letters of block length n.

Returns:

• Codewords{M}: An array of codewords, each of length M. Each codewords is a tuple, and each character in said word is a symbol.

Examples

julia> get_all_words(2, 2) # all words of block length 2 using 2 unique symbols
2×2 Array{Tuple{Symbol,Symbol},2}:
 (Symbol("##254"), Symbol("##254"))  (Symbol("##254"), Symbol("##253"))
 (Symbol("##253"), Symbol("##254"))  (Symbol("##253"), Symbol("##253"))

get_codewords(G::AbstractArray, m::Int) -> Codewords{M}

Get codewords of a code from the generating matrix under a finite field of modulo m. Precisely, computes all linear combinations of the rows of the generating matrix.

Parameters:

• G::AbstractArray: A matrix of Ints which generates the code.
• m::Int: The bounds of the finite field (i.e., the molulus you wish to work in).

Returns:

• Codewords{M}: An array of codewords, each of length M. Each codewords is a tuple, and each character in said word is a symbol.

get_codewords(𝒰::UniverseParameters, d::Int; m::Int=10, m_random::Int = 1000) -> Codewords{M}
get_codewords(Σ::Alphabet{N}, q::Int, n::Int, d::Int; m::Int=10, m_random::Int=1000) -> Codewords{M}
get_codewords(q::Int, n::Int, d::Int; m::Int=10, m_random::Int=1000) -> Codewords{M}
get_codewords(q::Int, n::Int, d::Int; m::Int=10, m_random::Int=1000) -> Codewords{M}
get_codewords(Σ::AbstractArray, q::Int, n::Int, d::Int; m::Int=10, m_random::Int=1000) -> Codewords{M}
get_codewords(Σ::AbstractArray, n::Int, d::Int; m::Int=10, m_random::Int=1000) -> Codewords{M}
get_codewords(Σ::AbstractArray, q::Int, n::Int, d::Int, 𝒰::AbstractArray; m::Int=10, m_random::Int=1000) -> Codewords{M}

Use function get_codewords_random m many times (with get_codewords_random(..., m = m_random)), and get_codewords_greedy. Return the code with the greatest number of words. The alphabet will be uniquely generated if none is given. You can omit Σ and 𝒰. You can omit q if Σ is given.

Parameters:

• Σ::AbstractArray: The alphabet allowed.
• q::Int: The size of the alphabet.
• n::Int: The (fixed) length of the words in the code.
• d::Int: The minimum distance between words in the code.
• 𝒰::AbstractArray: The universe of all codewords of q many letters of block length n.
• m::Int (kwarg): Try a random code m many times.
• m_random::Int (kwarg): The number of possible words get_codewords_random chooses from for each word it selects.

Returns:

• Codewords{M}: An array of codewords, each of length M. Each codewords is a tuple, and each character in said word is a symbol.

Examples

julia> get_codewords(["a", "b", "c"], 3, 2) # get codewords of block length 3 with distance 2.  Once again, are symbols for uniqueness
9-element Array{Tuple{Symbol,Symbol,Symbol},1}:
 (:a, :b, :a)
 (:c, :a, :b)
 (:b, :c, :c)
 (:b, :a, :a)
 (:c, :b, :c)
 (:a, :a, :c)
 (:a, :c, :b)
 (:c, :c, :a)
 (:b, :b, :b)

get_codewords_greedy(𝒰::UniverseParameters, d::Int) -> Codewords{M}
get_codewords_greedy(Σ::Alphabet{N}, q::Int, n::Int, d::Int) -> Codewords{M}
get_codewords_greedy(Σ::Alphabet{N}, n::Int, d::Int) -> Codewords{M}
get_codewords_greedy(q::Int, n::Int, d::Int) -> Codewords{M}
get_codewords_greedy(Σ::AbstractArray, q::Int, n::Int, d::Int) -> Codewords{M}
get_codewords_greedy(Σ::AbstractArray, n::Int, d::Int) -> Codewords{M}
get_codewords_greedy(Σ::AbstractArray, q::Int, n::Int, d::Int, 𝒰::AbstractArray) -> Codewords{M}

Search through the universe of all codewords and find a code of block length n and distance d, using the alphabet Σ. The alphabet will be uniquely generated if none is given. This uses a greedy algorithm, simply iterating through all words (see above) and choosing them if they fit in the code. In some cases the greedy algorithm is the best, but in others it is very much not.

Parameters:

• 𝒰::UniverseParameters: The parameters of the universe of all codewords of q many letters of block length n.
• Σ::AbstractArray: The alphabet allowed.
• q::Int: The size of the alphabet.
• n::Int: The (fixed) length of the words in the code.
• d::Int: The minimum distance between words in the code.

Returns:

• Codewords{M}: An array of codewords, each of length M. Each codewords is a tuple, and each character in said word is a symbol.

get_codewords_random(𝒰::UniverseParameters, d::Int; m::Int = 1000) -> Codewords{M}
get_codewords_random(Σ::Alphabet{N}, q::Int, n::Int, d::Int; m::Int=1000) -> Codewords{M}
get_codewords_random(Σ::Alphabet{N}, n::Int, d::Int; m::Int=1000)	-> Codewords{M}
get_codewords_random(q::Int, n::Int, d::Int; m::Int=1000) -> Codewords{M}
get_codewords_random(Σ::AbstractArray, q::Int, n::Int, d::Int; m::Int=1000) -> Codewords{M}
get_codewords_random(Σ::AbstractArray, n::Int, d::Int; m::Int=1000) -> Codewords{M}
get_codewords_random(Σ::AbstractArray, q::Int, n::Int, d::Int, 𝒰::AbstractArray; m::Int=1000) -> Codewords{M}

Search through the universe of all codewords at random and find a code of block length n and distance d, using the alphabet Σ. The alphabet will be uniquely generated if none is given. This is a cleverer algorithm than the greedy algorithm. Increasing the m keyword argument arbitrarily should produce a maximal code, as for each codeword it chooses, it collects a list of m many random words, and chooses the best one from that intermediate list.

Parameters:

• Σ::AbstractArray: The alphabet allowed.
• q::Int: The size of the alphabet.
• n::Int: The (fixed) length of the words in the code.
• d::Int: The minimum distance between words in the code.
• 𝒰::AbstractArray: The universe of all codewords of q many letters of block length n.

Returns:

• Codewords{M}: An array of codewords, each of length M. Each codewords is a tuple, and each character in said word is a symbol.

hamming_ball(Σⁿ::AbstractArray, w::Vector, e::Int) -> Vector{Vector}

Get the codewords of radius $e$ of a ball centered at word $w$. That is, all words whose distance from w is less than or equal to the radius.

Parameters:

• Σⁿ::AbstractArray: An array of words in the code.
• w::Vector: A word.
• e::Int: The radius of the ball.

Returns:

• AbstractArray: The list of words in Σⁿ whose distance from w is less than or equal to e. Returns an array of array of symbols.

Examples

julia> hamming_ball([[1, 0, 1], [0, 1, 1], [1, 0, 0]], [1, 0, 0], 2) # given a list of words, a word, and a distance e (respectively), calculate all the words in the alphabet within distance e of that word.  Converts to symbols in order to keep unique lengths
2-element Array{Any,1}:
 [Symbol("1"), Symbol("0"), Symbol("1")]
 [Symbol("1"), Symbol("0"), Symbol("0")]

hamming_distance(w₁, w₂) -> Int

The Hamming distance of two words is the number of changes that need to be made to each letter in the word for the words to be the same. This does not work for words of unequal length.

Parameters:

• w₁: A word.
• w₂: Another word.

Returns:

• Int: the number of changes needing to be made to one word for it to be identical to the other.

Examples

julia> hamming_distance("ABC", "BBC") # computes the hamming distance
1

hamming_sphere(Σⁿ::AbstractArray, w::Vector, e::Int) -> Vector{Vector}

Get the codewords of radius e of a sohere centered at word w. That is, all words whose distance from w is exactly equal to to the radius.

Parameters:

• Σⁿ::AbstractArray: An array of words in the code.
• w::Vector: A word.
• e::Int: The radius of the ball.

Returns:

• AbstractArray: The list of words in Σⁿ whose distance from w is exactly equal to e. Returns an array of array of symbols.

has_identity(M::Matrix) -> Bool
has_identity(M::Matrix, n::Integer) -> Bool

Checks if a matrix has an identity in it. If given a number n, the function will specifically check if it has an identity matrix of size n in M.

See CodingTheory._has_identity for more information.

Examples

julia> A = [1 0 0 2 3 0; 0 1 0 1 2 2; 0 0 1 4 3 0]
3×6 Array{Int64,2}:
 1  0  0  2  3  0
 0  1  0  1  2  2
 0  0  1  4  3  0

julia> B = [1 0 1 2 3 0; 0 1 0 1 2 2; 0 0 1 4 3 0]
3×6 Array{Int64,2}:
 1  0  1  2  3  0
 0  1  0  1  2  2
 0  0  1  4  3  0

julia> C = [-96 -66 20 1 0 0; -65 59 -82 0 1 0; -16 87 -113 0 0 1]
3×6 Array{Int64,2}:
-96  -66    20  1  0  0
-65   59   -82  0  1  0
-16   87  -113  0  0  1

julia> D = [78 -99 125 -123 -111 -71 17; -115 78 40 -88 81 -40 78; -99 126 -54 1 0 0 24; -55 88 42 0 1 0 -8; 119 55 2 0 0 1 -92; -40 -21 -89 -79 59 -44 9]
6×7 Array{Int64,2}:
   78  -99  125  -123  -111  -71   17
 -115   78   40   -88    81  -40   78
  -99  126  -54     1     0    0   24
  -55   88   42     0     1    0   -8
  119   55    2     0     0    1  -92
  -40  -21  -89   -79    59  -44    9

julia> has_identity(A)
true

julia> has_identity(B)
true

julia> has_identity(B, 3) # no identity matrix of size 3 exists
false

julia> has_identity(C)
true

julia> has_identity(D)
true

julia> has_identity(D, 4)
false

has_identity_on_left(M::Matrix) -> Bool

Checks if the left-hand side of a matrix contains an identity matrix.

Examples

julia> A = [1 0 0 2 3 0; 0 1 0 1 2 2; 0 0 1 4 3 0]
3×6 Array{Int64,2}:
 1  0  0  2  3  0
 0  1  0  1  2  2
 0  0  1  4  3  0

julia> B = [-96 -66 20 1 0 0; -65 59 -82 0 1 0; -16 87 -113 0 0 1]
3×6 Array{Int64,2}:
 -96  -66    20  1  0  0
 -65   59   -82  0  1  0
 -16   87  -113  0  0  1

julia> has_identity_on_left(A)
true

julia> has_identity_on_left(B)
false

isgolayperfect(n::Int, k::Int, d::Int, q::Int) -> Bool

Golay found two perfect codes. isgolayperfect checks if a code of block length n, distance d, alphabet size q, and dimension k, is a perfect code as described by Golay.

Parameters:

• n::Int: The block length of words in the code (e.g., word "abc" has block length 3).
• k::Int: The dimension of the code.
• d::Int: The distance of the code (i.e., the minimum distance between codewords in the code).
• q::Int: An Int that is a prime power. The modulus of the finite field.

Returns:

• Bool: true or false.

Examples

julia> isgolayperfect(11, 6, 5, 3) # this is one of golay's perfect codes
true

ishammingbound(r::Int, q::Int) -> Bool

Checks if the code is a perfect code that is of the form of a generalised Hamming code.

Parameters:

• r::Int: number of rows of a parity check matrix.
• q::Int: The size of the alphabet of the code.

Returns:

• Bool: true or false

ishammingperfect(n::Int, k::Int, d::Int, q::Int) -> Bool
ishammingperfect(q::Int, n::Int, d::Int) -> Bool

Checks if the code is a perfect code that is of the form of a generalised Hamming code.

Parameters:

• q:::Int: The size of the alphabet of the code.
• n::Int: The length of the words in the code (block length).
• d::Int: The distance of the code.
• k::Int: The dimension of the code.

Returns:

• Bool: true or false

Examples

julia> isgolayperfect(11, 6, 5, 3) # this is one of golay's perfect codes
true

isincode(v̲::Vector, Hᵀ::AbstractArray{Int}, n::Int) -> Bool

If the syndrome of a code is the zero vector, then the word used to calculate the syndrome is in the code.

Parameters:

• v̲::Vector: A word.
• Hᵀ::AbstractArray{Int}: The transpose of a parity check matrix.

Returns:

• Bool: If the word is in the code or not (true or false).

Examples

julia> isincode([0, 2, 1, 2, 0, 1, 0], transpose(parity_check([1 0 0 0 2 2 2; 0 1 0 0 2 0 1; 0 0 1 0 1 0 2; 0 0 0 1 2 2 1], 3)), 3) # tests if the syndrome is equal to the zero vector, and is thus in the code
true

isirreducible(f::AbstractPolynomial, modulo::Int) -> Bool

Checks if a polynomial is irreducible.

Parameters:

• f::Polynomial: The polynomial you need to check.
• modulo::Int: The modulus under which you are working.

Returns:

• Bool: Whether or not the polynomial is irreducible (true or false).

Examples

julia> isirreducible(Polynomial([1, 1, 0, 0, 1]), 2) # is 1 + x + x^4 mod 2 irreducible?
true

islinear(C::Vector, modulo::Int; verbose::Bool = false) -> Bool

Determines whether a code C is a linear code (i.e., if it is closed under addition, scalar multiplication, and has the zero vector in it).

Parameters:

• C::Vector: A code, typically consisting of multiple vectors or strings.
• modulo::Int: The modulus of the field under which you are working.
• verbose::Bool (kwarg): print the point at which C fails, if it does.

Returns:

• Bool: Whether or not the code C is linear (true or false).

Examples

julia> islinear([[0,0,0],[1,1,1],[1,0,1],[1,1,0]], 2) # checks whether a vector of vectors is linear/a subspace (modulo 2)
false

isperfect(n::Int, k::Int, d::Int, q::Int) -> Bool

Checks if a code is perfect. That is, checks if the number of words in the code is exactly the "Hamming bound", or the "Sphere Packing Bound".

Parameters:

• q:::Int: The size of the alphabet of the code.
• n::Int: The length of the words in the code (block length).
• d::Int: The distance of the code.
• k::Int: The dimension of the code.

Returns:

• Bool: true or false

Examples

julia> isperfect(11, 6, 5, 3)
true

isperfectpower(n::Integer) -> Bool

Given an integer n, returns true or false depending on whether or not it is a perfect power.

Here, a perfect power is some number of the form $a^b$, where $a, b \in \mathbb{N}$, and $b > 1$.

This function is a wrapper around Hecke.jl's really excellent and efficient ispower function.

See also: CodingTheory.isperfectpower.

isprimepower(n::Integer) -> Bool

Given an integer n, returns true or false depending on whether or not it is a prime power.

A prime power is some number of the form $p^b$, where $p, b \in \mathbb{N}$, and $p$ is a prime number``.

This function is a wrapper around Hecke.jl's really excellent and effcient ispower function.

See also: CodingTheory.isperfectpower.

levenshtein(source::AbstractString, target::AbstractString) -> Integer
levenshtein(source::AbstractString, target::AbstractString, cost::Real) -> Integer
levenshtein(
    source::AbstractString,
    target::AbstractString,
    deletion_cost::R,
    insertion_cost::S,
    substitution_cost::T) -> Integer
levenshtein!(
    source::AbstractString,
    target::AbstractString,
    deletion_cost::R,
    insertion_cost::S,
    substitution_cost::T,
    costs::Matrix = Array{promote_type(R, S, T)}(undef, 2, length(target) + 1)
) -> Integer

Computes the Levenshtein distance.

These methods are adapted from Levenshtein.jl, by Roger Tu.

list_polys(n::Int, m::Int) -> Array

Lists all polynomials of degree less than to n under modulo m.

Parameters:

• n::Int: Highest degree of polynomial.
• m::Int: The modulus of the field.

Returns:

• Array: An array of polynomials of degree less than n, under modulo m.

list_span(u̲::Vector, v̲::Vector,... modulo::Int) -> Array

Given any number of vectors u̲, v̲,... , prints all linear combinations of those vectors, modulo modulo.

Parameters:

• u̲::Vector: One vector.
• v̲::Vector: Another vector.
• ...: Other vectors.
• modulo::Int: The modulus of the field.

Returns:

• Array: All vectors in the span of u̲ and v̲, under modulo.

Examples

julia> list_span([2, 1, 1], [1, 1, 1], 3) # list the span of two vectors modulo 3
9-element Array{Array{T,1} where T,1}:
 [0, 0, 0]
 [1, 1, 1]
 [2, 2, 2]
 [2, 1, 1]
 [0, 2, 2]
 [1, 0, 0]
 [1, 2, 2]
 [2, 0, 0]
 [0, 1, 1]

multiplication_table(degree::Int, modulo::Int) -> Matrix

Returns a table (matrix) of the multiplication of all combinations of polynomials for degree less than degree, under modulo modulo.

Parameters:

• degree::Int: Highest degree of polynomial.
• modulo::Int: The modulus of the field.

Returns:

• Matrix: A multiplication table of all polynomials with degree less than n, under modulus.

Examples

julia> julia> multiplication_table(2, 3) # multiplication table of all polynomials of degree less than 3 modulo 2
9×9 Array{Polynomial,2}:
 Polynomial(0)  Polynomial(0)        Polynomial(0)        …  Polynomial(0)                Polynomial(0)
 Polynomial(0)  Polynomial(1)        Polynomial(2)           Polynomial(1 + 2*x)          Polynomial(2 + 2*x)
 Polynomial(0)  Polynomial(2)        Polynomial(1)           Polynomial(2 + x)            Polynomial(1 + x)
 Polynomial(0)  Polynomial(x)        Polynomial(2*x)         Polynomial(x + 2*x^2)        Polynomial(2*x + 2*x^2)
 Polynomial(0)  Polynomial(1 + x)    Polynomial(2 + 2*x)     Polynomial(1 + 2*x^2)        Polynomial(2 + x + 2*x^2)
 Polynomial(0)  Polynomial(2 + x)    Polynomial(1 + 2*x)  …  Polynomial(2 + 2*x + 2*x^2)  Polynomial(1 + 2*x^2)
 Polynomial(0)  Polynomial(2*x)      Polynomial(x)           Polynomial(2*x + x^2)        Polynomial(x + x^2)
 Polynomial(0)  Polynomial(1 + 2*x)  Polynomial(2 + x)       Polynomial(1 + x + x^2)      Polynomial(2 + x^2)
 Polynomial(0)  Polynomial(2 + 2*x)  Polynomial(1 + x)       Polynomial(2 + x^2)          Polynomial(1 + 2*x + x^2)

mutate_codeword(w::NonStaticAbstractWord{N, T}, n::Int, i::Int, a::T) where {T, N} -> MVector{N, T}
mutate_codeword(w::Word{N, T}, n::Int, i::Int, a::T) where {T, N} -> MVector{N, T}

Mutates the word w, which is an MVector of length N, changing its iᵗʰ index to a.

normal_form!(M::AbstractArray{Int}, n::Int) -> Matrix{Int}

Convert a matrix M into normal form under modulo n via Gauss-Jordan elimination. This directly changes the matrix M. Use normal_form for a non-mutating version of this function.

Parameters:

• M::AbstractArray{Int}: A matrix of Ints.
• n::Int: The modulus of the finite field.

Returns:

• Matrix{Int}: A matrix in normal form from Gauss-Jordan elimination.

Examples

julia> normal_form!([1 2 0 1 2 1 2; 2 2 2 0 1 1 1; 1 0 1 1 2 1 2; 0 1 0 1 1 2 2], 3) # computes rref colswap = false
4×7 Array{Int64,2}:
1  0  0  0  2  2  2
0  1  0  0  2  0  1
0  0  1  0  1  0  2
0  0  0  1  2  2  1

normal_form(M::AbstractArray{Int}, n::Int) -> Matrix{Int}

Convert a matrix M into normal form under modulo n via Gauss-Jordan elimination.

Parameters:

• M::AbstractArray{Int}: A matrix of Ints.
• n::Int: The modulus of the finite field.

Returns:

• Matrix{Int}: A matrix in normal form from Gauss-Jordan elimination.

Examples

julia> normal_form([1 2 0 1 2 1 2; 2 2 2 0 1 1 1; 1 0 1 1 2 1 2; 0 1 0 1 1 2 2], 3) # computes rref colswap = false
4×7 Array{Int64,2}:
1  0  0  0  2  2  2
0  1  0  0  2  0  1
0  0  1  0  1  0  2
0  0  0  1  2  2  1

parity_check(M::AbstractArray{Int}, n::Int) -> Matrix{Int}

Constructs a parity check matrix. This is calculated from taking the non-identity part of a matrix in normal form (or equivalent — see generator), transposing it, multiplying it by negative one, and appending to it an appropriate sized identity matrix.

Parameters:

• M::AbstractArray{Int}: A matrix of Ints.
• n::Int: The modulus of the finite field.

Returns:

• Matrix{Int}: A parity check matrix.

push_if_allowed!(C::AbstractArray{T}, w::T, d::Int)

Takes in an array and a word. As long as the word does not mean that the distance is smaller than d, we add w to the array. If we are successful in doing this, return true. Otherwise, return false. This is a mutating function.

push_if_allowed!(C::AbstractArray{T}, C′::AbstractArray{T}, w::T, d::Int)

Takes in two arrays, A and B. If w is allowed in C given distance d, push to C′. If we are successful in doing this, return true. Otherwise, return false. This is a mutating function.

rate(q::Integer, M::Integer, n::Integer) -> Real

Calculate the rate of a code. That is, how efficient the code is.

Parameters:

• q::Integer: the number of symbols in the code.
• M::Integer: the size/number of elements in the code.
• n::Integer: The word length.

Returns:

• Real: Rate of the code.

Examples

julia> rate(3, 5, 4) # the rate of the code which has 3 symbols, 5 words in the code, and word length of 4 (e.g., Σ = {A, B, C}, C = {ABBA,CABA,BBBB,CAAB,ACBB})
0.3662433801794817

replace_if_allowed!(C::AbstractArray, d::Int, w, w′) -> Bool

Takes in an array and a word. As long as the word does not mean that the distance is smaller than d, we replace a with b in the array. Replaces and returns true if allowed; otherwise returns false. This is a mutating function.

rref!(A::Matrix{Int}, n::Int; colswap::Bool=false, verbose::Bool=false, vverbose::Bool=false) -> Matrix{Int}

Performs Gauss-Jordan Elimination on a matrix A. This directly changes the matrix A. Use rref for a non-mutating version of this function.

Parameters:

• A::Matrix{Int}: A matrix of Ints you wish to perform Gauss-Jordan elimiation on.
• n::Int: The modulus of the finite field you are working under.
• colswap::Bool (kwarg): Whether or not you allow for column swapping.
• verbose::Bool (kwarg): Print the row operations.
• vverbose::Bool (kwarg): Print the intermediate matrices of the algorithm.

Returns:

• Matrix{Int}: a matrix in row echelon form.

Examples

julia> rref!([1 1 0 2 3 1; 2 0 1 3 4 1; 1 2 2 1 4 3], 5, colswap=true) # gauss-jordan elimitation modulo 5 with column swapping
3×6 Array{Int64,2}:
 1  0  0  3  2  2
 0  1  0  2  1  1
 0  0  1  0  0  4

rref(A::Matrix{Int}, n::Int; colswap::Bool=false, verbose::Bool=false, vverbose::Bool=false) -> Matrix{Int}

Performs Gauss-Jordan Elimination on a matrix A.

Parameters:

• A::Matrix{Int}: A matrix of Ints you wish to perform Gauss-Jordan elimiation on.
• n::Int: The modulus of the finite field you are working under.
• colswap::Bool (kwarg): Whether or not you allow for column swapping.
• verbose::Bool (kwarg): Print the row operations.
• vverbose::Bool (kwarg): Print the intermediate matrices of the algorithm.

Returns:

• Matrix{Int}: a matrix in row echelon form.

Examples

julia> rref([1 1 0 2 3 1; 2 0 1 3 4 1; 1 2 2 1 4 3], 5, colswap=true) # gauss-jordan elimitation modulo 5 with column swapping
3×6 Array{Int64,2}:
 1  0  0  3  2  2
 0  1  0  2  1  1
 0  0  1  0  0  4

sizeof_all_words(q::Number, n::Number) -> Number

Calculates the number of gigabytes required to store all unique words of length n from an alphabet of size q.

sizeof_perfect_code(q::Number, n::Number, d::Number) -> Number

Calculates the number of gigabytes required to store a perfect code of parameters q, n, and d.

sphere_covering_bound(q::Integer, n::Integer, d::Integer) -> Integer

Computes the sphere covering bound of a $[n, d]_q$-code.

Parameters:

• q::Integer: the number of symbols in the code.
• n::Integer: the word length.
• d::Integer: the distance of the code.

Returns:

• Integer: the sphere covering bound.

Examples

julia> sphere_covering_bound(5,7,3)
215

sphere_packing_bound(q::Integer, n::Integer, d::Integer) -> Integer
sphere_packing_bound(q::Integer, n::Integer, d::Integer, ::Rounding) -> Real

Computes the sphere packing bound of a $[n, d]_q$-code. The sphere packing bound is also known as the hamming bound. You can use hamming_bound to compute the same thing.

Parameters:

• q::Integer: the number of symbols in the code.
• n::Integer: the word length.
• d::Integer: the distance of the code.
• ::Rounding: use the argument no_round in this position to preserve the rounding of the code — which usually by default rounds down.

Returns:

• Integer: the sphere packing bound.

Examples

julia> sphere_packing_bound(5,7,3)
2693

syndrome(v̲::Vector, Hᵀ::AbstractArray{Int}, n::Int) -> Matrix{Int}

Calculates the syndrome of a given word v̲ and a parity check matrix, transposed (Hᵀ), under modulo n.

Parameters:

• v̲::Vector: A word in the code.
• Hᵀ::AbstractArray{Int}: The transpose of a parity check matrix.

Returns:

• Vector: The syndrome of a word in the code.

Examples

julia> syndrome([0, 2, 1, 2, 0, 1, 0], [1 1 1; 1 0 2; 2 0 1; 1 1 2; 1 0 0; 0 1 0; 0 0 1], 3)
1×3 Array{Int64,2}:
0  0  0

julia> syndrome([0, 2, 1, 2, 0, 1, 0], transpose(parity_check([1 0 0 0 2 2 2; 0 1 0 0 2 0 1; 0 0 1 0 1 0 2; 0 0 0 1 2 2 1], 3)), 3)
1×3 Array{Int64,2}:
 0  0  0

t_error_correcting(C::AbstractArray{T}, t::Int) -> Bool

Check if a given code C can correct t many errors.

Parameters:

• C::AbstractArray: An array of words in the code.
• t::Int: The number of errors you want to check that the code can correct.

Returns:

• Bool: Yes, C can correct t errors, or no it cannot (true of false).

t_error_detecting(C::AbstractArray{T}, t::Int) -> Bool

Check if a given code C can detect t many errors.

Parameters:

• C::AbstractArray: An array of words in the code.
• t::Int: The number of errors you want to check that the code can detect.

Returns:

• Bool: Yes, C can detect t errors, or no it cannot (true of false).

Examples

julia> t_error_detecting([[1, 0, 1], [0, 1, 1], [1, 0, 0]], 3)
false