Comparison of the worst and best sum-of-products expressions for multiple-valued functions

Author

Sasao, Tsutomu ; Butler, Jon T.

Author_Institution

Dept. of Comput. Sci., Kyushu Inst. of Technol., Iizuka, Japan

fYear

1997

fDate

28-30 May 1997

Firstpage

55

Lastpage

60

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^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

Keywords

logic design; minimisation; multivalued logic; switching functions; best sum-of-products expressions; logic design algorithms; multiple-valued functions; multiple-valued variables; product terms; switching functions; upper bound; worst sum-of-products expressions; Algorithm design and analysis; Computer science; Logic design; Logic functions; Minimization methods; Upper bound;

fLanguage

English

Publisher

ieee

Conference_Titel

Multiple-Valued Logic, 1997. Proceedings., 1997 27th International Symposium on

Conference_Location

Antigonish, NS

Print_ISBN

0-8186-7910-7

Type

conf

DOI

10.1109/ISMVL.1997.601374

Filename

601374