ldpc_toolbox/decoder/
horizontal_layered.rs

1//! LDPC decoder with horizontal layered schedule.
2//!
3//! This module implements a generice belief propagation LDPC decoder with a
4//! serial, per check node (horizontal layered) schedule as described in [An
5//! Efficient Message-Passing Schedule for LDPC
6//! Decoding](https://www.eng.biu.ac.il/~goldbej/papers/engisrael.pdf), by
7//! E. Sharon, S. Litsyn, and J. Goldberg.
8
9use super::{
10    DecoderOutput, LdpcDecoder, SentMessages, arithmetic::DecoderArithmetic, check_llrs,
11    hard_decisions,
12};
13use crate::sparse::SparseMatrix;
14
15/// LDPC belief propagation horizontal layered decoder.
16#[derive(Debug, Clone, PartialEq)]
17pub struct Decoder<A: DecoderArithmetic> {
18    arithmetic: A,
19    h: SparseMatrix,
20    llrs: Box<[A::VarLlr]>,                        // Qv
21    check_messages: SentMessages<A::CheckMessage>, // Rcv
22}
23
24impl<A: DecoderArithmetic> Decoder<A> {
25    /// Creates a new horizontal layered LDPC decoder.
26    ///
27    /// The parameter `h` indicates the parity check matrix.
28    pub fn new(h: SparseMatrix, arithmetic: A) -> Self {
29        let llrs = vec![Default::default(); h.num_cols()].into_boxed_slice();
30        let check_messages = SentMessages::from_iter((0..h.num_rows()).map(|r| h.iter_row(r)));
31        Decoder {
32            arithmetic,
33            h,
34            llrs,
35            check_messages,
36        }
37    }
38
39    /// Decodes a codeword.
40    ///
41    /// The parameters are the LLRs for the received codeword and the maximum
42    /// number of iterations to perform. If decoding is successful, the function
43    /// returns an `Ok` containing the (hard decision) on the decoded codeword
44    /// and the number of iterations used in decoding. If decoding is not
45    /// successful, the function returns an `Err` containing the hard decision
46    /// on the final decoder LLRs (which still has some bit errors) and the
47    /// number of iterations used in decoding (which is equal to
48    /// `max_iterations`).
49    pub fn decode(
50        &mut self,
51        llrs: &[f64],
52        max_iterations: usize,
53    ) -> Result<DecoderOutput, DecoderOutput> {
54        assert_eq!(llrs.len(), self.llrs.len());
55        let input_llrs_hard_decision = |x| x <= 0.0;
56        if check_llrs(&self.h, llrs, input_llrs_hard_decision) {
57            // No bit errors case
58            return Ok(DecoderOutput {
59                codeword: hard_decisions(llrs, input_llrs_hard_decision),
60                iterations: 0,
61            });
62        }
63        self.initialize(llrs);
64        for iteration in 1..=max_iterations {
65            self.process_check_nodes();
66            if check_llrs(&self.h, &self.llrs, |x| {
67                self.arithmetic
68                    .llr_hard_decision(self.arithmetic.var_llr_to_llr(x))
69            }) {
70                // Decode succeeded
71                return Ok(DecoderOutput {
72                    codeword: hard_decisions(&self.llrs, |x| {
73                        self.arithmetic
74                            .llr_hard_decision(self.arithmetic.var_llr_to_llr(x))
75                    }),
76                    iterations: iteration,
77                });
78            }
79        }
80        // Decode failed
81        Err(DecoderOutput {
82            codeword: hard_decisions(&self.llrs, |x| {
83                self.arithmetic
84                    .llr_hard_decision(self.arithmetic.var_llr_to_llr(x))
85            }),
86            iterations: max_iterations,
87        })
88    }
89
90    fn initialize(&mut self, llrs: &[f64]) {
91        // Initialize Qv to input LLRs.
92        for (x, &y) in self.llrs.iter_mut().zip(llrs.iter()) {
93            *x = self
94                .arithmetic
95                .llr_to_var_llr(self.arithmetic.input_llr_quantize(y))
96        }
97        // Initialize Rcv to zero.
98        for x in self.check_messages.per_source.iter_mut() {
99            for msg in x.iter_mut() {
100                msg.value = A::CheckMessage::default();
101            }
102        }
103    }
104
105    fn process_check_nodes(&mut self) {
106        for messages in self.check_messages.per_source.iter_mut() {
107            self.arithmetic
108                .update_check_messages_and_vars(messages, &mut self.llrs);
109        }
110    }
111}
112
113impl<A: DecoderArithmetic> LdpcDecoder for Decoder<A> {
114    fn decode(
115        &mut self,
116        llrs: &[f64],
117        max_iterations: usize,
118    ) -> Result<DecoderOutput, DecoderOutput> {
119        Decoder::decode(self, llrs, max_iterations)
120    }
121}
ldpc_toolbox/decoder/horizontal_layered.rs

ldpc_toolbox/decoder/
horizontal_layered.rs
