Trellises

A trellis is a layered graph whose paths are exactly the codewords of a code, built from a generator matrix in trellis-oriented (minimal-span) form. Its size depends on the coordinate ordering, so the permutation and sectionalization functions below search for an ordering that keeps the vertex and edge counts small. The past and future profiles are what drive that search: they record how many generators are active on each side of every coordinate boundary.

Because a trellis represents the whole code compactly, it yields weight distributions and minimum distances without enumerating codewords; see Weight enumerators.

CodingTheory.edge_counts — Function
edge_counts(
    k::Int64,
    n::Int64,
    past::Vector{Int64},
    future::Vector{Int64}
) -> Vector{Int64}
edge_counts(
    k::Int64,
    n::Int64,
    past::Vector{Int64},
    future::Vector{Int64},
    boundaries::Vector{Int64}
) -> Vector{Int64}

Return an array representing the edge complexity (number of active generators) for each macro-section defined by the boundaries for the Trellis Product graph. Defaults to the unsectionalized step-by-step counts if boundaries is omitted.

source
CodingTheory.optimal_sectionalization — Method
optimal_sectionalization(
    M::Array{T, 2},
    q::Int64;
    type,
    max_width,
    p,
    p_x,
    p_y,
    grid_x,
    grid_y
) -> Vector{Int64}

Return sectional boundaries optimized to minimize the Viterbi trellis's peak state and branch complexity. Enforces a strict max_width to prevent exponential branch evaluation traps in low-density or syndrome matrices.

Notes

The supported sectionalization types are:

  • :linear - Standard optimal sectionalization for a generic code.
  • :QC - Imposes periodicity for a Quasi-Cyclic code. Requires kwarg p (block size).
  • :twoD - Evaluates a 2D grid mapped to 1D. Requires kwargs p_x, p_y, grid_x, grid_y.
source
CodingTheory.optimize_trellis_permutation — Method
optimize_trellis_permutation(
    M::Array{T, 2}
) -> Tuple{Matrix, Vector{Int64}, Int64}
optimize_trellis_permutation(
    M::Array{T, 2},
    num_trials::Int64
) -> Tuple{Matrix, Vector{Int64}, Int64}

Applies random column permutations to matrix M, transforms each into Trellis-Oriented Form (TOF), and profiles the maximum active edge span. Returns the permuted TOF matrix that yields the smallest peak trellis complexity.

source
CodingTheory.past_future_profiles — Method
past_future_profiles(
    L::Vector{Int64},
    R::Vector{Int64},
    n::Int64
) -> Tuple{Vector{Int64}, Vector{Int64}}

Return the past and future dimension profiles at boundaries $0, \ldots, n$. For each boundary, the past profile counts row spans ending there or earlier, while the future profile counts row spans starting strictly later.

source
CodingTheory.vertex_counts — Function
vertex_counts(
    k::Int64,
    n::Int64,
    past::Vector{Int64},
    future::Vector{Int64}
) -> Vector{Int64}
vertex_counts(
    k::Int64,
    n::Int64,
    past::Vector{Int64},
    future::Vector{Int64},
    boundaries::Vector{Int64}
) -> Vector{Int64}

Return an array representing the number of active generators (vertex exponent) exactly at each chosen section boundary for the Trellis Product graph. Defaults to the unsectionalized step-by-step counts if boundaries is omitted.

source
CodingTheory.weight_distribution_trellis — Method
weight_distribution_trellis(
    C::AbstractLinearCode;
    num_trials,
    verbose
) -> Dict{Int64, BigInt}

Return the Hamming weight distribution of the linear code C computed from a trellis.

Notes

  • Uses the primal generator trellis product for low-rate codes and the dual generator trellis product followed by the MacWilliams identity for high-rate codes.
source