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

//! Transmission channels.

use crate::GF2;
use rand::distributions::Uniform;
use rand::{thread_rng, Rng};

/// A trait that represent a binary transmission channel. It takes an `GF2` element
/// and (randomly) map it to an other `GF2` element. It has an intrinsic likelyhood
/// for each output.
///
/// # Example
///
/// ```
/// # use believer::*;
/// // Create a bsc with error prob of 0.2.
/// let bsc = channel::BinarySymmetricChannel::new(0.2);
/// // Sample the channel by always sending 0.
/// let received = bsc.sample_uniform(GF2::B0, 1000);
/// let number_of_one = received.iter()
///     .filter(|&x| x == &GF2::B1)
///     .collect::<Vec<_>>()
///     .len();
/// println!("{}", number_of_one); // Should be around 200.
/// ```
pub trait BinaryChannel: Sync + Send {
    /// For a given `output`, compute log(p(output|input = 1) / p(output|input = 0)).
    ///
    /// # Example
    ///
    /// ```
    /// # use believer::*;
    /// let bsc = channel::BinarySymmetricChannel::new(0.2);
    /// assert_eq!(bsc.intrinsic_likelyhood(GF2::B0), -2.0);
    /// assert_eq!(bsc.intrinsic_likelyhood(GF2::B1), 2.0);
    /// ```
    fn intrinsic_likelyhood(&self, output: GF2) -> f64;

    /// For a given `input`, returns an `output` according to some
    /// probability distribution depending on the channel.
    fn send(&self, input: GF2) -> GF2;

    // Returns the likelyhood of a given message.
    fn message_likelyhood(&self, output: &[GF2]) -> Vec<f64> {
        output
            .iter()
            .map(|x| self.intrinsic_likelyhood(*x))
            .collect()
    }

    /// Returns a `Vec` of outputs as long as the `inputs` where each
    /// output is sample using the `send` method.
    fn sample(&self, inputs: &[GF2]) -> Vec<GF2> {
        inputs.iter().map(|input| self.send(*input)).collect()
    }

    /// Returns a `Vec` of outputs where the `input` is send `n_inputs` times.
    fn sample_uniform(&self, input: GF2, n_inputs: usize) -> Vec<GF2> {
        (0..n_inputs).map(|_| self.send(input)).collect()
    }
}

/// A binary symmetric channel caracterize by its error probability `prob`.
/// That is, every time an input is send throught the channel, it is
/// flipped with probability `prob`.
#[derive(Clone)]
pub struct BinarySymmetricChannel {
    prob: f64,
    log_likelyhood: f64,
}

impl BinarySymmetricChannel {
    /// Creates a new binary symmetric channel from an given `prob` of error.
    ///
    /// # Panic
    ///
    /// Panic if `prob` is not between 0 and 1.
    pub fn new(prob: f64) -> Self {
        if 0.0 <= prob && prob <= 1.0 {
            Self {
                prob,
                log_likelyhood: (prob / (1.0 - prob)).log2(),
            }
        } else {
            panic!("prob is not between 0 and 1")
        }
    }
}

impl BinaryChannel for BinarySymmetricChannel {
    fn intrinsic_likelyhood(&self, output: GF2) -> f64 {
        if output == GF2::B0 {
            self.log_likelyhood
        } else {
            -1.0 * self.log_likelyhood
        }
    }

    fn send(&self, input: GF2) -> GF2 {
        let rand = thread_rng().sample(Uniform::new(0.0, 1.0));
        if rand < self.prob {
            input + GF2::B1
        } else {
            input
        }
    }
}

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn binary_symmetric_channel() {
        let channel = BinarySymmetricChannel::new(0.2);

        assert_eq!(channel.intrinsic_likelyhood(GF2::B0), -2.0);
        assert_eq!(channel.intrinsic_likelyhood(GF2::B1), 2.0);
        assert_eq!(
            channel.message_likelyhood(&[GF2::B1, GF2::B0, GF2::B1]),
            vec![2.0, -2.0, 2.0]
        );
    }
}