Qm

The Quine-McCluskey Algorithm for Minimization of Boolean Functions.

Ported to Haskell from the Python qm Package (http://pypi.python.org/pypi/qm) and its improved version (including Petrick's method) by George Prekas (http://github.com/prekageo/optistate).

Documentation

type BitVector = Word64

A fixed-width vector of 64 Bits.

newtype QmTerm

A min- or maxterm consisting of a tuple (variables, mask). The variables BitVector contains the 'True'/'False' values of the variables. The mask BitVector contains the dashes, i.e. for each 1 in the mask, the variable at that position can take any value.

Constructors

QmTerm (BitVector, BitVector)

Construct a QmTerm out of a tuple (variables, mask).

Instances

Eq QmTerm

Ord QmTerm

Show QmTerm

getTerm :: QmTerm -> BitVector

Extract the variables BitVector.

getMask :: QmTerm -> BitVector

Extract the mask BitVector.

getMaskedTerm :: QmTerm -> BitVector

Extract the variables BitVector, with all masked positions set to 0.

fromString :: String -> QmTerm

Reads a String of the form "01-0-" and creates a QmTerm. The "-" characters indicate masked positions.

qm

Arguments

:: [BitVector]

Ones, i.e. the set of min/maxterms that must be covered.

-> [BitVector]

Zeros, i.e. the set of min/maxterms that must not be covered.

-> [BitVector]

"Don't-care"-terms. These may be covered or not, whichever yields smaller subset of primes.

-> [QmTerm]

The minimum set of prime terms, covering all ones.

The Quine-McCluskey algorithm. Calculates the minimum cover of prime terms for a list of ones, zeros and "don't care" terms. All three can be non-empty, but at least either the ones or zeros must be non-empty. Based on that, the rest will be determined automatically.

compute_primes

Arguments

:: Set BitVector

Min/maxterms that must be covered.

-> Set QmTerm

The set of prime terms covering all min/maxterms.

Calculates the (generally not minimum) set of prime terms covering a set of min/maxterms.

bitcount

Arguments

:: Bits a

=> Bool

True to count 1s, False to count 0s.

-> a

-> Int

Counts the number of 1s (or 0s) in a BitVector.

merge

Arguments

:: QmTerm

-> QmTerm

-> Maybe QmTerm

Merged QmTerm, or Nothing if the merge isn't allowed.

Merges two QmTerms into one, if allowed. The merge is allowed iff (1) the masks of the two QmTerms are identical and (2) the two variable BitVectors differ in no more than one position.

unate_cover

Arguments

:: [QmTerm]

List of primes (generally not minimal)

-> [BitVector]

Min/maxterms that must be covered

-> (Int, Set QmTerm)

The minimum subset of primes.

Calculates the minimum subset of primes covering all min/maxterms, using Petrick's method (http://en.wikipedia.org/wiki/Petrick's_method).