Title :
Reducing the number of variable movements in exact BDD minimization
Author_Institution :
Dept. of Comput. Sci., Kaiserslautern Univ., Germany
Abstract :
Ordered Binary Decision Diagrams (BDDs) are frequently used in logic synthesis. In this paper a new exact BDD minimization algorithm is presented, which is based on state space search. In contrast to all previous approaches, in which variables are moved through the BDD when exploring the state space, the new method makes use of a new technique to expand states to its successor states without expensive variable movements. Experimental results are given to show the efficiency of the approach.
Keywords :
binary decision diagrams; directed graphs; logic CAD; minimisation of switching nets; state-space methods; BDD minimization algorithm; exact BDD minimization; logic synthesis; number of variable movements; ordered binary decision diagrams; state space search; successor states; Binary decision diagrams; Boolean functions; Circuits; Computer science; Data structures; Logic; Minimization methods; Runtime; Space exploration; State-space methods;
Conference_Titel :
Circuits and Systems, 2003. ISCAS '03. Proceedings of the 2003 International Symposium on
Print_ISBN :
0-7803-7761-3
DOI :
10.1109/ISCAS.2003.1206385
