ldpc_toolbox/
decoder.rs

1//! LDPC belief propagation decoders.
2//!
3//! This module provides several implementations of a LDPC decoders using belief
4//! propagation (the sum-product algorithm). The implementations differ in
5//! details about their numerical algorithms, data types and message passing
6//! schedules.
7
8use crate::sparse::SparseMatrix;
9
10pub mod arithmetic;
11pub mod factory;
12pub mod flooding;
13pub mod horizontal_layered;
14
15/// Generic LDPC decoder.
16///
17/// This trait is used to form LDPC decoder trait objects, abstracting over the
18/// internal implementation decoder.
19pub trait LdpcDecoder: std::fmt::Debug + Send {
20    /// Decodes a codeword.
21    ///
22    /// The parameters are the LLRs for the received codeword and the maximum
23    /// number of iterations to perform. If decoding is successful, the function
24    /// returns an `Ok` containing the (hard decision) on the decoded codeword
25    /// and the number of iterations used in decoding. If decoding is not
26    /// successful, the function returns an `Err` containing the hard decision
27    /// on the final decoder LLRs (which still has some bit errors) and the
28    /// number of iterations used in decoding (which is equal to
29    /// `max_iterations`).
30    fn decode(
31        &mut self,
32        llrs: &[f64],
33        max_iterations: usize,
34    ) -> Result<DecoderOutput, DecoderOutput>;
35}
36
37/// LDPC decoder output.
38#[derive(Debug, Clone, Eq, PartialEq, Hash)]
39pub struct DecoderOutput {
40    /// Decoded codeword.
41    ///
42    /// Contains the hard decision bits of the decoded codeword.
43    pub codeword: Vec<u8>,
44    /// Number of iterations.
45    ///
46    /// Number of iterations used in decoding.
47    pub iterations: usize,
48}
49
50/// LDPC decoder message.
51///
52/// This represents a message used by the flooding belief propagation
53/// decoder. It is used for messages received by the nodes.
54#[derive(Debug, Copy, Clone, Eq, PartialEq, Default, Hash)]
55pub struct Message<T> {
56    /// Message source.
57    ///
58    /// Contains the index of the variable node or check node that sent the
59    /// message.
60    pub source: usize,
61    /// Value.
62    ///
63    /// Contains the value of the message.
64    pub value: T,
65}
66
67/// LDPC decoder outgoing message.
68///
69/// This represents a message used by the flooding belief propagation
70/// decoder. It is used for messages sent by the nodes.
71#[derive(Debug, Copy, Clone, Eq, PartialEq, Default, Hash)]
72pub struct SentMessage<T> {
73    /// Message destination.
74    ///
75    /// Contains the index of the variable node or check node to which the
76    /// message is addressed.
77    pub dest: usize,
78    /// Value.
79    ///
80    /// Contains the value of the message.
81    pub value: T,
82}
83
84#[derive(Debug, Clone, Eq, PartialEq, Default, Hash)]
85struct Messages<T> {
86    per_destination: Box<[Box<[Message<T>]>]>,
87}
88
89impl<T: Default> Messages<T> {
90    fn from_iter<I, J, B>(iter: I) -> Messages<T>
91    where
92        I: Iterator<Item = J>,
93        J: Iterator<Item = B>,
94        B: core::borrow::Borrow<usize>,
95    {
96        Messages {
97            per_destination: iter
98                .map(|i| {
99                    i.map(|j| Message {
100                        source: *j.borrow(),
101                        value: T::default(),
102                    })
103                    .collect::<Vec<_>>()
104                    .into_boxed_slice()
105                })
106                .collect::<Vec<_>>()
107                .into_boxed_slice(),
108        }
109    }
110
111    fn send(&mut self, source: usize, destination: usize, value: T) {
112        let message = self.per_destination[destination]
113            .iter_mut()
114            .find(|m| m.source == source)
115            .expect("message for source not found");
116        message.value = value;
117    }
118}
119
120#[derive(Debug, Clone, Eq, PartialEq, Default, Hash)]
121struct SentMessages<T> {
122    per_source: Box<[Box<[SentMessage<T>]>]>,
123}
124
125impl<T: Default> SentMessages<T> {
126    fn from_iter<I, J, B>(iter: I) -> SentMessages<T>
127    where
128        I: Iterator<Item = J>,
129        J: Iterator<Item = B>,
130        B: core::borrow::Borrow<usize>,
131    {
132        SentMessages {
133            per_source: iter
134                .map(|i| {
135                    i.map(|j| SentMessage {
136                        dest: *j.borrow(),
137                        value: T::default(),
138                    })
139                    .collect::<Vec<_>>()
140                    .into_boxed_slice()
141                })
142                .collect::<Vec<_>>()
143                .into_boxed_slice(),
144        }
145    }
146
147    #[allow(dead_code)]
148    fn send(&mut self, source: usize, destination: usize, value: T) {
149        let message = self.per_source[source]
150            .iter_mut()
151            .find(|m| m.dest == destination)
152            .expect("message for destination not found");
153        message.value = value;
154    }
155}
156
157fn check_llrs<T, F>(h: &SparseMatrix, llrs: &[T], hard_decision: F) -> bool
158where
159    T: Copy,
160    F: Fn(T) -> bool,
161{
162    // Check if hard decision on LLRs satisfies the parity check equations
163    !(0..h.num_rows()).any(|r| h.iter_row(r).filter(|&&c| hard_decision(llrs[c])).count() % 2 == 1)
164}
165
166fn hard_decisions<T, F>(llrs: &[T], hard_decision: F) -> Vec<u8>
167where
168    T: Copy,
169    F: Fn(T) -> bool,
170{
171    llrs.iter()
172        .map(|&llr| u8::from(hard_decision(llr)))
173        .collect()
174}
ldpc_toolbox/decoder.rs

ldpc_toolbox/
decoder.rs
