Linear Codes

Generic linear codes may be constructed from a matrix or a vector-space object. If the optional parameter parity is true, a matrix input is interpreted as a parity-check matrix. Zero rows are removed automatically, while zero columns are retained. See the Linear Codes tutorial for usage examples.

Accessors are provided for every stored attribute, and users are strongly encouraged to use them rather than reaching into the structs directly: many functions rely on the stored data being in a specific order, and the accessors compute and cache derived quantities on first use.

If a code was created from a generator or parity-check matrix, that matrix is stored alongside the standard form. It is potentially overcomplete, meaning it has more rows than its rank. Passing stand_form = true returns the standard form instead. Some families are not built from an explicit matrix; there the matrices start out missing and are computed on demand.

Putting a matrix into standard form may require column permutations. When it does, standard_form_permutation returns the permutation matrix $P$ with $\mathrm{rowspace}(G) = \mathrm{rowspace}(G_\mathrm{stand} P)$, and missing otherwise.

The minimum distance of some families is known and is set during construction, and it is computed automatically for codes deemed small enough. Otherwise it is missing and must be requested explicitly; see Minimum distance. Functions that depend on knowing the distance return missing when it is unknown. The distance and its bounds may also be set by hand, in which case nothing is done to check the value for correctness.

CodingTheory.LinearCode — Type
LinearCode(
    Gs::Vector{Vector{Int64}},
    q::Int64
) -> LinearCode
LinearCode(
    Gs::Vector{Vector{Int64}},
    q::Int64,
    parity::Bool
) -> LinearCode

Return the linear code generated by integer row vectors over the finite field of order q.

source
CodingTheory.LinearCode — Type
LinearCode(G::Matrix{Int64}, q::Int64) -> LinearCode
LinearCode(
    G::Matrix{Int64},
    q::Int64,
    parity::Bool
) -> LinearCode

Return the linear code generated by an integer matrix over the finite field of order q.

source
CodingTheory.LinearCode — Type
LinearCode(
    G::Union{Nemo.FqMatrix, Nemo.fpMatrix, Hecke.SMat, SparseArrays.SparseMatrixCSC}
) -> LinearCode
LinearCode(
    G::Union{Nemo.FqMatrix, Nemo.fpMatrix, Hecke.SMat, SparseArrays.SparseMatrixCSC},
    parity::Bool
) -> LinearCode

Return the linear code constructed with matrix G. If parity is true, G is treated as the parity-check matrix. Safely handles sparse matrices and uses lazy evaluation to avoid eager rank and dual computations.

source
CodingTheory.LinearCode — Method
LinearCode(
    G::Union{Nemo.FqMatrix, Nemo.fpMatrix, Hecke.SMat, SparseArrays.SparseMatrixCSC},
    H::Union{Nemo.FqMatrix, Nemo.fpMatrix, Hecke.SMat, SparseArrays.SparseMatrixCSC};
    check_orthogonality
) -> LinearCode

Return the linear code defined by generator matrix G and parity-check matrix H, including when the matrices mix sparse and dense representations.

source
CodingTheory.LinearCode — Method
LinearCode(
    Gs::Vector{<:Union{Nemo.FqMatrix, Nemo.fpMatrix, Hecke.SMat, SparseArrays.SparseMatrixCSC}}
) -> LinearCode

Return the linear code generated by the vertical concatenation of Gs.

source
Base.:⊆ — Method
⊆(C1::AbstractLinearCode, C2::AbstractLinearCode) -> Any

Return whether or not C1 is a subcode of C2.

source
Base.:⊊ — Method
⊊(C1::AbstractLinearCode, C2::AbstractLinearCode) -> Any

Return whether C1 is a proper subcode of C2.

Notes

  • Containment is proper exactly when it holds and the dimensions differ, since a subcode of the same dimension is the whole code.
source
Base.in — Method
in(
    v::Union{Vector{Int64}, Vector{Nemo.FpFieldElem}, Vector{Nemo.fpFieldElem}, Nemo.FqMatrix, Nemo.fpMatrix, Hecke.SMat, SparseArrays.SparseMatrixCSC},
    C::AbstractLinearCode
) -> Any

Return whether or not v is a codeword of C.

