Accession Number:

ADA608073

Title:

On the Minimization of SOPs for Bi-Decomposable Functions

Descriptive Note:

Corporate Author:

NAVAL POSTGRADUATE SCHOOL MONTEREY CA DEPT OF ELECTRICAL AND COMPUTER ENGINEERING

Personal Author(s):

Report Date:

2001-02-01

Pagination or Media Count:

0.0

Abstract:

A function f is AND bi-decomposable if it can be written as function X1,X2 h1X1h2X2. In this case, a sum-of products expression SOP for f is obtained from minimum SOPs MSOP for h1 and h2 by applying the law of distributivity. If the result is an MSOP, then the complexity of minimization is reduced. However, the application of the law of distributivity to MSOPs for h1 and h2 does not always produce an MSOP for function. We show an incompletely specified function of nn - 1 variables that requires at most n products in an MSOP, while 2 - 1 products are required by minimizing the component functions separately. We introduce a new class of logic functions, called orthodox functions, where the application of the law of distributivity to MSOPs for component functions of f always produces an MSOP for function. We show that orthodox functions include all functions with three or fewer variables, all symmetric functions, all unate functions, many benchmark functions, and few random functions with many variables.

Subject Categories:

  • Numerical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE