组合逻辑电路课教案.ppt

IE7 Released,,Computer Organization and Design Lecture 15 – Representations of Combinatorial Logic Circuits,,This week, after more than 3 years since the last major update, Microsoft finally releases the next generation of their Internet Explorer web browser,Review,State elements are used to: Build memories Control the flow of information between other state elements and combinational logic D-flip-flops used to build registers Clocks tell us when D-flip-flops change Setup and Hold times important We pipeline long-delay CL for faster clock Finite State Machines extremely useful Represent states and transitions,组合逻辑,FSMs有状态和变化 如何从一个状态变化到另一个状态? 答案: 组合逻辑,Truth Tables : Unique Define CL Function,0,What do we need to know about CL?,如何设计: 给定定义 分解为合适尺寸的块来实现 如何分析: 延时量为多少 需要多少晶体管 耗费多少能量 如何实现: 组合逻辑块用逻辑门电路实现,TT Example #1: 1 iff one (not both) a,b=1,TT Example #2: 2-bit adder,How Many Rows?,TT Example #3: 32-bit unsigned adder,How Many Rows?,TT Example #4: 3-input majority circuit,Logic Gates (1/2),And vs. Or review – Dan’s mnemonic,AND Gate,Definition,AND,,Logic Gates (2/2),2-输入门扩展为 n-输入,N-输入异或（XOR） 是唯一一个不显然的 XOR为1，当且仅当输入端的 1的个数为奇数 ,Truth Table  Gates (e.g., majority circ.),,Truth Table  Gates (e.g., FSM circ.),,or equivalently…,Boolean Algebra,George Boole, 19世纪数学家 开发了涉及逻辑的代数系统 后被称为 “Boolean代数” 基本函数: AND, OR and NOT 布尔代数：存在由AND, OR和NOT构成的门电路与布尔代数中的方程间的一一对应 + 意即 OR, • 意即 AND, x 意即 NOT,Boolean Algebra (e.g., for majority fun.),y = a • b + a • c + b • c y = ab + ac + bc,Boolean Algebra (e.g., for FSM),,or equivalently…,布尔代数: 电路及代数简化,布尔代数也可用于 验证电路 电路 X = 电路 Y? 用布尔代数证明!,Laws of Boolean Algebra,Boolean Algebraic Simplification Example,The Three Representations of CL,组合逻辑表示转换,布尔表达式 转真值表: 尝试所有右边变量的值，列出表 门电路图: 把布尔表达式的AND /OR/NOT操作用 AND-gate/OR-gate/Inverter替换 门电路图 转真值表: 对所有输入的组合，算出电路的输出 转布尔表达式: 上面过程的逆 真值表转布尔表达式?,正则形式 (1/2),,乘积的和 (ORs of ANDs),,Canonical forms (2/2),,Peer Instruction,(a+b)• (a+b) = b N-input gates can be thought of cascaded 2-input gates. I.e., (a ∆ bc ∆ d ∆ e) = a ∆ (bc ∆ (d ∆ e)) where ∆ is one of AND, OR, XOR, NAND You can use NOR(s) with clever wiring to simulate AND, OR, & NOT,ABC 1: FFF 2: FFT 3: FTF 4: FTT 5: TFF 6: TFT 7: TTF 8: TTT,,(a+b)•(a+b) = aa+ab+ba+bb = 0+b(a+a)+b = b+b = b TRUE (next slide) You can use NOR(s) with clever wiring to simulate AND, OR, & NOT. NOR(a,a)= a+a = aa = a Using this NOT, can we make a NOR an OR? An And? TRUE,Peer Instruction Answer,(a+b)• (a+b) = b N-input gates can be thought of cascaded 2-input gates. I.e., (a ∆ bc ∆ d ∆ e) = a ∆ (bc ∆ (d ∆ e)) where ∆ is one of AND, OR, XOR, NAND You can use NOR(s) with clever wiring to simulate AND, OR, & NOT,ABC 1: FFF 2: FFT 3: FTF 4: FTT 5: TFF 6: TFT 7: TTF 8: TTT,,,,,,,,,N-input gates can be thought of cascaded 2-input gates. I.e., (a ∆ bc ∆ d ∆ e) = a ∆ (bc ∆ (d ∆ e)) where ∆ is one of AND, OR, XOR, NAND…FALSE Let’s confirm!,CORRECT 3-input XYZ|AND|OR|XOR|NAND 000| 0 |0 | 0 | 1 001| 0 |1 | 1 | 1 010| 0 |1 | 1 | 1 011| 0 |1 | 0 | 1 100| 0 |1 | 1 | 1 101| 0 |1 | 0 | 1 110| 0 |1 | 0 | 1 111| 1 |1 | 1 | 0,CORRECT 2-input YZ|AND|OR|XOR|NAND 00| 0 |0 | 0 | 1 01| 0 |1 | 1 | 1 10| 0 |1 | 1 | 1 11| 1 |1 | 0 | 0,0 0 0 1 0 1 1 1 0 1 1 1 0 1 0 1 0 1 1 0 0 1 0 0 0 1 0 0 1 1 1 1,,,,,Peer Instruction Answer (B),“And In conclusion…”,Pipeline big-delay CL for faster clock Finite State Machines extremely useful You’ll see them again in 150, 152 & 164 Use this table and techniques we learned to transform from 1 to another,。