ldpc_toolbox/
peg.rs

1//! # Progressive Edge Growth (PEG) LDPC construction
2//!
3//! This implements the algorithm described in *Xiao-Yu Hu, E. Eleftheriou and
4//! D. M. Arnold, "Regular and irregular progressive edge-growth tanner graphs,"
5//! in IEEE Transactions on Information Theory, vol. 51, no. 1, pp. 386-398,
6//! Jan. 2005.*
7//!
8//! The algorithm works by adding edge by edge to the Tanner graph. For each
9//! symbol node, `wc` check nodes are selected to be joined by edges. Each one
10//! is selected in a different step, and the edge is added to the graph, which
11//! affects subsequent decisions.
12//!
13//! To select an edge for the current symbol node, a breadth-first search is
14//! done with that node as the root, in order to find the distance from each of
15//! check nodes to the root. If there are any check nodes not yet reachable from
16//! the root, a node at random is selected among the unreachable nodes that
17//! have minimum degree (note that this always happens whenever the first edge
18//! is added to a symbol node). If all the check nodes are rechable from the
19//! root, the set of nodes of minimum degree among those nodes at maximum
20//! distance from the root is selected. A node is picked at random from that
21//! set.
22//!
23//! This procedure tries to maximize local girth greedily and to fill the
24//! check nodes uniformly.
25//!
26//! Note that no check of row weights is currently performed. If any row has
27//! weight less than 2, the resulting matrix is likely to be poorly suited to
28//! decoding. It is suggested that the column weight `wc` be at least 3.
29
30use crate::rand::{Rng, *};
31use crate::sparse::{Node, SparseMatrix};
32use crate::util::{compare_some, *};
33use std::cmp::Ordering;
34use std::fmt;
35use std::fmt::{Display, Formatter};
36
37/// Runtime errors of the PEG construction.
38#[derive(Debug, Clone, Copy, PartialEq, Eq)]
39pub enum Error {
40    /// Not enought rows available.
41    NoAvailRows,
42}
43
44impl Display for Error {
45    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
46        match self {
47            Error::NoAvailRows => write!(f, "not enough rows available"),
48        }
49    }
50}
51
52impl std::error::Error for Error {}
53
54/// Result type used to indicate PEG runtime errors.
55pub type Result<T> = std::result::Result<T, Error>;
56
57/// Configuration for the Progressive Edge Growth construction
58///
59/// This configuration is used to set the parameters of the
60/// LDPC code to construct.
61#[derive(Debug, Clone, PartialEq, Eq)]
62pub struct Config {
63    /// Number of rows of the parity check matrix.
64    pub nrows: usize,
65    /// Number of columns of the parity check matrix.
66    pub ncols: usize,
67    /// Column weight of the parity check matrix.
68    pub wc: usize,
69}
70
71impl Config {
72    /// Runs the Progressive Edge Growth algorith using a random seed `seed`.
73    pub fn run(&self, seed: u64) -> Result<SparseMatrix> {
74        Peg::new(self, seed).run()
75    }
76}
77
78struct Peg {
79    wc: usize,
80    h: SparseMatrix,
81    rng: Rng,
82}
83
84impl Peg {
85    fn new(conf: &Config, seed: u64) -> Peg {
86        Peg {
87            wc: conf.wc,
88            h: SparseMatrix::new(conf.nrows, conf.ncols),
89            rng: Rng::seed_from_u64(seed),
90        }
91    }
92
93    fn insert_edge(&mut self, col: usize) -> Result<()> {
94        let row_dist = self.h.bfs(Node::Col(col)).row_nodes_distance;
95        let row_num_dist_and_weight: Vec<_> = row_dist
96            .into_iter()
97            .enumerate()
98            .map(|(j, d)| (j, d, self.h.row_weight(j)))
99            .collect();
100        let selected_row = row_num_dist_and_weight
101            .sort_by_random_min(
102                |(_, x, w), (_, y, v)| match compare_some(x, y).reverse() {
103                    Ordering::Equal => w.cmp(v),
104                    c => c,
105                },
106                &mut self.rng,
107            )
108            .ok_or(Error::NoAvailRows)?
109            .0;
110        self.h.insert(selected_row, col);
111        Ok(())
112    }
113
114    fn run(mut self) -> Result<SparseMatrix> {
115        for col in 0..self.h.num_cols() {
116            for _ in 0..self.wc {
117                self.insert_edge(col)?;
118            }
119        }
120        Ok(self.h)
121    }
122}
ldpc_toolbox/peg.rs

ldpc_toolbox/
peg.rs
