Cyclic Codes

BCHCode(
    q::Int64,
    n::Int64,
    δ::Int64
) -> Union{BCHCode, ReedSolomonCode}
BCHCode(
    q::Int64,
    n::Int64,
    δ::Int64,
    b::Int64
) -> Union{BCHCode, ReedSolomonCode}

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

CyclicCode(
    q::Int64,
    n::Int64,
    elements::Vector{<:AbstractAlgebra.FinFieldElem};
    type
) -> Union{BCHCode, CyclicCode, ReedSolomonCode}

Return the Cyclic code of length n over GF(q) defined by the exact field elements passed in elements. If type = :nonzeros, they are treated as the non-roots.

CyclicCode(
    q::Int64,
    n::Int64,
    elements::Vector{Int64};
    type
) -> Union{BCHCode, CyclicCode, ReedSolomonCode}

Return the Cyclic code of length n over GF(q) defined by the roots given as integer exponents in elements (where the roots are β^i for i ∈ elements). If type = :nonzeros is passed, elements are treated as the non-root exponents.

CyclicCode(
    q::Int64,
    n::Int64,
    cosets::Vector{Vector{Int64}}
) -> Union{BCHCode, CyclicCode, ReedSolomonCode}

Return the CyclicCode of length n over GF(q) with q-cyclotomic cosets cosets. Evaluates lazily and auto-detects BCH and Reed-Solomon parameters.

CyclicCode(
    n::Int64,
    g::Union{Nemo.FqPolyRingElem, Nemo.fpPolyRingElem, Nemo.fqPolyRepPolyRingElem}
) -> Union{BCHCode, CyclicCode, ReedSolomonCode}

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

ReedSolomonCode(q::Int64, d::Int64) -> ReedSolomonCode
ReedSolomonCode(
    q::Int64,
    d::Int64,
    b::Int64
) -> ReedSolomonCode

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

is_irreducible(C::AbstractCyclicCode) -> Bool

Return true if the cyclic code C is irreducible.

Notes

• An irreducible cyclic code has no non-trivial cyclic subcodes.
• Algebraically, this occurs if and only if its non-zeros form exactly one q-cyclotomic coset (meaning it has exactly one constituent).

polynomial_ring(C::AbstractCyclicCode) -> Any

Return the polynomial ring of the generator polynomial.

⊆(C1::AbstractCyclicCode, C2::AbstractCyclicCode) -> Any

Return whether or not C1 is a subcode of C2. A cyclic code is a subcode of another if and only if its defining set is a superset of the other's.

zeros(C::AbstractCyclicCode) -> Any

Return the zeros (as field elements) of C.

⊂(C1::AbstractCyclicCode, C2::AbstractCyclicCode) -> Any

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

BCH_bound(C::AbstractCyclicCode) -> Any

Return the BCH bound for C. Computes lazily and caches the result.

BCH_offset(C::AbstractCyclicCode) -> Any

Return the offset of the BCH bound for C. Computes lazily.

DuadicCodes(
    q::Int64,
    n::Int64;
    include_zero
) -> NamedTuple{(:codes, :multiplier), <:Tuple{Vector{T} where T<:AbstractCyclicCode, Union{Missing, Int64}}}

Return the pair of Duadic codes of length n over GF(q).

Notes

• Duadic codes exist if and only if there is a multiplier of order 2 that splits the roots.
• Quadratic Residue (QR) codes are a special, highly symmetric case of Duadic codes.

FireCode(
    p::Union{Nemo.FqPolyRingElem, Nemo.fpPolyRingElem},
    l::Int64
) -> Union{BCHCode, CyclicCode, ReedSolomonCode}

Return the fire code with generator polynomial (x^(2l - 1) + 1) * p.

HT_bound(C::AbstractCyclicCode) -> Any

Return the Hartmann-Tzeng bound for C. Computes lazily and caches the result.

Hadamard_product_code(
    C1::AbstractCyclicCode,
    C2::AbstractCyclicCode
) -> Union{BCHCode, CyclicCode, ReedSolomonCode}

Return the entrywise product code of C1 and C2, or the entrywise square of C. This is an alias for Schur_product_code.

MattsonSolomon_transform(
    v::Vector{<:AbstractAlgebra.FinFieldElem},
    α::AbstractAlgebra.FinFieldElem
) -> Any

