Struct MinimumWeightDecoding 

pub struct MinimumWeightDecoding { /* private fields */ }

Minimum Weight Decoding.

Given an n×m binary matrix H and a binary syndrome vector s, find a binary vector x of length m that minimizes the Hamming weight |x| (number of 1s) subject to Hx ≡ s (mod 2).

Representation

Each of the m columns corresponds to a binary variable x_j ∈ {0, 1}. The evaluator checks whether the GF(2) linear system Hx = s is satisfied, and returns the Hamming weight of x if feasible.

Example

use problemreductions::models::algebraic::MinimumWeightDecoding;
use problemreductions::{Problem, BruteForce};

let matrix = vec![
    vec![true, false, true, true],
    vec![false, true, true, false],
    vec![true, true, false, true],
];
let target = vec![true, true, false];
let problem = MinimumWeightDecoding::new(matrix, target);
let solver = BruteForce::new();
let witness = solver.solve(&problem).unwrap();
assert!(witness.is_some());

Implementations

impl MinimumWeightDecoding

pub fn new(matrix: Vec<Vec<bool>>, target: Vec<bool>) -> Self

Create a new MinimumWeightDecoding instance.

Panics

Panics if the matrix is empty, rows have inconsistent lengths, target length does not match the number of rows, or there are no columns.

pub fn matrix(&self) -> &[Vec<bool>]

Returns a reference to the parity-check matrix H.

pub fn target(&self) -> &[bool]

Returns a reference to the syndrome vector s.

pub fn num_rows(&self) -> usize

Returns the number of rows of H.

pub fn num_cols(&self) -> usize

Returns the number of columns of H.

Trait Implementations

impl BruteForceProblem for MinimumWeightDecoding

fn dimensions(&self) -> Vec<usize>

Cardinality of each coordinate in the brute-force search space.

fn num_variables(&self) -> usize

Number of coordinates in the brute-force search space.

impl Clone for MinimumWeightDecoding

fn clone(&self) -> MinimumWeightDecoding

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for MinimumWeightDecoding

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl DeclaredVariant for MinimumWeightDecoding

impl<'de> Deserialize<'de> for MinimumWeightDecoding

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl Problem for MinimumWeightDecoding

const NAME: &'static str = "MinimumWeightDecoding"

Base name of this problem type (e.g., “MaximumIndependentSet”).

type Solution = Vec<bool>

Mathematical witness type for this problem.

type Value = Min<i64>

The evaluation value type.

fn parameter_names() -> &'static [&'static str]

Canonical parameter names for this problem model.

fn parameters(&self) -> ProblemParameters

Measure the complete canonical parameters of this concrete instance.

fn variant() -> Vec<(&'static str, &'static str)>

Returns variant attributes derived from type parameters.

fn evaluate(&self, config: &Self::Solution) -> Result<Min<i64>, EvaluationError>

Evaluate the problem on a solution.

fn problem_type() -> ProblemType

Look up this problem’s catalog entry.

impl ReduceTo<ILP<i64>> for MinimumWeightDecoding

type Result = ReductionMinimumWeightDecodingToILP

The reduction result type.

fn reduce_to(&self) -> Result<Self::Result, ReductionError>

Reduce this problem to the target problem type.

fn target_construction(error: ConstructionError) -> ReductionError

where Self: Sized,

Attach this reduction edge to a target-construction failure.

fn exact_i64( value: usize, operation: impl Into<String>, ) -> Result<i64, ReductionError>

where Self: Sized,

Convert a structural count used by the target’s exact integer algebra.

impl ReduceTo<MinimumWeightDecoding> for ThreeDimensionalMatching

type Result = ReductionThreeDimensionalMatchingToMinimumWeightDecoding

The reduction result type.

fn reduce_to(&self) -> Result<Self::Result, ReductionError>

Reduce this problem to the target problem type.

fn target_construction(error: ConstructionError) -> ReductionError

where Self: Sized,

Attach this reduction edge to a target-construction failure.

fn exact_i64( value: usize, operation: impl Into<String>, ) -> Result<i64, ReductionError>

where Self: Sized,

Convert a structural count used by the target’s exact integer algebra.

impl Serialize for MinimumWeightDecoding

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.