Browse Prior Art Database

Expansion Procedure for Single Output Decision Problems

IP.com Disclosure Number: IPCOM000046412D
Original Publication Date: 1983-Jul-01
Included in the Prior Art Database: 2005-Feb-07
Document File: 2 page(s) / 28K

Publishing Venue

IBM

Related People

Brown, A: AUTHOR [+2]

Abstract

An expansion order for a multi-level, single output function is efficiently determined by assigning a vector to each input and adding the input vectors to each block within the network to determine that block's output vector. The output vector for the function is used to develop an expansion order for the function.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 65% of the total text.

Page 1 of 2

Expansion Procedure for Single Output Decision Problems

An expansion order for a multi-level, single output function is efficiently determined by assigning a vector to each input and adding the input vectors to each block within the network to determine that block's output vector. The output vector for the function is used to develop an expansion order for the function.

Many problems in boolean analysis can be phrased as a single output decision problem. To find a 2-level AND-OR implementation of a multi-level network f, one can use the known concept of successive elimination f(x,y) =xf(o,y)+xf(1,y) x to find the solutions of f. Another exampleis the case of design verification where two implementations (IO, Il) of the same specification are compared for equivalence by formulating the problem as

(Image Omitted)

In both of these examples, an expansion order for the input variables is required. A good expansion order prunes the expansion tree quickly by trying to eliminate as many unnecessary expansions as possible.

The present procedure determines a "good" expansion order. The implementation is defined as an opcode PA = "path analysis". The input to the opcode is a levelized graph of connections. The basic idea behind path analysis is to identify the input variables which affect the largest number of paths in the network and then expand around those variables first.

The first step is to create a vector whose length is equal to the number of inputs. Each input "i"...