Generalized Belief Propagation

Ordinary belief propagation minimizes the Bethe free energy, an approximation that is exact only on a tree. Generalized belief propagation (GBP) instead works on a region graph: vertices are regions, each a set of variable and check nodes, and edges record containment between regions. Passing messages between regions rather than between individual nodes accounts for the short cycles inside each region exactly, which is precisely what ordinary belief propagation gets wrong on an LDPC code.

Each region carries an overcounting number, the Möbius coefficient that makes every variable and check counted exactly once across the region graph. A region graph is valid when those coefficients sum correctly, and the helper functions below construct candidate region graphs from base regions or clusters, repair them, and check that condition before decoding.

The cost of GBP grows quickly with region size, so it is best used with small regions chosen around the problematic cycles identified by the cycle and ACE tools.

CodingTheory.GBPWorkspace — Type

struct GBPWorkspace

Preallocated state for generalized belief propagation on a RegionGraph.

The workspace stores region-local factors and beliefs, parent-to-child messages, marginalization maps, update order, variable incidence data, and reusable decoding buffers.

CodingTheory.Region — Type

struct Region

A region in a region graph.

The variable-node labels are stored in id. The integer vectors parents, ancestors, and subregions index regions in the containing RegionGraph; parents and ancestors point toward strict supersets, while subregions points toward strict subsets. The Möbius counting number is stored in overcounting_number.

CodingTheory.RegionGraph — Type

struct RegionGraph

A region graph represented by an indexed collection of Region objects.

Relations in each region are indices into regions.

CodingTheory.ancestors — Method

ancestors(r::Region) -> Vector{Int64}

Return the indices of all strict-superset ancestors of r.

CodingTheory.base_regions — Method

base_regions(
    R::RegionGraph
) -> Base.Generator{Base.Iterators.Filter{CodingTheory.var"#base_regions##0#base_regions##1", Vector{Region}}, typeof(identity)}

Return an iterator over the regions of R having no parents.

CodingTheory.basic_clusters — Method

basic_clusters(
    R::RegionGraph
) -> Base.Generator{Base.Iterators.Filter{CodingTheory.var"#base_regions##0#base_regions##1", Vector{Region}}, typeof(identity)}

Return the base regions of R.

CodingTheory.bethe_region_graph — Method

bethe_region_graph(
    H::Union{Nemo.FqMatrix, Nemo.fpMatrix, Hecke.SMat, SparseArrays.SparseMatrixCSC}
) -> RegionGraph

The Bethe region graph: one outer region per parity check holding that check's support, and one inner region per variable.

This is the region graph on which generalized belief propagation reduces exactly to ordinary sum-product belief propagation, so it is the control that validates a GBP implementation. Note that it is not what canonical_region_graph returns: that takes the intersection closure of the check supports, whose inner regions may hold several variables and which is therefore already a strictly stronger approximation than Bethe.

Counting numbers are 1 for each check region and 1 - deg(v) for each variable region, which satisfies the validity conditions of is_valid_region_graph.

CodingTheory.canonical_region_graph — Method

canonical_region_graph(
    H::Union{Nemo.FqMatrix, Nemo.fpMatrix, Hecke.SMat, SparseArrays.SparseMatrixCSC}
) -> RegionGraph

Return the region graph generated by closing the row supports of H under nonempty proper intersections.

The row supports are the base regions. The overload for an LDPC code uses its parity-check matrix.

CodingTheory.extract_hard_decisions — Method

extract_hard_decisions(
    W::GBPWorkspace,
    R::RegionGraph,
    num_var::Int64
) -> Vector{UInt8}

Hard decisions from the counting-number weighted marginals.

CodingTheory.gbp_decode! — Method

Master GBP API wrapper. Executes generalized belief propagation with early termination on syndrome validity.

schedule is :flooding (all messages from the current beliefs, then one belief rebuild) or :serial (each message applied before the next is computed). Return (success, hard_decisions, iterations).

CodingTheory.gbp_marginal_llrs — Method

gbp_marginal_llrs(W::GBPWorkspace; mode) -> Vector{Float64}

Single-variable LLRs, positive favouring bit 0.

At a consistent fixed point every region containing a variable agrees on its marginal, so the two modes coincide. Off the fixed point they do not:

