Decoding LDPC Codes

struct SoftDecisionWorkspace{T<:AbstractFloat}

Store every buffer the soft-decision decoder needs, allocated once for one fixed parity-check matrix and reused for every syndrome.

The Tanner graph is stored as a flat edge list in check-major order. Edge e connects check c (the unique c with chk_ptr[c] <= e < chk_ptr[c + 1]) to variable edge_var[e]. The edges incident on variable v are var_edges[var_ptr[v]:var_ptr[v + 1] - 1].

balance_of_layered_schedule(
    layer_ptr::AbstractVector{<:Integer}
) -> Any

Return the ratio of the largest layer to the smallest. 1 means every layer is the same size, which is the best case for a parallel implementation of a layered schedule.

Reference: Layered decoding of quantum LDPC codes.

boxplus_exact(x::Float64, y::Float64) -> Float64

Return the exact box-plus operator (Jacobian logarithm) for sum-product. Mathematically the tanh rule, but numerically bulletproof against NaNs.

boxplus_minsum(x::Float64, y::Float64) -> Float64

Return the min-sum box-plus operator.

boxplus_minsum_correction(x::Float64, y::Float64) -> Float64

Return the min-sum box-plus operator with a low-complexity correction term.

csr_of(H::AbstractMatrix) -> Tuple{Any, Vector{Int64}}

Return a compressed sparse row description of H, 1-based, with column indices ascending within each row. A convenience for Julia-side callers and tests; FlamingPy passes scipy's CSR arrays straight to init_soft_workspace instead, and this function is the only thing in the file that is quadratic in the matrix size.

csr_of(
    H::Union{Nemo.FqMatrix, Nemo.fpMatrix}
) -> Tuple{Vector{Int64}, Vector{Int64}}

Return the Flint-native form for CodingTheory callers holding an Oscar matrix. The plain array and compressed-sparse-row entry points throughout this file are reserved for the Python caller, which never sees a Flint matrix, so the conversion to a dense Julia matrix is confined to this thin layer – and, since every use of it is a workspace constructor, is paid once per matrix rather than once per decode.

decode!(
    W::SoftDecisionWorkspace{Float64},
    LLR_in::AbstractVector{<:Real};
    algorithm,
    schedule,
    decimation,
    oscillation,
    max_iter,
    attenuation,
    offset,
    dec_thresh,
    dec_rounds,
    syndrome,
    erasures,
    decimated_bits,
    decimated_values,
    out
) -> Tuple{Bool, Int64}

Return (converged, iterations) after decoding one channel realization into W, and optionally copy the hard decisions into out.

Only (converged, iterations) is returned, so that a decode moves no array across a language boundary unless the caller asks for one (FIX-14). The decisions also stay available as W.current_bits until the next decode overwrites them. A negative iterations means the decoder stopped early on a detected oscillation.

Keyword arguments:

• algorithm: :sum_product, :min_sum, :normalized_min_sum, :offset_min_sum or :min_sum_correction.
• schedule: :flooding, or :layered/:serial to sweep the partition the workspace was built with.
• max_iter, attenuation (normalized min-sum), offset (offset min-sum).
• decimation: :none, :auto, :guided or :manual.
• oscillation: :none, or :active to detect a two-cycle in the hard decisions and either force a decimation step or give up.
• syndrome, erasures, decimated_bits, decimated_values: forwarded to load_soft_channel!.
• out: a length-num_var integer buffer to receive the hard decisions.

On a small dense high-rate matrix decoded from a constant channel LLR vector, the min-sum family under :layered/:serial can stall at an exact stationary point; see the :layered engine above and notes/MP_and_OSD_decoder_findings.md.

init_soft_workspace(
    H::AbstractMatrix;
    schedule,
    layer_ptr,
    layer_checks
) -> SoftDecisionWorkspace{Float64}

Return a decoder workspace from any AbstractMatrix. This method densely scans H, so prefer the compressed-sparse-row form for anything large.

init_soft_workspace(
    row_ptr::AbstractVector{<:Integer},
    col_ind::AbstractVector{<:Integer},
    num_check::Integer,
    num_var::Integer;
    schedule,
    layer_ptr,
    layer_checks,
    base
) -> SoftDecisionWorkspace{Float64}

Return a newly allocated decoder workspace for the parity-check matrix given in compressed sparse row form. Linear in the number of edges (FIX-9).

row_ptr and col_ind are exactly scipy's H.indptr and H.indices for a csr_matrix; pass base = 0 for those, which is the default, since the Python caller is the hot path.

schedule selects the layer partition to precompute: :flooding builds none, :layered colours the graph, :serial puts one check per layer. Passing layer_ptr and layer_checks supplies a partition directly – computed once on the Python side, cached, and reused across processes – and overrides schedule.

init_soft_workspace(
    H::Union{Nemo.FqMatrix, Nemo.fpMatrix};
    schedule,
    layer_ptr,
    layer_checks
) -> SoftDecisionWorkspace{Float64}

Return a decoder workspace from a Flint matrix, as in csr_of.

layered_schedule(H::AbstractMatrix) -> Vector

Return the nested-vector schedule form for interactive use.

layered_schedule(
    row_ptr::AbstractVector{<:Integer},
    col_ind::AbstractVector{<:Integer},
    num_check::Integer,
    num_var::Integer;
    base
) -> Tuple{Vector{Int64}, Any}

Return a partition of the checks into layers such that no two checks in a layer share a variable, so that the checks of one layer can be updated in any order – or all at once – without changing the result.

Return (layer_ptr, layer_checks), the flat form described in SoftDecisionWorkspace, with 1-based check indices.

