LDPC Ensemble Analysis

An LDPC ensemble is specified by its degree distributions rather than by a particular parity-check matrix, and density evolution tracks the distribution of decoder messages through the iterations to predict the ensemble's threshold: the worst channel parameter for which the error probability still converges to zero as the blocklength grows. The design of good irregular codes is the search for degree distributions with a high threshold at a given rate, which is what the optimization routines below do.

The ensemble types themselves, LDPCEnsemble and METEnsemble, are documented with the channels. EXIT and protograph-EXIT charts visualize the same convergence question one iteration at a time; the plotting functions require a Makie backend to be loaded.

Optimizing degree distributions

The optimization helpers support the following workflows:

optimal_lambda and optimal_rho: given $\rho$ (or $\lambda$) and a threshold $\epsilon^{BP}$ or target rate, find the other distribution with at least that threshold maximizing design rate, or with at least that target rate maximizing threshold.
optimal_lambda_and_rho: given a target rate or threshold, find both $\lambda$ and $\rho$ maximizing the other quantity.
optimal_threshold: given $\lambda$ and $\rho$, compute the threshold.

Example of using optimal_lambda_and_rho and optimal_threshold:

julia> λ, ρ, r, ε = optimal_lambda_and_rho(8, 6, 0.4, :ε); 0.4 - optimal_threshold(λ, ρ)
2.849104958069226e-7

julia> λ, ρ, r, ε = optimal_lambda_and_rho(8, 6, 0.4, :ε, Δλ = 0.0001); 0.4 - optimal_threshold(λ, ρ)
1.0256726462598564e-7

julia> λ, ρ, r, ε = optimal_lambda_and_rho(8, 6, 0.4, :ε, Δλ = 0.0001); 0.4 - optimal_threshold(λ, ρ, Δ = BigFloat("1e-7"))
1.025672727266482436145720743991009459178786186514042575060182100591178904349331e-07

julia> λ, ρ, r, ε = optimal_lambda_and_rho(8, 6, 0.4, :ε, Δλ = 0.0001, Δρ = 0.001); 0.4 - optimal_threshold(λ, ρ, Δ = BigFloat("1e-7"))
1.025672727266482436145720743991009459178786186514042575060182100591178904349331e-07

This shows the accuracy of these functions and how to tune it. optimal_lambda and optimal_rho also take a keyword Δ for the same purpose. Note that BigFloat only behaves properly for optimal_threshold; any other Δ should be a Float64, and even for optimal_threshold it is best to use Float64 unless you are specifically testing numerical stability.

CodingTheory.LDPCEnsemble — Method

LDPCEnsemble(
    λ::AbstractAlgebra.PolyRingElem,
    ρ::AbstractAlgebra.PolyRingElem
) -> LDPCEnsemble

Return the LDPC ensemble determined by the variable degree distribution λ and the check degree distribution ρ, both from an edge perspective.

CodingTheory.LDPCEnsemble — Method

LDPCEnsemble(L::AbstractLDPCCode) -> LDPCEnsemble

Return the LDPC ensemble determined by the variable degree distribution λ and the check degree distribution ρ of L, both from an edge perspective.

CodingTheory.EXIT_chart_data — Method

EXIT_chart_data(
    E::LDPCEnsemble,
    Ch::BAWGNChannel;
    pts
) -> NTuple{4, Vector{Float64}}

Return EXIT-chart curve data for the ensemble over a BAWGN channel using the Gaussian approximation.

CodingTheory.EXIT_chart_data — Method

EXIT_chart_data(
    E::LDPCEnsemble,
    Ch::BinaryErasureChannel;
    pts
) -> Tuple{Vector{Float64}, Vector, Vector, Vector{Float64}}

Return the tuple (vnd_x, vnd_y, cnd_x, cnd_y) of EXIT-chart curve data for the ensemble over a binary erasure channel.

Notes

vnd curves represent the Variable Node Decoder mutual information transfer.
cnd curves represent the Check Node Decoder mutual information transfer.
On a standard EXIT chart, the axes are swapped for the CND curve to visualize the decoding tunnel.

CodingTheory.EXIT_chart_data — Method

EXIT_chart_data(
    E::LDPCEnsemble,
    Ch::CodingTheory.AbstractChannel;
    pts
) -> Tuple{Vector{Float64}, Vector, Vector, Vector{Float64}}

Return EXIT-chart curve data for the ensemble over an arbitrary symmetric channel using the AWGN-equivalent capacity approximation.

CodingTheory.EXIT_chart_plot — Function

EXIT_chart_plot(E::LDPCEnsemble, Ch::AbstractChannel; tol::Float64 = 1e-9)

Return a plot of the EXIT chart for the ensemble given the channel up to a numerical tolerance of tol.

Note

Run using Makie to activate this extension.

CodingTheory.PEXIT_chart_data — Method

PEXIT_chart_data(
    B::Matrix{Int64},
    sigma_ch::Vector{Float64};
    pts
) -> NTuple{4, Vector{Float64}}

Return the tuple (vnd_x, vnd_y, cnd_x, cnd_y) of averaged EXIT-chart curve data for the protograph base matrix B.

Arguments

B::Matrix{Int}: The protograph base matrix.
sigma_ch::Vector{Float64}: The channel LLR standard deviation for each variable node.

