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

2021/6/13,1,Chapter 4 Combinational Logic Design Principles,本章重点 1、开关代数：公理、定理、定义 2、组合电路的分析：组合电路的结构、逻辑表达式、真值表、时序图等。 3、组合电路的综合（设计）：逻辑抽象定义电路的功能，写出逻辑表达式，得到实际的电路。,Chapter 4,2,Combinational logic circuit,The outputs depend only on its current inputs. each output can be specified by truth table or Boolean expression.,Chapter 4,3,4.1 Switching Algebra,Deals with boolean values : 0, 1 Signal values denoted by variables(X, Y, FRED, etc.) Boolean operators ：+, , 1、Axioms,Chapter 4,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,Chapter 4,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 addition T8logical 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 （分配律）,Chapter 4,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) （一致律）,Chapter 4,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,Chapter 4,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, , +),Chapter 4,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.,Chapter 4,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+Y01 Exp.：find the duality expression . F=(AB+AC)+1B,duality,duality,Chapter 4,11,relation between duality and theorem 14： F(X1,X2,Xn, + , ，)= FD(X1,X2,Xn, , + ，) 正逻辑约定与负逻辑约定互为对偶关系。 正逻辑“与”=负逻辑“或” 正逻辑“或”=负逻辑“与” 正逻辑“与非”=负逻辑“或非” 正逻辑“或非”=负逻辑“与非”,Chapter 4,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),Chapter 4,13,7. Standard representation of logic functions,truth table definitions （p.197） literal（也可称作元素、因子） product term XYZ，ABGG，R sum-of-products (SOP) sum term C+D+H，X+X+W product-of-sums (POS) normal term (标准项),Chapter 4,14,n-variable minterm,normal product term with n literals 3-variable X, Y, Z,one combination only let one minterm be 1,one n-variable minterm represent one n-variable combination .,Chapter 4,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 .,Chapter 4,16,properties of minterm a、所有输入组合取值中，只有一组取值能令特定的某个最小项的值为1。 b、任意两个不同最小项之积为0，mimj=0 ij c、全部最小项之和为1， properties of maxterm a、所有输入组合取值中，只有一组取值能令特定的某个最大项的值为0。 b、任意两个不同最大项之和为1， Mi+Mj=1 ij c、全部最大项之积为0， 编号相同的最小项和最大项互为反函数 mi=(Mi)， Mj=(mj),properties of minterm and maxterm,Chapter 4,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,Chapter 4,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),Chapter 4,19,若已知标准和，则集合中剩下的编号就可以构建标准积；反之亦然。 例：XYZ（0、1、2、3）=XYZ（4、5、6、7）,Conversion between maxterm list and minterm list,n variable logic function,Chapter 4,20,inverse function of a canonical logic expression： F=+mi+mj+ ij Its inverse function: F= Mi Mj ij 反之亦然。 Representation of a logic function truth table canonical sum minterm list canonical product maxterm list,Chapter 4,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.,Chapter 4,22,Analyzing example,Input variable:,X, Y, Z,Output variable:,F,F=X,Y,Z(1,2,5,7)=XYZ+XYZ+XYZ+XYZ,OR F=X,Y,Z(0,3,4,6) =(X+Y+Z)(X+Y+Z)(X+Y+Z)(X+Y+Z),Chapter 4,23,Minimizing the expression F=X,Y,Z(1,2,5,7) =XYZ+XYZ+XYZ+XYZ =XZ+YZ+XYZ OR F=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 circuit F=(X+Y)Z)+XYZ,Chapter 4,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,Chapter 4,25,“AND-OR” and “NAND-NAND”,AND OR,NAND NAND,first-level,second-level,Chapter 4,26,“OR-AND” and “NOR-NOR”,OR-AND,NOR-NOR,first-level,second-level,Chapter 4,27,Timing diagram,Chapter 4,28,课堂练习,分析如下电路， 1）直接写出逻辑函数表达式并化简 2）列出真值表,Chapter 4,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,Chapter 4,30,1、circuit descriptions and designs,Exp1：design a 4-bit prime-number detector.,4-bit Prime-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),Chapter 4,31,Exp2：alarm circuit,alarm circuit,ALARM,SECURE=WINDOWDOORGARAGE,Chapter 4,32,2、circuit manipulations,从真值表或后面将要讲述的方法所得到的组合电路均是“与或”、“或与”结构。从CMOS电路的实现上来说，带“非”的门的速度要快些，因而在具体实现时，往往需要将所得的电路作一些电路的等效变换，成为能用带“非”的门实现。,Chapter 4,33,3、combinational-circuit minimization,Minimizing by switching algebra Minimizing by karnaugh map Minimization methods： Minimizing the number of first-level gates Minimizing the number of inputs on each first-level gates Minimizing the number of inputs on the second-level gates Basing on：T10、T10 XY+XY=X；（X+Y）（X+Y）=X,Chapter 4,34,4、Karnaugh Map,graphical representation of a logic functions truth table . stucture n-variable k-map has 2n cells. 1-var k-map 2-var k-map F（X，Y）,each cell has a number which correspond to a minterm number in a truth table.,Chapter 4,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,Chapter 4,36, fill in the k-map for a given truth table,编号相同的真值表的每一行与卡诺图的方格是一一对应的。将真值表各行的输出值填入卡诺图的对应方格中。 Exp：F=X,Y,Z（1,2,5,7） truth table k-map？,Chapter 4,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（？ ）,Chapter 4,38,Chapter 4,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.,Chapter 4,40,adjacent,adjacent,adjacent,adjacent,Chapter 4,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）。,Chapter 4,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 .,Chapter 4,43,Exp,Chapter 4,44,complete sum sum of all prime implicants. F= XYZ+ WXZ+ WYZ+ WX need to find the minimal sum find the distinguished “1” cell make sure the Essential Prime Implicant, EPI） minimal sum is the sum of EPI.,Chapter 4,45,distinguished “1” cell,Chapter 4,46,Exp1：,X,complete sum：F=YZ+XZ+XY,minimal sum：F=YZ+XZ,Chapter 4,47,Exp2：derive the minimal sum by k-map. F=AC+AC+BC+BC,rules： 按照表达式中出现的变量确定变量的个数，画好方格图； 再按照每个积项确定方格图中的主蕴含项；确定主蕴含项时，由积项中出现的变量因子对应于图中的区域的交叉部分填入“1”即可。,Chapter 4,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,Chapter 4,49,Combinational circuit design example,Exp.2：design a 3-bit Gray code binary code decoder. Let Gray code : G2G1G0 Binary code: B2B1B0,Chapter 4,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,Chapter 4,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。,Chapter 4,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,Chapter 4,53,Dividing into two part,Adjacent：each cell is adjacent to 5 cells.,V=0,Chapter 4,54,例：写出下列逻辑函数的最小积之和， F=VWXYZ（7,8,9,10,11,12,23,24,26,28）,Chapter 4,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),Chapter 4,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.,Chapter 4,57,Exp.1,00,01,11,10,F,AB,CD,00,01,11,A,C,D,B,10,F=CD+ABD+ACD,Chapter 4,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,Result Yes: F=1 No: F=0,F=N3N0+N2N1,Chapter 4,59,Exp.3：minimizing the following expression to minimal sum and “NAND-NAND” representation. F=ABC+ABD+ACD+ABC AB+AC=0 (约束项) 约束无关项输入变量的取值组合受到约束，这些输入组合对应的输出也是任意的。,Chapter 4,60,F,A B,C D,A,C,D,B,AC,AB,dont care term,the k-map,minimization,Chapter 4,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,Chapter 4,62,(2) Find the common terms, the synthesis again Algorithm find the m-product function of all output. circle the m-products EPI. (the common part) find the EPI in the leaving “1”cell. combining step、, get the final circuit.,Chapter 4,63,F=XY+XYZ,G=XY+XYZ,重新划出质主蕴含项,Chapter 4,64,列表法,Chapter 4,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、hazard reason: delay Static Hazard: static-1, static-0 hazards,Chapter 4,66,1、static hazards,static1 hazards definition：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.,Chapter 4,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.,Chapter 4,68, static0 hazards definition：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,Chapter 4,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.,Chapter 4,70,2、finding static hazards,（1）逻辑代数法 当在一个函数表达式中，某变量的原变量和反变量的形式同时出现，且在保持该变量形式不变，其他变量取各种取值组合时，出现如下情况： 表达式可化简为F=Xi+Xi形式，则该变量发生变化时，在电路中可能出现静态1冒险。 表达式可化简为F=Xi Xi时，则该变量发生变化时，在电路中可能出现静态0冒险。,Chapter 4,71,(2) using k-map,若主质蕴含项（EPI）之间存在相切的部分，则电路可能存在静态冒险。,Chapter 4,72,(3) eliminate the static hazards,引入一致项（consensus，冗余项）：将相切的部分划入一个质蕴含项。,AC,得 F=AD+CD+AC,Chapter 4,73,X,Y,Z,Z,XZ,YZ,F,1,0,0,1,XY,1,1,F=XZ+YZ+XY,Chapter 4,74,第四章小结,开关代数 掌握开关代数的公理、定理。熟练应用于逻辑电路的分析和设计中。 摩根定理、广义摩根定理（反演定理）、对偶定理。 掌握逻辑函数的表示法真值表、标准和、标准积，及最小项、最大项的定义和性质。,Chapter 4,75,组合逻辑电路的分析,能写出电路的逻辑表达式。 能化简表达式（代数法、卡诺图法） 能作电路结构的变换（“与或”转“与非与非”，“或与”转“或非或非”） 能对原电路作是否存在“冒险”的判断 能画出正确的时序图。,Chapter 4,76,分析如下电路 根据电路图写出逻辑表达式，判断原电路是否存在冒险。 写出最小积之和式. 若输入信号为以下顺序，无输入延迟时，请画出输出波形。,Chapter 4,77,A,B,C,F,D,Chapter 4,78,组合逻辑电路的综合 综合运用所学知识（过去所学的课程）分析、理解设计要求。 将分析所得的输入变量、输出变量及二者间的逻辑关系列入真值表。 化简，画电路 对多输出的处理一般以各自独立输出方式求解。,Chapter 4,79,试设计一个电路，当输入的4位二进制数能被2整除时，输出Y=1，当输入数能被3整除时，输出Z=1，不满足上述条件时，输出为0。,Chapter 4,80,定时冒险 掌握冒险可能出现的情况：“与或”结构可能出现静态1冒险；“或与”结构可能出现静态0冒险。,