Binary Decision Diagrams (BDDs) are an important data structure for the design of digital circuits using VLSI CAD tools. The ordering of variables affects the total number of nodes and path length in the BDDs. Finding a good variable ordering is an optimization problem and previously many optimization approaches have been implemented for BDDs in a number of research works. In this paper, an optimization approach based on Spider Monkey Optimization (SMO) algorithm is proposed for the BDD variable ordering problem targeting number of nodes and longest path length. SMO is a well-known swarm intelligence-based optimization approach based on spider monkeys foraging behavior. The proposed work has been compared with other latest BDD reordering approaches using Particle Swarm Optimization (PSO) algorithm. The results obtained show significant improvement over the Particle Swarm Optimization method. The proposed SMO-based method is applied to different benchmark digital circuits having different levels of complexities. The node count and longest path length for the maximum number of tested circuits are found to be better in SMO than PSO.

This paper presents an approach of logic mapping into LUT-Array-Based PLD where Boolean functions in the form of the sum of generalized complex terms (SGCTs) can be mapped directly. While previous mapping approach requires predetermined variable ordering, our approach performs mapping and variable reordering simultaneously. For the purpose, we propose a directed acyclic graph based on the multiple-valued decision diagram (MDD) and an algorithm to construct the graph. Our algorithm generates candidates of SGCT expressions for each node in a bottom-up manner and selects the variables in the current level by evaluating the sizes of SGCT expressions directly. Experimental results show that our approach reduces the number of terms maximum to 71 percent for the MCNC benchmark circuits.

OPKFDDs (Ordered Pseudo-Kronecker Functional Decision Diagrams) are a data structure that provides compact representation of Boolean functions. The size of OPKFDDs depends on a variable ordering and on decomposition type choices. Finding an optimal representation is very hard and the size of the search space is n! 32n-1, where n is the number of input variables. To overcome the huge search space of the problem, a genetic algorithm is proposed for the generation of OPKFDDs with minimal number of nodes.

This paper proposes a method to construct smaller binary decision diagrams for characteristic functions (BDDs for CFs). A BDD for CF represents an n-input m-output function, and evaluates all the outputs in O(n+m) time. We derive an upper bound on the number of nodes of the BDD for CF of n-bit adders (adrn). We also compare complexities of BDDs for CFs with those of shared binary decision diagrams (SBDDs) and multi-terminal binary decision diagrams (MTBDDs). Our experimental results show: 1) BDDs for CFs are usually much smaller than MTBDDs; 2) for adrn and for some benchmark circuits, BDDs for CFs are the smallest among the three types of BDDs; and 3) the proposed method often produces smaller BDDs for CFs than an existing method.

An ordered binary decision diagram (OBDD) is a directed acyclic graph for representing a Boolean function. OBDDs are widely used in various areas which require Boolean function manipulation, since they can represent efficiently many practical Boolean functions and have other desirable properties. However, there is very little theoretical research on the complexity of constructing an OBDD. In this paper, we prove that the optimal variable ordering problem of a shared BDD is NP-complete, and briefly discuss the approximation hardness of this problem and related OBDD problems.

Binary Decision Diagrams (BDDs) and Shared Binary Decision Diagrams (SBDDs), which are improved BDDs, are useful for implementing VLSI logic design systems. Recently, these representations, which are graph representations of Boolean functions, have become popular because of their efficiency in terms of time and space. The forms of the BDD vary with the order of the input variables though they represent the same function. The size of the graphs greatly depends on the order. The variable ordering algorithm is one of the most important issues in the application of BDDs. In this paper, we consider methods which reduce the graph size by reordering input variables on a given BDD with a certain variable order. We propose the Minimum-Width Method which gives a considerably good order in a practicable time and space. In the method, the order is determined by width of BDDs as a cost function. In addition, we show the effect of combining our method with the local search method, and also describe the improvement using the threshold. Experimental results show that our method can reduce the size of BDDs remarkably for most examples. The method needs no additional information, such as the topological information of the circuit. The results can be a measure for evaluation of other ordering methods.