source
Base.length — Method
length(C::AbstractLinearCode) -> Any

Return the length of C.

source
CodingTheory.:⊂ — Method
⊂(C1::AbstractLinearCode, C2::AbstractLinearCode) -> Any

Return whether C1 is a subcode of C2, not necessarily properly. This is an alias for ⊆; use ⊊ to test proper containment.

source
CodingTheory.Euclidean_hull — Method
Euclidean_hull(
    C::AbstractLinearCode
) -> Union{Tuple{Missing, Int64}, Tuple{LinearCode, Any}}

Return the Euclidean hull $C \cap C^\perp$ and its dimension. This is an alias for hull; the code component is missing when the hull has dimension zero.

source
CodingTheory.Hermitian_dual — Method
Hermitian_dual(
    C::AbstractLinearCode
) -> Union{LinearCode, MatrixProductCode}

Return the Hermitian dual of a code defined over a quadratic extension.

source
CodingTheory.Hermitian_hull — Method
Hermitian_hull(
    C::AbstractLinearCode
) -> Union{Tuple{Missing, Int64}, Tuple{LinearCode, Any}}

Return the Hermitian hull of C and its dimension. The Hermitian hull of a code is the intersection of it and its Hermitian dual.

source
CodingTheory.Singleton_bound — Method
Singleton_bound(C::AbstractLinearCode) -> Int64

Return the Singleton bound on the minimum distance of the code ($d \leq n - k + 1$).

source
CodingTheory.Singleton_bound — Method
Singleton_bound(n::Int64, a::Int64) -> Int64

Return the Singleton bound $d \leq n - k + 1$ or $k \leq n - d + 1$ depending on the interpretation of a.

source
CodingTheory.change_field! — Method
change_field!(
    C::AbstractLinearCode,
    F::AbstractAlgebra.FinField
)

In-place change of the base ring of C to F. Safely updates all cached matrices.

source
CodingTheory.change_field — Method
change_field(
    C::AbstractLinearCode,
    F::AbstractAlgebra.FinField
) -> AbstractLinearCode

Return a new linear code which is C changed to the base ring F.

source
CodingTheory.characteristic_polynomial — Method
characteristic_polynomial(C::AbstractLinearCode) -> Any

Return the characteristic polynomial of C.

Notes

  • The product runs over the nonzero weights of the dual code, so this requires the weight distribution of $C^\perp$.
source
CodingTheory.codewords — Function
codewords(C::AbstractLinearCode) -> Union{Nothing, Vector}
codewords(
    C::AbstractLinearCode,
    only_print::Bool
) -> Union{Nothing, Vector}

Return all codewords of C, or print them and return nothing when only_print is true. This is an alias for words; enumerating all $q^k$ codewords can require substantial time and memory.

source
CodingTheory.elements — Function
elements(C::AbstractLinearCode) -> Union{Nothing, Vector}
elements(
    C::AbstractLinearCode,
    only_print::Bool
) -> Union{Nothing, Vector}

Return all elements of C, or print them and return nothing when only_print is true. This is an alias for codewords and words; enumerating all $q^k$ elements can require substantial time and memory.

source
CodingTheory.hull — Method
hull(
    C::AbstractLinearCode
) -> Union{Tuple{Missing, Int64}, Tuple{LinearCode, Any}}

Return the (Euclidean) hull of C and its dimension.

source
CodingTheory.is_Hermitian_LCD — Method
is_Hermitian_LCD(C::AbstractLinearCode) -> Any

Return true if C is linear complementary Hermitian dual. A code is linear complementary Hermitian dual if the dimension of Hermitian_hull(C) is zero.

source
CodingTheory.is_MDS — Method
is_MDS(C::AbstractLinearCode) -> Any

Return true if code is maximum distance separable (MDS). Calculates the exact minimum distance if currently missing.

source
CodingTheory.is_l_Galois_LCD — Method
is_l_Galois_LCD(C::AbstractLinearCode, l::Int64) -> Any

Return true if C is linear complementary l-Galois dual (i.e., the dimension of l_Galois_hull(C, l) is zero).

