數(shù)字設(shè)計 第四章 組合邏輯設(shè)計原理ppt課件

1、Chapter 4 Combinational Logic Design Principles本章重點(diǎn)本章重點(diǎn)1、開關(guān)代數(shù)：公理、定理、定義、開關(guān)代數(shù)：公理、定理、定義2、組合電路的分析：組合電路的構(gòu)造、邏輯表達(dá)式、真值表、時序、組合電路的分析：組合電路的構(gòu)造、邏輯表達(dá)式、真值表、時序圖等。圖等。3、組合電路的綜合設(shè)計：邏輯籠統(tǒng)定義電路的功能，寫出邏輯、組合電路的綜合設(shè)計：邏輯籠統(tǒng)定義電路的功能，寫出邏輯表達(dá)式，得到實(shí)踐的電路。表達(dá)式，得到實(shí)踐的電路。Combinational logic circuit The outputs depend only on its current input

2、s. each output can be specified by truth table or Boolean expression.4.1 Switching AlgebraDeals with boolean values : 0, 1 Signal values denoted by variables(X, Y, FRED, etc.)Boolean operators ：+, , 1、Axioms( 1)01( 1)10( 2)01( 2)10( 3) 0 00( 3)1 11( 4)1 11( 4) 000( 5) 0 11 00( 5)100 11AXif XAXif XAi

3、f Xthen XAif Xthen XAAAAAA 2. Single Variable TheoremsProofs by perfect induction將變量的一切取值代入定理表達(dá)式，假設(shè)等號兩邊將變量的一切取值代入定理表達(dá)式，假設(shè)等號兩邊一直相等，那么得證。一直相等，那么得證。自等律自等律0-1律律同一概同一概復(fù)原律復(fù)原律互補(bǔ)律互補(bǔ)律(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=03. two-and three-variable theoremsPa

4、renthesization 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)結(jié)合律結(jié)合律(T8) XY+XZ=X(Y+Z) (T8) (X+Y)

5、(X+Z)=X+YZ 分配律分配律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) 一致律一致律4. n-

6、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 (廣義同一概廣義同一概)(T13) (X1X2Xn)=X1+X2+Xn(T13) (X1+X2+Xn)=X1X2Xn DeMorgan theorems DeMorgan theoremsT14Generalized DeMorgans theorem，也，

7、也稱為稱為“反演定理反演定理,get the complement of a logic expression (inverse function)。 keep the original operating order;complement all variables;swapping 0 and 1;swapping + and 注：如邏輯式中有帶括號的表達(dá)式取反，反函注：如邏輯式中有帶括號的表達(dá)式取反，反函數(shù)中保管非號不變。數(shù)中保管非號不變。例：例：F=AB+CE+G的反函數(shù)。的反函數(shù)。(T14) F(X1,X2,Xn, + , )=F(X1,X2,Xn, , +)finite induc

8、tion 1proving the theorem is true for n=2; 2then proving that if the theorem is true for n=i, then it is also true for n=i+1.5. DualityAny 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

9、：FD=F(X1,X2,Xn, , + , ) XYX+Y01Exp.：find the duality expression . F=(AB+AC)+1Bdualityduality relation between duality and theorem 14： F(X1,X2,Xn, + , ，)= FD(X1,X2,Xn, , + ，)正邏輯商定與負(fù)邏輯商定互為對偶關(guān)系。正邏輯商定與負(fù)邏輯商定互為對偶關(guān)系。 正邏輯正邏輯“與與=負(fù)邏輯負(fù)邏輯“或或 正邏輯正邏輯“或或=負(fù)邏輯負(fù)邏輯“與與 正邏輯正邏輯“與非與非=負(fù)邏輯負(fù)邏輯“或非或非 正邏輯正邏輯“或非或非=負(fù)邏輯負(fù)邏輯“與非與非6.

10、Using switching algebra in minimizing logic functionExp.：1F=AD+AD+AB+AC+BD+ABEF+BEF2F=AB+CBC3F=AB+AC+BC+CB+CD+BD +ADE(F+G)7. Standard representation of logic functions truth table definitions p.197literal也可稱作元素、因子也可稱作元素、因子product term XYZ，ABGG，Rsum-of-products (SOP)sum term C+D+H，X+X+Wproduct-of-sum

11、s (POS)normal term (規(guī)范項(xiàng)規(guī)范項(xiàng))n-variable mintermnormal product term with n literals3-variable X, Y, Z X YZmintermminterm number000XYZm0001XYZm1 010XYZm2011XYZm3100XYZm4101XYZm5110XYZm6111XYZm7one mintermone binary combinationone combination only let one minterm be 1one n-variable minterm represent one

