Cycles and ACE

Message passing is exact on a tree, so the cycles of the Tanner graph are what limit an LDPC code's iterative decoding performance. This page collects the tools for measuring them.

Two notions of cycle appear here and they are not interchangeable. A short cycle is one of length at most twice the girth, enumerated per variable node; these are the cycles that matter for decoding and can be counted cheaply. A simple cycle is any cycle without repeated vertices, and enumerating all of them is exponential in general, so those functions are for small graphs only.

The approximate cycle extrinsic message degree (ACE) of a cycle is the number of edges leaving it, counting the degree of each variable node on the cycle minus two. A cycle with a low ACE value is nearly isolated from the rest of the graph, so extrinsic information reaches it slowly, which is what makes low-ACE short cycles the usual culprits in error floors. The ACE spectrum records the smallest ACE value found at each cycle length, and the distribution functions summarize per-variable-node ACE values by their mean, median, or mode.

remove_cycles greedily edits the parity-check matrix to eliminate cycles, and the plotting functions require a Makie backend to be loaded.

CodingTheory.ACE_distribution — Method

ACE_distribution(C::LDPCCode, vs::Vector{Int64}) -> Vector

Return the exact ACE arrays for the shortest cycles of the given variable node(s).

CodingTheory.ACE_spectrum — Method

ACE_spectrum(C::LDPCCode) -> Dict{Int64, Dict{Int64, Int64}}

Return the ACE spectrum of the Tanner graph of C. Return a Dict{Int, Dict{Int, Int}} mapping Cycle Length -> (Minimum ACE -> Count).

CodingTheory.ACE_spectrum_plot — Function

ACE_spectrum_plot(C::AbstractLDPCCode)

Return an interactive figure and data for the ACE spectrum of the Tanner graph of C.

Note

Run using Makie to activate this extension.

CodingTheory.average_ACE_distribution — Method

average_ACE_distribution(
    C::LDPCCode,
    vs::Vector{Int64}
) -> Vector

Return the average ACE of the vertex v or vertices vs of the Tanner graph of C. If no vertices are given, all vertices are computed (individually) by default.

CodingTheory.average_short_cycle_length — Method

average_short_cycle_length(C::LDPCCode) -> Float64

Return the average cycle length of unique short cycles up to length len of the Tanner graph of L. If len is -1, then all short cycles will be enumerated.

Note

Short cycles are defined to be those with lengths between $g$ and $2g - 2$, where $g$ is the girth.
This function calls enumerate_simple_cycles(L, len = len), which could be expensive if not already cached.

CodingTheory.average_simple_cycle_length — Method

average_simple_cycle_length(C::LDPCCode; len) -> Float64

Return the average cycle length of unique simple cycles up to length len of the Tanner graph of L. If len is -1, then all simple cycles will be enumerated.

Note

Simple cycles do not contain the same vertex twice.
This function calls enumerate_simple_cycles(L, len = len), which could be expensive if not already cached.

CodingTheory.computation_graph — Function

computation_graph(C::AbstractLDPCCode, lvl::Int, v::Int, v_type::Symbol = :v)

Return a figure representing the expansion of the Tanner graph of C to level lvl for node v. If v_type is :v, v is interpreted as a variable node; otherwise, v_type is :c and v is interpreted as a check node.

Note

Run using Makie to activate this extension.

CodingTheory.count_short_cycles — Method

count_short_cycles(C::LDPCCode) -> Int64

Return the total number of unique short cycles up to length len of the Tanner graph of L. If len is -1, then all short cycles will be enumerated.

Note

Short cycles are defined to be those with lengths between $g$ and $2g - 2$, where $g$ is the girth.
This function calls enumerate_simple_cycles(L, len = len), which could be expensive if not already cached.

CodingTheory.count_simple_cycles — Method

count_simple_cycles(C::LDPCCode; len) -> Int64

Return the total number of unique simple cycles up to length len of the Tanner graph of L. If len is -1, then all simple cycles will be enumerated.

Note

Simple cycles do not contain the same vertex twice.
This function calls enumerate_simple_cycles(L, len = len), which could be expensive if not already cached.

CodingTheory.enumerate_short_cycles — Method

enumerate_short_cycles(C::LDPCCode) -> Any

Return the unique short cycles (length between g and 2g - 2) of the Tanner graph of C.

CodingTheory.enumerate_simple_cycles — Method

enumerate_simple_cycles(C::AbstractLDPCCode; len) -> Any

