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
26use crate::rand::{Rng, *};
27use crate::sparse::{Node, SparseMatrix};
28use crate::util::{compare_some, *};
29use std::cmp::Ordering;
30use std::fmt;
31use std::fmt::{Display, Formatter};
32
33/// Runtime errors of the PEG construction.
34#[derive(Debug, Clone, Copy, PartialEq, Eq)]
35pub enum Error {
36    /// Not enought rows available.
37    NoAvailRows,
38}
39
40impl Display for Error {
41    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
42        match self {
43            Error::NoAvailRows => write!(f, "not enough rows available"),
44        }
45    }
46}
47
48impl std::error::Error for Error {}
49
50/// Result type used to indicate PEG runtime errors.
51pub type Result<T> = std::result::Result<T, Error>;
52
53/// Configuration for the Progressive Edge Growth construction
54///
55/// This configuration is used to set the parameters of the
56/// LDPC code to construct.
57#[derive(Debug, Clone, PartialEq, Eq)]
58pub struct Config {
59    /// Number of rows of the parity check matrix.
60    pub nrows: usize,
61    /// Number of columns of the parity check matrix.
62    pub ncols: usize,
63    /// Column weight of the parity check matrix.
64    pub wc: usize,
65}
66
67impl Config {
68    /// Runs the Progressive Edge Growth algorith using a random seed `seed`.
69    pub fn run(&self, seed: u64) -> Result<SparseMatrix> {
70        Peg::new(self, seed).run()
71    }
72}
73
74struct Peg {
75    wc: usize,
76    h: SparseMatrix,
77    rng: Rng,
78}
79
80impl Peg {
81    fn new(conf: &Config, seed: u64) -> Peg {
82        Peg {
83            wc: conf.wc,
84            h: SparseMatrix::new(conf.nrows, conf.ncols),
85            rng: Rng::seed_from_u64(seed),
86        }
87    }
88
89    fn insert_edge(&mut self, col: usize) -> Result<()> {
90        let row_dist = self.h.bfs(Node::Col(col)).row_nodes_distance;
91        let row_num_dist_and_weight: Vec<_> = row_dist
92            .into_iter()
93            .enumerate()
94            .map(|(j, d)| (j, d, self.h.row_weight(j)))
95            .collect();
96        let selected_row = row_num_dist_and_weight
97            .sort_by_random_min(
98                |(_, x, w), (_, y, v)| match compare_some(x, y).reverse() {
99                    Ordering::Equal => w.cmp(v),
100                    c => c,
101                },
102                &mut self.rng,
103            )
104            .ok_or(Error::NoAvailRows)?
105            .0;
106        self.h.insert(selected_row, col);
107        Ok(())
108    }
109
110    fn run(mut self) -> Result<SparseMatrix> {
111        for col in 0..self.h.num_cols() {
112            for _ in 0..self.wc {
113                self.insert_edge(col)?;
114            }
115        }
116        Ok(self.h)
117    }
118}
ldpc_toolbox/peg.rs

ldpc_toolbox/
peg.rs
