Module density_evolution 

Density evolution of regular LDPC ensembles under message passing (Richardson & Urbanke 2001): the expected fraction of incorrect messages on a cycle-free Tanner graph, iteration after iteration, and the threshold of the channel parameter below which it tends to zero.

For the $(d_{v}, d_{c})$-regular ensemble, an output-symmetric binary-input channel and a symmetric decoder, the all-one codeword may be assumed (Lemma 1 of the paper) and the densities of the messages evolve deterministically:

• hard decisions on the BSC (hard_decision_error, hard_decision_threshold): Gallager’s algorithm A, eq. (6), $$p^{(\ell)} = \epsilon - \epsilon \left[\frac{1 + (1 - 2p^{(\ell-1)})^{d_{c}-1}}{2}\right]^{d_{v}-1} + (1 - \epsilon) \left[\frac{1 - (1 - 2p^{(\ell-1)})^{d_{c}-1}}{2}\right]^{d_{v}-1},$$ algorithm B (Example 4: the received bit is flipped when at least $b_{\ell}$ of the $d_{v} - 1$ incoming check messages disagree, $b_{\ell}$ chosen by Gallager’s rule), and algorithm E (Example 5: ternary messages ${-1, 0, 1}$, the received bit weighted by $w^{(\ell)}$ chosen to maximise the capacity (7) of the induced binary symmetric erasure channel);
• belief propagation (BpDensityEvolution): the densities of the log-likelihood ratios on a uniform grid; at a variable node the channel density convolved with $d_{v} - 1$ check densities (eq. (9), by FFT), at a check node the $d_{c} - 1$ variable densities combined by $m = 2 \operatorname{atanh}\left(\tanh\frac{a}{2} \tanh\frac{b}{2}\right)$ pair by pair on the grid (the discretized density evolution of Chung, Forney, Richardson & Urbanke, IEEE Commun. Lett. 5(2), 2001; the paper computes the same density with the transform of eq. (8)). An LLR of zero counts as half an error.

The threshold is found by bisection (comnum_math::bisect) of the predicate “the fraction of incorrect messages falls below the target”. With a finite grid and a finite number of iterations the computed threshold is an estimate; Richardson & Urbanke give theirs rounded down (Tables I and II).

Examples

use comnum_fec::density_evolution::{hard_decision_threshold, HardDecoder, RegularEnsemble};
// Gallager A on the (3, 6)-regular ensemble: 0.0395 (Table I prints 0.04)
let e = RegularEnsemble::new(3, 6)?;
let t = hard_decision_threshold(&e, HardDecoder::GallagerA)?;
assert!((t - 0.0395).abs() < 5e-4, "{t}");

References

1. T. J. Richardson, R. L. Urbanke, “The capacity of low-density parity-check codes under message-passing decoding,” IEEE Trans. Inf. Theory 47(2), 599–618, 2001: eq. (6), Examples 3–5, 10–11, Tables I–II.
2. S.-Y. Chung, G. D. Forney, T. J. Richardson, R. Urbanke, “On the design of low-density parity-check codes within 0.0045 dB of the Shannon limit,” IEEE Commun. Lett. 5(2), 58–60, 2001: the discretized density evolution of the check node.
3. D. J. C. MacKay, “Good error-correcting codes based on very sparse matrices,” IEEE Trans. Inf. Theory 45(2), 399–431, 1999: eqs. (44), (54)–(57).

Structs

BpDensityEvolution

Discretized density evolution of belief propagation (see the module).

DensityEvolutionRun

The outcome of a run of density evolution.

RegularEnsemble

The $(d_{v}, d_{c})$-regular LDPC ensemble: every variable node of degree $d_{v}$, every check node of degree $d_{c}$, design rate $1 - d_{v}/d_{c}$.

Enums

BinaryInputChannel

A binary-input memoryless output-symmetric channel, the input of BpDensityEvolution.

HardDecoder

A hard-decision message-passing decoder on the binary symmetric channel.

Functions

correction_effect_threshold

The crossover probability below which a bit of the BSC that every one of its $t$ checks votes against is more likely in error than correct, the “correction effect” bound of MacKay’s simple decoder (MacKay 1999, eqs. (44), (54)–(57)): with $p_{z}(\tau) = \frac12 - \frac12(1 - 2f)^{\tau}$, $a = p_{z}(t_{r} - 1)^{t}$ and $b = (1 - p_{z}(t_{r} - 1))^{t}$, the root in $f$ of $a(1 - f) - b f$ ($t = d_{v}$, $t_{r} = d_{c}$; bisection to $10^{-12}$). It bounds the first iteration only.

hard_decision_error

The fraction of incorrect variable-to-check messages after iterations iterations of decoder on the BSC of crossover probability eps (an erasure counts as half an error), on a cycle-free graph of the ensemble.

hard_decision_threshold

The largest crossover probability for which decoder drives the fraction of incorrect messages to zero on the ensemble (Table I of Richardson & Urbanke): a bisection of $[0, 1/2]$ to $10^{-6}$, each point iterated until the fraction falls below $10^{-12}$ (at most $10^{5}$ iterations).