Application of the Constrained Implicants Set Concept to the Minimization of Binary Functions
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1990
- Accession Number
- ADA239470
Entities
People
- Ugur Ozkan
Organizations
- Naval Postgraduate School