Cyclic Codes

Cyclic codes are a subtype of LinearCode and inherit its methods. For more information on how to use these functions, see the cyclic code tutorial.

Cyclotomic Cosets

The following set of functions are useful for defining cyclic codes.

CodingTheory.ord — Function

ord(n::Int, q::Int)

Return the order of n mod q.

source

CodingTheory.cyclotomic_coset — Function

cyclotomic_coset(x::Int, q::Int, n::Int, to_sort::Bool=true, verbose::Bool=false)

Return the q-cyclotomic coset of x modulo n.

Notes

If the optional parameter to_sort is set to false, the result will not be

sorted. If the optional parameter verbose is set to true, the result will pretty print.

source

CodingTheory.all_cyclotomic_cosets — Function

all_cyclotomic_cosets(q::Int, n::Int, to_sort::Bool=true, verbose::Bool=false)

Return all q-cyclotomic cosets modulo n.

Notes

If the optional parameter to_sort is set to false, the result will not be

sorted. If the optional parameter verbose is set to true, the result will pretty print.

source

CodingTheory.complement_qcosets — Function

complement_qcosets(q::Int, n::Int, qcosets::Vector{Vector{Int64}})

Return the complement of the q-cyclotomic cosets modulo n of qcosets.

source

CodingTheory.qcoset_pairings — Function

qcoset_pairings(arr::Vector{Vector{Int64}}, n::Int)

Return the q-cyclotomic cosets modulo n collected into complementary pairs.

source

Missing docstring.

Missing docstring for qcoset_table. Check Documenter's build log for details.

CodingTheory.dual_qcosets — Function

dual_qcosets(q::Int, n::Int, qcosets::Vector{Vector{Int64}})

Return the dual of the q-cyclotomic cosets modulo n of qcosets.

source

Constructors

CodingTheory.CyclicCode — Type

CyclicCode(q::Int, n::Int, cosets::Vector{Vector{Int}})

Return the CyclicCode of length n over GF(q) with q-cyclotomic cosets cosets.

Notes

This function will auto determine if the constructed code is BCH or Reed-Solomon

and call the appropriate constructor.

Examples

julia> q = 2; n = 15; b = 3; δ = 4;
julia> cosets = defining_set([i for i = b:(b + δ - 2)], q, n, false);
julia> C = CyclicCode(q, n, cosets)

source

CyclicCode(n::Int, g::fq_nmod_poly)

Return the length n cyclic code generated by the polynomial g.

source

CodingTheory.BCHCode — Type

BCHCode(q::Int, n::Int, δ::Int, b::Int=0)

Return the BCHCode of length n over GF(q) with design distance δ and offset b.

Notes

This function will auto determine if the constructed code is Reed-Solomon

and call the appropriate constructor.

Examples

julia> q = 2; n = 15; b = 3; δ = 4;
julia> B = BCHCode(q, n, δ, b)
[15, 5, ≥7; 1]_2 BCH code over splitting field GF(16).
2-Cyclotomic cosets:
        C_1 ∪ C_3 ∪ C_5
Generator polynomial:
        x^10 + x^8 + x^5 + x^4 + x^2 + x + 1
Generator matrix: 5 × 15
        1 1 1 0 1 1 0 0 1 0 1 0 0 0 0
        0 1 1 1 0 1 1 0 0 1 0 1 0 0 0

        0 0 1 1 1 0 1 1 0 0 1 0 1 0 0
        0 0 0 1 1 1 0 1 1 0 0 1 0 1 0
        0 0 0 0 1 1 1 0 1 1 0 0 1 0 1

source

BCHCode(C::AbstractCyclicCode)

Return the BCH supercode of the cyclic code C.

source

CodingTheory.ReedSolomonCode — Type

ReedSolomonCode(q::Int, δ::Int, b::Int=0)

Return the ReedSolomonCode over GF(q) with distance d and offset b.

Examples

julia> ReedSolomonCode(8, 3, 0)
[7, 5, ≥3; 0]_8 Reed Solomon code.
8-Cyclotomic cosets:
        C_0 ∪ C_1
Generator polynomial:
        x^2 + (α + 1)*x + α
Generator matrix: 5 × 7
        α α + 1 1 0 0 0 0
        0 α α + 1 1 0 0 0
        0 0 α α + 1 1 0 0
        0 0 0 α α + 1 1 0
        0 0 0 0 α α + 1 1

julia> ReedSolomonCode(13, 5, 1)
[12, 8, ≥5; 1]_13 Reed Solomon code.
13-Cyclotomic cosets:
        C_1 ∪ C_2 ∪ C_3 ∪ C_4
