John Gamble
and 1 contributors

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

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

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

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 minterm attribute as far as solve() is concerned.

It is possible for solve() to return two different (but equally valid) equations on separate runs. You can have the full list of possible equations by using "get_covers()", described below.

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 chart() function 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.

It is possible to have more than one possible equation solve a boolean expression. The solve() method returns a minimum set, but other sets are often generated too as part of the solving process. To see the other solutions, return them via get_covers().

    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 = @{$covers->[$idx]};

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

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

prints

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

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)