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

Chapter4CombinationalLogicDesignPrinciples本章重點1、開關(guān)代數(shù)：公理、定理、定義2、組合電路的分析：組合電路的結(jié)構(gòu)、邏輯表達式、真值表、時序圖等。3、組合電路的綜合（設(shè)計）：邏輯抽象定義電路的功能，寫出邏輯表達式，得到實際的電路。2025/2/281數(shù)字邏輯設(shè)計及應(yīng)用CombinationallogiccircuitTheoutputsdependonlyonitscurrentinputs.eachoutputcanbespecifiedbytruthtableorBooleanexpression.2數(shù)字邏輯設(shè)計及應(yīng)用4.1SwitchingAlgebraDealswithbooleanvalues:0,1

Signalvaluesdenotedbyvariables

(X,Y,FRED,etc.)Booleanoperators

：+,·,’1、Axioms3數(shù)字邏輯設(shè)計及應(yīng)用2.SingleVariableTheoremsProofsbyperfectinduction將變量的所有取值代入定理表達式，若等號兩邊始終相等，則得證。自等律0-1律同一律還原律互補律(T1)X+0=X(T1’)X·1=X(T2)X+1=1(T2’)X·0=0(T3)X+X=X(T3’)X·X=X(T4)(X’)’=X(T5)X+X’=1(T5’)X·X’=04數(shù)字邏輯設(shè)計及應(yīng)用3.two-andthree-variabletheoremsParenthesizationororderoftermsinalogicalsumorlogicalproductisirrelevant.T8—logicalmultiplicationdistributesoverlogicaladditionT8’—logicaladditiondistributesoverlogicalmultiplication(T6)X+Y=Y+X(T6’)X·Y=Y·X（交換律）(T7)(X+Y)+Z=X+(Y+Z)

(T7’)(X·Y)·Z=X·(Y·Z)（結(jié)合律）(T8)X·Y+X·Z=X·(Y+Z)(T8’)(X+Y)·(X+Z)=X+Y·Z（分配律）5數(shù)字邏輯設(shè)計及應(yīng)用T9、T9’、T10、T10’:beusedtominimizelogicfunctions.Y·Zand(Y+Z)termaretheredundanttermsintheexpression.Supplement：

A+A’B=A+B（消因律）

A’+AB=A’+B(T9)X+X·Y=X(T9’)X·(X+Y)=X（吸收律）(T10)X·Y+X·Y’=X(T10’)(X+Y)·(X+Y’)=X（組合律）(T11)X·Y+X’·Z+Y·Z=X·Y+X’·Z

(T11’)(X+Y)·(X’+Z)·(Y+Z)=(X+Y)·(X’+Z)

（一致律）6數(shù)字邏輯設(shè)計及應(yīng)用4.n-variabletheoremsT13---

equivalenttransformbetween“AND-NOT”and“NOT-OR”.T13’---equivalenttransformbetween“OR-NOT”and“NOT-AND”.Exp.：G=X’Y+VW’Z———=？(T12)X+X+…+X=X(T12’)X·X·…·X=X(廣義同一律)(T13)(X1·X2·……·Xn)’=X1’+X2’+……+Xn’(T13’)(X1+X2+……+Xn)’=X1’·X2’·……·Xn’（DeMorgantheorems

）DeMorgantheorems7數(shù)字邏輯設(shè)計及應(yīng)用T14—GeneralizedDeMorgan’stheorem，也稱為“反演定理”,getthecomplementofalogicexpression(inversefunction)。

keeptheoriginaloperatingorder;complementallvariables;swapping‘0’and‘1’;swapping‘+’and‘·’（注：如邏輯式中有帶括號的表達式取反，反函數(shù)中保留非號不變。）例：F=[（A·B’+C）·E]’+G’的反函數(shù)。(T14)[F(X1,X2,……,Xn,+,·

)]’=F(X1’,X2’,……Xn’,·,+)8數(shù)字邏輯設(shè)計及應(yīng)用finiteinduction（1）provingthetheoremistrueforn=2;（2）thenprovingthatifthetheoremistrueforn=i,thenitisalsotrueforn=i+1.9數(shù)字邏輯設(shè)計及應(yīng)用5.DualityAnytheoremoridentityinswitchingalgebraremainstrueif0and1areswappedand·and+areswappedthroughout.

