叉决策图.ppt

* * * * * * * * * * * * * * * 6 Inverters and InterConnections 引入Inverter—减少结点数量 6.1 概述 6.2 inverter的引入 默认左0,右1 减少结点个数 6 Inverters and InterConnections Example：Full adder Ci-1+Ai+Bi=Si---------Ci 6.1 概述 6.2 inverter的引入 6 Inverters and InterConnections 6.1 概述 6.2 inverter的引入 6.3 BDD的互联 D1与D2连接： (1)把D1中的所有的结点用D2中的gi代替 (2)连接相同的gi (3)替换输出节点名称 6 Inverters and InterConnections 6.1 概述 6.2 inverter的引入 6.3 BDD的互联 6 Inverters and InterConnections Example：4-bit adder 输入:A3-A2-A1-A0 and B3-B2-B1-B0,进位标识：CIN 输出：二进制和，S4-S3-S2-S1-S0（S4相当于Cout） 6.1 概述 6.2 inverter的引入 6.3 BDD的互联 6 Inverters and InterConnections Example：4-bit adder 利用四个前面讲到的Full adder互联 6.1 概述 6.2 inverter的引入 6.3 BDD的互联 6 Inverters and InterConnections Carry look-ahead--先行进位 G（CIN=0），P（CIN=1） 6.1 概述 6.2 inverter的引入 6.3 BDD的互联 6.4 4-bit carry look-ahead adder 6 Inverters and InterConnections 6.1 概述 6.2 inverter的引入 6.3 BDD的互联 6.4 4-bit carry look-ahead adder 相关内容 1 Introduction 2 Defining Diagram 3 Analyzing Diagram 4 Test Generation 5 Implementing Diagram 6 Inverters and InterConnections 7 Conclusion 7 Conclusion Introduction to Binary Decision Diagram. How to define BDD. Application to digital function. Note:breadth ,not depth. * * * * * * * * * * * * * * * * * * 计算入度（带权）： 初始化：最上层节点的两条分支初始化为1，以后各节点的分支均为次结点带权入度之和，最后把所有出口处相关的权值相加。 * * * * Binary Decision Diagrams 王帼钕 相关内容 1 Introduction 2 Defining Diagram 3 Analyzing Diagram 4 Test Generation 5 Implementing Diagram 6 Inverters and InterConnections 7 Conclusion 1 Introduction F = AC + BC 数字电路 表现形式：逻辑表达式，真值表，卡诺图 逻辑表达式 卡诺图 真值表 1 Introduction Existing Problem 真值表，卡诺图等普通的表现形式随着变量个数增加呈指数级增长。 数字电路越来越复杂，特别是到系统级后，用真值表，卡诺图等来设计数字电路变得相当困难。 迫切需要一种简单的数字电路表现形式。 相关内容 1 Introduction 2 Defining Diagram 3 Analyzing Diagram 4 Test Generation 5 Implementing Diagram 6 Inverters and InterConnections 7 Conclusion 2 Defining Diagram 2.1 what is BDD 2.2 Derive an BDD from truth table 2.3 Derive an BDD from Shannon expansion formula 2.4 BDD store i