数字逻辑设计及应用教学英文课件：Lec06-Chap 4

1、1Digital Logic Design and Application Lecture #6UESTC, Spring 2011Chapter 4 Combinational Logic Design PrinciplesBasic Logic Algebra学习要求掌握:逻辑代数的公理、定理，正负逻辑的概念与对偶关系、反演关系、香农展开定理，以及在逻辑代数化简时的作用；掌握:逻辑函数的表达形式：积之和与和之积标准型、真值表、卡诺图、最小逻辑表达式之间的关系；掌握:组合电路的分析：穷举法和代数法；卡诺图化简方法；掌握:组合电路的综合过程：将功能叙述表达为组合逻辑函数的表达形式、使用与非门、

2、或非门表达的逻辑函数表达式、逻辑函数的最简表达形式及综合设计的其他问题：无关项(dont-care terms)的处理。理解：逻辑函数表达式的基本化简方法函数化简方法；多输出(multiple-output)逻辑化简的方法和定时冒险（timing hazards）问题。了解：组合逻辑电路和时序逻辑电路的基本概念；逻辑代数化简时的几个概念：蕴含项（implicant）、主蕴含项（prime implicant）、奇异“ 1 ”单元（distinguished 1-cell )、质主蕴含项(essential prime implicant);五变量及以上逻辑函数卡诺图化简方法；了解：开集（on-

3、set）、闭集(off-set)的概念；23Basic ConceptsTwo types of logic circuits:combinational logic circuitsequential logic circuitOutputs depend only on its current inputs.Outputs depends not only on the current inputs but also on the past sequence of inputs.A combinational circuit dont contain feedback loops whic

4、h generally create sequential circuit behavior.4.1 Switching Algebra454.1 Switching Algebra4.1.1 Axioms (公理)A1: X = 0, if X 1X = 1, if X 0A2: 0 = 11 = 0A3: 00 = 01+1 = 1A4: 11 = 10+0 = 0A5: 01 = 10 = 01+0 = 0+1 = 1a.k.a. “Boolean algebra”数字抽象基本逻辑门的输出4.1 Switching Algebra (撇号)为逻辑非操作符;表达式Y=x， 表示信号Y与x之

5、间的逻辑关系;逻辑加操作符“+”，有些地方用“ ”“ or”表示;逻辑乘操作符“”，有些地方用“& ”“ and”表示;优先级:逻辑非逻辑乘逻辑加。6F = 0 + 1 ( 0 + 1 0 ) = 0 + 1 1= 074.1.2 Single-Variable TheoremsIdentities(自等律): X+0=XX1=XNull Elements(0-1律): X+1=1X0=0Involution(还原律): ( X ) = XIdempotency(同一律): X+X=XXX=XComplements(互补律): X+X=1XX=0The relationship between

6、 variable and constantThe relationship between variable and itself单变量定理 T1T5所有定理都可以通过完全归纳法来证明!84.1.3 Two- and Three-Variable TheoremsSimilar relationships with general algebraCommutativity (交换律) AB = BAA+B = B+AAssociativity (结合律) A(BC) = (AB)CA+(B+C) = (A+B)+CDistributivity (分配律) AB+BC=A(B+C) A+BC