alogicexpression：F(X1,X2,……,Xn,+,·

，’)

itsduality：FD=F(X1,X2,……,Xn,·,+,’)

X·Y———X+Y 0———1Exp.：findthedualityexpression.F=(AB+A’C)’+1·Bdualityduality10數(shù)字邏輯設(shè)計及應(yīng)用

relationbetweendualityandtheorem14：

[F(X1,X2,……,Xn,+,·

，’)]’=FD(X1’,X2’,……,Xn’,·,+

，’)正邏輯約定與負邏輯約定互為對偶關(guān)系。正邏輯“與”=負邏輯“或”

正邏輯“或”=負邏輯“與”

正邏輯“與非”=負邏輯“或非”

正邏輯“或非”=負邏輯“與非”11數(shù)字邏輯設(shè)計及應(yīng)用6.UsingswitchingalgebrainminimizinglogicfunctionExp.：（1）F=AD+AD’+AB+A’C+BD+AB’EF+B’EF（2）F=A·（B’+C）’·（BC）’（3）F=AB+AC’+B’C+C’B+CD’+BD’+ADE(F+G)12數(shù)字邏輯設(shè)計及應(yīng)用7.Standardrepresentationoflogicfunctions①truthtable②definitions

（p.197）literal（也可稱作元素、因子）producttermX·Y·Z’，A·B’·G·G，Rsum-of-products(SOP)sumtermC+D+H’，X+X+W’product-of-sums(POS)normalterm(標準項)13數(shù)字邏輯設(shè)計及應(yīng)用n-variablemintermnormalproducttermwithnliterals3-variableX,Y,ZXYZmintermmintermnumber000X’·Y’·Z’m0001X’·Y’·Zm1010X’·Y·Z’m2011X’·Y·Zm3100X·Y’·Z’m4101X·Y’·Zm5110X·Y·Z’m6111X·Y·Zm7onemintermonebinarycombinationonecombinationonlyletonemintermbe1onen-variablemintermrepresentonen-variablecombination.14數(shù)字邏輯設(shè)計及應(yīng)用n-variablemaxtermnormalsumtermwithnliteralsXYZmaxtermmaxtermnumber000X+Y+ZM0001X+Y+Z’M1010X+Y’+ZM2011X+Y’+Z’M3100X’+Y+ZM4101X’+Y+Z’

M5110X’+Y’+ZM6111X’+Y’+Z’M7onemaxtermonecombinationonlyletonemaxtermbe0onebinarycombinationonemaxtermonen-variablemaxtermrepresentonen-variablecombination.15數(shù)字邏輯設(shè)計及應(yīng)用①propertiesofminterma、所有輸入組合取值中，只有一組取值能令特定的某個最小項的值為1。b、任意兩個不同最小項之積為0，mi×mj=0i≠jc、全部最小項之和為1，

②propertiesofmaxterma、所有輸入組合取值中，只有一組取值能令特定的某個最大項的值為0。b、任意兩個不同最大項之和為1，

Mi+Mj=1i≠jc、全部最大項之積為0，③編號相同的最小項和最大項互為反函數(shù)

mi=(Mi)’，

Mj=(mj)’propertiesofmintermandmaxterm16數(shù)字邏輯設(shè)計及應(yīng)用canonicalsumsumofmintermscorrespondingtoinputcombinationforwhichthefunctionproducesa1output.

Exp.

F=？

=X’·Y’·Z’+X’·Y·Z+X·Y’·Z’+X·Y·Z’+X·Y·Z=Σ(0,3,4,6,7)XYZF00010010010001111001101011011111inputoutput17數(shù)字邏輯設(shè)計及應(yīng)用canonicalproductproductofmaxtermscorrespondingtoinputcombinationforwhichthefunctionproducesa0output.F=(X+Y+Z’)·(X+Y’+Z)·(X’+Y+Z’)=∏X,Y,Z(1,2,5)XYZF0001001001000111100110101101111118數(shù)字邏輯設(shè)計及應(yīng)用∴若已知標準和，則集合中剩下的編號就可以構(gòu)建標準積；反之亦然。例：∑XYZ（0、1、2、3）=∏XYZ（4、5、6、7）Conversionbetweenmaxtermlistandmintermlistnvariablelogicfunctionmintermlistktermsmaxtermlistjtermsk