CodingTheory.check_concentrated_degree_distribution — Method

check_concentrated_degree_distribution(
    Ch::BinaryErasureChannel,
    gap::Real
)

Return the check-concentrated degree distribution (λ, ρ) for the binary erasure channel given the desired multiplicative gap.

CodingTheory.density_evolution — Method

density_evolution(
    E::LDPCEnsemble,
    Ch::CodingTheory.AbstractChannel
) -> Tuple{Vector{Float64}, Vector{Float64}}

Return the density evolution of the LDPC ensemble given the noise channel.

CodingTheory.density_evolution_MET_GA — Method

density_evolution_MET_GA(
    E::METEnsemble,
    Ch::BAWGNChannel;
    max_iters,
    tol
)

Run Multi-Edge Type (MET) Density Evolution using Gaussian Approximation for the BAWGN channel.

CodingTheory.density_evolution_MET_GA — Method

density_evolution_MET_GA(
    E::METEnsemble,
    Ch::CodingTheory.AbstractChannel;
    max_iters,
    tol
)

Run Multi-Edge Type (MET) Density Evolution for any arbitrary discrete or continuous channel using the AWGN-equivalent capacity approximation.

CodingTheory.density_evolution_MET_GA — Method

density_evolution_MET_GA(
    E::METEnsemble,
    sigma_ch::Float64;
    max_iters,
    tol
) -> Bool

Run Multi-Edge Type (MET) Density Evolution using Gaussian Approximation for an AWGN channel. Return true if the ensemble decodes, false otherwise.

Arguments

E::METEnsemble: The Multi-Edge Type ensemble definition.
sigma_ch::Float64: The AWGN channel LLR standard deviation (2.0 / sigma_noise).

CodingTheory.density_lower_bound — Method

density_lower_bound(
    Ch::CodingTheory.AbstractChannel,
    gap::Real
) -> Any

Return a lower bound on the density of a (full rank) parity-check matrix for the channel given the multiplicative gap.

CodingTheory.multiplicative_gap — Method

multiplicative_gap(
    E::LDPCEnsemble,
    Ch::CodingTheory.AbstractChannel
) -> Any

Return the multiplicative gap of the ensemble with respect to the given channel.

CodingTheory.multiplicative_gap_lower_bound — Method

multiplicative_gap_lower_bound(E::LDPCEnsemble) -> Float64

Return a lower bound on the multiplicative gap of the ensemble

CodingTheory.optimal_lambda — Function

optimal_lambda(ρ, l_max, param, var_type; Δ = 1e-3)

Return the optimal variable-node distribution λ for the check-node distribution ρ, maximum variable-node degree l_max, and target parameter param which refers to threshold if var_type == :ε or rate if var_type == :r.

Notes

Δ refers to the step size for x in the LP to solve for λ.

CodingTheory.optimal_lambda_and_rho — Function

optimal_lambda_and_rho(l_max, r_max, param, var_type; Δρ = 1e-2, Δλ = 1e-3)

Return the optimal distribution pair λ, ρ for param, where param is either a threshold if var_type == :ε or a target rate if var_type == :r.

Notes

Δρ gives the step size for possible values of c where ρ = (1 - c) * x^(rmax - 2) + c * x^(rmax - 1)
Δλ gives the step size for values of x in the LP for finding λ given ρ.

CodingTheory.optimal_rho — Function

optimal_rho(λ, r_max, param, var_type; Δ = 1e-3)

Return the optimal check-node distribution ρ for the variable-node distribution λ, maximum check-node degree r_max, and target parameter param which refers to threshold if var_type == :ε or rate if var_type == :r.

Notes

Δ refers to the step size for x in the LP to solve for ρ.

CodingTheory.optimal_threshold — Method

optimal_threshold(
    E::AbstractLDPCFamily,
    ::Type{BinarySymmetricChannel};
    tol
) -> Float64

Return the optimal crossover-probability threshold p for the binary symmetric channel.

CodingTheory.optimal_threshold — Method

optimal_threshold(
    E::AbstractLDPCFamily,
    ::Type{RayleighFadingChannel};
    tol
) -> Float64

Return the optimal ergodic noise threshold σ for the Rayleigh fading channel.

CodingTheory.optimal_threshold — Method

optimal_threshold(
    E::AbstractLDPCFamily,
    ::Type{ZChannel};
    tol
) -> Float64

Return the optimal crossover-probability threshold p for the Z-channel.

CodingTheory.optimal_threshold — Method

optimal_threshold(
    E::LDPCEnsemble,
    ::Type{BinaryErasureChannel};
    Δ
) -> Any

Return the optimal threshold for the LDPC ensemble over the specified Channel type.

CodingTheory.optimal_threshold — Method

optimal_threshold(E::METEnsemble, ::Type{BAWGNChannel}; tol)

Return the optimal AWGN noise threshold (maximum standard deviation σ_n) for a multi-edge-type (MET) ensemble using the Gaussian approximation.

CodingTheory.protograph_threshold — Method

protograph_threshold(B::Matrix{Int64}; punctured) -> Float64

Return the estimated AWGN noise threshold (maximum standard deviation σ_n) for a protograph base matrix using PEXIT analysis.

Arguments

B::Matrix{Int}: The protograph base matrix.
punctured::Vector{Bool}: A boolean vector indicating if a column is punctured. Defaults to all false.