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)]
55#[serde(try_from = "MinimumWeightDecodingCreateSpec")]
56pub struct MinimumWeightDecoding {
57    /// The n×m binary parity-check matrix H.
58    matrix: Vec<Vec<bool>>,
59    /// The binary syndrome vector s of length n.
60    target: Vec<bool>,
61}
62
63#[derive(Debug, Deserialize, crate::CreateSpec)]
64struct MinimumWeightDecodingCreateSpec {
65    /// Binary parity-check matrix as JSON.
66    #[create(codec = "json")]
67    matrix: Vec<Vec<bool>>,
68    /// Binary syndrome vector.
69    #[create(name = "rhs", codec = "comma-separated")]
70    target: Vec<bool>,
71}
72
73impl TryFrom<MinimumWeightDecodingCreateSpec> for MinimumWeightDecoding {
74    type Error = crate::registry::ConstructionError;
75
76    fn try_from(spec: MinimumWeightDecodingCreateSpec) -> Result<Self, Self::Error> {
77        Self::try_new(spec.matrix, spec.target)
78    }
79}
80
81impl MinimumWeightDecoding {
82    /// Create a new MinimumWeightDecoding instance.
83    ///
84    /// # Panics
85    ///
86    /// Panics if the matrix is empty, rows have inconsistent lengths,
87    /// target length does not match the number of rows, or there are no columns.
88    pub fn new(matrix: Vec<Vec<bool>>, target: Vec<bool>) -> Self {
89        Self::try_new(matrix, target).unwrap_or_else(|error| panic!("{error}"))
90    }
91
92    fn try_new(
93        matrix: Vec<Vec<bool>>,
94        target: Vec<bool>,
95    ) -> Result<Self, crate::registry::ConstructionError> {
96        let first = matrix.first().ok_or("matrix must have at least one row")?;
97        if first.is_empty() {
98            return Err("matrix must have at least one column".into());
99        }
100        if matrix.iter().any(|row| row.len() != first.len()) {
101            return Err("all matrix rows must have the same length".into());
102        }
103        if target.len() != matrix.len() {
104            return Err("Target length must equal number of rows".into());
105        }
106        Ok(Self { matrix, target })
107    }
108
109    /// Returns a reference to the parity-check matrix H.
110    pub fn matrix(&self) -> &[Vec<bool>] {
111        &self.matrix
112    }
113
114    /// Returns a reference to the syndrome vector s.
115    pub fn target(&self) -> &[bool] {
116        &self.target
117    }
118
119    /// Returns the number of rows of H.
120    pub fn num_rows(&self) -> usize {
121        self.matrix.len()
122    }
123
124    /// Returns the number of columns of H.
125    pub fn num_cols(&self) -> usize {
126        self.matrix[0].len()
127    }
128}
129
130impl Problem for MinimumWeightDecoding {
131    const NAME: &'static str = "MinimumWeightDecoding";
132    type Solution = Vec<bool>;
133    type Value = Min<i64>;
134
135    crate::problem_parameters![("num_cols", num_cols), ("num_rows", num_rows),];
136
137    fn variant() -> Vec<(&'static str, &'static str)> {
138        crate::variant_params![]
139    }
140
141    fn evaluate(
142        &self,
143        config: &Self::Solution,
144    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
145        Ok({
146            if config.len() != self.num_cols() {
147                return Err(crate::traits::EvaluationError::InvalidConfiguration(
148                    "decoded-word length does not match the matrix columns".into(),
149                ));
150            }
151            // Check Hx ≡ s (mod 2) for each row
152            for (i, row) in self.matrix.iter().enumerate() {
153                let dot: usize = row
154                    .iter()
155                    .zip(config.iter())
156                    .filter(|(&h, &x)| h && x)
157                    .count();
158                let syndrome_bit = dot % 2 == 1;
159                if syndrome_bit != self.target[i] {
160                    return Ok(Min(None));
161                }
162            }
163
164            // Feasible: return Hamming weight
165            let weight: usize = config.iter().filter(|&&v| v).count();
166            Min(Some(i64::try_from(weight).map_err(|_| {
167                crate::traits::EvaluationError::IntegerOverflow(
168                    "converting Hamming weight to i64".into(),
169                )
170            })?))
171        })
172    }
173}
174
175impl crate::solvers::BruteForceProblem for MinimumWeightDecoding {
176    fn dimensions(&self) -> Vec<usize> {
177        vec![2; self.num_cols()]
178    }
179}
180
181crate::declare_variants! {
182    default MinimumWeightDecoding => "2^(0.0494 * num_cols)" create MinimumWeightDecodingCreateSpec,
183}
184
185crate::register_brute_force! {
186    MinimumWeightDecoding decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
187}
188
189#[cfg(feature = "example-db")]
190pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
191    // H (3×4): [[1,0,1,1],[0,1,1,0],[1,1,0,1]], s = [1,1,0]
192    // Config [0,0,1,0] → weight 1, Hx = [1,1,0] ≡ s → Min(1)
193    let matrix = vec![
194        vec![true, false, true, true],
195        vec![false, true, true, false],
196        vec![true, true, false, true],
197    ];
198    let target = vec![true, true, false];
199    vec![crate::example_db::specs::ModelExampleSpec {
200        id: "minimum_weight_decoding",
201        instance: Box::new(MinimumWeightDecoding::new(matrix, target)),
202        optimal_config: serde_json::json!(vec![false, false, true, false]),
203        optimal_value: serde_json::json!(1),
204    }]
205}
206
207#[cfg(test)]
208#[path = "../../unit_tests/models/algebraic/minimum_weight_decoding.rs"]
209mod tests;
problemreductions/models/algebraic/minimum_weight_decoding.rs

problemreductions/models/algebraic/
minimum_weight_decoding.rs
