Accession Number:

ADA239470

Title:

Application of the Constrained Implicants Set Concept to the Minimization of Binary Functions

Descriptive Note:

Master's thesis

Corporate Author:

NAVAL POSTGRADUATE SCHOOL MONTEREY CA

Personal Author(s):

Report Date:

1990-09-01

Pagination or Media Count:

88.0

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.

Subject Categories:

  • Computer Hardware

Distribution Statement:

APPROVED FOR PUBLIC RELEASE