Techniques for the heuristic and exact two-level minimization of Boolean and multivalued
functions are presented. The work is based on a previously existing algorithmic
framework for two-level minimization known as directed search. This method is capable
of selecting covering prime implicants without generating all of them. Directed
search differs from most other minimization methods in that implicant cubes are
generated from minterms, not from other cubes.
Heretofore, the directed search algorithm and published variants have not been
capable of minimizing PLA’s of “industrial” size. The algorithms in this Work significantly
ameliorate this situation. In particular, original and efficient techniques
are proposed for prime implicant generation, computation of dominance relations,
elimination of redundant minterms, storage and retrieval of cubes and minterms, and,
isolation and reduction of cycles.
The algorithms are embodied in a working minimizer called MDSA. In the absence
of cycles, MDSA provides provably optimum cube covers. Empirical comparison with
other minimizers show the new algorithms to be very competitive, even superior.
For mid-sized non-cyclic PLA’s, MDSA is nearly always faster, and usually faster for
PLA’s containing cycles, than the best known heuristic competitor. The number of
cubes found for cyclic PLA’s is also better (lower), on average. MDSA can also be set
to provide provably minimum solutions for cyclic functions. In this case, MDSA again
outperforms competitive minimizers in a similar mode of operation. Both heuristic
and exact versions of MDSA are restricted to PLA’s with. 32 or fewer inputs, and 32
or fewer outputs. / Graduate
| Identifer | oai:union.ndltd.org:uvic.ca/oai:dspace.library.uvic.ca:1828/9643 |
| Date | 09 July 2018 |
| Creators | Whitney, Michael James |
| Contributors | Muzio, Jon C. |
| Source Sets | University of Victoria |
| Language | English, English |
| Detected Language | English |
| Type | Thesis |
| Format | application/pdf |
| Rights | Available to the World Wide Web |
Page generated in 0.002 seconds