12、n-variable combination .n-variable maxtermnormal sum term with n literalsX Y Zmaxtermmaxterm number00 0X+Y+ZM000 1X+Y+ZM101 0X+Y+ZM201 1X+Y+ZM310 0X+Y+ZM410 1X+Y+Z M511 0X+Y+ZM611 1X+Y+ZM7one maxtermone combination only let one maxterm be 0one binary combinationone maxtermone n-variable maxterm repr

13、esent one n-variable combination .properties of minterma、一切輸入組合取值中，只需一組取值能令特定的某個最、一切輸入組合取值中，只需一組取值能令特定的某個最小項(xiàng)的值為小項(xiàng)的值為1。b、恣意兩個不同最小項(xiàng)之積為、恣意兩個不同最小項(xiàng)之積為0，mimj=0 ijc、全部最小項(xiàng)之和為、全部最小項(xiàng)之和為1， properties of maxterma、一切輸入組合取值中，只需一組取值能令特定的某個最、一切輸入組合取值中，只需一組取值能令特定的某個最大項(xiàng)的值為大項(xiàng)的值為0。b、恣意兩個不同最大項(xiàng)之和為、恣意兩個不同最大項(xiàng)之和為1， Mi+Mj=1

14、ijc、全部最大項(xiàng)之積為、全部最大項(xiàng)之積為0， 編號一樣的最小項(xiàng)和最大項(xiàng)互為反函數(shù)編號一樣的最小項(xiàng)和最大項(xiàng)互為反函數(shù) mi=(Mi)， Mj=(mj)2101niim2100niiMproperties of minterm and maxtermcanonical 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)XYZF0001001001000111100

15、1101011011111inputoutputcanonical 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) XYZF00010010010001111001101011011111假設(shè)知規(guī)范和，那么集合中剩下的編號就可以構(gòu)假設(shè)知規(guī)范和，那么集合中剩下的編號就可以構(gòu)建規(guī)范積；反之亦然。建規(guī)范積；反之亦然。 例：例：XYZXYZ0 0、1 1、2 2、3

16、3=XYZ=XYZ4 4、5 5、6 6、7 7Conversion between maxterm list and minterm listn variable logic functionminterm listk termsmaxterm listj termsk minterm numbersj maxterm numbersComplement subset of the 2n numbersk+j=2ninverse function of a canonical logic expression：F=+mi+mj+ ijIts inverse function:F= Mi Mj

17、 ij反之亦然。反之亦然。Representation of a logic function truth table canonical sum minterm list canonical product maxterm list4.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

18、sum or product.Minimizing the equation.Sometime, write the logic expression according to the circuit directly.timing diagram maybe needed.Analyzing 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)(X+Y+Z)(X+Y

19、+Z)(X+Y+Z)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)+XYZBasic structure of logic circuitTwo types two level “AND OR； two level “OR AND； two level

20、“NAND NAND； two level “NOR NOR。DeMorgan theorem“AND-OR and “NAND-NANDAND ORNAND NANDfirst-levelsecond-level“OR-AND and “NOR-NOROR-ANDNOR-NORfirst-levelsecond-levelTiming diagram課堂練習(xí)課堂練習(xí)分析如下電路，分析如下電路， 1直接寫出邏輯函數(shù)表達(dá)式并化簡直接寫出邏輯函數(shù)表達(dá)式并化簡 2列出真值表列出真值表ABCDF1F2T1T2T3T44.3 Combinational-Circuit SynthesisSynthesi

21、s 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 diagram1、circuit descriptions and des

22、ignsExp1：design a 4-bit prime-number detector.4-bitPrime-number detector4-bitbinary numberN3N2N1N0Yes or NoYes: F=1 No: F=0N3N2N1N0F0000000011001010011101000010110110001111N3N2N1N0F0000000010001000011101000010110110001110F=N3,N2,N1,N0 (1,2,3,5,7,11,13)Exp2：alarm circuit alarm circuitWINDOWDOORGARAGE