Return the Mattson–Solomon polynomial of a vector v over F.

Notes

• The Mattson-Solomon transform is the finite field equivalent of the Discrete Fourier Transform (DFT).

PolyadicCodes(
    q::Int64,
    n::Int64,
    m::Int64;
    include_zero
) -> NamedTuple{(:codes, :multiplier), <:Tuple{Vector{T} where T<:AbstractCyclicCode, Union{Missing, Int64}}}

Return the family of m Polyadic codes of length n over GF(q).

Notes

• Searches for a multiplier μ_a that splits the non-zero roots into m cycling sets.
• Returns a NamedTuple containing the array of m codes and the multiplier a used.
• If include_zero = true, the root 0 is added to all defining sets (yielding the even-like subcodes).

QuadraticResidueCode(
    q::Int64,
    n::Int64
) -> Union{BCHCode, CyclicCode, ReedSolomonCode}

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

Roos_bound(C::AbstractCyclicCode) -> Any

Return the Roos bound for C. Computes lazily and caches the result.

Schur_product_code(
    C1::AbstractCyclicCode,
    C2::AbstractCyclicCode
) -> Union{BCHCode, CyclicCode, ReedSolomonCode}

Return the entrywise product code of C1 and C2, or the entrywise square of C. This is an alias for entrywise_product_code.

TetradicCodes(
    q::Int64,
    n::Int64;
    include_zero
) -> NamedTuple{(:codes, :multiplier), <:Tuple{Vector{T} where T<:AbstractCyclicCode, Union{Missing, Int64}}}

Return the quad of Tetradic codes of length n over GF(q).

TriadicCodes(
    q::Int64,
    n::Int64;
    include_zero
) -> NamedTuple{(:codes, :multiplier), <:Tuple{Vector{T} where T<:AbstractCyclicCode, Union{Missing, Int64}}}

Return the triplet of Triadic codes of length n over GF(q).

ambient_constituents(
    q::Int64,
    n::Int64
) -> Vector{AbstractCyclicCode}

Return all irreducible cyclic codes of length n over GF(q).

Notes

• This decomposes the entire ambient space F_q[x]/<x^n - 1> into its minimal ideals.

apply_multiplier(
    C::AbstractCyclicCode,
    a::Int64
) -> Union{BCHCode, CyclicCode, ReedSolomonCode}

Return a new cyclic code by applying the multiplier a to the cyclic code C.

Notes

• Algebraically, this multiplies the defining set of the code by a (mod n).
• This implies the codewords of the new code are a permutation of the original codewords.

apply_multiplier(v::Array{T, 1}, a::Int64) -> Vector

Apply the multiplier a to the vector v of length n.

Notes

• The multiplier maps the coordinate index i to a * i (mod n).
• Requires gcd(a, n) == 1 to ensure the mapping is a valid permutation.

componentwise_product_code(
    C1::AbstractCyclicCode,
    C2::AbstractCyclicCode
) -> Union{BCHCode, CyclicCode, ReedSolomonCode}

Return the entrywise product code of C1 and C2, or the entrywise square of C. This is an alias for Schur_product_code.

constituents(
    C::AbstractCyclicCode
) -> Vector{<:AbstractCyclicCode}

Return the irreducible cyclic constituents of the cyclic code C.

Notes

• By the Chinese Remainder Theorem, every cyclic code is a direct sum of irreducible cyclic codes.
• These constituents correspond to the individual q-cyclotomic cosets that make up the non-zeros (the trace representation) of C.

defining_set(
    nums::Vector{Int64},
    q::Int64,
    n::Int64
) -> Union{Vector{Vector{Int64}}, Vector{Int64}}
defining_set(
    nums::Vector{Int64},
    q::Int64,
    n::Int64,
    flat::Bool
) -> Union{Vector{Vector{Int64}}, Vector{Int64}}

Return the set of q-cyclotomic cosets of the numbers in nums modulo n. If flat is true, returns a single sorted array of the defining set.

defining_set(C::AbstractCyclicCode) -> Any

Return the defining set (as integer exponents) of the cyclic code.

design_distance(C::AbstractBCHCode) -> Any

Return the design distance of the BCH code.

dual_defining_set(
    def_set::Vector{Int64},
    n::Int64
) -> Vector{Int64}

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

Notes

