problemreductions/models/algebraic/
minimum_weight_decoding.rs

1//! Minimum Weight Decoding problem implementation.
2//!
3//! Given an n x m binary matrix H (parity-check matrix) and a binary syndrome
4//! vector s of length n, find a binary vector x of length m minimizing the
5//! Hamming weight |x| subject to Hx ≡ s (mod 2).
6
7use crate::registry::{FieldInfo, ProblemSchemaEntry};
8use crate::traits::Problem;
9use crate::types::Min;
10use serde::{Deserialize, Serialize};
11
12inventory::submit! {
13    ProblemSchemaEntry {
14        name: "MinimumWeightDecoding",
15        display_name: "Minimum Weight Decoding",
16        aliases: &[],
17        dimensions: &[],
18        module_path: module_path!(),
19        description: "Find minimum Hamming weight binary vector x such that Hx ≡ s (mod 2)",
20        fields: &[
21            FieldInfo { name: "matrix", type_name: "Vec<Vec<bool>>", description: "n×m binary parity-check matrix H" },
22            FieldInfo { name: "target", type_name: "Vec<bool>", description: "binary syndrome vector s of length n" },
23        ],
24    }
25}
26
27/// Minimum Weight Decoding.
28///
29/// Given an n×m binary matrix H and a binary syndrome vector s, find a binary
30/// vector x of length m that minimizes the Hamming weight |x| (number of 1s)
31/// subject to Hx ≡ s (mod 2).
32///
33/// # Representation
34///
35/// Each of the m columns corresponds to a binary variable x_j ∈ {0, 1}.
36/// The evaluator checks whether the GF(2) linear system Hx = s is satisfied,
37/// and returns the Hamming weight of x if feasible.
38///
39/// # Example
40///
41/// ```
42/// use problemreductions::models::algebraic::MinimumWeightDecoding;
43/// use problemreductions::{Problem, Solver, BruteForce};
44///
45/// let matrix = vec![
46///     vec![true, false, true, true],
47///     vec![false, true, true, false],
48///     vec![true, true, false, true],
49/// ];
50/// let target = vec![true, true, false];
51/// let problem = MinimumWeightDecoding::new(matrix, target);
52/// let solver = BruteForce::new();
53/// let witness = solver.find_witness(&problem);
54/// assert!(witness.is_some());
55/// ```
56#[derive(Debug, Clone, Serialize, Deserialize)]
57pub struct MinimumWeightDecoding {
58    /// The n×m binary parity-check matrix H.
59    matrix: Vec<Vec<bool>>,
60    /// The binary syndrome vector s of length n.
61    target: Vec<bool>,
62}
63
64impl MinimumWeightDecoding {
65    /// Create a new MinimumWeightDecoding instance.
66    ///
67    /// # Panics
68    ///
69    /// Panics if the matrix is empty, rows have inconsistent lengths,
70    /// target length does not match the number of rows, or there are no columns.
71    pub fn new(matrix: Vec<Vec<bool>>, target: Vec<bool>) -> Self {
72        assert!(!matrix.is_empty(), "Matrix must have at least one row");
73        let num_cols = matrix[0].len();
74        assert!(num_cols > 0, "Matrix must have at least one column");
75        for row in &matrix {
76            assert_eq!(row.len(), num_cols, "All rows must have the same length");
77        }
78        assert_eq!(
79            target.len(),
80            matrix.len(),
81            "Target length must equal number of rows"
82        );
83        Self { matrix, target }
84    }
85
86    /// Returns a reference to the parity-check matrix H.
87    pub fn matrix(&self) -> &[Vec<bool>] {
88        &self.matrix
89    }
90
91    /// Returns a reference to the syndrome vector s.
92    pub fn target(&self) -> &[bool] {
93        &self.target
94    }
95
96    /// Returns the number of rows of H.
97    pub fn num_rows(&self) -> usize {
98        self.matrix.len()
99    }
100
101    /// Returns the number of columns of H.
102    pub fn num_cols(&self) -> usize {
103        self.matrix[0].len()
104    }
105}
106
107impl Problem for MinimumWeightDecoding {
108    const NAME: &'static str = "MinimumWeightDecoding";
109    type Value = Min<usize>;
110
111    fn variant() -> Vec<(&'static str, &'static str)> {
112        crate::variant_params![]
113    }
114
115    fn dims(&self) -> Vec<usize> {
116        vec![2; self.num_cols()]
117    }
118
119    fn evaluate(&self, config: &[usize]) -> Min<usize> {
120        if config.len() != self.num_cols() {
121            return Min(None);
122        }
123        if config.iter().any(|&v| v >= 2) {
124            return Min(None);
125        }
126
127        // Check Hx ≡ s (mod 2) for each row
128        for (i, row) in self.matrix.iter().enumerate() {
129            let dot: usize = row
130                .iter()
131                .zip(config.iter())
132                .filter(|(&h, &x)| h && x == 1)
133                .count();
134            let syndrome_bit = dot % 2 == 1;
135            if syndrome_bit != self.target[i] {
136                return Min(None);
137            }
138        }
139
140        // Feasible: return Hamming weight
141        let weight: usize = config.iter().filter(|&&v| v == 1).count();
142        Min(Some(weight))
143    }
144}
145
146crate::declare_variants! {
147    default MinimumWeightDecoding => "2^(0.0494 * num_cols)",
148}
149
150#[cfg(feature = "example-db")]
151pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
152    // H (3×4): [[1,0,1,1],[0,1,1,0],[1,1,0,1]], s = [1,1,0]
153    // Config [0,0,1,0] → weight 1, Hx = [1,1,0] ≡ s → Min(1)
154    let matrix = vec![
155        vec![true, false, true, true],
156        vec![false, true, true, false],
157        vec![true, true, false, true],
158    ];
159    let target = vec![true, true, false];
160    vec![crate::example_db::specs::ModelExampleSpec {
161        id: "minimum_weight_decoding",
162        instance: Box::new(MinimumWeightDecoding::new(matrix, target)),
163        optimal_config: vec![0, 0, 1, 0],
164        optimal_value: serde_json::json!(1),
165    }]
166}
167
168#[cfg(test)]
169#[path = "../../unit_tests/models/algebraic/minimum_weight_decoding.rs"]
170mod tests;
problemreductions/models/algebraic/minimum_weight_decoding.rs

problemreductions/models/algebraic/
minimum_weight_decoding.rs