7、= (A+B)(A+C)These theorems can be proved by truth table.二、三变量定理 T6T89Notices不存在变量的指数 AAA A3没有定义除法 if AB=BC A=C ? 没有定义减法 if A+B=A+C B=C ?A=1, B=0, C=0AB=AC=0, ACA=1, B=0, C=1 A+B=A+C, BC 错！错！104.1.3 Two- and Three-Variable TheoremsCovering (吸收律)X + XY = X X(X+Y) = XCombining (组合律)XY + XY = X (X+Y)(X+

8、Y) = XConsensus (添加律/一致性定理)XY + XZ + YZ = XY + XZ(X+Y)(X+Z)(Y+Z) = (X+Y)(X+Z)Some Special Relationships 对偶 二、三变量定理 T9T1111(X+Y) + (X+Y) = 1A + A = 1XY + XY = X(A+B)(A(B+C) + (A+B)(A(B+C) = (A+B)代入定理： 在含有变量 X 的逻辑等式中，如果将式中所有出现 X 的地方都用另一个表达式 F 来代替，则等式仍然成立。124.1.4 n-Variable Theorems n变量定理 T12T15General

9、ized idempotency theorem 广义同一律X + X + + X = X X X X = XShannons expansion theorem 香农展开定理F(X1, X2, , Xn)= X1 F(1,X2,Xn) + X1 F(0,X2,Xn)= X1 + F(0,X2,Xn) X1 + F(1,X2,Xn) N变量定理能够使用有限归纳法来证明!How to prove?13To prove: AD + AC + CD + ABCD = AD + AC= A ( 1D + 1C + CD + 1BCD ) + A ( 0D + 0C + CD + 0BCD )= A (

10、 D + CD + BCD ) + A ( C + CD )= AD+ AC144.1.4 n-Variable TheoremsDeMorgans Theorem 摩根定理 T13 Complement Theorem 反演定理 (A B) = A + B(A + B) = A Bn变量定理 T12T15Xi可以是任意表达式15DeMorgan SymbolsQuiz: 如何用NAND门实现NOR功能?逻辑功能的电路实现的多样性164.1.4 n-Variable Theorems n变量定理 T12T15Complement of a logic expression: , 0 1, Co

11、mplementing all VariablesKeep the previous priorityNotice the out of parenthesesExample1: Write the complement function for each of the following logic functions.F1 = A(B+C)+CDF2 = (AB)+CDEExample2: Prove that (AB + AC) = AB + ACF1 = (A+BC)(C+D)F2 = AB(C+D+E)17(A+B)(A+C) 反演定理AA +AC + AB + BC 结合律AC +

12、 AB 一致律 AC + AB + BC 互补率Example2: Prove (AB + AC) = AB + AC4.1.4 n-Variable Theorems n变量定理 T12T154.1.5 Duality (对偶性)Duality Rule , 0 1 Keep the previous priority 对任意逻辑表达式，将其中的“或”“与”操作对换，“0”“1”对换，并保持原来的逻辑优先级不变，得到新的等式仍然成立。新的等式FD称为F的对偶式。18 FD(X1 , X2 , , Xn , + , , ) = F(X1 , X2 , , Xn , , + , ) 回顾公理、定

13、理对偶的性质0D=1，1D=0；变量XD=X；对函数F，G有：（F+G）D= FDGD；（F G）D= FD+ GD（F D ）D=F若F=G，则FD =GD 19Example: Write the Duality function for each of the following Logic functions. F1 = A+B(C+D)F2 = ( A(B+C) + (C+D) )F1D = A(B+CD)F2D = ( (A+BC) (CD) )4.1.5 Duality (对偶性)Counterexample: 优先级的处理 X+XY = XXX+Y = X X+Y = XX(X

14、+Y) = X204.1.5 Duality (对偶性)Principle of Duality Any logic equation remains true if the duals of it is true. 证明公式：A+BC = (A+B)(A+C)A(B+C)AB+AC214.1.5 Duality (对偶性)Write the duality and complement function for each of the following logic functions. F1 = A(B+C) + CD F2 = ( A(B+C) + (C+D) )224.1.5 Dual

15、ity (对偶性)Duality: FD(X1 , X2 , , Xn , + , , ) = F(X1 , X2 , , Xn , , + , ) The relation between the positive-logic convention and the negative-logic convention is duality.正逻辑与负逻辑之间是对偶的关系G1ABFA B FL L LL H LH L LH H Helectrical functionA B F0 0 00 1 01 0 01 1 1positive logicA B F1 1 11 0 10 1 10 0 0n

16、egative logicF = ABF = A+B对偶4.1.5 Duality (对偶性)由于正负逻辑之间的对偶关系使得：逻辑电路（circuit）有不唯一的描述（解释）形式逻辑功能（function）有不唯一的实现形式23唯一的电气特性 (H and L level)唯一的truth Table4.1.5 Duality (对偶性)采用不同的逻辑体制描述同一个数字电路（circuit）24Example：某个数字电路电气特性如下表，用正逻辑描述（解释），其逻辑表达式和逻辑电路图如下所示。请给出用负逻辑描述的表达式和电路图。Positive logicF=AB+CABFCNegative

17、logicF=(A+B)CABFC4.1.5 Duality (对偶性)25A B F0 0 00 1 01 0 01 1 1Truth TableA B FL L LL H LH L LH H HPositive logicelectrical functionF=A BABF采用不同的逻辑体制来实现同一种逻辑功能Use 3 NMOS to build the electric circuitExample：某数字电路完成的逻辑功能如真值表所示，若分别用正/负逻辑体制实现，给出其逻辑电路图和电路图。4.1.5 Duality (对偶性)采用不同的逻辑体制来实现同一种逻辑功能26Example

18、：某逻辑电路需要完成的逻辑功能如真值表所示，分别用正/负逻辑体制实现，给出其逻辑电路图和电路图。A B F0 0 00 1 01 0 01 1 1Truth TableA B FH H HH L HL H HL L LNegative logicelectrical functionF=A + BABFUse 3 PMOS to build the electric circuitF=A B4.1.5 Duality (对偶)and Complement获得任意函数的反函数的方法通过对的对偶函数求非，且对偶函数自变量为的反变量；27Complement: F(X1 , X2 , , Xn) =

19、 FD(X1 , X2, , Xn ) F(X1 , X2 , , Xn) = FD(X1 , X2, , Xn ) A B F0 0 00 1 01 0 01 1 1positive logicF = ABF = ABF = AB =F （ A，B） =（F （ A，B）ABFC4.1.5 Duality (对偶性) and Complement由于对偶关系的存在，一旦得到积之和的表达式综合出二级与-或电路，就可以很方便的得到和之积表达式并综合出二级或-与逻辑电路。28Positive logicF=AB+CABFCPositive logic=（F（ A，B）And-OR circuitO

20、R- And circuit4.1.5 Duality (对偶性) and Complement29304.1.6 Logic Function and its RepresentationsSome definitionsLiteral(文字): a variable or its complement such as X, X, CS_LExpression(表达式): literals combined by AND, OR, parentheses, complementation( FREDZ + CS_LABC + Q5 )RESET Product term(乘积项): PQRS

21、um term(求和项): X+Y+ZSum-of-products expression(积之和表达式): A + BC + ABC Product-of-sums expression (和之积表达式): (B+C) (A+B+C)Equation(方程/函数): Variable = expressionP = ( FREDZ + CS_LABC + Q5)RESET 4.1.6 Logic Function and its RepresentationsSome definitions标准项（normal term）：一个乘积或求和项，每个变量只出现一次；非标准项可以化为标准项。n变量

22、最小项（Miniterm）：具有n个变量的标准乘积项；n变量最大项（Maxterm）：具有n个变量的标准求和项；31F (A,B ) = AB+AF (A,B ) = AB+AB+AB3变量：ABC，A BC，任何非标准项都可以化为最大或最小项。3变量：A+B+C，A+ B+C，324.1.6 Logic Function and its Representations举重裁判电路Y = F (A,B,C ) = A(B+C)ABYC&1ABCYLogic Circuit开关ABC:1-闭合指示灯Y:1-亮000001110 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1

23、1 1 0 1 1 1 ABCYTruth TableLogic Equation 4.1.6 Logic Function and its Representations逻辑函数的描述方式真值表(Truth table)逻辑代数表达式(Logic Function/ Equation)逻辑电路图(Logic circuit)33分析设计34Y = A + BC + ABC0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1ABCBCABCY110000000111111000000100Sum-of-Products expression“积之和”表达式“与-或”

24、式二级电路实现方式literalproduct term乘积项11114.1.6 Logic Function and its RepresentationsLogic Expression Truth Table逻辑函数真值表4.1.6 Logic Function and its RepresentationsLogic Expression Truth Table逻辑函数真值表35Y = (B+C) (A+B+C)0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1ABCB+CA+B+CY001111111111111111110000sum term求和项P

25、roduct-of-Sums expression“和之积”表达式“或-与”式二级电路实现方式4.1.6 Standard Representations of Logic FunctionsTruth table logic function真值表逻辑函数36ABC1 variable0 (variable)product terms: 0 0 0 00 0 1 00 1 0 00 1 1 11 0 0 01 0 1 01 1 0 01 1 1 0ABCFTruth TableA product term that is 1 in exactly one row of the truth t

26、able真值表中使某行为1的乘积项minterm*F = ABC37Canonical Sum（标准和）: a sum of mintermsOn-Set开集0 0 0 00 0 1 00 1 0 00 1 1 11 0 0 01 0 1 11 1 0 11 1 1 0ABCF00010000F1= + +00000100F200000010F3F = ABC + ABC + ABC= A,B,C(3,5,6)MintermListm0m1m2m3m4m5m6m74.1.6 Standard Representations of Logic Functions实际上是挑选取1的Miniterm

27、集合来描述逻辑函数384.1.6 Standard Representations of Logic FunctionsMinterm (最小项) An n-variable minterm is a normal product term with n literals.There are 2n such product terms.The sum of all minterms is 1.The product of any two different product-terms is 0.ABCABCABCABCABCABCABCABC0 0 00 0 10 1 00 1 11 0 01

28、 0 11 1 01 1 1ABCMinitermTruth table logic function真值表逻辑函数Truth Table394.1.6 Standard Representations of Logic Functions11101111G(ABC) = A+B+CF = ABCG = A+B+C0 0 0 00 0 1 00 1 0 00 1 1 11 0 0 01 0 1 01 1 0 01 1 1 0ABCFTruth TableA sum term that is 0 in exactly one row of the truth table真值表中使某行为0的求和项

29、maxterm *0 variable1 (variable)sum terms: 40Canonical Product （标准积） : a product of maxterms0 0 0 00 0 1 10 1 0 10 1 1 01 0 0 11 0 1 11 1 0 11 1 1 0ABCF01111111F1= 11101111F211111110F3F = (A+B+C)(A+B+C)(A+B+C)= A,B,C(0,3,7)Off-Set闭集MaxtermListM0M1M2M3M4M5M6M74.1.6 Standard Representations of Logic Fu

30、nctions实际上是挑选取0的Maxterm集合来描述逻辑函数414.1.6 Standard Representations of Logic Functions Maxterms (最大项) An n-variable maxterm is a normal sum term with n literals. There are 2n such sum terms.The product of all maxterms is 0.The sum of any two different sum-terms is 1.A+B+CA+B+CA+B+CA+B+CA+B+CA+B+CA+B+CA

31、+B+C0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1ABCMaxtermTruth table logic function真值表逻辑函数42ABCABCABCABCABCABCABCABCmintermm0m1m2m3m4m5m6m70 0 0 00 0 1 10 1 0 20 1 1 31 0 0 41 0 1 51 1 0 61 1 1 7ABCrowA+B+CA+B+CA+B+CA+B+CA+B+CA+B+CA+B+CA+B+CM0M1M2M3M4M5M6M7maxtermProduct term:0 (variable)1 variableSum

32、term:1 (variable)0 variable Mi = mi ； mi = Mi ；Why does every logic function can be written as a canonical sum or a canonical product?为什么任何逻辑函数都可以表示为标准积或者标准和的形式？任何非标准项都可以化为最大或最小项，因此可以用最大项之积或最小项之和来表示任意逻辑函数。逻辑函数的互斥二值取值；取1的Miniterm之和描述了逻辑函数取1的所有情况；取0的Maxterm之积描述了逻辑函数取0的情况；采取哪种描述形式视简便而定。4.1.6 Standard Representations of Logic FunctionsAny logic function can be written as a canonical sum.44Example: Write the canonical sum for the following function: F(A,B,C) = AB +ACUsing theorem: X + X = 1F(A,B,C) = AB + AC = AB(C+C) + AC(B+B) = ABC + ABC + ABC + ABC1 1 11 1 00 1 10 0 1= A,B,C