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

NAME

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

SYNOPSIS

use Algorithm::QuineMcCluskey;

#
# Five-bit, 12-minterm Boolean expression test with don't-cares
#
my $q = Algorithm::QuineMcCluskey->new(
    width => 5,
    minterms => [ 0, 5, 7, 8, 10, 11, 15, 17, 18, 23, 26, 27 ],
    dontcares => [ 2, 16, 19, 21, 24, 25 ]
);

my $result = $q->solve();

or

    use Algorithm::QuineMcCluskey;

    my $q = Algorithm::QuineMcCluskey->new(
	width => 5,
        columnstring => '10-0010110110001-11-0-01--110000'
    );

    my $result = $q->solve();

In either case $result will be "(AC') + (A'BDE) + (B'CE) + (C'E')".

The strings that represent the covered terms are also viewable:

use Algorithm::QuineMcCluskey;

#
# Five-bit, 12-minterm Boolean expression test with don't-cares
#
my $q = Algorithm::QuineMcCluskey->new(
    width => 4,
    minterms => [ 1, 6, 7, 8, 11, 13, 15],
);

my @covers = $q->get_covers();

print $q->solve(), "\n", join(", ", @covers[0];

Will print out

'0001', '011-', '1-11', '1000', '11-1'
(A'B'C'D) + (A'BC) + (ACD) + (AB'C'D') + (ABD)

DESCRIPTION

This module minimizes Boolean expressions using the Quine-McCluskey algorithm.

Object Methods

new([<attribute> => value, ...])

Creates the QuineMcCluskey object. The attributes are:

'width'

The number of variables (columns) in the Boolean expression.

This is a required attribute.

'minterms'

An array reference of terms representing the 1-values of the Boolean expression.

'maxterms'

An array reference of terms representing the 0-values of the Boolean expression. This will also indicate that you want the expression in product-of-sum form, instead of the default sum-of-product form.

'dontcares'

An array reference of terms representing the don't-care-values of the Boolean expression. These represent inputs that simply shouldn't happen (e.g., numbers 11 through 15 in a base 10 system), and therefore don't matter to the result.

'columnstring'

Present the entire list of values of the boolean expression as a single string. The values are ordered from left to right in the string. For example, a simple two-variable AND equation would have a string "0001".

'dc'

Default value: '-'

Change the representation of the don't-care character. The don't-care character is used both in the columnstring, and internally as a place holder for eliminated variables in the equation. Some of those internals may be examined via other methods.

'title'

A title for the problem you are solving.

'vars'

Default value: ['A' .. 'Z']

The variable names used to form the equation. The names will be taken from the leftmost first:

    my $f1 = Algorithm::QuineMcCluskey->new(
        width => 4,
        maxterms => [1 .. 11, 13, 15],
	vars => ['w' .. 'z']
    );

The names do not have to be single characters, e.g.:

vars => ['a1', 'a0', 'b1', 'b0']

solve()

Returns a string of the Boolean equation.

For now, the form of the equation is set by the choice of terms used to create the object. If you use the minterms attribute, the equation will be returned in sum-of-product form. If you use the maxterms attribute, the equation will be returned in product-of-sum form.

Using the columnstring attribute is the same as using the minterms attribute as far as solve() is concerned.

It is possible that there will be more than one equation that solves the boolean expression. Therefore solve() can return a different (but equally valid) equation on separate runs. You can have the full list of possible equations by using "all_solutions()". Likewise, the terms that describe the solution (before they are converted with the variable names) are returned with "get_covers()", described below.

all_solutions()

Return an array of strings that represent the Boolean equation.

It is often the case that there will be more than one equation that covers the terms.

my @sol = $q->all_solutions();

print "    ", join("\n    ", @sol), "\n";

The first equation in the list will be the equation returned by "solve".

complement()

Returns a new object that's the complement of the existing object:

my $qc = $q->complement();
print $qc->solve(), "\n";

Prints

(ABC) + (A'B'D'E) + (BD'E) + (CE')

dual()

Returns a new object that's the dual of the existing object:

my $qd = $q->dual();
print $qd->solve(), "\n";

Prints

(ABCE') + (A'B'C') + (B'DE') + (C'E)

get_primes()

Returns the prime implicants of the boolean expression, as a hash reference. The keys of the hash are the prime implicants, while the values of the hash are arrays of the terms each implicant covers.

use Algorithm::QuineMcCluskey;

my $q = Algorithm::QuineMcCluskey->new(
    width => 4,
    minterms => [0, 2, 3, 4, 5, 10, 12, 13, 14, 15]
    );

#
# Remember, get_primes() returns a hash reference.
#
my $prime_ref = $q->get_primes();
print join(", ", sort keys %{$prime_ref}), "\n";

prints

-010, -10-, 0-00, 00-0, 001-, 1-10, 11--

See the function "chart()" in Algorithm::QuineMcCluskey::Format for an example of the prime implicant/term chart.

get_essentials()

Returns the essential prime implicants of the boolean expression, as an array reference. The array elements are the prime implicants that are essential, that is, the only ones that happen to cover certain terms in the expression.

use Algorithm::QuineMcCluskey;

my $q = Algorithm::QuineMcCluskey->new(
    width => 4,
    minterms => [0, 2, 3, 4, 5, 10, 12, 13, 14, 15]
    );

my $ess_ref = $q->get_essentials();
print join(", ", @{$ess_ref}), "\n";

prints

-10-, 001-, 11--

get_covers()

Returns all of the reduced implicant combinations that cover the booelan expression.

The implicants are in a form that combines 1, 0, and the don't-care character (found and set with the dc attribute). These are used by "solve()" to create a boolean equation that solves the set of minterms or maxterms.

It is possible that there will be more than one equation that solves a boolean expression. The solve() method returns a minimum set, and all_solutions() show the complete set of solutions found by the algorithm.

But if you want to see how the solutions match up with their associated covers, you may use this:

use Algorithm::QuineMcCluskey;

my $q = Algorithm::QuineMcCluskey->new(
    width => 4,
    minterms => [0, 2, 3, 4, 5, 10, 12, 13, 14, 15]
    );

#
# get_covers() returns an array ref of arrays.
#
my $covers = $q->get_covers();

for my $idx (0 .. $#{$covers})
{
    my @cvs = sort @{$covers->[$idx]};

    #
    # The raw ones, zeroes, and dont-care characters.
    #
    print "'", join("', '",  @cvs), "' => ";

    #
    # And the resulting boolean equation.
    #
    print $q->to_boolean(\@cvs), "\n";
}

prints

'-010', '-10-', '00-0', '001-', '11--' => (B'CD') + (BC') + (A'B'D') + (A'B'C) + (AB)
'-10-', '00-0', '001-', '1-10', '11--' => (BC') + (A'B'D') + (A'B'C) + (ACD') + (AB)
'-010', '-10-', '0-00', '001-', '11--' => (B'CD') + (BC') + (A'C'D') + (A'B'C) + (AB)
'-10-', '0-00', '001-', '1-10', '11--' => (BC') + (A'C'D') + (A'B'C) + (ACD') + (AB)

Note the use of the method to_boolean() in the loop. This is the method solve() uses to create its equation, by passing it the first of the list of covers.

to_columnstring()

Return a string made up of the function's column's values. Position 0 in the string is the 0th row of the column, and so on. The string will consist of zeros, ones, and the don't-care character (which by default is '-').

my $column = $self->to_columnstring();

AUTHOR

Darren M. Kulp darren@kulp.ch

John M. Gamble jgamble@cpan.org (current maintainer)

SEE ALSO

  • Introduction To Logic Design, by Sajjan G. Shiva, 1998.

  • Discrete Mathematics and its Applications, by Kenneth H. Rosen, 1995

LICENSE AND COPYRIGHT

Copyright (c) 2006 Darren Kulp. All rights reserved. This program is free software; you can redistribute it and/or modify it under the same terms as Perl itself.

See http://dev.perl.org/licenses/ for more information.