一类新型抽象数据类型:有序二叉决策图  

The novel abstract data type:ordered binary decision diagrams

作　　者：古天龙[1] 

机构地区：[1]桂林电子科技大学计算机科学与工程学院,广西桂林541004

出　　处：《桂林电子科技大学学报》2010年第5期374-388,共15页Journal of Guilin University of Electronic Technology

摘　　要：有序二叉决策图OBDD(Ordered Binary Decision Diagram)是布尔函数的一种规范表达形式、一种的新的数据结构。基于OBDD能够完成布尔函数的有效表述和操作运算,可以看作为一类新的抽象数据类型。OBDD在VLSI逻辑综合和验证的成功应用结果引起了学术界和工业应用界的极大关注。迄今为止,OBDD技术及其工业应用已有了长足的发展、产生了不少的研究结果。本文对OBDD相关技术问题、OBDD扩展形式、OBDD应用等方面的研究现状进行了综述和讨论。An ordered binary decision diagram（OBDD） is a canonical and graphic form of a Boolean function,and is also considered as a new kind of data structure.Using OBDDs,Boolean functions can be not only represented but also manipulated in very efficient way.Thus,OBDDs can be considered as a kind of abstract date type.The application of OBDD to VLSI verification attracted the attention and renewed the interested of many researchers.So far,a large number of the basic OBDD concept have been suggested,and numerous applications in many areas such as VLSI CAD,AI planning,symbolic scheduling,Petri Nets analysis,and discrete event dynamic systems,have been found.This paper provides a brief overview of the state of the art in OBDDs and its applications.Basic properties of OBDD are discussed,and manipulation algorithms are described.The order of variables in an OBDD has a great effect on its size,and some recent progresses of variable order problems are explained.Variants of OBDDs can improve the efficiency of manipulation and the ability to represent non-bit functions,and the extensions of basic OBDD are outlined.We also present several applications of OBDDs and their variants.

关 键 词：有序二叉决策图 抽象数据类型 数据结构 符号技术 布尔函数 

分 类 号：TP311.12[自动化与计算机技术—计算机软件与理论]