Comparison of the Worst and Best Sum-Of-Products Expressions for Multiple-Valued Functions

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1997
Accession Number
ADA599955

Entities

People

  • Jon T. Butler
  • Tsutomu Sasao

Organizations

  • Naval Postgraduate School

Tags

Communities of Interest

  • Advanced Electronics

DTIC Thesaurus Topics

  • Algorithms
  • Computer Science
  • Computers
  • Demographic Cohorts
  • Demography
  • Education
  • Electronics
  • Engineering
  • Experimental Data
  • Index Terms
  • Information Operations
  • Integrated Circuits
  • Mathematics
  • New York
  • Redundancy
  • Scientific Research
  • Switching

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Theoretical Analysis.