We present a new data structure called edge-valued binary-decision diagrams (EVBDD). An EVBDD is a directed acyclic graph, that provides a canonical and compact representation of functions that involve both Boolean and integer quantities. In general, EVBDDs provide a more versatile and powerful representation than ordinary binary decision diagrams. We first describe the structure and properties of EVBDDs, and present a general algorithm for performing a variety of binary operations. Next, we describe an important extension of EVBDDs, called Structural EVBDDs, and show how they can be used for hierarchical verification.

This paper presents algorithms for disjunctive and nondisjunctive decomposition of Boolean functions and Boolean methods for identifying common subfunctions from multiple Boolean functions. Ordered binary decision diagrams are used to represent and manipulate Boolean functions so that the proposed methods can be implemented concisely. These techniques are applied to the synthesis of look-up table based field programmable gate arrays and results are presented.

Presents two Boolean methods for identifying common subfunctions from multiple-output functions. The first method is based on encoding the distinct columns in the stacked decomposition chart of the multiple-output function; the second method is based on the examination and encoding of all possible subfunctions that can be generated from a function with respect to a given subset of input variables. We then apply these methods to the synthesis of lookup-table based field programmable gate arrays. Experimental results are very encouraging.>

Edge-Valued Binary-Decision Diagrams (EVBDD's) are directed acyclic graphs that can represent and manipulate integer functions as effectively as Ordered Binary-Decision Diagrams OBDD's) do for Boolean functions. They have been used in logic verification for showing the equivalence between Boolean functions and arithmetic functions. In this paper, we present EVBDD-based algorithms for solving integer linear programs, computing spectral coefficients of Boolean functions, and performing function decomposition. These algorithms have been implemented in C under the SIS environment and experimental results are provided.>

This paper presents a theory for (disjunctive and nondisjunctive) function decomposition using the BDD representation of Boolean functions.Incompletely specified as well as multi-output Boolean functions are addressed as part of the general theory.A novel algorithm (based on an EVBDD representation) for generating the set of all bound variables that make the function decomposable is also presented.We compared our BDD-based decomposition procedure with existing implementations of the Roth-Karp procedure and obtained significant speed-ups.1

Edge-valued binary-decision diagrams (EVBDDs) are directed acyclic graphs which can represent and manipulate integer functions as effectively as ordered binary-decision diagrams (OBDDs) do for Boolean functions. They have been used to perform logic verification and compute the decomposability of Boolean functions. In this paper, we present a new EVBDD application for solving integer linear programs (ILP), which is an NP-hard problem that appears in many applications. Our approach is to combine the benefits of the EVBDD data structure (in terms of subgraph sharing and caching of computational results) with the state-of-the-art ILP solving techniques. Our program, called FGILP (Function Graph ILP) has been implemented in C under the SIS environment. The preliminary results of FGILP are comparable to those of LINDO.

An algorithm for Boolean matching based on binary decision diagrams using a level-first search strategy is presented. This algorithm is generally not restricted to circuits with just a few inputs and can be used for both technology mapping and logic verification. Unlike depth-first and breadth-first strategies, a level-first strategy permits significant pruning of the search space. A set of filters that further improve the performance of the matching algorithm is described. A method of analyzing the effectiveness of a filter is presented, and the various filters are ranked on the basis of their effect/cost ratio. Experimental results on a number of benchmark circuits are presented, comparing the basic matching algorithm with and without the use of various filters. It is shown how the matching algorithm and the filters can be extended to Boolean functions with don't cares.>