有序二叉决策图及应用

出版时间：2009-7  出版社：科学出版社  作者：古天龙，徐周波 著  页数：275  
Tag标签：无  

前言

　　布尔代数是计算机科学和逻辑系统设计的重要基石。VLSI系统CAD、软件测试和验证、AI规划与调度等领域中的诸多问题都归结为逻辑函数及其序列的操作和运算。毫无疑问，布尔函数的表述及其操作对这些领域中问题的合理有效解决起着尤为关键的作用。不幸的是，布尔函数的可满足性和等价性等问题的NP完备性所导致的状态组合爆炸问题严重地制约了大规模、甚至工业小规模问题的解决。然而，在实际问题的处理中，对布尔函数采取恰当的描述并建立相应描述下的操作算法，可以有效地减缓甚至避免问题处理过程中的状态组合复杂性。有序二叉决策图（ordered binary decision diagram，0BDD）则是该方面的有益探索和结果。　　0BDD是一种新型数据结构，是迄今为止布尔函数表述和操作中最为有效的技术之一。人们对它的研究最早可追溯到20世纪50年代Lee的二叉决策程序和20世纪70年代Aker’s的二叉决策图（binary decision diagram，BDD）概念。20世纪80年代Bryant对BDD附加了变量序和简化约束，使之成为布尔表达式表述的一种规范型，即OBDD。OB—DD不同于BDD之处在于，OBDD中任一从根节点到叶节点的路径上变量出现的顺序保持一致。这一变量序的限制，使得OBDD成为表述布尔函数的规范式。Bryant关于OB—DD构造和操作的图形算法，极大地推进了OBDD的广泛深入研究。为了满足能够表述非0—1数值函数的应用需求，建立了多端二叉决策图（multi—terminal binary decision dia—gram，MTBDD）、代数决策图（algebraic decision diagr。am，ADD）、边值二叉决策图（edge—valued binary decision diagram，EVBD[））、二叉矩量图（binary moment diagram，BMD）等。除BMD之外，OBDD及上述这些扩展形式都是依据布尔函数的香农（Shannon）分解而构造的。Kebsehull等基于正Davio分解提出了有序函数决策图（ordered functionaldecision diagram，OFDD）；Drechsler等将OBDD和正Davio分解及负Davio分解复合，建立了有序Kronecker函数决策图（ordered Kronecker functional decision diagram，0KFDD）。在OFDD的基础上，Bryant和Chen提出了基于正Davio分解规则的二叉矩量图。此外，Minato通过采取不同的简化策略给出了适合于组合问题有效处理的零压缩二叉决策图（zero—suppressed binarly decision diagram，ZBDD）。OBDD中的变量顺序的选择也是研究人员关注的重要问题，研究人员已开展了动态变量序、最优变量序、启发式变量序、无变量序限制的自由BDD等的研究。

内容概要

有序二叉决策图是布尔函数的一种规范表达形式、一种新型数据结构。基于()BDD可以完成布尔函数的有效表述和操作运算，OBDD在VKSI逻辑综合和验证方面的成功应用引起了学术界和工业应用界的极大关注。本书对()BDD相关技术问题、()BDD扩展形式、()BDD应用等方面进行了介绍和讨沦，主要内容包括布尔表达式及其描述、有序二叉决策网、零压缩二叉决策图、代数决策图、边值二叉决策图、二叉矩量图、时问变量决策图、应用专题等。    本书可供高零院校计算机、电子工程、自动化等专业的高年级本科生、研究生以及相关领域的科研和工程技术人员参考。

书籍目录

前言第1章 布尔表达式及其描述  1.1 布尔函数    1.1.1 布尔代数    1.1.2 布尔表达式    1.1.3 布尔函数    1.1.4 布尔函数的范式    1.2 命题公式    1.2.1 命题与联结词    1.2.2 合式公式    1.2.3 命题公式的范式    1.2.4 命题公式与布尔函数  1.3 逻辑电路    1.3.1 基本逻辑门    1.3.2 逻辑电路的布尔函数  1.4 布尔表达式的其他描述形式    1.4.1 真值表    1.4.2 决策树    1.4.3 二叉决策图  参考文献第2章 有序二叉决策图  2.1 OBDD及其规范型    2.1.1 OBDD的定义    2.1.2 OBDD的性质  2.2 OBDD的简化算法    2.2.1 OBDD的简化    2.2.2 简化算法  2.3 OBDD的构造及操作    2.3.1 ()BDD的构造    2.3.2 OBDD的操作    2.3.3 补边OBDD  2.4 OBDD的变量序    2.4.1 OBDD的最小化    2.4.2 OBDD的重排序    2.4.3 OBDD的变量序算法  参考文献第3章 零压缩二叉决策图  3.1 ZBDD及其性质    3.1.1 组合集合及其表示    3.1.2 ZBDD的定义    3.1.3 ZBDD的性质  3.2 ZBDD的构造及基本操作    3.2.1 ZBDD的操作    3.2.2 ZBDD的构造    3.2.3 补边ZBDD  3.3 一元Cube集合代数    3.3.1 基本概念    3.3.2 基本运算    3.3.3 算法实现    3.3.4 皇后问题的求解  3.4 二元Cube集合代数    3.4.1 二元Cube集的表示    3.4.2 基本操作及算法    3.4.3 数字电路设计  3.5 多项式的隐式表示    3.5.1 变量次数的表示    3.5.2 多项式系数的表示    3.5.3 算术操作的算法实现  参考文献第4章 代数决策图  4.1 ADD及其性质    4.1.1 ADD的定义      4.1.2 ADD的矩阵表示  4.2 ADD基本操作    4.2.1 布尔操作    4.2.2 算术操作    4.2.3 提取操作  4.3 矩阵乘法计算    4.3.1 准环和半环    4.3.2 半环上的矩阵乘算法    4.3.3 准环上的矩阵乘算法  参考文献第5章 边值二叉决策图第6章 二叉矩量图第7章 时间变量决策图第8章 应用专题

用户评论 (总计1条)

•   写的很不错，建议学OBDD的读者看一看！