Generator polynomial:
        x^4 + 9*x^3 + 7*x^2 + 2*x + 10
Generator matrix: 8 × 12
        10 2 7 9 1 0 0 0 0 0 0 0
        0 10 2 7 9 1 0 0 0 0 0 0
        0 0 10 2 7 9 1 0 0 0 0 0
        0 0 0 10 2 7 9 1 0 0 0 0
        0 0 0 0 10 2 7 9 1 0 0 0
        0 0 0 0 0 10 2 7 9 1 0 0
        0 0 0 0 0 0 10 2 7 9 1 0
        0 0 0 0 0 0 0 10 2 7 9 1

source

CodingTheory.QuadraticResidueCode — Function

QuadraticResidueCode(q::Int, n::Int)

Return the cyclic code whose roots are the quadratic residues of q, n.

source

Attributes

CodingTheory.splitting_field — Function

splitting_field(C::AbstractCyclicCode)

Return the splitting field of the generator polynomial.

source

AbstractAlgebra.polynomial_ring — Function

polynomial_ring(C::AbstractCyclicCode)

Return the polynomial ring of the generator polynomial.

source

CodingTheory.primitive_root — Function

primitive_root(C::AbstractCyclicCode)

Return the primitive root of the splitting field.

source

CodingTheory.offset — Function

offset(C::AbstractBCHCode)

Return the offset of the BCH code.

source

CodingTheory.design_distance — Function

design_distance(C::AbstractBCHCode)

Return the design distance of the BCH code.

source

CodingTheory.qcosets — Function

qcosets(C::AbstractCyclicCode)

Return the q-cyclotomic cosets of the cyclic code.

source

CodingTheory.qcosets_reps — Function

qcosets_reps(C::AbstractCyclicCode)

Return the set of representatives for the q-cyclotomic cosets of the cyclic code.

source

CodingTheory.defining_set — Function

defining_set(C::AbstractCyclicCode)

Return the defining set of the cyclic code.

source

defining_set(nums::Vector{Int}, q::Int, n::Int, flat::Bool=true)

Returns the set of q-cyclotomic cosets of the numbers in nums modulo n.

Notes

If flat is set to true, the result will be a single flattened and sorted array.

source

Base.zeros — Function

zeros(C::AbstractCyclicCode)

Return the zeros of C.

source

CodingTheory.nonzeros — Function

nonzeros(C::AbstractCyclicCode)

Return the nonzeros of C.

source

CodingTheory.generator_polynomial — Function

generator_polynomial(C::AbstractCyclicCode)

Return the generator polynomial of the cyclic code.

source

CodingTheory.parity_check_polynomial — Function

parity_check_polynomial(C::AbstractCyclicCode)

Return the parity-check polynomial of the cyclic code.

source

CodingTheory.idempotent — Function

idempotent(C::AbstractCyclicCode)

Return the idempotent (polynomial) of the cyclic code.

source

Missing docstring.

Missing docstring for BCH_bound. Check Documenter's build log for details.

CodingTheory.is_narrowsense — Function

is_narrow_sense(C::AbstractBCHCode)

Return true if the BCH code is narrowsense.

source

CodingTheory.is_reversible — Function

is_reversible(C::AbstractCyclicCode)

Return true if the cyclic code is reversible.

source

CodingTheory.is_degenerate — Function

is_degenerate(C::AbstractCyclicCode)

Return true if the cyclic code is degenerate.

Notes

A cyclic code is degenerate if the parity-check polynomial divides x^r - 1 for

some r less than the length of the code.

source

Hecke.is_primitive — Function

is_primitive(C::AbstractBCHCode)

Return true if the BCH code is primitive.

source

CodingTheory.is_antiprimitive — Function

is_antiprimitive(C::AbstractBCHCode)

Return true if the BCH code is antiprimitive.

source

Methods

Missing docstring.

Missing docstring for defining_set. Check Documenter's build log for details.

CodingTheory.dual_defining_set — Function

dual_defining_set(def_set::Vector{Int}, n::Int)

Return the defining set of the dual code of length n and defining set def_set.

source

CodingTheory.is_cyclic — Function

is_cyclic(C::AbstractLinearCode)

Return true and the equivalent cyclic code object if C is a cyclic code; otherwise, return false, missing.

source

Oscar.complement — Function

complement(C::AbstractCyclicCode)

Return the cyclic code whose cyclotomic cosets are the completement of C's.

source

Base.:∩ — Function

∩(C1::AbstractCyclicCode, C2::AbstractCyclicCode)

Return the intersection code of C1 and C2.

source

Base.:+ — Function

+(C1::AbstractCyclicCode, C2::AbstractCyclicCode)

Return the addition code of C1 and C2.

source