23、ALARMPANIC1ENABLE1EXITING0SECUREnoSECURE=WINDOWDOORGARAGE2、circuit manipulations 從真值表或后面將要講述的方法所得到的組合電從真值表或后面將要講述的方法所得到的組合電路均是路均是“與與或、或、“或或與構(gòu)造。從與構(gòu)造。從CMOS電電路的實(shí)現(xiàn)上來說，帶路的實(shí)現(xiàn)上來說，帶“非的門的速度要快些，非的門的速度要快些，因此在詳細(xì)實(shí)現(xiàn)時，往往需求將所得的電路作一因此在詳細(xì)實(shí)現(xiàn)時，往往需求將所得的電路作一些電路的等效變換，成為能用帶些電路的等效變換，成為能用帶“非的門實(shí)現(xiàn)。非的門實(shí)現(xiàn)。3、combinational-circuit

24、 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+YX+Y=X4、Karnaugh Map graph

25、ical representation of a logic functions truth table .stucturen-variable k-map has 2n cells.1-var k-map2-var k-map FX，YFX0101FX0101Y0123each cell has a number which correspond to a minterm number in a truth table.3-var k-map FX，Y，Z4-var k-map FW, X, Y, ZFXY000101Z012311106745ZXYFWX000101YZ4511101213

26、8932671514111000011110WYXZXY is arranged in Gray code.the contents is output value corresponding to each input combination fill in the k-map for a given truth table編號一樣的真值表的每一行與卡諾圖的方格是一一對應(yīng)的。將真值表各行的輸出值填入卡諾圖的對應(yīng)方格中。Exp：F=X,Y,Z1,2,5,7truth table k-map？XYZF00000011010101101000101111001111FX YZ 1 1 0 1 0

27、0 1 000011110XY01Z fill in the k-map for a logic expression普通步驟：先將所求積之和式變換為規(guī)范和式，每普通步驟：先將所求積之和式變換為規(guī)范和式，每個最小項(xiàng)代表了真值表中令輸出為個最小項(xiàng)代表了真值表中令輸出為1的輸入組合，的輸入組合，按照最小項(xiàng)編號依次將對應(yīng)的卡諾圖方格中填按照最小項(xiàng)編號依次將對應(yīng)的卡諾圖方格中填1。Exp：F=ABCD+ABD+ACD+AB, represent it by k-map.solution：F=？ =ABCD？ 00011110F1001101010101100ABCD000111ACD105、minim

28、izing 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.1adjacent input combinations of adjacent cell only differ in one variable，that is also called wrapround.FXY0001Z011110ZXYFWX0001YZ111000011110WYXZadjacentadjacentadja

29、centadjacent2methods of minimizationcircle 2i adjacent “1cells, it will be a new product term with (n-i) literals.the circle must be promised the biggest one, if enlarge the circle, then “0cell may be included。the combined product term is called prime implicant，PI。1001101000011110F10101100W XY Z0001

30、11WYZ10Xderive 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 as area where it is 1, then it isnt appear . Exp1001101000011110F10101100W XY Z0001

31、11WYZ10XWXXYZWXZWYZcomplete 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, EPIminimal sum is the sum of EPI.1001101000011110F10101100W XY Z000111WYZ10Xdistinguished “1 cell Exp1：11110110011000000

32、0011110FW XY Z000111WYZcomplete sum：F=YZ+XZ+XYminimal sum：F=YZ+XZExp2：derive the minimal sum by k-map. F=AC+AC+BC+BCFABC 1 0 1 1 1 1 1 000011110AB01Crules：按照表達(dá)式中出現(xiàn)的變按照表達(dá)式中出現(xiàn)的變量確定變量的個數(shù)，畫量確定變量的個數(shù)，畫好方格圖；好方格圖；再按照每個積項(xiàng)確定方再按照每個積項(xiàng)確定方格圖中的主蘊(yùn)含項(xiàng)；確格圖中的主蘊(yùn)含項(xiàng)；確定主蘊(yùn)含項(xiàng)時，由積項(xiàng)定主蘊(yùn)含項(xiàng)時，由積項(xiàng)中出現(xiàn)的變量因子對應(yīng)中出現(xiàn)的變量因子對應(yīng)于圖中的區(qū)域的交叉部于圖中的區(qū)

33、域的交叉部分填入分填入“1即可。即可。Combinational circuit design exampleExp1：4-bit prime-number detector. F=N3N2N1N01，2，3，5，7，11，131FN3N200011N1N011110111100011110N3N1N2N0minimal sum:F=N3N0+N2N1N0+N2N1N0+N3N2N1Combinational circuit design exampleExp.2：design a 3-bit Gray code binary code decoder. Let Gray code : G2G

34、1G0Binary code: B2B1B0G2 G1 G0 B2 B1 B0000000001001011010010011110100111101101110100111Combinational circuit design exampleExp3：design a 3-bit majority-rule circuit, that the output value is same as the most of input bits.ABCF0000001001000111100010111101111100100111FABCCABCombinational circuit desig