mintermnumbersj

maxtermnumbersComplementsubsetofthe2nnumbersk+j=2n19數(shù)字邏輯設(shè)計及應(yīng)用inversefunctionofacanonicallogicexpression：F=…+mi+mj+…i≠jItsinversefunction:F’=…·Mi·Mj·…

i≠j反之亦然。Representationofalogicfunction

①truthtable②canonicalsum

③mintermlist

④canonicalproduct

⑤maxtermlist20數(shù)字邏輯設(shè)計及應(yīng)用4.2Combinational-CircuitAnalysisAnalyzingsteps：Makesurethatitiscombinationalcircuit.Findinputandoutputvariables,fillthetruthtableaccordingtothecircuit.Canonicalsumorproduct.Minimizingtheequation.Sometime,writethelogicexpressionaccordingtothecircuitdirectly.timingdiagrammaybeneeded.21數(shù)字邏輯設(shè)計及應(yīng)用AnalyzingexampleInputvariable:X,Y,ZOutputvariable:FXYZF00000011010101101000101111001111F=ΣX,Y,Z(1,2,5,7)=X’·Y’·Z+X’·Y·Z’+X·Y’·Z+X·Y·ZORF=ΠX,Y,Z(0,3,4,6)=(X+Y+Z)·(X+Y’+Z’)·(X’+Y+Z)·(X’+Y’+Z)22數(shù)字邏輯設(shè)計及應(yīng)用MinimizingtheexpressionF=ΣX,Y,Z(1,2,5,7)=X’·Y’·Z+X’·Y·Z’+X·Y’·Z+X·Y·Z=X·Z+Y’·Z+X’·Y·Z’ORF=Π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’)WritethelogicexpressionaccordingtothecircuitF=((X+Y’)·Z)+X’·Y·Z’23數(shù)字邏輯設(shè)計及應(yīng)用BasicstructureoflogiccircuitTwotypes①twolevel“AND—OR”；②twolevel“OR—AND”；③twolevel“NAND—NAND”；④twolevel“NOR—NOR”。De’Morgantheorem24數(shù)字邏輯設(shè)計及應(yīng)用“AND-OR”and“NAND-NAND”AND—ORNAND—NANDfirst-levelsecond-level25數(shù)字邏輯設(shè)計及應(yīng)用“OR-AND”and“NOR-NOR”O(jiān)R-ANDNOR-NORfirst-levelsecond-level26數(shù)字邏輯設(shè)計及應(yīng)用Timingdiagram27數(shù)字邏輯設(shè)計及應(yīng)用課堂練習分析如下電路，

1）直接寫出邏輯函數(shù)表達式并化簡

2）列出真值表ABCDF1F2T1T2T3T428數(shù)字邏輯設(shè)計及應(yīng)用4.3Combinational-CircuitSynthesisSynthesissteps：analyzetheworddescription,makesurethatitcouldberealizedbycombinational-circuit；Findallinputandoutputvariable；Usetruthtabletorepresenttheinput-outputlogicrelation；Usekarnaugh-maptominimizethelogicexpression；Givethecircuitdiagram29數(shù)字邏輯設(shè)計及應(yīng)用1、circuitdescriptionsanddesignsExp1：designa4-bitprime-numberdetector.4-bitPrime-numberdetector4-bit

binarynumberN3N2N1N0YesorNoYes:F=1

No:F=0N3N2N1N0F0000000011001010011101000010110110001111N3N2N1N0F0000000010001000011101000010110110001110F=ΣN3,N2,N1,N0(1,2,3,5,7,11,13)30數(shù)字邏輯設(shè)計及應(yīng)用Exp2：alarmcircuit—