Return the unique simple cycles up to length len of the Tanner graph of L. An empty Vector{Vector{Int}} is returned when there is no cycles.

Note

Simple cycles do not contain the same vertex twice.
Cycles are returned as a vector of vertex indices, where the vertices are ordered left-to-right by columns of parity_check_matrix(L) then top-to-bottom by rows.

CodingTheory.local_girth — Method

local_girth(C::LDPCCode, v::Int64) -> Any

Return the local girth (computation tree depth) for the variable node v in the Tanner graph of C.

Notes

This metric intrinsically captures the "lollipop graph" penalty. It returns the length of the shortest message-passing loop that originates from and returns to v, calculating the cycle length plus twice the length of the stem.
Returns -1 if the node is part of a tree structure (no cycles reachable).

CodingTheory.local_girth — Method

local_girth(C::LDPCCode, vs::Vector{Int64}) -> Vector

Return the local girth for a specified list of variable nodes vs.

CodingTheory.local_girth — Method

local_girth(C::LDPCCode) -> Vector

Return the local girth for every variable node in the LDPC code C.

CodingTheory.median_ACE_distribution — Method

median_ACE_distribution(
    C::LDPCCode,
    vs::Vector{Int64}
) -> Vector

Return the median ACE of the vertex v or vertices vs of the Tanner graph of C. If no vertices are given, all vertices are computed (individually) by default.

CodingTheory.median_short_cycle_length — Method

median_short_cycle_length(C::LDPCCode) -> Float64

Return the median cycle length of unique short cycles up to length len of the Tanner graph of L. If len is -1, then all short cycles will be enumerated.

Note

Short cycles are defined to be those with lengths between $g$ and $2g - 2$, where $g$ is the girth.
This function calls enumerate_simple_cycles(L, len = len), which could be expensive if not already cached.

CodingTheory.median_simple_cycle_length — Method

median_simple_cycle_length(C::LDPCCode; len) -> Float64

Return the median cycle length of unique simple cycles up to length len of the Tanner graph of L. If len is -1, then all simple cycles will be enumerated.

Note

Simple cycles do not contain the same vertex twice.
This function calls enumerate_simple_cycles(L, len = len), which could be expensive if not already cached.

CodingTheory.mode_ACE_distribution — Method

mode_ACE_distribution(
    C::LDPCCode,
    vs::Vector{Int64}
) -> Vector

Return the mode ACE of the vertex v or vertices vs of the Tanner graph of C. If no vertices are given, all vertices are computed (individually) by default.

Note

In case of ties, the smallest tied value is returned.

CodingTheory.mode_short_cycle_length — Method

mode_short_cycle_length(
    C::LDPCCode
) -> Union{Nothing, Float64, Int64}

Return the most common cycle length of unique short cycles up to length len of the Tanner graph of L. If len is -1, then all short cycles will be enumerated.

Note

Short cycles are defined to be those with lengths between $g$ and $2g - 2$, where $g$ is the girth.
This function calls enumerate_simple_cycles(L, len = len), which could be expensive if not already cached.

CodingTheory.mode_simple_cycle_length — Method

mode_simple_cycle_length(
    C::LDPCCode;
    len
) -> Union{Nothing, Float64, Int64}

Return the most common cycle length of unique simple cycles up to length len of the Tanner graph of L. If len is -1, then all simple cycles will be enumerated.

Note

Simple cycles do not contain the same vertex twice.
This function calls enumerate_simple_cycles(L, len = len), which could be expensive if not already cached.

CodingTheory.node_adjacencies — Method

node_adjacencies(C::LDPCCode) -> Tuple{Any, Any}

Return the bipartite adjacency lists (check_adj, var_adj) for the LDPC code. Computes lazily and caches the result.

CodingTheory.remove_cycles — Method

remove_cycles(
    C::LDPCCode,
    target_girth::Int64;
    max_iters
) -> LDPCCode

Attempt to structurally remove cycles of length strictly less than target_girth from the LDPC code C using the BFS Socket-Swapping algorithm.

Notes

target_girth must be an even integer >= 4.
This algorithm exactly preserves the degree distributions (λ and ρ) of the original code.
Returns a strictly new LDPCCode object. If the target girth cannot be reached within max_iters, it returns the best-effort matrix achieved so far.

CodingTheory.short_cycle_distribution_by_variable_node — Method

short_cycle_distribution_by_variable_node(
    C::LDPCCode
) -> Dict{Int64, Int64}

