Browse Prior Art Database

Differential Boolean Analyzer

IP.com Disclosure Number: IPCOM000050349D
Original Publication Date: 1982-Oct-01
Included in the Prior Art Database: 2005-Feb-10
Document File: 2 page(s) / 14K

Publishing Venue

IBM

Related People

Bahnsen, RJ: AUTHOR

Abstract

Introduction Problems in verification and test generation for logic networks as well as other areas can often be formulated in a way that requires a solution of a Differential Boolean Analyzer (DBA), which is an algorithm that will find one or more solutions to F(x,y,...,z)=1, if any exist. It can also describe the space of all solutions to F=1. The space is described by an array of cubes. This array of cubes is called a cover for the function F. For example, let cube 0-1 be a cube of the solution space of F(x,y,z)=1. This cube represents the (x,y,z) points: (0,0,1), (0,1,1). If no solutions exist, DBA determines this fact. General Description

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 56% of the total text.

Page 1 of 2

Differential Boolean Analyzer

Introduction Problems in verification and test generation for logic networks as well as other areas can often be formulated in a way that requires a solution of a Differential Boolean Analyzer (DBA), which is an algorithm that will find one or more solutions to F(x,y,...,z)=1, if any exist. It can also describe the space of all solutions to F=1. The space is described by an array of cubes. This array of cubes is called a cover for the function F. For example, let cube 0-1 be a cube of the solution space of F(x,y,z)=1. This cube represents the (x,y,z) points: (0,0,1), (0,1,1). If no solutions exist, DBA determines this fact. General Description

The symbols *, +, and ' will be used to denote AND, OR, and complementation. A Boolean function F(x,y...z) can be expanded about the variable x in the following way: F(x,y...z)=x*F(1,y...z) + x'*F(0,y...z).

If y=a...z=b is a solution to F(1,y...z)=1, then x=1,y=a...z=b is a solution to F(x,y...z)=1. Similarly, if y=c...z=d is a solution to F(0,y...z)=1, then x=0,y=c...z=d is a solution to F(x,y...z)=1.

Thus, the search for a solution to F(x,y...z)=1 is reduced to the search for solutions to the two subproblems, F(1,y...z)=1 and F(0,y...z)=1. This expansion theorem is applied iteratively, each time choosing a variable v about which to expand that is expected to reduce the sub-problems as much as possible.

The DBA Algorithm

The input to DBA consists of: 1. A description of the Boolean function F for which a solution

to F(x,y...z)=1 is desired. The description may be in the

form of a logic network consisting of interconnected logic

blocks having primitive Boolean functions of AND, OR, AI,

OI and Exclusive OR. Other blocks would have to be expanded

into an equivalent circuit composed of these primitives.

2. A primary input list which identifies the input variables

(independent variables).

A primary output list which identifies the output

corresponding to the function F.

DBA then performs the following steps.

1. A Polish string is derived which expresses F as a function

of the primary input (independent variables).

2. A tree corresponding to the Polish string is formed. An

array of weights is also determined. The weights represent

the frequency of occurrence of the variables in the string.

3. The variable having the highest weight is picked as the

variable about which to expand. When the variable is picked,

the locations within the string that contain the chosen

variable are determined.

4. Using the tree description (plus some use of the string,

too), a reduced formula or string is obtained as a

consequence of substituting 0 for the chosen variable. This

is also repeated substituting 1 for the chosen variable.

1

Page 2 of 2

5. The strings resulting from the expansion in 4 are then

ex...