alarmcircuitWINDOWDOORGARAGEALARMPANIC1ENABLE1EXITING0SECUREnoSECURE=WINDOW·DOOR·GARAGE31數(shù)字邏輯設(shè)計及應(yīng)用2、circuitmanipulations從真值表或后面將要講述的方法所得到的組合電路均是“與—或”、“或—與”結(jié)構(gòu)。從CMOS電路的實現(xiàn)上來說，帶“非”的門的速度要快些，因而在具體實現(xiàn)時，往往需要將所得的電路作一些電路的等效變換，成為能用帶“非”的門實現(xiàn)。32數(shù)字邏輯設(shè)計及應(yīng)用3、combinational-circuitminimizationMinimizingbyswitchingalgebraMinimizingbykarnaughmapMinimizationmethods：Minimizingthenumberoffirst-levelgatesMinimizingthenumberofinputsoneachfirst-levelgatesMinimizingthenumberofinputsonthesecond-levelgatesBasingon：T10、T10’X·Y+X·Y’=X；（X+Y）·（X+Y’）=X33數(shù)字邏輯設(shè)計及應(yīng)用4、KarnaughMap

graphicalrepresentationofalogicfunction’struthtable.①stucturen-variablek-maphas2ncells.1-vark-map2-vark-map

F（X，Y）FX0101FX0101Y0123eachcellhasanumberwhichcorrespondtoamintermnumberinatruthtable.34數(shù)字邏輯設(shè)計及應(yīng)用3-vark-map

F（X，Y，Z）4-vark-map

F（W,X,Y,Z）FXY000101Z012311106745ZXYFWX000101YZ45111012138932671514111000011110WYXZXYisarrangedinGraycode.thecontentsisoutputvaluecorrespondingtoeachinputcombination35數(shù)字邏輯設(shè)計及應(yīng)用②fillinthek-mapforagiventruthtable編號相同的真值表的每一行與卡諾圖的方格是一一對應(yīng)的。將真值表各行的輸出值填入卡諾圖的對應(yīng)方格中。Exp：F=∑X,Y,Z（1,2,5,7）truthtablek-map？XYZF00000011010101101000101111001111FXYZ

1

1

0

1

0

0

1

000011110XY01Z36數(shù)字邏輯設(shè)計及應(yīng)用③fillinthek-mapforalogicexpression一般步驟：先將所求積之和式變換為標準和式，每個最小項代表了真值表中令輸出為1的輸入組合，按照最小項編號依次將對應(yīng)的卡諾圖方格中填1。Exp：F=A’·B’·C’·D+A’·B·D’+A·C·D+A·B’,representitbyk-map.solution：F=？=∑ABCD（？）37數(shù)字邏輯設(shè)計及應(yīng)用00011110F1001101010101100ABCD000111ACDB1038數(shù)字邏輯設(shè)計及應(yīng)用5、minimizingsumsofproductsbaseon：T10、T10’

X·Y+X·Y’=X(X+Y)·(X+Y’)=X

combinetwoadjacent“1”cellintoaproducttermandeliminateoneliteral.（1）adjacent

inputcombinationsofadjacentcellonlydifferinonevariable，thatisalsocalledwrapround.39數(shù)字邏輯設(shè)計及應(yīng)用FXY0001Z011110ZXYFWX0001YZ111000011110WYXZadjacentadjacentadjacentadjacent40數(shù)字邏輯設(shè)計及應(yīng)用（2）methodsofminimizationcircle2iadjacent“1”cells,itwillbeanewproducttermwith(n-i)literals.thecirclemustbepromisedthebiggestone,ifenlargethecircle,then“0”cellmaybeincluded。thecombinedproducttermiscalledprimeimplicant，PI）。1001101000011110F10101100WXYZ000111WYZ10X41數(shù)字邏輯設(shè)計及應(yīng)用deriveprimeimplicantinareascoveredbythecirclewhere①avariableis0,thenitiscomplementedintheproductterm.②avariableis1,thenitisuncomplementedintheproductterm.③avariableis0aswellasareawhereitis1,thenitisn’tappear.42數(shù)字邏輯設(shè)計及應(yīng)用Exp1001101000011110F10101100WXYZ000111WYZ10XW·X’X’·Y’·ZW’·X·Z’W·Y·Z43數(shù)字邏輯設(shè)計及應(yīng)用completesum—sumofallprimeimplicants.

