rustiq_core/routines/
decoding.rs

1use rand::seq::SliceRandom;
2use rand::thread_rng;
3
4pub fn syndrome_decoding(parities: &[Vec<bool>], input_target: &Vec<bool>) -> Option<Vec<bool>> {
5    let mut target = input_target.clone();
6    let mut solution = vec![false; parities.len()];
7    let mut hweight = target.iter().filter(|a| **a).count();
8    loop {
9        let mut best_reduction = 0;
10        let mut best_index: i32 = -1;
11        for (index, parity) in parities.iter().enumerate() {
12            let new_hweight = parity
13                .iter()
14                .zip(target.iter())
15                .map(|(a, b)| a ^ b)
16                .filter(|a| *a)
17                .count();
18            if (hweight as i32 - new_hweight as i32) > best_reduction {
19                best_reduction = hweight as i32 - new_hweight as i32;
20                best_index = index as i32;
21            }
22        }
23        if best_index == -1 {
24            break;
25        }
26        for (a, b) in target.iter_mut().zip(parities[best_index as usize].iter()) {
27            *a ^= b;
28        }
29        solution[best_index as usize] ^= true;
30        hweight = target.iter().filter(|a| **a).count();
31    }
32    let mut true_target = vec![false; target.len()];
33    for (i, b) in solution.iter().enumerate() {
34        if *b {
35            for (x, y) in parities[i].iter().zip(true_target.iter_mut()) {
36                *y ^= x;
37            }
38        }
39    }
40    if true_target != *input_target {
41        return None;
42    }
43    Some(solution)
44}
45
46fn colop(parities: &mut [Vec<bool>], i: usize, j: usize) {
47    for row in parities.iter_mut() {
48        row[j] ^= row[i];
49    }
50}
51
52fn shuffle_parities(
53    parities: &mut Vec<Vec<bool>>,
54    target: &mut [bool],
55    row_ech: bool,
56) -> Vec<usize> {
57    let n = parities.first().unwrap().len();
58    let mut row_permutation: Vec<usize> = (0..parities.len()).collect();
59    row_permutation.shuffle(&mut thread_rng());
60    let mut new_parities = Vec::new();
61    for j in row_permutation.iter() {
62        new_parities.push(parities[*j].clone());
63    }
64    if row_ech {
65        let mut rank = 0;
66        for i in 0..parities.len() {
67            let mut pivot = None;
68            for j in rank..n {
69                if new_parities[i][j] {
70                    pivot = Some(j);
71                    break;
72                }
73            }
74            if let Some(pivot) = pivot {
75                if pivot != rank {
76                    colop(&mut new_parities, pivot, rank);
77                    target[rank] ^= target[pivot];
78                }
79                for j in 0..n {
80                    if new_parities[i][j] && j != rank {
81                        colop(&mut new_parities, rank, j);
82                        target[j] ^= target[rank];
83                    }
84                }
85                rank += 1;
86                if rank == n {
87                    break;
88                }
89            }
90        }
91    }
92    *parities = new_parities;
93
94    row_permutation
95}
96
97fn fix_permutation(solution: &[bool], permutation: &[usize]) -> Vec<bool> {
98    let mut new_solution = vec![false; solution.len()];
99    for (i, j) in permutation.iter().enumerate() {
100        new_solution[*j] = solution[i];
101    }
102    new_solution
103}
104
105pub fn information_set_decoding(
106    input_parities: &[Vec<bool>],
107    input_target: &Vec<bool>,
108    ntries: usize,
109    row_ech: bool,
110) -> Option<Vec<bool>> {
111    let mut best_solution = None;
112    let mut best_cost = None;
113    for _ in 0..ntries {
114        let mut parities = input_parities.to_owned();
115        let mut target = input_target.clone();
116        let permutation = shuffle_parities(&mut parities, &mut target, row_ech);
117        let solution = syndrome_decoding(&parities, &target);
118        if let Some(solution) = solution {
119            let solution = fix_permutation(&solution, &permutation);
120            let cost = solution.iter().filter(|a| **a).count();
121            if let Some(best_cost) = best_cost {
122                if best_cost < cost {
123                    continue;
124                }
125            }
126            best_cost = Some(cost);
127            best_solution = Some(solution);
128        }
129    }
130    if let Some(solution) = best_solution {
131        let mut true_target = vec![false; input_target.len()];
132        for (i, b) in solution.iter().enumerate() {
133            if *b {
134                for (x, y) in input_parities[i].iter().zip(true_target.iter_mut()) {
135                    *y ^= x;
136                }
137            }
138        }
139        assert_eq!(true_target, *input_target);
140        return Some(solution);
141    }
142    None
143}
144
145#[cfg(test)]
146mod decoding_tests {
147    use super::*;
148    #[test]
149    fn test_raw_decoding() {
150        let parities = vec![
151            vec![true, false, false],
152            vec![false, true, false],
153            vec![false, false, true],
154            vec![true, false, true],
155        ];
156        let target = vec![true, true, true];
157        let solution = syndrome_decoding(&parities, &target);
158        println!("{:?}", solution);
159        assert_eq!(solution, Some(vec![false, true, false, true]));
160    }
161    #[test]
162    fn test_isd() {
163        let parities = vec![
164            vec![true, false, false],
165            vec![false, true, false],
166            vec![false, false, true],
167            vec![true, false, true],
168        ];
169        let target = vec![true, true, true];
170        let solution = information_set_decoding(&parities, &target, 100, true);
171        println!("{:?}", solution);
172    }
173}
rustiq_core/routines/decoding.rs

rustiq_core/routines/
decoding.rs
