Back to search

University of Victoria (Canada)

Minterm based search algorithms for two-level minimization of discrete functions

Abstract

dc:description.abstract

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.

Degree

thesis:*
Level thesis:degree_level
Doctor of Philosophy Ph.D.
Department thesis:degree_department
Department of Computer Science
Year dc:date.issued
2018

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Whitney, Michael James
Advisor dc:contributor.supervisor
  • Muzio, Jon C.

Subjects

dc:subject × 1

Rights

dc:rights
Statement dc:rights
  • Available to the World Wide Web
Language dc:language.iso
en, English

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1828/9643

Chain of custody

source
Harvested from
University of Victoria (Canada)
Base URL
dspace.library.uvic.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Whitney, Michael James. Minterm based search algorithms for two-level minimization of discrete functions. Doctor of Philosophy Ph.D. thesis, 2018. http://hdl.handle.net/1828/9643