F=X’Y’Z+W’XZ’+WYZ+WX’needtofindtheminimalsumfindthedistinguished“1”cellmakesuretheEssentialPrimeImplicant,EPI）minimalsumisthesumofEPI.44數(shù)字邏輯設(shè)計及應(yīng)用1001101000011110F10101100WXYZ000111WYZ10Xdistinguished“1”cell45數(shù)字邏輯設(shè)計及應(yīng)用

Exp1：111101100110000000011110FWXYZ000111WYZXcompletesum：F=Y’Z+XZ’+XY’minimalsum：F=Y’Z+XZ’46數(shù)字邏輯設(shè)計及應(yīng)用Exp2：derivetheminimalsumbyk-map.F=AC’+A’C+B’C+BC’FABC

1

0

1

1

1

1

1

000011110AB01Crules：按照表達式中出現(xiàn)的變量確定變量的個數(shù)，畫好方格圖；再按照每個積項確定方格圖中的主蘊含項；確定主蘊含項時，由積項中出現(xiàn)的變量因子對應(yīng)于圖中的區(qū)域的交叉部分填入“1”即可。47數(shù)字邏輯設(shè)計及應(yīng)用CombinationalcircuitdesignexampleExp1：4-bitprime-numberdetector.F=∑N3N2N1N0（1，2，3，5，7，11，13）1FN3N200011N1N011110111100011110N3N1N2N0minimalsum:F=N3’·N0+N2·N1’·N0+N2’·N1·N0+N3’·N2’·N148數(shù)字邏輯設(shè)計及應(yīng)用CombinationalcircuitdesignexampleExp.2：designa3-bitGraycode–binarycodedecoder.LetGraycode:G2G1G0Binarycode:B2B1B0G2G1G0B2B1B000000000100101101001001111010011110110111010011149數(shù)字邏輯設(shè)計及應(yīng)用CombinationalcircuitdesignexampleExp3：designa3-bitmajority-rulecircuit,thattheoutputvalueissameasthemostofinputbits.ABCF0000001001000111100010111101111100100111FABCCAB50數(shù)字邏輯設(shè)計及應(yīng)用CombinationalcircuitdesignexampleExp.4：aprioritycircuitcanjudgewhetherthenumberofinput“1”bitsisoddornot，trytodesignsucha4-bitodd-prioritycircuit.Exp.5：finishthefollowingoperationbyusingk-map.KnownF1=BC’+C’D’+B’CDandF2=AD’+CD+A’B’C’，doFA=F1·F2，F(xiàn)B=F1+F2。51數(shù)字邏輯設(shè)計及應(yīng)用（3）k-mapmorethan4-variable5-variable，32cells，letvariablesareV、W、X、Y、Z041282428201615139252921173715112731231926141026302218FVWXYZ00000101101011011110110000011110ZYVWXNumberofcellArrangeInGraycode52數(shù)字邏輯設(shè)計及應(yīng)用DividingintotwopartAdjacent：eachcellisadjacentto5cells.913518124000011110F1101462111573WXYZ000111WYZX10V=0252921172428201600011110F22630221827312319WXYZ000111WYZX10V=153數(shù)字邏輯設(shè)計及應(yīng)用例：寫出下列邏輯函數(shù)的最小積之和，F(xiàn)=∑VWXYZ（7,8,9,10,11,12,23,24,26,28）111111WXYZWYZXV=01111WXYZWYZXV=154數(shù)字邏輯設(shè)計及應(yīng)用6、minimizing“product-of-sums”Combiningadjacent2i“0”cell,getanewsumtermwith(n-i)literals.orderivetheminimalsumF’∑oftheinversefunctionfirst；thencomplementtheF’∑,sotheminimalproductF∏couldbederived.Exp.00011110F1111011000101110WXYZ000111WYZX10F’=WYZ’+W’YX’+X’Z’F=(W’+Y’+Z)·(W+X+Y’)·(X+Z)55數(shù)字邏輯設(shè)計及應(yīng)用7、“don’t-care”inputcombinationsTheoutputdoesn’tmatterforcertaininputcombination(maybeneveroccur).Thesearecalleddon’tcareterms.Usesymbol“d”、“×”、“Φ”

