Algorithm::QuineMcCluskey - solve Quine-McCluskey set-cover problems
This document describes version 0.01 released 24 June 2006.
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)" # );
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
Finding prime essentials
Finding essential prime implicants
Delete essential primes from table
Generating Boolean expressions
Main solution sub (wraps recurse_solve())
Recursive divide-and-conquer solver
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.
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.
You can also look for information at:
Darren M. Kulp
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.