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::{CreateSpec, 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        category: crate::registry::ProblemCategory::Algebraic,
19        module_path: module_path!(),
20        description: "Find minimum Hamming weight binary vector x such that Hx ≡ s (mod 2)",
21        fields: MinimumWeightDecodingCreateSpec::FIELDS,
22    }
23}
24
25/// Minimum Weight Decoding.
26///
27/// Given an n×m binary matrix H and a binary syndrome vector s, find a binary
28/// vector x of length m that minimizes the Hamming weight |x| (number of 1s)
29/// subject to Hx ≡ s (mod 2).
30///
31/// # Representation
32///
33/// Each of the m columns corresponds to a binary variable x_j ∈ {0, 1}.
34/// The evaluator checks whether the GF(2) linear system Hx = s is satisfied,
35/// and returns the Hamming weight of x if feasible.
36///
37/// # Example
38///
39/// ```
40/// use problemreductions::models::algebraic::MinimumWeightDecoding;
41/// use problemreductions::{Problem, BruteForce};
42///
43/// let matrix = vec![
44///     vec![true, false, true, true],
45///     vec![false, true, true, false],
46///     vec![true, true, false, true],
47/// ];
48/// let target = vec![true, true, false];
49/// let problem = MinimumWeightDecoding::new(matrix, target);
50/// let solver = BruteForce::new();
51/// let witness = solver.solve(&problem).unwrap();
52/// assert!(witness.is_some());
53/// ```
54#[derive(Debug, Clone, Serialize, Deserialize)]
55pub struct MinimumWeightDecoding {
56    /// The n×m binary parity-check matrix H.
57    matrix: Vec<Vec<bool>>,
58    /// The binary syndrome vector s of length n.
59    target: Vec<bool>,
60}
61
62#[derive(Debug, Deserialize, crate::CreateSpec)]
63struct MinimumWeightDecodingCreateSpec {
64    /// Binary parity-check matrix as JSON.
65    #[create(codec = "json")]
66    matrix: Vec<Vec<bool>>,
67    /// Binary syndrome vector.
68    #[create(name = "rhs", codec = "comma-separated")]
69    target: Vec<bool>,
70}
71
72impl TryFrom<MinimumWeightDecodingCreateSpec> for MinimumWeightDecoding {
73    type Error = crate::registry::ConstructionError;
74    fn try_from(spec: MinimumWeightDecodingCreateSpec) -> Result<Self, Self::Error> {
75        let first = spec
76            .matrix
77            .first()
78            .ok_or("matrix must have at least one row")?;
79        if first.is_empty() {
80            return Err("matrix must have at least one column".into());
81        }
82        if spec.matrix.iter().any(|row| row.len() != first.len()) {
83            return Err("all matrix rows must have the same length".into());
84        }
85        if spec.target.len() != spec.matrix.len() {
86            return Err("rhs length must equal number of rows".into());
87        }
88        Ok(Self {
89            matrix: spec.matrix,
90            target: spec.target,
91        })
92    }
93}
94
95impl MinimumWeightDecoding {
96    /// Create a new MinimumWeightDecoding instance.
97    ///
98    /// # Panics
99    ///
100    /// Panics if the matrix is empty, rows have inconsistent lengths,
101    /// target length does not match the number of rows, or there are no columns.
102    pub fn new(matrix: Vec<Vec<bool>>, target: Vec<bool>) -> Self {
103        assert!(!matrix.is_empty(), "Matrix must have at least one row");
104        let num_cols = matrix[0].len();
105        assert!(num_cols > 0, "Matrix must have at least one column");
106        for row in &matrix {
107            assert_eq!(row.len(), num_cols, "All rows must have the same length");
108        }
109        assert_eq!(
110            target.len(),
111            matrix.len(),
112            "Target length must equal number of rows"
113        );
114        Self { matrix, target }
115    }
116
117    /// Returns a reference to the parity-check matrix H.
118    pub fn matrix(&self) -> &[Vec<bool>] {
119        &self.matrix
120    }
121
122    /// Returns a reference to the syndrome vector s.
123    pub fn target(&self) -> &[bool] {
124        &self.target
125    }
126
127    /// Returns the number of rows of H.
128    pub fn num_rows(&self) -> usize {
129        self.matrix.len()
130    }
131
132    /// Returns the number of columns of H.
133    pub fn num_cols(&self) -> usize {
134        self.matrix[0].len()
135    }
136}
137
138impl Problem for MinimumWeightDecoding {
139    const NAME: &'static str = "MinimumWeightDecoding";
140    type Solution = Vec<bool>;
141    type Value = Min<i64>;
142
143    crate::problem_parameters![("num_cols", num_cols), ("num_rows", num_rows),];
144
145    fn variant() -> Vec<(&'static str, &'static str)> {
146        crate::variant_params![]
147    }
148
149    fn evaluate(
150        &self,
151        config: &Self::Solution,
152    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
153        Ok({
154            if config.len() != self.num_cols() {
155                return Err(crate::traits::EvaluationError::InvalidConfiguration(
156                    "decoded-word length does not match the matrix columns".into(),
157                ));
158            }
159            // Check Hx ≡ s (mod 2) for each row
160            for (i, row) in self.matrix.iter().enumerate() {
161                let dot: usize = row
162                    .iter()
163                    .zip(config.iter())
164                    .filter(|(&h, &x)| h && x)
165                    .count();
166                let syndrome_bit = dot % 2 == 1;
167                if syndrome_bit != self.target[i] {
168                    return Ok(Min(None));
169                }
170            }
171
172            // Feasible: return Hamming weight
173            let weight: usize = config.iter().filter(|&&v| v).count();
174            Min(Some(i64::try_from(weight).map_err(|_| {
175                crate::traits::EvaluationError::IntegerOverflow(
176                    "converting Hamming weight to i64".into(),
177                )
178            })?))
179        })
180    }
181}
182
183impl crate::solvers::BruteForceProblem for MinimumWeightDecoding {
184    fn dimensions(&self) -> Vec<usize> {
185        vec![2; self.num_cols()]
186    }
187}
188
189crate::declare_variants! {
190    default MinimumWeightDecoding => "2^(0.0494 * num_cols)" create MinimumWeightDecodingCreateSpec,
191}
192
193crate::register_brute_force! {
194    MinimumWeightDecoding decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
195}
196
197#[cfg(feature = "example-db")]
198pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
199    // H (3×4): [[1,0,1,1],[0,1,1,0],[1,1,0,1]], s = [1,1,0]
200    // Config [0,0,1,0] → weight 1, Hx = [1,1,0] ≡ s → Min(1)
201    let matrix = vec![
202        vec![true, false, true, true],
203        vec![false, true, true, false],
204        vec![true, true, false, true],
205    ];
206    let target = vec![true, true, false];
207    vec![crate::example_db::specs::ModelExampleSpec {
208        id: "minimum_weight_decoding",
209        instance: Box::new(MinimumWeightDecoding::new(matrix, target)),
210        optimal_config: serde_json::json!(vec![false, false, true, false]),
211        optimal_value: serde_json::json!(1),
212    }]
213}
214
215#[cfg(test)]
216#[path = "../../unit_tests/models/algebraic/minimum_weight_decoding.rs"]
217mod tests;
problemreductions/models/algebraic/minimum_weight_decoding.rs

problemreductions/models/algebraic/
minimum_weight_decoding.rs
