《数字设计课件第四章组合逻辑设计原理》由会员分享，可在线阅读，更多相关《数字设计课件第四章组合逻辑设计原理（80页珍藏版）》请在金锄头文库上搜索。
1、2024/8/242024/8/241 1Chapter 4 Combinational Logic Design Principles本章重点1、开关代数：公理、定理、定义2、组合电路的分析：组合电路的结构、逻辑表达式、真值表、时序图等。3、组合电路的综合（设计）：逻辑抽象定义电路的功能，写出逻辑表达式，得到实际的电路。Chapter 42Combinational logic circuitThe outputs depend only on its current inputs.each output can be specified by truth table or Boolean
2、expression.Chapter 434.1 Switching AlgebraDeals with boolean values : 0, 1 Signal values denoted by variables(X, Y, FRED, etc.)Boolean operators ：+, , 1、AxiomsChapter 442. Single Variable TheoremsProofs by perfect inductionl将变量的所有取值代入定理表达式，若等号两边始终相等，则得证。自等律0-1律同一律还原律互补律(T1) X+0=X (T1) X1=X(T2) X+1=1
3、 (T2) X0=0(T3) X+X=X (T3) XX=X(T4) (X)=X(T5) X+X=1 (T5) XX=0Chapter 453. two-and three-variable theoremsParenthesization or order of terms in a logical sum or logical product is irrelevant.T8logical multiplication distributes over logical additionT8logical addition distributes over logical multiplic
4、ation(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 46T9、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)=
5、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 474. n-variable theoremsT13- 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 (广义同一律
6、)(T13) (X1X2Xn)=X1+X2+Xn(T13) (X1+X2+Xn)=X1X2Xn （ DeMorgan theorems ）DeMorgan theoremsChapter 48T14Generalized 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 （注：如逻辑式中有
7、带括号的表达式取反，反函数中保留非号不变。）例：F=（AB+C）E+G的反函数。(T14) F(X1,X2,Xn, + , )=F(X1,X2,Xn, , +)Chapter 49finite 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 4105. DualityAny theorem or identity in switching algebra rem
8、ains 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)+1BdualitydualityChapter 411 relation between duality and theorem 14： F(X1,X2,Xn, + , ，)= FD(X1,X2,Xn, , + ，
9、)正逻辑约定与负逻辑约定互为对偶关系。 正逻辑“与”=负逻辑“或” 正逻辑“或”=负逻辑“与” 正逻辑“与非”=负逻辑“或非” 正逻辑“或非”=负逻辑“与非”Chapter 4126. Using switching algebra in minimizing logic functionExp.：（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 4137. Standard representation of logic functions truth table defini
10、tions （p.197）literal（也可称作元素、因子）product term XYZ，ABGG，Rsum-of-products (SOP)sum term C+D+H，X+X+Wproduct-of-sums (POS)normal term (标准项)Chapter 414n-variable mintermnormal product term with n literals3-variable X, Y, Z X YZmintermminterm number000XYZm0001XYZm1 010XYZm2011XYZm3100XYZm4101XYZm5110XYZm611
11、1XYZm7one mintermone binary combinationone combination only let one minterm be 1one n-variable minterm represent one n-variable combination .Chapter 415n-variable maxtermnormal sum term with n literalsX Y Z maxtermmaxterm number00 0X+Y+ZM000 1X+Y+ZM101 0X+Y+ZM201 1X+Y+ZM310 0X+Y+ZM410 1X+Y+Z M511 0X
12、+Y+ZM611 1X+Y+ZM7one maxtermone combination only let one maxterm be 0one binary combinationone maxtermone n-variable maxterm represent one n-variable combination .Chapter 416properties of minterma、所有输入组合取值中，只有一组取值能令特定的某个最小项的值为1。b、任意两个不同最小项之积为0，mimj=0 ijc、全部最小项之和为1， properties of maxterma、所有输入组合取值中，只
13、有一组取值能令特定的某个最大项的值为0。b、任意两个不同最大项之和为1， Mi+Mj=1 ijc、全部最大项之积为0， 编号相同的最小项和最大项互为反函数 mi=(Mi)， Mj=(mj)properties of minterm and maxtermChapter 417canonical sumsum 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)XYZF00010
14、010010001111001101011011111inputoutputChapter 418canonical productproduct 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) XYZF00010010010001111001101011011111Chapter 419若已知标准和，则集合中剩下的编号就可以构建标准积；反之亦然。 例：XYZ（0、1、2、3）=XYZ（4
15、、5、6、7）Conversion between maxterm list and minterm listn variable logic functionminterm listk termsmaxterm listj termsk minterm numbersj maxterm numbersComplement subset of the 2n numbersk+j=2nChapter 420inverse function of a canonical logic expression：F=+mi+mj+ ijIts inverse function:F= Mi Mj ij反之亦
16、然。Representation of a logic function truth table canonical sum minterm list canonical product maxterm listChapter 4214.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
17、sum or product.Minimizing the equation.Sometime, write the logic expression according to the circuit directly.timing diagram maybe needed.Chapter 422Analyzing exampleInput variable:X, Y, ZOutput variable:FXYZF00000011010101101000101111001111F=X,Y,Z(1,2,5,7)=XYZ+XYZ+XYZ+XYZORF=X,Y,Z(0,3,4,6) =(X+Y+Z)
18、(X+Y+Z)(X+Y+Z)(X+Y+Z)Chapter 423Minimizing 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)+XYZChapter 424Basic structure of logic circuitTwo types two level “AND
19、OR”； two level “OR AND”； two level “NAND NAND”； two level “NOR NOR”。DeMorgan theoremChapter 425“AND-OR” and “NAND-NAND”AND ORNAND NANDfirst-levelsecond-levelChapter 426“OR-AND” and “NOR-NOR”OR-ANDNOR-NORfirst-levelsecond-levelChapter 427Timing diagramChapter 428课堂练习分析如下电路， 1）直接写出逻辑函数表达式并化简 2）列出真值表AB
20、CDF1F2T1T2T3T4Chapter 4294.3 Combinational-Circuit SynthesisSynthesis 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 log
21、ic expression；Give the circuit diagramChapter 4301、circuit descriptions and designsExp1：design a 4-bit prime-number detector.4-bitPrime-number detector4-bitbinary numberN3N2N1N0Yes or NoYes: F=1 No: F=0N3N2N1N0F0000000011001010011101000010110110001111N3N2N1N0F0000000010001000011101000010110110001110
22、F=N3,N2,N1,N0 (1,2,3,5,7,11,13)Chapter 431Exp2：alarm circuit alarm circuitWINDOWDOORGARAGEALARMPANIC1ENABLE1EXITING0SECUREnoSECURE=WINDOWDOORGARAGEChapter 4322、circuit manipulations 从真值表或后面将要讲述的方法所得到的组合电路均是“与或”、“或与”结构。从CMOS电路的实现上来说，带“非”的门的速度要快些，因而在具体实现时，往往需要将所得的电路作一些电路的等效变换，成为能用带“非”的门实现。Chapter 4333
23、、combinational-circuit minimizationMinimizing 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）（
24、X+Y）=XChapter 4344、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）FX0101FX0101Y0123each cell has a number which correspond to a minterm number in a truth table.Chapter 4353-var k-map F（X，Y，Z）4-var k-map F（W,
25、X, Y, Z）FXY000101Z012311106745ZXYFWX000101YZ45111012138932671514111000011110WYXZXY is arranged in Gray code.the contents is output value corresponding to each input combinationChapter 436 fill in the k-map for a given truth table编号相同的真值表的每一行与卡诺图的方格是一一对应的。将真值表各行的输出值填入卡诺图的对应方格中。Exp：F=X,Y,Z（1,2,5,7）tru
26、th table k-map？XYZF00000011010101101000101111001111FX YZ 1 1 0 1 0 0 1 000011110XY01ZChapter 437 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 43800011110F1001101010
27、101100ABCD000111ACDB B10Chapter 4395、minimizing sums of productsbase 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 440FXY000
28、1Z011110ZXYFWX0001YZ111000011110WYXZadjacentadjacentadjacentadjacentChapter 441（2）methods of minimizationcircle 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 produc
29、t term is called prime implicant，PI）。1001101000011110F10101100W XY Z000111WYZ10XChapter 442derive prime implicantin 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
30、as area where it is 1, then it isnt appear . Chapter 443Exp1001101000011110F10101100W XY Z000111WYZ10XWXXYZWXZWYZChapter 444complete 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 su
31、m is the sum of EPI.Chapter 4451001101000011110F10101100W XY Z000111WYZ10Xdistinguished “1” cellChapter 446 Exp1：111101100110000000011110FW XY Z000111WYZX Xcomplete sum：F=YZ+XZ+XYminimal sum：F=YZ+XZChapter 447Exp2：derive the minimal sum by k-map. F=AC+AC+BC+BCFABC 1 0 1 1 1 1 1 000011110AB01Crules：按
32、照表达式中出现的变量确定变量的个数，画好方格图；再按照每个积项确定方格图中的主蕴含项；确定主蕴含项时，由积项中出现的变量因子对应于图中的区域的交叉部分填入“1”即可。Chapter 448Combinational circuit design exampleExp1：4-bit prime-number detector. F=N3N2N1N0（1，2，3，5，7，11，13）1FN3N200011N1N011110111100011110N3N1N2N0minimal sum:F=N3N0+N2N1N0+N2N1N0+N3N2N1Chapter 449Combinational circu
33、it design exampleExp.2：design a 3-bit Gray code binary code decoder. Let Gray code : G2G1G0Binary code: B2B1B0G2 G1 G0 B2 B1 B0000000001001011010010011110100111101101110100111Chapter 450Combinational circuit design exampleExp3：design a 3-bit majority-rule circuit, that the output value is same as th
34、e most of input bits.ABCF0000001001000111100010111101111100100111FABCCABChapter 451Combinational circuit design exampleExp.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
35、-map.Known F1=BC+CD+BCD and F2=AD+CD+ABC，do FA=F1F2，FB=F1+F2。Chapter 452（3）k-map more than 4-variable5-variable，32 cells，let variables are V、W、X、Y、Z041282428201615139252921173715112731231926141026302218FVWXYZ00000101101011011110110000011110ZYVWXNumber of cellArrange In Gray codeChapter 453Dividing i
36、nto two partAdjacent：each cell is adjacent to 5 cells.913518124000011110F1101462111573W XY Z000111WYZX10V=0252921172428201600011110F22630221827312319W XY Z000111WYZX10V=1Chapter 454例：写出下列逻辑函数的最小积之和，F=VWXYZ（7,8,9,10,11,12,23,24,26,28）111111W XY ZWYZXV=01111W XY ZWYZXV=1Chapter 4556、minimizing “produc
37、t-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.00011110F1111011000101110W XY Z000111WYZX10F=WYZ+WYX+XZF=(W+Y+Z)(W+X+Y)(X+Z)Chapter 4567、“don
38、t-care” input combinationsThe 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 457Exp.100011110F1d110d0000d1100
39、0ABCD000111ACDB B10F=CD+ABD+ACDChapter 458Exp.2：a BCD prime-number detector.00001001: valid input BCD; 10101111: invalid input, so output dont care。BCD prime-number detectorBCD inputResultYes: F=1No: F=0FN3N2N1N0N3N1N2N011dd111ddddF=N3N0+N2N14Chapter 4618、multiple-output minimizationusing common ter
40、ms enough.Exp：F=XYZ(3,6,7), G=XYZ(0,1,3), derive the circuit.：(1) synthesis individuallyFX YZ 0 1 1 0 0 1 0 000011110XY01ZGX YZ 00 1 1 0 0 0 100011110XY01ZF=XY+YZG=XY+XZChapter 462(2) Find the common terms, the synthesis againAlgorithm find the m-product function of all output.circle the m-products
41、EPI. (the common part)find the EPI in the leaving “1”bining step、, get the final circuit.FGX YZ001 0000 000011110XY01ZXYZChapter 463FX YZ0110010000011110XY01ZGX YZ0011000100011110XY01ZFGX YZ 00 1 0 0 0 0 000011110XY01ZXYZF=XY+XYZG=XY+XYZ重新划出质主蕴含项Chapter 4654.5 Timing HazardsA Static Hazard is define
42、d 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 hazardsChapter 4661、static hazardsstati
43、c1 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.Chapter 467when XYZ=111 110FX YZ01101 1 0 000011110XY01ZXYZZXZYZF1001 10 glitchF=XZ+Y
44、ZStatic-1 hazards occur in SOP implementations. Chapter 468 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 Chapter 469FX YZ 0 1 1 01 1 0 000011110XY01ZY+ZX+Z
45、F=(X+Z)(Y+Z)X0 0Y0 0ZZF1 glitchStatic 0 hazards occur in Product-Of-Sums POS implementations.Chapter 4702、finding static hazards（1）逻辑代数法 当在一个函数表达式中，某变量的原变量和反变量的形式同时出现，且在保持该变量形式不变，其他变量取各种取值组合时，出现如下情况：表达式可化简为F=Xi+Xi形式，则该变量发生变化时，在电路中可能出现静态1冒险。表达式可化简为F=Xi Xi时，则该变量发生变化时，在电路中可能出现静态0冒险。Chapter 471(2) using
46、 k-map 若主质蕴含项（EPI）之间存在相切的部分，则电路可能存在静态冒险。00011110F0011111100000011A BC D000111ACDB10CDADChapter 47200011110F0011111100000011A BC D000111ACDB10CDAD(3) eliminate the static hazards引入一致项（consensus，冗余项）：将相切的部分划入一个质蕴含项。AC得 F=AD+CD+ACChapter 473FX YZ 0 1 1 01 1 0 000011110XY01ZXYZZXZYZF1001XY11F=XZ+YZ+XYCh
47、apter 474第四章小结开关代数 掌握开关代数的公理、定理。熟练应用于逻辑电路的分析和设计中。 摩根定理、广义摩根定理（反演定理）、对偶定理。 掌握逻辑函数的表示法真值表、标准和、标准积，及最小项、最大项的定义和性质。Chapter 475组合逻辑电路的分析能写出电路的逻辑表达式。能化简表达式（代数法、卡诺图法）能作电路结构的变换（“与或”转“与非与非”，“或与”转“或非或非”）能对原电路作是否存在“冒险”的判断能画出正确的时序图。Chapter 476分析如下电路(1)根据电路图写出逻辑表达式，判断原电路是否存在冒险。(2)写出最小积之和式.(3)若输入信号为以下顺序，无输入延迟时，请画出输出波形。FABCDChapter 477ABCFDChapter 478组合逻辑电路的综合 综合运用所学知识（过去所学的课程）分析、理解设计要求。 将分析所得的输入变量、输出变量及二者间的逻辑关系列入真值表。 化简，画电路 对多输出的处理一般以各自独立输出方式求解。Chapter 479试设计一个电路，当输入的4位二进制数能被2整除时，输出Y=1，当输入数能被3整除时，输出Z=1，不满足上述条件时，输出为0。Chapter 480定时冒险 掌握冒险可能出现的情况：“与或”结构可能出现静态1冒险；“或与”结构可能出现静态0冒险。
