| 二元判决图应用中函数组合方法的改进 |
| |
| 引用本文： | 章小兵,陈光. 二元判决图应用中函数组合方法的改进[J]. 电子科技大学学报(社会科学版), 1997, 0(1) |
| |
| 作者姓名： | 章小兵 陈光 |
| |
| 作者单位： | 电子科技大学ＣＡＴ研究室 |
| |
| 基金项目： | 国家“八五”重点科研项目 |
| |
| 摘 要： | 文中确定了Ｂｒｙａｎｔ的基于图的函数组合方法［１］的时间复杂度为Ｏ（｜Ｇ１｜２·｜Ｇ２｜），并提出了基于改进ＩＴＥ算符的函数组合方法。该方法省去了对结果二元判决图的约简步骤，保持了二元判决图的强正则性，提高了效率
|
| 关 键 词： | 二元判决图；函数组合；时间复杂度；优化 |
Improvement on Composition Methods in Binary Decision Diagrams Based Applications |
| |
| Zhang Xiaobing Chen Guangju. Improvement on Composition Methods in Binary Decision Diagrams Based Applications[J]. Journal of University of Electronic Science and Technology of China(Social Sciences Edition), 1997, 0(1) |
| |
| Authors: | Zhang Xiaobing Chen Guangju |
| |
| Abstract: | 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. |
| |
| Keywords: | binary decision diagram compose time complexity optimization |
| 本文献已被 CNKI 等数据库收录！ |
