NAME

QM - A Raku module that implements the Quine–McCluskey (QM) algorithm for simplifying Boolean functions

DESCRIPTION

The Quine-McCluskey algorithm is a simplification technique to systematically reach a minimal solution using a system of any n variables.

See the tutorial for more information about the algorithm which also has an example that walks through the algorithm. The same example can be found in examples/ex01.p6 as a Raku file.

The Quine–McCluskey algorithm on Wikipedia.

INSTALLATION

Using zef:

zef update && zef install QM

From source:

git clone git@gitlab.com:uzluisf/quine-mccluskey.git
cd quine-mccluskey && zef install .

SYNOPSIS

The module is implemented in a OO-style. To apply the algorithm, an object of the QM must be instantiated through the minterms. The following code snippet showcases all the methods made available by QM using the example from the tutorial:

use QM;

my @regular-minterms = 0, 1, 2, 5, 6, 7, 8, 9, 10, 14;
my @dont-care = []; 

# the don't care conditions array is optional.
my $qm = QM.minterms(@regular-minterms, @dont-care);

put $qm.all-minterms.join(', ');      #=> 0, 1, 2, 5, 6, 7, 8, 9, 10, 14

put $qm.prime-implicants<all>;        #=> 011- 0-01 01-1 --10 -00- -0-0

put $qm.essential-prime-implicants;   #=> --10 -00-

put $qm.prime-implicants-chart.perl;
#=>
#`{
"0" => $["-00-", "-0-0"],
"1" => $["-00-", "0-01"],
"10" => $["--10", "-0-0"],
"14" => $["--10"],
"2" => $["--10", "-0-0"],
"5" => $["01-1", "0-01"],
"6" => $["--10", "011-"],
"7" => $["011-", "01-1"],
"8" => $["-00-", "-0-0"],
"9" => $["-00-"]
}

put $qm.prime-implicants-chart(:dec).perl;
#=> 
# ([2, 6, 10, 14], [0, 2, 8, 10], [0, 1, 8, 9], [1, 5], [5, 7], [6, 7]).Seq

put $qm.reduced-boolean-expression;  #=> A'BD + CD' + B'C'

METHODS

• all-minterms - Return both the regular minterms and the don't care conditions if provided.

• prime-implicants - Return all prime implicants for the boolean function, including the essential prime implicants.

• essential-prime-implicants - Return the essential prime implicants for the boolean function.

• prime-implicants-chart - Return a hash representing the Prime Implicant Chart (PIC) detailing the minterms and the prime implicants which cover them.

  • prime-implicants-chart(:dec) - Return a sequence of arrays of prime implicants as decimal numerals.

• reduced-boolean-expression - Return the minimal SoP for the boolean function.

Materials

This modules was inspired by int-main's Python script implementing the algorithm and the paper Programing implementation of the Quine-McCluskey method for minimization of Boolean expression.

AUTHOR

Luis F. Uceta

LICENSE

Artistic License 2.0