Module ldpc 

Low-density parity-check (LDPC) codes.

A code is the null space of a sparse parity-check matrix $H$ ($m \times n$): $H c = 0$. Its Tanner graph links every variable node (coded bit) to the check nodes (parity equations) it takes part in.

Construction

LdpcCode::peg builds $H$ by progressive edge growth (Hu, Eleftheriou & Arnold 2005): every new edge of a variable node goes to the check node farthest from it in the current graph (lowest degree among the farthest), which maximises the local girth. LdpcCode::from_rows takes any $H$ (for instance the lifted base graph of a standard), and LdpcCode::from_alist reads it from MacKay’s alist format (the format of the matrices of MacKay’s encyclopedia and of AFF3CT). The encoder brings $H$ to the systematic form $[A \mid I]$ by Gaussian elimination over GF(2) (with a column permutation), so that the parity bits are $p = A u$.

Decoding

Message passing on the Tanner graph, with the LLR convention of the library (positive for a 0). A variable node sends the sum of its channel LLR and of the other incoming messages; a check node sends

$$ L_{c \to v} = 2 \operatorname{atanh} \prod_{v’ \ne v} \tanh\frac{L_{v’ \to c}}{2} \quad \text{(sum-product)}, \qquad L_{c \to v} \approx \alpha \prod_{v’ \ne v} \operatorname{sgn} L_{v’ \to c} \min_{v’ \ne v} |L_{v’ \to c}| \quad \text{(min-sum)}, $$

with the normalisation $\alpha$ (Chen & Fossorier 2002) or an offset. The schedule is flooding, or layered (row by row with immediate updates, Hocevar 2004), which converges in about half the iterations; decoding stops as soon as $H \hat c = 0$.

The decoder settings of a new code (LdpcDecoder, the field decoder) are the defaults of the crate, which the specifications (comnum_spec) and the Python bindings also take: DEFAULT_RULE (sum-product), DEFAULT_LAYERED (layered) and DEFAULT_MAX_ITERATIONS (50); DEFAULT_ALPHA is the scale or the offset of a min-sum rule named without it, DEFAULT_VAR_DEGREE and DEFAULT_PEG_SEED those of a PEG construction.

Examples

use comnum_fec::block::BlockCode;
use comnum_fec::ldpc::LdpcCode;
let code = LdpcCode::peg(256, 128, 3, 1)?;                 // (256, 128), degree 3
assert_eq!(code.k(), 128);
let info: Vec<u8> = (0..128).map(|i| (i % 5 == 2) as u8).collect();
let c = code.encode_block(&info)?;
assert!(code.is_codeword(&c));
let llr: Vec<f64> = c.iter().map(|&b| if b == 0 { 4.0 } else { -4.0 }).collect(); // noiseless
assert_eq!(code.decode_block(&llr)?, info);

References

1. R. G. Gallager, “Low-density parity-check codes,” IRE Trans. Inf. Theory, 8(1), 21–28, 1962.
2. X.-Y. Hu, E. Eleftheriou and D. M. Arnold, “Regular and irregular progressive edge-growth Tanner graphs,” IEEE Trans. Inf. Theory, 51(1), 386–398, 2005.
3. J. Chen and M. P. C. Fossorier, “Near optimum universal belief propagation based decoding of low-density parity check codes,” IEEE Trans. Commun., 50(3), 406–414, 2002.
4. D. E. Hocevar, “A reduced complexity decoder architecture via layered decoding of LDPC codes,” Proc. IEEE SiPS, 107–112, 2004.
5. T. Richardson and R. Urbanke, Modern Coding Theory, Cambridge University Press, 2008.

Structs

LdpcCode

An LDPC code with its systematic encoder and its decoder settings.

LdpcDecoder

The settings of the belief-propagation decoder of an LdpcCode.

Enums

CheckRule

The check-node rule of the decoder.

Constants

DEFAULT_ALPHA

The default scale $\alpha$ of the normalised min-sum, or offset $\beta$ of the offset min-sum, when a rule is named without it.

DEFAULT_LAYERED

The default schedule: layered.

DEFAULT_MAX_ITERATIONS

The default maximum number of iterations.

DEFAULT_PEG_SEED

The default seed of a PEG construction.

DEFAULT_RULE

The default check-node rule: sum-product, the exact belief propagation (the reference of the performance tables of the standards).

DEFAULT_VAR_DEGREE

The default degree of the variable nodes of a PEG construction.