Greedy: each check takes the smallest admissible existing layer, and opens a new one only if every existing layer already holds a neighbour. Admissibility is read off a stamp array in one pass over the check's two-step neighbourhood, which is linear in the graph rather than upstream's rescan of every layer per check.

Pass base = 0 for 0-based input arrays, as produced by scipy.

Reference: Mansour and Shanbhag, "Turbo decoder architectures for low-density parity-check codes" (2002).

layered_schedule(
    H::Union{Nemo.FqMatrix, Nemo.fpMatrix}
) -> Vector{Vector{Int64}}

Return the nested-vector schedule for a Flint matrix, as in csr_of.

load_soft_channel!(
    W::SoftDecisionWorkspace{Float64},
    LLR_in::AbstractVector{<:Real};
    syndrome,
    erasures,
    decimated_bits,
    decimated_values
) -> SoftDecisionWorkspace{Float64}

Return W after loading one channel realization: channel LLRs, target syndrome, erasures (neutral belief) and manually decimated bits (pinned belief). Resets the messages, so a workspace can be reused for an unrelated syndrome.

Allocation-free: the defaults are shared empty constants and every argument is copied into a pre-allocated buffer (FIX-14).

serial_schedule(num_check::Integer) -> Tuple{Any, Any}

Return the fully serial schedule with one check per layer.

LP_decoder_LDPC(H::Union{CTMatrixTypes, AbstractMatrix{<:Number}}, v::Union{CTMatrixTypes, Vector{<:Integer}}, Ch::BinarySymmetricChannel)
LP_decoder_LDPC(C::AbstractLinearCode, v::Union{CTMatrixTypes, Vector{<:Integer}}, Ch::BinarySymmetricChannel)

Return

Note

• Run using JuMP, HiGHS to activate this extension.

struct GRANDWorkspace

Store the reusable buffers for guessing random additive noise decoding (GRAND). The syndrome is updated incrementally as candidate patterns are toggled, so no candidate requires a fresh matrix-vector product.

struct OSDWorkspace

Store the reusable buffers for ordered statistics decoding (OSD). Gaussian elimination is performed in-place using a pre-allocated dense matrix.

struct WBFWorkspace

Store the reusable buffers for weighted bit flipping (WBF), including the residual syndrome, which is updated in place as bits are flipped.

grand_decode!(
    W::GRANDWorkspace,
    total_llrs::Vector{Float64};
    syndrome,
    max_lrb,
    max_weight
) -> Tuple{Bool, Vector{UInt8}}

Return the syndrome-matching error pattern of least soft cost found by guessing random additive noise decoding (GRAND) applied to the belief-propagation output total_llrs.

Every error pattern of weight up to max_weight, capped at 3, is searched over the max_lrb least reliable bits, and the pattern of least soft cost sum(abs(total_llrs[i]) for i in flipped) is returned. That is the same maximum-likelihood rule osd_decode! ranks its candidates by; returning the first match in Hamming-weight order instead would prefer one expensive flip over several cheap ones.

The sweeps are still nested by Hamming weight, but every loop is bounded by the cost of the best match so far. Since W.lrb_reliabilities is nondecreasing, the cheapest pattern still reachable from a loop index is the one taking the next consecutive bits, so a bound failure prunes the entire remaining subtree and the result is provably the minimum-cost pattern in the search space.

init_grand_workspace(
    H::Union{Nemo.FqMatrix, Nemo.fpMatrix}
) -> GRANDWorkspace

Return a GRAND workspace built from a Flint matrix. See init_osd_workspace.

This delegates to the AbstractMatrix method above, so it is the only place any new GRANDWorkspace field has to be initialized.

init_osd_workspace(H::AbstractMatrix) -> OSDWorkspace

Return an ordered statistics decoding (OSD) workspace for the supplied parity-check matrix.

init_osd_workspace(
    H::Union{Nemo.FqMatrix, Nemo.fpMatrix}
) -> OSDWorkspace

Return an ordered statistics decoding (OSD) workspace built from a Flint matrix.

The array methods are reserved for callers crossing the Python boundary, so the one-time conversion to a plain Julia matrix lives here.

init_wbf_workspace(H::AbstractMatrix) -> WBFWorkspace

Return a weighted-bit-flipping (WBF) workspace for the supplied parity-check matrix.

init_wbf_workspace(
    H::Union{Nemo.FqMatrix, Nemo.fpMatrix}
) -> WBFWorkspace

Return a weighted-bit-flipping workspace built from a Flint matrix. See init_osd_workspace.

osd_decode!(
    W::OSDWorkspace,
    total_llrs::Vector{Float64};
    method,
    order,
    cs_lambda
) -> Vector{UInt8}

Return an OSD correction selected from the candidates generated by method and order. When a syndrome is supplied, return a representative of that syndrome class.

wbf_decode!(
    W::WBFWorkspace,
    total_llrs::Vector{Float64};
    syndrome,
    alpha,
    max_iters
) -> Tuple{Bool, Vector{UInt8}, Int64}

Return (success, codeword, iterations) from weighted bit flipping (WBF) applied to the belief-propagation output total_llrs.

Starting from the hard decisions of total_llrs, the bit maximizing the energy score

\[\mathrm{score}(v) = |\{c \sim v : c \text{ unsatisfied}\}| - \alpha\,|L_v|\]

is flipped, and the residual syndrome is updated incrementally. The first term rewards a bit that explains many unsatisfied checks and the second penalizes a bit the decoder is confident about, so alpha trades those off. Flipping stops as soon as the residual syndrome vanishes, in which case success is true, or after max_iters flips.