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, Solver, 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.find_witness(&problem);
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 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<'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 Value = Min<usize>

The evaluation value type.

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

Returns variant attributes derived from type parameters.

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

Configuration space dimensions. Each entry is the cardinality of that variable.

fn evaluate(&self, config: &[usize]) -> Min<usize>

Evaluate the problem on a configuration.

fn num_variables(&self) -> usize

Number of variables (derived from dims).

fn problem_type() -> ProblemType

Look up this problem’s catalog entry.

impl ReduceTo<ILP<i32>> for MinimumWeightDecoding

type Result = ReductionMinimumWeightDecodingToILP

The reduction result type.

fn reduce_to(&self) -> Self::Result

Reduce this problem to the target problem type.

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.

impl DeclaredVariant for MinimumWeightDecoding