35、n 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-map.Known F1=BC+CD+BCD and F2=AD+CD+ABC，do FA=F1F2，F(xiàn)B=F1+F2。3k-map more than 4-variable5-variable，32 cells，let

36、 variables are V、W、X、Y、Z041282428201615139252921173715112731231926141026302218FVWXYZ00000101101011011110110000011110ZYVWXNumber of cellArrange In Gray codeDividing into two partAdjacent：each cell is adjacent to 5 cells.913518124000011110F1101462111573W XY Z000111WYZX10V=0V=0252921172428201600011110F

37、22630221827312319W XY Z000111WYZX10V=1V=1例：寫出以下邏輯函數(shù)的最小積之和，例：寫出以下邏輯函數(shù)的最小積之和，F(xiàn)=VWXYZ7,8,9,10,11,12,23,24,26,28111111W XY ZWYZXV=01111W XY ZWYZXV=16、minimizing “product-of-sumsCombining adjacent 2i “0cell, get a new sum term with (n-i) literals.or derive the minimal sum F of the inverse function first；

38、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)7、“dont-care input combinationsThe output doesnt matter for certain input combination (maybe never occur). These are called dont care terms.Use symbol “d、“

39、、“ to represent the output value.In minimization, dont care term could be used as “1 or “0 if necessary.Exp.100011110F1d110d0000d11000ABCD000111ACD10F=CD+ABD+ACDExp.2：a BCD prime-number detector.00001001: valid input BCD; 10101111: invalid input, so output dont care。BCD prime-number detectorBCD inpu

40、tResultYes: F=1No: F=0FN3N2N1N0N3N1N2N011dd111ddddF=N3N0+N2N14Exp.3：minimizing the following expression to minimal sum and “NAND-NAND representation. F=ABC+ABD+ACD+ABC AB+AC=0 (約束項(xiàng)約束項(xiàng)) 約束無關(guān)項(xiàng)約束無關(guān)項(xiàng)輸入變量的取值組合遭到約束，這些輸入變量的取值組合遭到約束，這些輸入組合對應(yīng)的輸出也是恣意的。輸入組合對應(yīng)的輸出也是恣意的。dd1dd11Fd11d111A BC DACDBACABdont care term

41、dd1dd11Fd11d111A BC DACDBthe k-mapminimization8、multiple-output minimizationusing common terms 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+XZ(2) Find the common terms, the synthesi

42、s againAlgorithm find the m-product function of all output.circle the m-products EPI. (the common part)find the EPI in the leaving “bining step、, get the final circuit.FGX YZ001 0000 000011110XY01ZXYZFX YZ0110010000011110XY01ZGX YZ0011000100011110XY01ZFGX YZ 00 1 0 0 0 0 000011110XY01ZXYZF=XY+XYZG=X

43、Y+XYZ重新劃出質(zhì)主蘊(yùn)含項(xiàng)重新劃出質(zhì)主蘊(yùn)含項(xiàng)列表法主蘊(yùn)含主蘊(yùn)含項(xiàng)項(xiàng)最小項(xiàng)最小項(xiàng)01367F3 ,76 ,7G0 ,11 ,34.5 Timing HazardsA 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.ke

44、ywords：glitch、hazardreason: delayStatic Hazard: static-1, static-0 hazards1、static hazardsstatic1 hazardsdefinition：a pair of input combinationadiffer in only one variable bboth output 1 when the input change ,a momentary 0 output maybe occurred.Exp：F=XZ+YZ，assume each gate has the same propagation

45、delay.when XYZ=111 110FX YZ01101 1 0 000011110XY01ZXYZZXZYZF1000 glitchF=XZ+YZStatic-1 hazards occur in SOP implementations. static0 hazardsdefinition：a pair of input combinationadiffer in only one variable bboth output 0 when the input change ,a momentary 1 output maybe occurred.Exp： F=(X+Z)(Y+Z)when 000 001 FX YZ 0 1 1 01 1 0 000011110XY01ZY+ZX+ZF=(X+Z)(Y+Z)XYZZF1 glitchStatic 0 hazards occur in Product-Of-Sums POS implementations.2、finding static hazards1 1邏輯代數(shù)法邏輯代數(shù)法 當(dāng)在一個函數(shù)表達(dá)式中，某變量的原變量和反當(dāng)在一個函數(shù)表達(dá)式中，某變