:smallest reads the innermost region containing the variable. These are the beliefs whose consistency the message updates actually enforce, and on the Bethe region graph this is exactly the ordinary BP posterior, which is what makes GBP reduce to BP there.
:counting takes the counting-number weighted combination over every region containing the variable. Valid, but it is not BP's posterior on Bethe.

CodingTheory.id — Method

id(r::Region) -> Vector{Int64}

Return the variable-node labels of r.

CodingTheory.init_gbp_workspace — Method

init_gbp_workspace(
    R::RegionGraph,
    H::Union{Nemo.FqMatrix, Nemo.fpMatrix, Hecke.SMat, SparseArrays.SparseMatrixCSC}
) -> GBPWorkspace

Return a GBPWorkspace for the parent-to-child edges of R and the dimensions of parity-check matrix H.

The workspace allocates state tables for each region and message, constructs parent-to-child marginalization maps, and prepares a two-way topological update schedule.

CodingTheory.init_region_beliefs! — Method

Initializes the local factors, and hence the beliefs, of every region.

Each region receives every factor whose support it contains: the channel term of each of its variables and each parity check lying wholly inside it. Messages are reset to zero.

CodingTheory.is_valid_region_graph — Method

is_valid_region_graph(R::RegionGraph) -> Bool

Return true when both counting-number identities checked for R hold.

For every variable, the counting numbers of regions containing it must sum to one. For every region, its counting number plus those of all its ancestors must also sum to one.

CodingTheory.leaves — Method

leaves(
    R::RegionGraph
) -> Base.Generator{Base.Iterators.Filter{CodingTheory.var"#leaves##0#leaves##1", Vector{Region}}, typeof(identity)}

Return an iterator over the regions of R having no strict subregions.

CodingTheory.message_passing_order — Method

message_passing_order(R::RegionGraph) -> Vector{Int64}

Return region indices in a leaves-to-roots topological message-passing order.

An error is thrown if the parent relation contains a cycle.

CodingTheory.outer_regions — Method

outer_regions(
    R::RegionGraph
) -> Base.Generator{Base.Iterators.Filter{CodingTheory.var"#base_regions##0#base_regions##1", Vector{Region}}, typeof(identity)}

Return the base regions of R.

CodingTheory.overcounting_number — Method

overcounting_number(r::Region) -> Int64

Return the Möbius counting number of r.

For a graph built by region_graph_from_base_nodes, this number is one minus the sum of the counting numbers of all ancestors of r.

CodingTheory.parents — Method

parents(r::Region) -> Vector{Int64}

Return the indices of the stored strict-superset parents of r.

CodingTheory.region_graph_from_base_nodes — Method

region_graph_from_base_nodes(
    R::Vector{Vector{Int64}}
) -> RegionGraph

Return the region graph generated from the variable-node sets in R.

The supplied sets are the base regions. Additional regions are their nonempty proper intersections, with parent, ancestor, descendant, and Möbius counting data populated in the resulting graph.

CodingTheory.regions — Method

regions(R::RegionGraph) -> Vector{Region}

Return the indexed collection of regions in R.

CodingTheory.remove_generational_skips — Method

remove_generational_skips(R::RegionGraph) -> RegionGraph

Return a region graph with redundant parent edges to non-immediate ancestors removed.

The ancestor relation and counting numbers are preserved, and R itself is returned when no such edge exists.

CodingTheory.remove_zero_overcounting_numbers — Method

remove_zero_overcounting_numbers(
    R::RegionGraph
) -> RegionGraph

Return a region graph obtained by removing removable regions whose counting number is zero and compacting the stored region indices.

Leaf regions are retained unless their parent topology permits their removal.

CodingTheory.subregions — Method

subregions(r::Region) -> Vector{Int64}

Return the indices of the stored strict-subset subregions of r.

CodingTheory.triangulate_base_regions — Method

triangulate_base_regions(
    H::Union{Nemo.FqMatrix, Nemo.fpMatrix, Hecke.SMat, SparseArrays.SparseMatrixCSC}
) -> Vector{BitSet}

Return the maximal cliques produced by min-degree elimination of the primal graph of H.

Variable nodes are adjacent when they occur in a common row of H; fill edges added during elimination triangulate this graph. Each clique is returned as a BitSet of variable indices.