source
CodingTheory.is_overcomplete — Function
is_overcomplete(C::AbstractLinearCode) -> Any
is_overcomplete(C::AbstractLinearCode, which::Symbol) -> Any

Return true if the generator matrix is overcomplete. If the optional parameter is set to :H, returns true if the parity-check matrix is overcomplete.

source
CodingTheory.is_subcode — Method
is_subcode(
    C1::AbstractLinearCode,
    C2::AbstractLinearCode
) -> Any

Return whether C1 is a subcode of C2, not necessarily properly.

source
CodingTheory.l_Galois_dual — Method
l_Galois_dual(
    C::AbstractLinearCode,
    l::Int64
) -> Union{LinearCode, MatrixProductCode}

Return the l-Galois dual of a code defined over a finite field.

source
CodingTheory.l_Galois_hull — Method
l_Galois_hull(
    C::AbstractLinearCode,
    l::Int64
) -> Union{Tuple{Missing, Int64}, Tuple{LinearCode, Any}}

Return the l-Galois hull of C and its dimension.

source
CodingTheory.number_correctable_errors — Method
number_correctable_errors(C::AbstractLinearCode) -> Any

Return the number of correctable errors for the code.

Notes

  • The number of correctable errors is $t = \floor{(d - 1) / 2}$.
source
CodingTheory.parity_check_matrix — Function
parity_check_matrix(C::AbstractLinearCode) -> Any
parity_check_matrix(
    C::AbstractLinearCode,
    stand_form::Bool
) -> Any

Return the parity-check matrix of C. Evaluates lazily and caches the result. If the optional parameter stand_form is set to true, the standard form is returned.

source
CodingTheory.random_linear_code — Method
random_linear_code(
    F::AbstractAlgebra.FinField,
    n::Int64,
    k::Int64;
    rng
) -> LinearCode

Return a random [n, k] linear code over F. Bypasses standard constructor checks for massive speedups on large codes.

source
CodingTheory.standard_form_permutation — Method
standard_form_permutation(C::AbstractLinearCode) -> Any

Return the permutation matrix required to permute the columns of the code matrices to have the same row space as the matrices in standard form. Evaluates lazily if not already computed.

source
CodingTheory.syndrome — Method
syndrome(
    C::AbstractLinearCode,
    v::Union{Vector{Int64}, Vector{Nemo.FpFieldElem}, Vector{Nemo.fpFieldElem}, Nemo.FqMatrix, Nemo.fpMatrix, Hecke.SMat, SparseArrays.SparseMatrixCSC}
) -> Any

Return the syndrome of v with respect to C.

source
CodingTheory.words — Function
words(C::AbstractLinearCode) -> Union{Nothing, Vector}
words(
    C::AbstractLinearCode,
    only_print::Bool
) -> Union{Nothing, Vector}

Return the elements of C. If only_print is true, the elements are only printed to the console and not returned.

source
Hecke.dimension — Method
dimension(C::AbstractLinearCode) -> Union{Missing, Int64}

Return the dimension of C.

source
Hecke.dual — Method
dual(C::AbstractLinearCode) -> GabidulinCode

Return the (Euclidean) dual of the code C. Evaluates lazily by swapping the cached generator and parity-check matrices.

source
Hecke.genus — Method
genus(C::AbstractLinearCode) -> Any

Return the genus, $n + 1 - k - d$, of the code.

source
Oscar.encode — Method
encode(
    C::AbstractLinearCode,
    v::Union{Nemo.FqMatrix, Nemo.fpMatrix, Hecke.SMat, SparseArrays.SparseMatrixCSC, Vector{Int64}}
) -> Any

Return the encoding of v into C.

source
Oscar.field — Method
field(C::AbstractLinearCode) -> Any

Return the base ring of the generator matrix of C.

source
Oscar.generator_matrix — Function
generator_matrix(C::AbstractLinearCode) -> Any
generator_matrix(
    C::AbstractLinearCode,
    stand_form::Bool
) -> Any

Return the generator matrix of C. Evaluates lazily and caches the result. If the optional parameter stand_form is set to true, the standard form is returned.

source

The following are not exported but may be useful.

Hecke.genus — Function
genus(C::AbstractLinearCode) -> Any

Return the genus, $n + 1 - k - d$, of the code.

source