PORTLAND STATE UNIVERSITY
DEPARTMENT OF ELECTRICAL
AND COMPUTER ENGINEERING
SEMINAR


IRREDUNDAND SUM-OF-PRODUCTS EXPRESSIONS

by
Jon T. Butler
Department of Electrical and Computer Engineering
Naval Postgraduate School
Monterey, CA 93943-5121
Room 329 in Smith Center. 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.

Biography

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.