Comparison of the Worst and Best Sum-of-Products Expressions for Multiple-Valued Functions
Loading...
Authors
Sasao, Tsutomu
Butler, Jon T.
Subjects
Advisors
Date of Issue
1997-05
Date
Publisher
Language
Abstract
Because most practical logic design algorithms produce irredundant sum-of-products (ISOP) expressions, the understanding of ISOPs is crucial. We show a class of functions for which Morreale-Minato's ISOP generation algorithm produces worst ISOPs (WSOP), ISOPs with the most product terms. We show this class has the property that the ratio of the number of products in the WSOP to the number in the minimum ISOP (MSOP) is arbitrarily large when the number of variables is unbounded. The ramifications of this are significant; care must be exercised in designing algorithms that produce ISOPs. We also show that 2/sup n-1/ is a firm upper bound on the number of product terms in any ISOP for switching functions on n variables, answering a question that has been open for 30 years. We show experimental data and extend our results to functions of multiple-valued variables.
Type
Report
Description
Series/Report No
Department
Electrical and Computer Engineering (ECE)
Organization
Naval Postgraduate School (U.S.)
Identifiers
NPS Report Number
Sponsors
Funding
Format
7 p.
Citation
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.