数字设计课件第四章组合逻辑设计原理.ppt

2023/9/11,数字逻辑设计及应用,1,Chapter 4 Combinational Logic Design Principles,本章重点1、开关代数：公理、定理、定义2、组合电路的分析：组合电路的结构、逻辑表达式、真值表、时序图等。3、组合电路的综合（设计）：逻辑抽象定义电路的功能，写出逻辑表达式，得到实际的电路。,数字逻辑设计及应用,2,Combinational logic circuit,The outputs depend only on its current inputs.each output can be specified by truth table or Boolean expression.,数字逻辑设计及应用,3,4.1 Switching Algebra,Deals with boolean values:0,1 Signal values denoted by variables(X,Y,FRED,etc.)Boolean operators：+,1、Axioms,数字逻辑设计及应用,4,2.Single Variable Theorems,Proofs by perfect induction将变量的所有取值代入定理表达式，若等号两边始终相等，则得证。,自等律,0-1律,同一律,还原律,互补律,(T1)X+0=X(T1)X1=X,(T2)X+1=1(T2)X0=0,(T3)X+X=X(T3)XX=X,(T4)(X)=X,(T5)X+X=1(T5)XX=0,数字逻辑设计及应用,5,3.two-and three-variable theorems,Parenthesization or order of terms in a logical sum or logical product is irrelevant.T8logical multiplication distributes over logical additionT8logical addition distributes over logical multiplication,(T6)X+Y=Y+X(T6)XY=YX（交换律）,(T7)(X+Y)+Z=X+(Y+Z)(T7)(XY)Z=X(YZ)（结合律）,(T8)XY+XZ=X(Y+Z)(T8)(X+Y)(X+Z)=X+YZ（分配律）,数字逻辑设计及应用,6,T9、T9、T10、T10:be used to minimize logic functions.YZ and(Y+Z)term are the redundant terms in the expression.Supplement：A+AB=A+B（消因律）A+AB=A+B,(T9)X+XY=X(T9)X(X+Y)=X（吸收律）,(T10)XY+XY=X(T10)(X+Y)(X+Y)=X（组合律）,(T11)XY+XZ+YZ=XY+XZ(T11)(X+Y)(X+Z)(Y+Z)=(X+Y)(X+Z)（一致律）,数字逻辑设计及应用,7,4.n-variable theorems,T13-equivalent transform between“AND-NOT”and“NOT-OR”.T13-equivalent transform between“OR-NOT”and“NOT-AND”.Exp.：G=XY+VWZ=？,(T12)X+X+X=X(T12)XXX=X(广义同一律),(T13)(X1X2Xn)=X1+X2+Xn(T13)(X1+X2+Xn)=X1X2Xn（DeMorgan theorems）,DeMorgan theorems,数字逻辑设计及应用,8,T14Generalized DeMorgans theorem，也称为“反演定理”,get the complement of a logic expression(inverse function)。keep the original operating order;complement all variables;swapping 0 and 1;swapping+and（注：如逻辑式中有带括号的表达式取反，反函数中保留非号不变。）例：F=（AB+C）E+G的反函数。,(T14)F(X1,X2,Xn,+,)=F(X1,X2,Xn,+),数字逻辑设计及应用,9,finite induction（1）proving the theorem is true for n=2;（2）then proving that if the theorem is true for n=i,then it is also true for n=i+1.,数字逻辑设计及应用,10,5.Duality,Any theorem or identity in switching algebra remains true if 0 and 1 are swapped and and+are swapped throughout.a logic expression：F(X1,X2,Xn,+,，)its duality：FD=F(X1,X2,Xn,+,)XYX+Y01Exp.：find the duality expression.F=(AB+AC)+1B,duality,duality,数字逻辑设计及应用,11,relation between duality and theorem 14：F(X1,X2,Xn,+,，)=FD(X1,X2,Xn,+，)正逻辑约定与负逻辑约定互为对偶关系。正逻辑“与”=负逻辑“或”正逻辑“或”=负逻辑“与”正逻辑“与非”=负逻辑“或非”正逻辑“或非”=负逻辑“与非”,数字逻辑设计及应用,12,6.Using switching algebra in minimizing logic function,Exp.：（1）F=AD+AD+AB+AC+BD+ABEF+BEF（2）F=A（B+C）（BC）（3）F=AB+AC+BC+CB+CD+BD+ADE(F+G),数字逻辑设计及应用,13,7.Standard representation of logic functions,truth table definitions（p.197）literal（也可称作元素、因子）product term XYZ，ABGG，Rsum-of-products(SOP)sum term C+D+H，X+X+Wproduct-of-sums(POS)normal term(标准项),数字逻辑设计及应用,14,n-variable minterm,normal product term with n literals3-variable X,Y,Z,one combination only let one minterm be 1,one n-variable minterm represent one n-variable combination.,数字逻辑设计及应用,15,n-variable maxterm,normal sum term with n literals,one maxterm,one combination only let one maxterm be 0,one n-variable maxterm represent one n-variable combination.,数字逻辑设计及应用,16,properties of minterma、所有输入组合取值中，只有一组取值能令特定的某个最小项的值为1。b、任意两个不同最小项之积为0，mimj=0 ijc、全部最小项之和为1，properties of maxterma、所有输入组合取值中，只有一组取值能令特定的某个最大项的值为0。b、任意两个不同最大项之和为1，Mi+Mj=1 ijc、全部最大项之积为0，编号相同的最小项和最大项互为反函数 mi=(Mi)，Mj=(mj),properties of minterm and maxterm,数字逻辑设计及应用,17,canonical sum,sum of minterms corresponding to input combination for which the function produces a 1 output.Exp.F=？=XYZ+XYZ+XYZ+XYZ+XYZ=(0,3,4,6,7),input,output,数字逻辑设计及应用,18,canonical product,product of maxterms corresponding to input combination for which the function produces a 0 output.F=(X+Y+Z)(X+Y+Z)(X+Y+Z)=X,Y,Z(1,2,5),数字逻辑设计及应用,19,若已知标准和，则集合中剩下的编号就可以构建标准积；反之亦然。例：XYZ（0、1、2、3）=XYZ（4、5、6、7）,Conversion between maxterm list and minterm list,n variable logic function,数字逻辑设计及应用,20,inverse function of a canonical logic expression：F=+mi+mj+ijIts inverse function:F=Mi Mj ij反之亦然。Representation of a logic function truth table canonical sum minterm list canonical product maxterm list,数字逻辑设计及应用,21,4.2 Combinational-Circuit Analysis,Analyzing steps：Make sure that it is combinational circuit.Find input and output variables,fill the truth table according to the circuit.Canonical sum or product.Minimizing the equation.Sometime,write the logic expression according to the circuit directly.timing diagram maybe needed.,数字逻辑设计及应用,22,Analyzing example,Input variable:,X,Y,Z,Output variable:,F,F=X,Y,Z(1,2,5,7)=XYZ+XYZ+XYZ+XYZ,ORF=X,Y,Z(0,3,4,6)=(X+Y+Z)(X+Y+Z)(X+Y+Z)(X+Y+Z),数字逻辑设计及应用,23,Minimizing the expressionF=X,Y,Z(1,2,5,7)=XYZ+XYZ+XYZ+XYZ=XZ+YZ+XYZORF=X,Y,Z(0,3,4,6)=(X+Y+Z)(X+Y+Z)(X+Y+Z)(X+Y+Z)=(Y+Z)(X+Z)(X+Y+Z)Write the logic expression according to the circuitF=(X+Y)Z)+XYZ,数字逻辑设计及应用,24,Basic structure of logic circuit,Two types two level“AND OR”；two level“OR AND”；two level“NAND NAND”；two level“NOR NOR”。,DeMorgan theorem,数字逻辑设计及应用,25,“AND-OR”and“NAND-NAND”,AND OR,NAND NAND,first-level,second-level,数字逻辑设计及应用,26,“OR-AND”and“NOR-NOR”,OR-AND,NOR-NOR,first-level,second-level,数字逻辑设计及应用,27,Timing diagram,数字逻辑设计及应用,28,课堂练习,分析如下电路，1）直接写出逻辑函数表达式并化简 2）列出真值表,数字逻辑设计及应用,29,4.3 Combinational-Circuit Synthesis,Synthesis steps：analyze the word description,make sure that it could be realized by combinational-circuit；Find all input and output variable；Use truth table to represent the input-output logic relation；Use karnaugh-map to minimize the logic expression；Give the circuit diagram,数字逻辑设计及应用,30,1、circuit descriptions and designs,Exp1：design a 4-bit prime-number detector.,4-bitPrime-number detector,4-bitbinary number,N3N2N1N0,Yes or No,Yes:F=1 No:F=0,F=N3,N2,N1,N0(1,2,3,5,7,11,13),数字逻辑设计及应用,31,Exp2：alarm circuit,alarm circuit,ALARM,SECURE=WINDOWDOORGARAGE,数字逻辑设计及应用,32,2、circuit manipulations,从真值表或后面将要讲述的方法所得到的组合电路均是“与或”、“或与”结构。从CMOS电路的实现上来说，带“非”的门的速度要快些，因而在具体实现时，往往需要将所得的电路作一些电路的等效变换，成为能用带“非”的门实现。,数字逻辑设计及应用,33,3、combinational-circuit minimization,Minimizing by switching algebraMinimizing by karnaugh mapMinimization methods：Minimizing the number of first-level gatesMinimizing the number of inputs on each first-level gatesMinimizing the number of inputs on the second-level gatesBasing on：T10、T10XY+XY=X；（X+Y）（X+Y）=X,数字逻辑设计及应用,34,4、Karnaugh Map,graphical representation of a logic functions truth table.stucturen-variable k-map has 2n cells.1-var k-map2-var k-map F（X，Y）,each cell has a number which correspond to a minterm number in a truth table.,数字逻辑设计及应用,35,3-var k-map F（X，Y，Z）,4-var k-map F（W,X,Y,Z）,XY is arranged in Gray code.,the contents is output value corresponding to each input combination,数字逻辑设计及应用,36,fill in the k-map for a given truth table,编号相同的真值表的每一行与卡诺图的方格是一一对应的。将真值表各行的输出值填入卡诺图的对应方格中。Exp：F=X,Y,Z（1,2,5,7）truth table k-map？,数字逻辑设计及应用,37,fill in the k-map for a logic expression,一般步骤：先将所求积之和式变换为标准和式，每个最小项代表了真值表中令输出为1的输入组合，按照最小项编号依次将对应的卡诺图方格中填1。Exp：F=ABCD+ABD+ACD+AB,represent it by k-map.solution：F=？=ABCD（？）,数字逻辑设计及应用,38,数字逻辑设计及应用,39,5、minimizing sums of products,base on：T10、T10 XY+XY=X(X+Y)(X+Y)=X combine two adjacent“1”cell into a product term and eliminate one literal.（1）adjacent input combinations of adjacent cell only differ in one variable，that is also called wrapround.,数字逻辑设计及应用,40,adjacent,adjacent,adjacent,adjacent,数字逻辑设计及应用,41,（2）methods of minimization,circle 2i adjacent“1”cells,it will be a new product term with(n-i)literals.the circle must be promised the biggest one,if enlarge the circle,then“0”cell may be included。the combined product term is called prime implicant，PI）。,数字逻辑设计及应用,42,derive prime implicant,in areas covered by the circle where a variable is 0,then it is complemented in the product term.a variable is 1,then it is uncomplemented in the product term.a variable is 0 as well as area where it is 1,then it isnt appear.,数字逻辑设计及应用,43,Exp,数字逻辑设计及应用,44,complete sum sum of all prime implicants.F=XYZ+WXZ+WYZ+WXneed to find the minimal sumfind the distinguished“1”cellmake sure the Essential Prime Implicant,EPI）minimal sum is the sum of EPI.,数字逻辑设计及应用,45,distinguished“1”cell,数字逻辑设计及应用,46,Exp1：,X,complete sum：F=YZ+XZ+XY,minimal sum：F=YZ+XZ,数字逻辑设计及应用,47,Exp2：derive the minimal sum by k-map.F=AC+AC+BC+BC,rules：按照表达式中出现的变量确定变量的个数，画好方格图；再按照每个积项确定方格图中的主蕴含项；确定主蕴含项时，由积项中出现的变量因子对应于图中的区域的交叉部分填入“1”即可。,数字逻辑设计及应用,48,Combinational circuit design example,Exp1：4-bit prime-number detector.F=N3N2N1N0（1，2，3，5，7，11，13）,minimal sum:F=N3N0+N2N1N0+N2N1N0+N3N2N1,数字逻辑设计及应用,49,Combinational circuit design example,Exp.2：design a 3-bit Gray code binary code decoder.Let Gray code:G2G1G0Binary code:B2B1B0,数字逻辑设计及应用,50,Combinational circuit design example,Exp3：design a 3-bit majority-rule circuit,that the output value is same as the most of input bits.,F,AB,C,C,A,B,数字逻辑设计及应用,51,Combinational circuit design example,Exp.4：a priority circuit can judge whether the number of input“1”bits is odd or not，try to design such a 4-bit odd-priority circuit.Exp.5：finish the following operation by using k-map.Known F1=BC+CD+BCD and F2=AD+CD+ABC，do FA=F1F2，FB=F1+F2。,数字逻辑设计及应用,52,（3）k-map more than 4-variable,5-variable，32 cells，let variables are V、W、X、Y、Z,F,VWX,YZ,000,001,011,010,110,111,101,100,00,01,11,10,Number of cell,Arrange In Gray code,数字逻辑设计及应用,53,Dividing into two part,Adjacent：each cell is adjacent to 5 cells.,V=0,数字逻辑设计及应用,54,例：写出下列逻辑函数的最小积之和，F=VWXYZ（7,8,9,10,11,12,23,24,26,28）,数字逻辑设计及应用,55,6、minimizing“product-of-sums”,Combining adjacent 2i“0”cell,get a new sum term with(n-i)literals.or derive the minimal sum F of the inverse function first；then complement the F,so the minimal product F could be derived.Exp.,00,01,11,10,F,W X,Y Z,00,01,11,W,Y,Z,X,10,F=WYZ+WYX+XZ,F=(W+Y+Z)(W+X+Y)(X+Z),数字逻辑设计及应用,56,7、“dont-care”input combinations,The output doesnt matter for certain input combination(maybe never occur).These are called dont care terms.Use symbol“d”、“”、“”to represent the output value.In minimization,dont care term could be used as“1”or“0”if necessary.,数字逻辑设计及应用,57,Exp.1,00,01,11,10,F,AB,CD,00,01,11,A,C,D,B,10,F=CD+ABD+ACD,数字逻辑设计及应用,58,Exp.2：a BCD prime-number detector.00001001:valid input BCD;10101111:invalid input,so output dont care。,BCD prime-number detector,BCD input,ResultYes:F=1No:F=0,F=N3N0+N2N1,数字逻辑设计及应用,59,Exp.3：minimizing the following expression to minimal sum and“NAND-NAND”representation.F=ABC+ABD+ACD+ABC AB+AC=0(约束项)约束无关项输入变量的取值组合受到约束，这些输入组合对应的输出也是任意的。,数字逻辑设计及应用,60,F,A B,C D,A,C,D,B,AC,AB,dont care term,the k-map,minimization,数字逻辑设计及应用,61,8、multiple-output minimization,using common terms enough.Exp：F=XYZ(3,6,7),G=XYZ(0,1,3),derive the circuit.：(1)synthesis individually,F=XY+YZ,G=XY+XZ,数字逻辑设计及应用,62,(2)Find the common terms,the synthesis againAlgorithm find the m-product function of all output.circle the m-products EPI.(the common part)find the EPI in the leaving“1”bining step、,get the final circuit.,数字逻辑设计及应用,63,F=XY+XYZ,G=XY+XYZ,重新划出质主蕴含项,数字逻辑设计及应用,64,列表法,数字逻辑设计及应用,65,4.5 Timing Hazards,A Static Hazard is defined when a single variable change at the input causes a momentary change in another variable the output.A Dynamic Hazard occurs when a change in the input causes multiple changes in the output.keywords：glitch、hazardreason:delayStatic Hazard:static-1,static-0 hazards,数字逻辑设计及应用,66,1、static hazards,static1 hazardsdefinition：a pair of input combination（a）differ in only one variable（b）both output 1 when the input change,a momentary 0 output maybe occurred.Exp：F=XZ+YZ，assume each gate has the same propagation delay.,数字逻辑设计及应用,67,when XYZ=111 110,X,Y,Z,Z,XZ,YZ,F,1,0,0,1,0 glitch,F=XZ+YZ,Static-1 hazards occur in SOP implementations.,数字逻辑设计及应用,68,static0 hazardsdefinition：a pair of input combination（a）differ in only one variable（b）both output 0 when the input change,a momentary 1 output maybe occurred.Exp：F=(X+Z)(Y+Z)when 000 001,数字逻辑设计及应用,69,Y+Z,X+Z,F=(X+Z)(Y+Z),X,0,Y,0,Z,Z,F,Static 0 hazards occur in Product-Of-Sums POS implementations.,数字逻辑设计及应用,70,2、finding static hazards,（1）逻辑代数法 当在一个函数表达式中，某变量的原变量和反变量的形式同时出现，且在保持该变量形式不变，其他变量取各种取值组合时，出现如下情况：表达式可化简为F=Xi+Xi形式，则该变量发生变化时，在电路中可能出现静态1冒险。表达式可化简为F=Xi Xi时，则该变量发生变化时，在电路中可能出现静态0冒险。,数字逻辑设计及应用,71,(2)using k-map,若主质蕴含项（EPI）之间存在相切的部分，则电路可能存在静态冒险。,数字逻辑设计及应用,72,(3)eliminate the static hazards,引入一致项（consensus，冗余项）：将相切的部分划入一个质蕴含项。,AC,得 F=AD+CD+AC,数字逻辑设计及应用,73,X,Y,Z,Z,XZ,YZ,F,1,0,0,1,XY,1,1,F=XZ+YZ+XY,数字逻辑设计及应用,74,第四章小结,开关代数 掌握开关代数的公理、定理。熟练应用于逻辑电路的分析和设计中。摩根定理、广义摩根定理（反演定理）、对偶定理。掌握逻辑函数的表示法真值表、标准和、标准积，及最小项、最大项的定义和性质。,数字逻辑设计及应用,75,组合逻辑电路的分析,能写出电路的逻辑表达式。能化简表达式（代数法、卡诺图法）能作电路结构的变换（“与或”转“与非与非”，“或与”转“或非或非”）能对原电路作是否存在“冒险”的判断能画出正确的时序图。,数字逻辑设计及应用,76,分析如下电路根据电路图写出逻辑表达式，判断原电路是否存在冒险。写出最小积之和式.若输入信号为以下顺序，无输入延迟时，请画出输出波形。,数字逻辑设计及应用,77,A,B,C,F,D,数字逻辑设计及应用,78,组合逻辑电路的综合 综合运用所学知识（过去所学的课程）分析、理解设计要求。将分析所得的输入变量、输出变量及二者间的逻辑关系列入真值表。化简，画电路 对多输出的处理一般以各自独立输出方式求解。,数字逻辑设计及应用,79,试设计一个电路，当输入的4位二进制数能被2整除时，输出Y=1，当输入数能被3整除时，输出Z=1，不满足上述条件时，输出为0。,数字逻辑设计及应用,80,定时冒险 掌握冒险可能出现的情况：“与或”结构可能出现静态1冒险；“或与”结构可能出现静态0冒险。,