believer 0.2.1

A toolbox to simulate error correcting code performance.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159

//! A view over a check of a parity check matrix.
//!
//! # Example
//!
//! ```
//! # use believer::ParityCheckMatrix;
//! let all_checks = vec![
//!     vec![0, 1],
//!     vec![0, 3],
//!     vec![1, 2, 3],
//! ];
//! let matrix = ParityCheckMatrix::with_n_bits(4).with_checks(all_checks);
//!
//! let second_check = matrix.get_check(2);
//! ```

use crate::GF2;

/// A view over a check of a parity check matrix.
#[derive(Debug, PartialEq)]
pub struct CheckView<'a> {
    bits: &'a [usize],
}

impl<'a> CheckView<'a> {
    // Useful to create a check from a parity check matrix.
    pub(crate) fn from_slice(slice: &'a [usize]) -> Self {
        Self { bits: slice }
    }

    /// An iterator over the bits in `self`.
    pub fn iter(&self) -> std::slice::Iter<usize> {
        self.bits.iter()
    }

    /// Returns the syndrome of a given `message`. That is, returns the dot product between
    /// `self` and `message`.
    ///
    /// # Example
    ///
    /// ```
    /// # use believer::{GF2, ParityCheckMatrix};
    /// let parity_check = ParityCheckMatrix::with_n_bits(7)
    ///     .with_checks(vec![
    ///         vec![0, 1, 2, 4],
    ///         vec![0, 1, 3, 5],
    ///         vec![0, 2, 3, 6],
    ///     ]);
    /// let other = vec![GF2::B0, GF2::B1, GF2::B0, GF2::B1, GF2::B0, GF2::B1, GF2::B0];
    ///
    /// assert_eq!(parity_check.get_check(0).unwrap().compute_syndrome(&other), GF2::B1);
    /// assert_eq!(parity_check.get_check(1).unwrap().compute_syndrome(&other), GF2::B1);
    /// assert_eq!(parity_check.get_check(2).unwrap().compute_syndrome(&other), GF2::B1);
    /// ```
    pub fn compute_syndrome(&self, message: &[GF2]) -> GF2 {
        self.iter().fold(GF2::B0, |acc, &bit| {
            message.get(bit).map(|&value| acc + value).unwrap_or(acc)
        })
    }

    /// Returns `true` if the syndrome of `message` is `GF2::B1`.
    pub fn has_non_zero_syndrome(&self, message: &[GF2]) -> bool {
        self.compute_syndrome(message) == GF2::B1
    }

    /// Returns `true` if the syndrome of `message` is `GF2::B0`.
    pub fn has_zero_syndrome(&self, message: &[GF2]) -> bool {
        self.compute_syndrome(message) == GF2::B0
    }

    /// Returns the number of bits connected to `self`.
    pub fn get_n_bits(&self) -> usize {
        self.bits.len()
    }

    /// Returns the spread of `self`.
    ///
    /// # Example
    ///
    /// ```
    /// # use believer::ParityCheckMatrix;
    /// let parity_check = ParityCheckMatrix::with_n_bits(6).with_checks(
    ///     vec![
    ///         vec![0, 1],
    ///         vec![1, 2, 5],
    ///         vec![3],
    ///         vec![0, 4],
    ///     ]
    /// );
    ///
    /// assert_eq!(parity_check.get_check(0).unwrap().spread(), 2);
    /// assert_eq!(parity_check.get_check(1).unwrap().spread(), 5);
    /// assert_eq!(parity_check.get_check(2).unwrap().spread(), 1);
    /// assert_eq!(parity_check.get_check(3).unwrap().spread(), 5);
    /// ```
    pub fn spread(&self) -> usize {
        self.max() - self.min() + 1 // Well define (>= 0), because max >= min.
    }

    /// Returns the bit connected to `self` with maximal index.
    ///
    /// # Example
    ///
    /// ```
    /// # use believer::*;
    /// let parity_check = ParityCheckMatrix::with_n_bits(6).with_checks(
    ///     vec![
    ///         vec![0, 1],
    ///         vec![1, 2, 5],
    ///         vec![3],
    ///         vec![0, 4],
    ///     ]
    /// );
    ///
    /// assert_eq!(parity_check.get_check(0).unwrap().max(), 1);
    /// assert_eq!(parity_check.get_check(1).unwrap().max(), 5);
    /// assert_eq!(parity_check.get_check(2).unwrap().max(), 3);
    /// assert_eq!(parity_check.get_check(3).unwrap().max(), 4);
    /// ```
    pub fn max(&self) -> usize {
        *self.bits.last().unwrap() // Check is always sorted and non empty.
    }

    /// Returns the bit connected to `self` with minimal index if `self`
    ///
    /// # Example
    ///
    /// ```
    /// # use believer::*;
    /// let parity_check = ParityCheckMatrix::with_n_bits(6).with_checks(
    ///     vec![
    ///         vec![0, 1],
    ///         vec![1, 2, 5],
    ///         vec![3],
    ///         vec![0, 4],
    ///     ]
    /// );
    ///
    /// assert_eq!(parity_check.get_check(0).unwrap().min(), 0);
    /// assert_eq!(parity_check.get_check(1).unwrap().min(), 1);
    /// assert_eq!(parity_check.get_check(2).unwrap().min(), 3);
    /// assert_eq!(parity_check.get_check(3).unwrap().min(), 0);
    /// ```
    pub fn min(&self) -> usize {
        *self.bits.first().unwrap() // Check is always sorted and non empty.
    }

    /// Copies `self` into a new `Vec`.
    pub fn to_vec(&self) -> Vec<usize> {
        self.as_ref().to_vec()
    }
}

impl<'a> AsRef<[usize]> for CheckView<'a> {
    /// Returns the indices of the bits connected to `self` as a slice.
    fn as_ref(&self) -> &[usize] {
        self.bits
    }
}