Return to search

Efficient implementation of an exact multiple-output boolean function minimization algorithm

The performance of the Svoboda-Nadler-Vora algorithm for exact multiple-output boolean function minimization is studied and compared with a heuristic minimization method.

For this purpose, the algorithm has been implemented in optimized ANSI C code. This implementation introduces a new set of procedures to reduce the cost of prime implicant generation. The concept of weight as the number of 1 and don't care neighbors of a state is used to take advantage of the special cases when a state has only one neighbor or no neighbors at all. The cost of prime implicant generation is further reduced by using the fact that the input dependency of any given state is limited by which of its neighbors exist within an output that are 1 's or don't cares. A detailed example illustrates how the heuristic method can fail to find the absolute minimum of a boolean function. / M.S.

Identiferoai:union.ndltd.org:VTETD/oai:vtechworks.lib.vt.edu:10919/106530
Date January 1989
CreatorsDueñas, César A.
ContributorsElectrical Engineering
PublisherVirginia Polytechnic Institute and State University
Source SetsVirginia Tech Theses and Dissertation
LanguageEnglish
Detected LanguageEnglish
TypeThesis, Text
Formatvii, 238 leaves, application/pdf, application/pdf
RightsIn Copyright, http://rightsstatements.org/vocab/InC/1.0/
RelationOCLC# 20766030

Page generated in 0.0021 seconds