Quasi-Cyclic Codes

Quasi-cyclic codes are a subtype of LinearCode and inherit its methods. They may be viewed as a generalization of cyclic codes, but here they are treated as an independent topic.

A quasi-cyclic code is presented by a matrix over a polynomial quotient ring, each entry standing for a circulant block. The type parameter is either :G or :H, recording whether that polynomial matrix represents the generator or the parity-check matrix. The noncirculant forms below expand the blocks back out over the base field; they are not stored at construction and are computed when first requested.

CodingTheory.QuasiCyclicCode — Type
QuasiCyclicCode(
    v::Vector{AbstractCyclicCode},
    l::Int64
) -> QuasiCyclicCode
QuasiCyclicCode(
    v::Vector{AbstractCyclicCode},
    l::Int64,
    parity::Bool
) -> QuasiCyclicCode

Return the quasi-cyclic code of index l whose circulants are determined by the cyclic codes in v. If the optional paramater parity is set to true, the input is used to construct the parity check matrix.

source
CodingTheory.QuasiCyclicCode — Type
QuasiCyclicCode(
    v::Union{Nemo.FqMatrix, Nemo.fpMatrix, Hecke.SMat, SparseArrays.SparseMatrixCSC},
    l::Int64
) -> QuasiCyclicCode
QuasiCyclicCode(
    v::Union{Nemo.FqMatrix, Nemo.fpMatrix, Hecke.SMat, SparseArrays.SparseMatrixCSC},
    l::Int64,
    parity::Bool
) -> QuasiCyclicCode

Return the quasi-cyclic code of index l generated by right-bit shifts of size l of the generator vector v. If the optional paramater parity is set to true, the input is used to construct the parity check matrix.

source
CodingTheory.QuasiCyclicCode — Method
QuasiCyclicCode(
    A::AbstractAlgebra.MatElem{T<:AbstractAlgebra.ResElem}
) -> QuasiCyclicCode
QuasiCyclicCode(
    A::AbstractAlgebra.MatElem{T<:AbstractAlgebra.ResElem},
    parity::Bool
) -> QuasiCyclicCode

Return the quasi-cyclic code specified by the matrix A of polynomial circulant generators. Evaluates lazily.

source
CodingTheory.QuasiCyclicCode — Method
QuasiCyclicCode(
    v::Array{T<:Union{Nemo.FqMatrix, Nemo.fpMatrix, Hecke.SMat, SparseArrays.SparseMatrixCSC}, 1},
    l::Int64,
    circ_gens::Bool
) -> QuasiCyclicCode
QuasiCyclicCode(
    v::Array{T<:Union{Nemo.FqMatrix, Nemo.fpMatrix, Hecke.SMat, SparseArrays.SparseMatrixCSC}, 1},
    l::Int64,
    circ_gens::Bool,
    parity::Bool
) -> QuasiCyclicCode

Return the quasi-cyclic code of index l generated by right-bit shifts of size l of the generator vectors v. If circ_gens is true, the vectors are taken to be (column) generators for the circulant matrices instead of generator vectors for the code. If the optional paramater parity is set to true, the input is used to construct the parity-check matrix.

Notes

  • If circ_gens is false, then the length of the code is ncols(v[1]) and must be divisible by l.
  • If circ_gens is true, then the length of the code is ncols(v[1]) * l. Circulant matrices are stacked in rows of length l, so l must divide length(v).
source
CodingTheory.QuasiCyclicCode — Method
QuasiCyclicCode(
    v::Array{T<:Union{Nemo.FqMatrix, Nemo.fpMatrix, Hecke.SMat, SparseArrays.SparseMatrixCSC}, 1},
    n::Int64,
    l::Int64
) -> QuasiCyclicCode
QuasiCyclicCode(
    v::Array{T<:Union{Nemo.FqMatrix, Nemo.fpMatrix, Hecke.SMat, SparseArrays.SparseMatrixCSC}, 1},
    n::Int64,
    l::Int64,
    parity::Bool
) -> QuasiCyclicCode

Return the quasi-cyclic code of index l whose circulants are defined by the generator polynomials v. If the optional paramater parity is set to true, the input is used to construct the parity check matrix.

source
CodingTheory.algebraic_dimension — Method
algebraic_dimension(C::AbstractQuasiCyclicCode) -> Any

