Application of the constrained implicants set concept to the minimization of binary functions
Loading...
Authors
Ozkan, Ugur
Subjects
Constrained Implicants Set Concept
Binary Minimization
Binary Minimization
Advisors
Yang, Chyan
Butler, Jon T.
Date of Issue
1990
Date
Publisher
Monterey, California. Naval Postgraduate School
Language
en_US
Abstract
Several heuristics and algorithms have been developed to find minimal sum-of-products expressions in binary logic. Most of them use prime implicants during minimization process. An efficient search strategy has been developed for finding minimal sum-of-products expressions for multiple-valued logic (MVL) functions by using the constrained implicants set concept. The search space can be considerably reduced over the only other known exact minimization technique and exhaustive search. The primary goals of this research are to: (1) examine whether the constrained implicant set concept can be efficiently used in binary logic, and; (2) develop a heuristic called the constrained implicant set heuristic (CISH). The general idea of the CISH is to select the minterm with the least implicant cover size and find the implicant with the largest minterm coverage that covers a selected minterm. In this research, the implementation of the CISH is presented, the performance analysis of the CISH is shown by comparing with other heuristics (Maximum Implicant Heuristic, Espresso II) with respect to the average number of the product terms, the average computation time, and the average memory usage.
Type
Thesis
Description
Series/Report No
Department
Electrical and Computer Engineering
Organization
Naval Postgraduate School (U.S.)
Identifiers
NPS Report Number
Sponsors
Funder
Format
ix, 78 p.
Citation
Distribution Statement
Approved for public release; distribution is unlimited.
Rights
Copyright is reserved by the copryright owner.