• Mathematically, if C has roots β^i for i ∈ Z, the dual has roots β^(-i) for i ∉ Z.

entrywise_product_code(
    C1::AbstractCyclicCode,
    C2::AbstractCyclicCode
) -> Union{BCHCode, CyclicCode, ReedSolomonCode}

Return the entrywise (Schur / Hadamard) product of cyclic codes C1 and C2.

Notes

• By the Mattson-Solomon Transform, the non-zeros of the Schur product are the Minkowski sum of the non-zeros of the constituent codes.

entrywise_product_code(
    C::AbstractCyclicCode
) -> Union{BCHCode, CyclicCode, ReedSolomonCode}

Return the entrywise (Schur / Hadamard) product of C with itself.

generator_polynomial(C::AbstractCyclicCode) -> Any

Return the generator polynomial of the cyclic code.

idempotent(C::AbstractCyclicCode) -> Any

Return the idempotent (polynomial) of the cyclic code.

inverse_MattsonSolomon_transform(
    MS::AbstractAlgebra.PolyRingElem{<:AbstractAlgebra.FinFieldElem},
    n::Int64,
    α::AbstractAlgebra.FinFieldElem
) -> Any

Return the vector recovered by applying the inverse Mattson–Solomon transform to the Mattson–Solomon polynomial MS.

is_antiprimitive(C::AbstractBCHCode) -> Any

Return true if the BCH code is antiprimitive.

is_multiplier_equivalent(
    C1::AbstractCyclicCode,
    C2::AbstractCyclicCode
) -> Tuple{Bool, Any}

Return true and the multiplier a if the cyclic codes C1 and C2 are multiplier equivalent. Otherwise, return false and missing.

Notes

• Two cyclic codes are multiplier equivalent if there exists some multiplier a coprime to n such that μ_a(C1) == C2.
• Multiplier equivalence implies the codes are permutation equivalent and share the same weight enumerator and minimum distance.

is_narrowsense(C::AbstractBCHCode) -> Any

Return true if the BCH code is narrow-sense (offset b is 1 or 0 depending on convention).

is_reversible(C::AbstractCyclicCode) -> Any

Return true if the cyclic code is reversible.

is_self_dual(C::AbstractCyclicCode) -> Any

Return whether or not C == dual(C).

is_subcode(
    C1::AbstractCyclicCode,
    C2::AbstractCyclicCode
) -> Any

Return true if C1 is a subcode of C2, and false otherwise. For cyclic codes this holds exactly when the defining set of C1 contains the defining set of C2.

multiplier_group(C::AbstractCyclicCode) -> Vector{Int64}

Return the set of all multipliers a that map the cyclic code C strictly to itself.

Notes

• This set forms a subgroup of the multiplicative group (Z/nZ)*.
• These multipliers correspond to the automorphisms of the cyclic code.

multiplier_subgroup_Sn(
    C::AbstractCyclicCode
) -> Tuple{Oscar.PermGroup, Oscar.GAPGroupEmbedding{Oscar.PermGroup, Oscar.PermGroup}}

Return the multiplier group of C as a formal subgroup of the symmetric group S_n.

Notes

• Returns (H, f), where H is the subgroup and f is the inclusion morphism H -> S_n.
• The multiplier action i -> a * i (mod n) is internally shifted to 1-based indexing to match Oscar's permutation group standards.

multiplier_subgroup_Zn(C::AbstractCyclicCode) -> Any

Return the multiplier group of C as a formal subgroup of the unit group Z_n^x.

Notes

• Returns (H, inc), where H is the abstract abelian subgroup and inc is the injection.
• To map an element h ∈ H back to an integer, use the unit group isomorphism: R, _ = residue_ring(ZZ, C.n); U, f = unit_group(R); int_val = lift(f(inc(h)))

nonzeros(C::AbstractCyclicCode) -> Any

Return the nonzeros (as field elements) of C.

offset(C::AbstractBCHCode) -> Any

Return the offset of the BCH code.

parity_check_matrix(C::AbstractCyclicCode) -> Any
parity_check_matrix(
    C::AbstractCyclicCode,
    stand_form::Bool
) -> Any

Return the parity-check matrix of the cyclic code. Evaluates lazily by extracting the reversed coefficients of the parity polynomial C.h.

parity_check_polynomial(C::AbstractCyclicCode) -> Any

