布尔函数表示的二元判定图方法的研究与实现.pdf

12l论 文 布尔函数表示的二元判定图方法的研究与实现 陈 翎 潘中良 (华南师范大学物理与电信工程学院) 摘要：布尔函数是数字系统与计算机科学等领域的基础，有广泛的应用。本文对布尔函数的二元判定图表 示方法进行了详细讨论，说明了基于布尔函数的真值表和香农展开式来构造二元判定图的方法、二元判定图的简 化、以及它在数字 电路设计与测试中的应用。 关键词：布尔函数：表示方法：二元判定图；电路设计：电路测试 1引言 作。如，二元判定图有一个根节点的有向无环图，这 用G=-(V，E)表示，V为节点集，E为边集。节点集V 布尔函数是数字电路与系统、计算机科学、人工 有两类节点：非终节点和终节点。非终节点有两个属 智能等领域的基础，这其中的许多问题都可表示为一 性值：节点的编序和两个子节点。终节点只有一个属 系列布尔函数的运算。如，数字电路的逻辑功能常用 性。边的集合E由从父节点指向子节点的连接组成。 一 或多个布尔函数表示；一复杂数字系统对应的布尔 如对逻辑布尔函数f=X． -t-X．X，-t-X2 ，它的真 函数可由其子系统实现的布尔函数进行组合运算而 值表如表 1，它的BDD表示如图1。BDD图中的边 成。人们已研制了一些表示布尔函数方法，如真值表、 为从父节点指向子节点的有向边，一般不画出方向。 卡诺图、积之和的范式等，但不能满足现今复杂数字 表 1布尔函数f的真值表 系统的需要，存在如下缺点：对每个具有 n个变量的 0 0 布尔函数都有2“个或更多的表示式，在用计算机进行 0 0 0 l 处理时，需2“个空间单元 (存储单元)表示；有时对 0 1 这种表示做简单操作 (如取反)也会导致指数复杂性 1 0 l 0 的出现。这也给等价I生验证等常用操作带来困难。 1 1 1 1 图1由真值表获得的BDD 为此，对布尔函数，需研究高效简洁的表示和运 算方法。二元判定图(BDD，BinaryDecisionDiagram) 图 1中，BDD 的非终节点用一个圆圈表示，终 是一种被研究的有效方法，它将布尔函数的功能用图 节点用矩形框表示。节点的属性值标在圆圈或矩形框 的形式表示，图中从根节点到叶节点的路径对应了布 内。图中的边用虚线和实线表示，虚线称为0边，实 尔函数值为 1的一个输入矢量I2刊。二元判定图与布 线也称为 1边。图l中，共有 8个终节点，其属性值 尔函数的其他表示方法相比，具有：(1)大多实用中的 分别为0和 1。共有 7个非终节点，其中有一个根节 布尔函数都可用具相当少节点