Return the exact dimension k of the quasi-cyclic code, computed algebraically.

Notes

  • Uses the CRT decomposition to compute the rank over small extension fields.
  • Executes in a fraction of the time of rank(lift(A)).
source
CodingTheory.base_matrix — Method
base_matrix(
    A::AbstractAlgebra.MatElem{T<:AbstractAlgebra.ResElem}
) -> Any

Return the base matrix whose entries are the polynomial weights of A. This is an alias for weight_matrix.

source
CodingTheory.component_matrices — Method
component_matrices(
    C::AbstractQuasiCyclicCode
) -> Vector{Any}

Decompose the Quasi-Cyclic polynomial matrix into its Fourier/CRT components.

Notes

  • Returns a vector of tuples (g, A_K), where g is an irreducible factor of x^m - 1 and A_K is the polynomial matrix evaluated in the extension field F[x]/<g(x)>.
  • Bypasses the massive memory allocation of lift(A).
source
CodingTheory.exponent_matrix — Method
exponent_matrix(C::AbstractQuasiCyclicCode) -> Any

Return the exponent matrix of C, using -1 for zero circulants. This is an alias for shift_matrix and requires every nonzero polynomial entry to be a monomial.

source
CodingTheory.has_algebraic_4_cycle — Method
has_algebraic_4_cycle(C::AbstractQuasiCyclicCode) -> Bool

Return true if the quasi-cyclic code contains an algebraic 4-cycle, based on Fossorier's condition. Evaluates entirely in the polynomial domain.

source
CodingTheory.has_algebraic_cycle — Method
has_algebraic_cycle(
    C::AbstractQuasiCyclicCode,
    target_length::Int64
) -> Bool

Return true if the quasi-cyclic code contains an algebraic cycle of exactly target_length, based on Fossorier's condition.

Notes

  • target_length must be an even integer 2j (e.g., 4, 6, 8).
  • Evaluates entirely in the polynomial domain using a DFS backtracking algorithm.
source
CodingTheory.noncirculant_generator_matrix — Method
noncirculant_generator_matrix(
    C::AbstractQuasiCyclicCode
) -> Any

Return the non-circulant form of the generator matrix for the quasi-cyclic code C if the polynomial matrix specifies the generator matrix; otherwise, return missing.

source
CodingTheory.noncirculant_parity_check_matrix — Method
noncirculant_parity_check_matrix(
    C::AbstractQuasiCyclicCode
) -> Any

Return the non-circulant form of the parity-check matrix for the quasi-cyclic code C if the polynomial matrix specifies the parity-check matrix; otherwise, return missing.

source
CodingTheory.polynomial_matrix — Method
polynomial_matrix(C::AbstractQuasiCyclicCode) -> Any

Return the polynomial matrix used to define the code. Use polynomial_matrix_type to determine if specifies the generator or parity-check matrix.

source
CodingTheory.protograph_matrix — Method
protograph_matrix(
    A::AbstractAlgebra.MatElem{T<:AbstractAlgebra.ResElem}
) -> Any

Return the protograph matrix whose entries are the polynomial weights of A. This is an alias for weight_matrix and base_matrix.

source
CodingTheory.shift_matrix — Method
shift_matrix(C::AbstractQuasiCyclicCode) -> Any

Return the integer shift matrix (exponent matrix) of the Quasi-Cyclic code.

Notes

  • If a circulant is a pure monomial x^e, its entry is e.
  • If a circulant is the zero matrix, its entry is -1.
  • Throws an error if the matrix contains polynomials with multiple terms.
source
CodingTheory.type — Method
type(C::AbstractQuasiCyclicCode) -> Any

Return the type of the quasi-cycle code C.

source
CodingTheory.weight_matrix — Method
weight_matrix(
    A::AbstractAlgebra.MatElem{T<:AbstractAlgebra.ResElem}
) -> Any

Return the matrix whose entries are the numbers of nonzero coefficients in the polynomial representatives of the entries of A.

source
Hecke.index — Method
index(C::AbstractQuasiCyclicCode) -> Any

Return the index of the quasi-cyclic code.

source

The following are not exported but may be useful.

Hecke.index — Function
index(C::AbstractQuasiCyclicCode) -> Any

Return the index of the quasi-cyclic code.

source