Abstract
A method to restructure binary decision diagrams (BDDs) from a given input ordering to any other ordering is proposed. This technique is based on the concept of functional equivalence and BBDs structure equivalence. A transpositional operator is developed to implement the transformation. It is shown that this transformation is used to find a good input variable ordering for BBDs a good input partition for communication complexity based multilevel logic synthesis. Experimental results are presented.