二元判决图应用中函数组合方法的改进

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(|G 1| 2|G 2|) ,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.