Improvement on Composition Methods in Binary Decision Diagrams Based Applications

Function composition is a basic logical operation in most CAD applications,and is adopted as an improvement to a binary decisions diagram (BDD) based application.This paper determines the time complexity of the graph-based composition algorithm proposed by Bryant to O(|G1|2|G2|),then improves the composition algorithm based on the efficient ITE operator.The new algorithm omits the reducing step for result BDD,keeps the BDD representation as a strong canonical form and therefore improves the composition effciency.