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
use crate::GF2;
use rand::distributions::Uniform;
use rand::{thread_rng, Rng};
pub trait BinaryChannel: Sync {
fn intrinsic_likelyhood(&self, output: GF2) -> f64;
fn send(&self, input: GF2) -> GF2;
fn message_likelyhood(&self, output: &[GF2]) -> Vec<f64> {
output
.iter()
.map(|x| self.intrinsic_likelyhood(*x))
.collect()
}
fn sample(&self, inputs: &[GF2]) -> Vec<GF2> {
inputs.iter().map(|input| self.send(*input)).collect()
}
fn sample_uniform(&self, input: GF2, n_inputs: usize) -> Vec<GF2> {
(0..n_inputs).map(|_| self.send(input)).collect()
}
}
pub struct BinarySymmetricChannel {
prob: f64,
log_likelyhood: f64,
}
impl BinarySymmetricChannel {
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]
);
}
}