/ 
Algorithm-QuineMcCluskey-0.01
River stage one • 1 direct dependent • 1 total dependent
/ Algorithm::QuineMcCluskey

NAME

Algorithm::QuineMcCluskey - solve Quine-McCluskey set-cover problems

VERSION

This document describes version 0.01 released 24 June 2006.

SYNOPSIS

use Algorithm::QuineMcCluskey;

# Five-bit, 12-minterm Boolean expression test with don't-cares
my $q = new Algorithm::QuineMcCluskey(
	width => 5,
	minterms => [ qw(0 5 7 8 10 11 15 17 18 23 26 27) ],
	dontcares => [ qw(2 16 19 21 24 25) ]
);
my @result = $q->solve;
# @result is (
# 	"(B'CE) + (C'E') + (AC') + (A'BDE)"
# );

DESCRIPTION

NOTE: This module's API is NOT STABLE; the next version should support multiple-output problems and will add more object-oriented features, but in doing so will change the API. Upgrade at your own risk.

This module feebly stabs at providing solutions to Quine-McCluskey set-cover problems, which are used in electrical engineering/computer science to find minimal hardware implementations for a given input-output mapping. Since this problem is NP-complete, and since this implementation uses no heuristics, it is not expected to be useful for real-world problems.

The module is used in an object-oriented fashion; all necessary arguments can be (and currently must be) provided to the constructor. Unless only a certain step of is required, the whole algorithm is set off by calling solve() on an Algorithm::QuineMcCluskey object; this method returns a list of boolean expressions (as strings) representing valid solutions for the given inputs (see the SYNOPSIS).

METHODS

new

Default constructor

find_primes

Finding prime essentials

row_dom

Row-dominance

col_dom

Column-dominance

find_essentials

Finding essential prime implicants

purge_essentials

Delete essential primes from table

to_boolean

Generating Boolean expressions

solve

Main solution sub (wraps recurse_solve())

recurse_solve

Recursive divide-and-conquer solver

BUGS

Probably. The tests aren't complete enough, and the documentation is far from complete. Features missing include multiple-output support, which is in-progress but will require at least some rewriting to keep the code minimally ugly.

Please report any bugs or feature requests to bug-algorithm-quinemccluskey at rt.cpan.org, or through the web interface at http://rt.cpan.org/NoAuth/ReportBug.html?Queue=Algorithm-QuineMcCluskey. I will be notified, and then you'll automatically be notified of progress on your bug as I make changes.

SUPPORT

Feel free to contact me at the email address below if you have any questions, comments, suggestions, or complaints with regard to this module.

You can find documentation for this module with the perldoc command.

perldoc Algorithm::QuineMcCluskey

You can also look for information at:

AUTHOR

Darren M. Kulp <darren@kulp.ch>

COPYRIGHT AND LICENSE

Copyright (C) 2006 by Darren Kulp

This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself, either Perl version 5.8.7 or, at your option, any later version of Perl 5 you may have available.