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

Improvement on Composition Methods in Binary Decision Diagrams Based Applications

作　　者：章小兵[1] 陈光[1] 

机构地区：[1]电子科技大学CAT研究室

出　　处：《电子科技大学学报》1997年第1期54-57,共4页Journal of University of Electronic Science and Technology of China

基　　金：国家"八五"重点科研项目

摘　　要：文中确定了Ｂｒｙａｎｔ的基于图的函数组合方法［１］的时间复杂度为Ｏ（｜Ｇ１｜２·｜Ｇ２｜），并提出了基于改进ＩＴＥ算符的函数组合方法。该方法省去了对结果二元判决图的约简步骤，保持了二元判决图的强正则性。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.

关 键 词：二元判决图 函数组合 时间复杂度 优化 

分 类 号：O141[理学—数学]