P.W. C. Prasad and A. Assi and A. Harb and V.C. Prasad
Binary Decision Diagrams An Improved Variable Ordering using Graph Representation of Boolean Functions
523 - 529
2008
2
2
International Journal of Computer and Information Engineering
https://publications.waset.org/pdf/6093
https://publications.waset.org/vol/14
World Academy of Science, Engineering and Technology
This paper presents an improved variable ordering method to obtain the minimum number of nodes in Reduced Ordered Binary Decision Diagrams (ROBDD). The proposed method uses the graph topology to find the best variable ordering. Therefore the input Boolean function is converted to a unidirectional graph. Three levels of graph parameters are used to increase the probability of having a good variable ordering. The initial level uses the total number of nodes (NN) in all the paths, the total number of paths (NP) and the maximum number of nodes among all paths (MNNAP). The second and third levels use two extra parameters The shortest path among two variables (SP) and the sum of shortest path from one variable to all the other variables (SSP). A permutation of the graph parameters is performed at each level for each variable order and the number of nodes is recorded. Experimental results are promising; the proposed method is found to be more effective in finding the variable ordering for the majority of benchmark circuits.
Open Science Index 14, 2008