Return the parity-check polynomial of the cyclic code.

primitive_root(C::AbstractCyclicCode) -> Any

Return the primitive root of the splitting field.

print_all_cyclic_codes(io::IO, n::Int64, q::Int64)
print_all_cyclic_codes(
    io::IO,
    n::Int64,
    q::Int64,
    def_set::Bool
)

Print all cyclic codes of length n over GF(q).

Set def_set to true to include each defining set, BCH offset, and BCH bound. The table includes the zero and full ambient codes.

print_all_cyclotomic_cosets(io::IO, n::Int64, q::Int64)

Print one cyclic code for each q-cyclotomic coset modulo n.

Each row gives the code obtained by omitting that coset from the defining set, together with its dimension, BCH offset and bound, generator polynomial, idempotent, and defining cosets.

qcosets(C::AbstractCyclicCode) -> Any

Return the q-cyclotomic cosets of the cyclic code.

qcosets_reps(C::AbstractCyclicCode) -> Any

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

splitting_field(C::AbstractCyclicCode) -> Any

Return the splitting field of the generator polynomial.

trace_representation(C::AbstractCyclicCode) -> Vector{Int64}

Return the Trace representation parameters of the cyclic code C.

Notes

• Returns a vector of the primitive root powers that define the independent trace components of the codewords.
• A codeword c can be generated by c_i = sum_j Tr_{E/F}( A_j * β^(i * j) ) where A_j are arbitrary elements in the splitting field.

dual(
    C::AbstractCyclicCode
) -> Union{BCHCode, CyclicCode, ReedSolomonCode}

Return the dual of the cyclic code C. This operation evaluates in O(1) time using the dual defining set properties.

is_cyclic(
    C::AbstractLinearCode
) -> Union{Tuple{Bool, Missing}, Tuple{Bool, AbstractLinearCode}}

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

is_degenerate(C::AbstractCyclicCode) -> Bool

Return true if the cyclic code is degenerate. A cyclic code is degenerate if the parity-check polynomial divides x^r - 1 for some r < n.

is_primitive(C::AbstractBCHCode) -> Any

Return true if the BCH code is primitive.

complement(
    C::AbstractCyclicCode
) -> Union{BCHCode, CyclicCode, ReedSolomonCode}

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

generator_matrix(C::AbstractCyclicCode) -> Any
generator_matrix(
    C::AbstractCyclicCode,
    stand_form::Bool
) -> Any

Return the generator matrix of the cyclic code. Evaluates lazily by extracting the coefficients of the generator polynomial C.g and mapping them into a strictly typed dense matrix (fpMatrix or FqMatrix).

all_cyclotomic_cosets(
    q::Int64,
    n::Int64;
    to_sort,
    verbose
) -> Vector{Vector{Int64}}

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.

are_conjugates(
    x::AbstractAlgebra.FinFieldElem,
    y::AbstractAlgebra.FinFieldElem,
    q::Int64
) -> Bool

Return true if x and y are conjugates over the subfield of order q.

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

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

cyclotomic_coset(
    x::Int64,
    q::Int64,
    n::Int64;
    to_sort,
    verbose
) -> Vector{Int64}

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.

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

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

minimal_polynomial(
    coset::Vector{Int64},
    α::AbstractAlgebra.FinFieldElem
) -> Any

Return the minimal polynomial of α defined by the q-cyclotomic coset coset.

Notes

• The minimal polynomial is computed over the parent field of α, but mathematically its coefficients are guaranteed to lie in the base field GF(q).

ord(n::Int64, q::Int64) -> Int64

Return the multiplicative order of q mod n.

qcoset_pairings(
    arr::Vector{Vector{Int64}},
    n::Int64
) -> Tuple{Vector{Tuple{Vector{Int64}, Vector{Int64}}}, Vector{Tuple{Int64, Int64}}}

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

qcoset_table(a::Int64, b::Int64, q::Int64)

Print all q-cyclotomic cosets modulo n for n between a and b.

is_degenerate(C::AbstractCyclicCode) -> Bool

Return true if the cyclic code is degenerate. A cyclic code is degenerate if the parity-check polynomial divides x^r - 1 for some r < n.

is_cyclic(
    C::AbstractLinearCode
) -> Union{Tuple{Bool, Missing}, Tuple{Bool, AbstractLinearCode}}

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