torepresenttheoutputvalue.Inminimization,don’tcaretermcouldbeusedas“1”or“0”ifnecessary.56數(shù)字邏輯設(shè)計及應(yīng)用Exp.100011110F1d110d0000d11000ABCD000111ACDB10F=C’·D+A·B’·D+A’·C·D57數(shù)字邏輯設(shè)計及應(yīng)用Exp.2：aBCDprime-numberdetector.0000~1001:validinputBCD;1010~1111:invalidinput,sooutputdon’tcare。BCD

prime-numberdetectorBCDinputResultYes:F=1No:F=0FN3N2N1N0N3N1N2N011dd111ddddF=N3’·N0+N2’·N1458數(shù)字邏輯設(shè)計及應(yīng)用Exp.3：minimizingthefollowingexpressiontominimalsumand“NAND-NAND”representation.

F=A’B’C’+A’BD’+A’CD+ABCAB’+AC’=0(約束項)約束無關(guān)項—輸入變量的取值組合受到約束，這些輸入組合對應(yīng)的輸出也是任意的。59數(shù)字邏輯設(shè)計及應(yīng)用dd1dd11Fd11d111ABCDACDBAC’AB’don’tcaretermdd1dd11Fd11d111ABCDACDBthek-mapminimization60數(shù)字邏輯設(shè)計及應(yīng)用8、multiple-outputminimizationusingcommontermsenough.Exp：F=∑XYZ(3,6,7),G=∑XYZ(0,1,3),derivethecircuit.：(1)synthesisindividuallyFXYZ

0

1

1

0

0

1

0

000011110XY01ZGXYZ

00

1

1

0

0

0

100011110XY01ZF=X·Y+Y·ZG=X’·Y’+X’·Z61數(shù)字邏輯設(shè)計及應(yīng)用(2)Findthecommonterms,thesynthesisagainAlgorithm①findthem-productfunctionofalloutput.②circlethem-product’sEPI.(thecommonpart)③findtheEPIintheleaving“1”cell.④combiningstep②、③,getthefinalcircuit.F·GXYZ001

0000

000011110XY01ZX’·Y·Z62數(shù)字邏輯設(shè)計及應(yīng)用FXYZ0110010000011110XY01ZGXYZ0011000100011110XY01ZF·GXYZ

00

1

0

0

0

0

000011110XY01ZX’·Y·ZF=X·Y+X’·Y·ZG=X’·Y’+X’·Y·Z重新劃出質(zhì)主蘊含項63數(shù)字邏輯設(shè)計及應(yīng)用列表法主蘊含項最小項01367F{3,7}√√{6,7}√√G{0,1}√√{1,3}√√64數(shù)字邏輯設(shè)計及應(yīng)用4.5TimingHazardsAStaticHazardisdefinedwhenasinglevariablechangeattheinputcausesamomentarychangeinanothervariable[theoutput].ADynamicHazardoccurswhenachangeintheinputcausesmultiplechangesintheoutput.keywords：glitch、hazardreason:delayStaticHazard:static-1,static-0hazards65數(shù)字邏輯設(shè)計及應(yīng)用1、statichazards①static—1hazardsdefinition：apairofinputcombination（a）differinonlyonevariable（b）bothoutput1

whentheinputchange,amomentary0outputmaybeoccurred.Exp：F=X·Z’+Y·Z，assumeeachgatehasthesamepropagationdelay.66數(shù)字邏輯設(shè)計及應(yīng)用whenX·Y·Z=111→110FXYZ01101

1

0

000011110XY01ZXYZZ’X·Z’Y·ZF10010

glitchF=X·Z’+Y·ZSta