Return a dictionary of (node, count) pairs for the unique short cycles up to length len of the Tanner graph of L. If len is -1, then all short cycles will be enumerated. An empty dictionary is returned when there are no cycles.

Note

Short cycles are defined to be those with lengths between $g$ and $2g - 2$, where $g$ is the girth.
This function calls enumerate_simple_cycles(L, len = len), which could be expensive if not already cached.

CodingTheory.short_cycle_distribution_by_variable_node_plot — Function

short_cycle_distribution_by_variable_node_plot(L::AbstractLDPCCode; len::Int = 16)

Return bar graph and a dictionary of (node, count) pairs for the unique short cycles up to length len of the Tanner graph of L. If len is -1, then all short cycles will be enumerated. An empty figure and dictionary are returned when there are no cycles.

Note

Short cycles are defined to be those with lengths between $g$ and $2g - 2$, where $g$ is the girth.
This function calls enumerate_simple_cycles(L, len = len), which could be expensive if not already cached.
Run using Makie to activate this extension.

CodingTheory.short_cycle_length_distribution — Method

short_cycle_length_distribution(
    C::LDPCCode
) -> Dict{Int64, Int64}

Return a dictionary of (length, count) pairs for the unique short cycles up to length len of the Tanner graph of L. If len is -1, then all short cycles will be enumerated. An empty dictionary is returned when there are no cycles.

Note

Short cycles are defined to be those with lengths between $g$ and $2g - 2$, where $g$ is the girth.
This function calls enumerate_simple_cycles(L, len = len), which could be expensive if not already cached.

CodingTheory.short_cycle_length_distribution_plot — Function

short_cycle_length_distribution_plot(L::AbstractLDPCCode; len::Int = 16)

Return a bar graph and dictionary of (length, count) pairs for the unique short cycles up to length len of the Tanner graph of L. If len is -1, then all short cycles will be enumerated. An empty figure and dictionary are returned when there are no cycles.

Note

Short cycles are defined to be those with lengths between $g$ and $2g - 2$, where $g$ is the girth.
This function calls enumerate_simple_cycles(L, len = len), which could be expensive if not already cached.
Run using Makie to activate this extension.

CodingTheory.simple_cycle_distribution_by_variable_node — Method

simple_cycle_distribution_by_variable_node(
    C::LDPCCode;
    len
) -> Dict{Int64, Int64}

Return a dictionary of (node, count) pairs for the unique simple cycles up to length len of the Tanner graph of L. If len is -1, then all simple cycles will be enumerated. An empty dictionary is returned when there are no cycles.

Note

Simple cycles do not contain the same vertex twice.
This function calls enumerate_simple_cycles(L, len = len), which could be expensive if not already cached.

CodingTheory.simple_cycle_distribution_by_variable_node_plot — Function

simple_cycle_distribution_by_variable_node_plot(L::AbstractLDPCCode; len::Int = 16)

Return bar graph and a dictionary of (node, count) pairs for the unique simple cycles up to length len of the Tanner graph of L. If len is -1, then all simple cycles will be enumerated. An empty figure and dictionary are returned when there are no cycles.

Note

Simple cycles do not contain the same vertex twice.
This function calls enumerate_simple_cycles(L, len = len), which could be expensive if not already cached.
Run using Makie to activate this extension.

CodingTheory.simple_cycle_length_distribution — Method

simple_cycle_length_distribution(
    C::LDPCCode;
    len
) -> Dict{Int64, Int64}

Return a dictionary of (length, count) pairs for the unique simple cycles up to length len of the Tanner graph of L. If len is -1, then all simple cycles will be enumerated. An empty dictionary is returned when there are no cycles.

Note

Simple cycles do not contain the same vertex twice.
This function calls enumerate_simple_cycles(L, len = len), which could be expensive if not already cached.

CodingTheory.simple_cycle_length_distribution_plot — Function

simple_cycle_length_distribution_plot(L::AbstractLDPCCode; len::Int = 16)

Return a bar graph and dictionary of (length, count) pairs for the unique simple cycles up to length len of the Tanner graph of L. If len is -1, then all simple cycles will be enumerated. An empty figure and dictionary are returned when there are no cycles.

Note

Simple cycles do not contain the same vertex twice.
This function calls enumerate_simple_cycles(L, len = len), which could be expensive if not already cached.
Run using Makie to activate this extension.

Oscar.girth — Method

girth(C::LDPCCode) -> Any

Return the girth of the Tanner graph of C.