IRREDUNDAND SUM-OF-PRODUCTS EXPRESSIONS
Jon T. Butler
Department of Electrical and Computer Engineering
Naval Postgraduate School
Monterey, CA 93943-5121
Room will be announced. Thursday, 18 November 1999, 11:00 - 12:00
An irredundant sum-of-products (ISOP) expression has the property that
if any product (AND) term is deleted, the function is changed. Among all
ISOP's are minimal sum-of-products (MSOP) expressions. Much research has
been devoted to efficiently determining the MSOP. Also, among ISOP's are
worst sum-of-products (WSOP) expressions. Little research has been done
on this topic until recently, when certain algorithms have been shown to
produce such expressions. For example, the Minato-Morreale algorithm
produces the WSOP for whole classes of functions. This surprising result
has shown the need for understanding how many more products are in WSOP's
than in MSOP's. We show a class of functions for which the ratio of
number of products in WSOP's to the number of products in MSOP's increases
arbitrarily as n, the number of variables increases. These functions also
have the characteristic that the Minato-Morreale algorithm produces WSOP's.
We also explore the distribution of ISOP's to the number of product terms
giving insight into the difficulty of minimizing functions.
Jon T. Butler is a Professor of Electrical and Computer Engineering at
the Naval Postgraduate School, Monterey, CA. He received the B.E.E. and M.Engr.
degrees from Rensselaer Polytechnic Institute in 1966 and 1967, respectively.,
and the Ph.D. degree from Ohio State University in 1973. He was an editor
of the IEEE Transactions on Computers, and Editor-in-Chief of Computer and
Editor-in-Chief of Computer Society Press. He was the first chairman of
the Computer Society's Technical Committee on Multiple-Valued Logic and
is a Fellow of the IEEE. His research interests are multiple-valued logic
and general logic design.