Browse Prior Art Database

Expansions for TAU Boolean Equation Solver

IP.com Disclosure Number: IPCOM000100977D
Original Publication Date: 1990-Jun-01
Included in the Prior Art Database: 2005-Mar-16
Document File: 2 page(s) / 73K

Publishing Venue

IBM

Related People

Brown, A: AUTHOR [+4]

Abstract

It is well known that solving Boolean equations is a very important problem in many areas of VLSI digital design. The classical solution method of successive elimination of variables (1) has been shown to be a very effective technique and was implemented in (2). The technique is a branch-and-bound tree expansion procedure which involves successive evaluations of a Boolean function by expanding around Boolean variables. This procedure generates a disjunctive normal form expression along each path in the expansion tree. The more recent TAU algorithm (3), on the other hand, generates all the terms of the solution using a compact 3-level representation.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Expansions for TAU Boolean Equation Solver

       It is well known that solving Boolean equations is a very
important problem in many areas of VLSI digital design.  The
classical solution method of successive elimination of variables (1)
has been shown to be a very effective technique and was implemented
in (2).  The technique is a branch-and-bound tree expansion procedure
which involves successive evaluations of a Boolean function by
expanding around Boolean variables.  This procedure generates a
disjunctive normal form expression along each path in the expansion
tree.  The more recent TAU algorithm (3), on the other hand,
generates all the terms of the solution using a compact 3-level
representation.

      The key to success in (2) of the Differential Boolean Analyzer
(DBA) version of successive elimination is its novel ability to
recognize equivalent sets of partials (ESP), which avoids
reevaluating subtrees in the expansion process.

      Disclosed is an enhancement to TAU and DBA/ESP which combines
the best of both algorithms.  The approach of successive elimination
in DBA/ESP is used to create subproblems which are then solved using
the TAU algorithm. Furthermore, expansions are generalized to include
internal variables rather than limiting the expansion process only to
primary inputs.

      The algorithm consists of the following steps:
-    Identify variables for expansion.
-    For each expansion variable compute its Boolean function and
complement using TAU.  If the expansion variable is a primary input,
then the function is trivial.  If it is an internal variable, then
computing the Boolean function involves propagating PLAs through the
network using the PLA intersection, union, and complementatio...