数字设计 第四章 组合逻辑设计原理

Chapter4CombinationalLogicDesignPrinciples本章重点1、开关代数：公理、定理、定义2、组合电路的分析：组合电路的结构、逻辑表达式、真值表、时序图等。3、组合电路的综合（设计）：逻辑抽象定义电路的功能，写出逻辑表达式，得到实际的电路。2023/4/211.CombinationallogiccircuitTheoutputsdependonlyonitscurrentinputs.eachoutputcanbespecifiedbytruthtableorBooleanexpression.2.4.1SwitchingAlgebraDealswithbooleanvalues:0,1

Signalvaluesdenotedbyvariables

(X,Y,FRED,etc.)Booleanoperators：+,·,’1、Axioms3.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.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)（结合律）(T8)X·Y+X·Z=X·(Y+Z)(T8’)(X+Y)·(X+Z)=X+Y·Z（分配律）5.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.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.T14—GeneralizedDeMorgan’stheorem，也称为“反演定理”,getthecomplementofalogicexpression(inversefunction)。

keeptheoriginaloperatingorder;complementallvariables;swapping‘0’and‘1’;swapping‘+’and‘·’（注：如逻辑式中有带括号的表达式取反，反函数中保留非号不变。）例：F=[（A·B’+C）·E]’+G’的反函数。(T14)[F(X1,X2,……,Xn,+,·)]’=F(X1’,X2’,……Xn’,·,+)8.finiteinduction（1）provingthetheoremistrueforn=2;（2）thenprovingthatifthetheoremistrueforn=i,thenitisalsotrueforn=i+1.9.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.

relationbetweendualityandtheorem14：

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

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

，’)正逻辑约定与负逻辑约定互为对偶关系。正逻辑“与”=负逻辑“或”

正逻辑“或”=负逻辑“与”

正逻辑“与非”=负逻辑“或非”

正逻辑“或非”=负逻辑“与非”11.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.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.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.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.①propertiesofminterma、所有输入组合取值中，只有一组取值能令特定的某个最小项的值为1。b、任意两个不同最小项之积为0，mi×mj=0i≠jc、全部最小项之和为1，

②propertiesofmaxterma、所有输入组合取值中，只有一组取值能令特定的某个最大项的值为0。b、任意两个不同最大项之和为1，Mi+Mj=1i≠jc、全部最大项之积为0，③编号相同的最小项和最大项互为反函数

mi=(Mi)’，

Mj=(mj)’propertiesofmintermandmaxterm16.canonicalsumsumofmintermscorrespondingtoinputcombinationforwhichthefunctionproducesa1output.

Exp.

F=？

=X’·Y’·Z’+X’·Y·Z+X·Y’·Z’+X·Y·Z’+X·Y·Z=Σ(0,3,4,6,7)XYZF00010010010001111001101011011111inputoutput17.canonicalproductproductofmaxtermscorrespondingtoinputcombinationforwhichthefunctionproducesa0output.F=(X+Y+Z’)·(X+Y’+Z)·(X’+Y+Z’)=∏X,Y,Z(1,2,5)XYZF0001001001000111100110101101111118.∴若已知标准和，则集合中剩下的编号就可以构建标准积；反之亦然。例：∑XYZ（0、1、2、3）=∏XYZ（4、5、6、7）ConversionbetweenmaxtermlistandmintermlistnvariablelogicfunctionmintermlistktermsmaxtermlistjtermskmintermnumbersjmaxtermnumbersComplementsubsetofthe2nnumbersk+j=2n19.inversefunctionofacanonicallogicexpression：F=…+mi+mj+…i≠jItsinversefunction:F’=…·Mi·Mj·…i≠j反之亦然。Representationofalogicfunction①truthtable②canonicalsum③mintermlist④canonicalproduct⑤maxtermlist20.4.2Combinational-CircuitAnalysisAnalyzingsteps：Makesurethatitiscombinationalcircuit.Findinputandoutputvariables,fillthetruthtableaccordingtothecircuit.Canonicalsumorproduct.Minimizingtheequation.Sometime,writethelogicexpressionaccordingtothecircuitdirectly.timingdiagrammaybeneeded.21.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.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.BasicstructureoflogiccircuitTwotypes①twolevel“AND—OR”；②twolevel“OR—AND”；③twolevel“NAND—NAND”；④twolevel“NOR—NOR”。De’Morgantheorem24.“AND-OR”and“NAND-NAND”AND—ORNAND—NANDfirst-levelsecond-level25.“OR-AND”and“NOR-NOR”OR-ANDNOR-NORfirst-levelsecond-level26.Timingdiagram27.课堂练习分析如下电路，

1）直接写出逻辑函数表达式并化简

2）列出真值表ABCDF1F2T1T2T3T428.4.3Combinational-CircuitSynthesisSynthesissteps：analyzetheworddescription,makesurethatitcouldberealizedbycombinational-circuit；Findallinputandoutputvariable；Usetruthtabletorepresenttheinput-outputlogicrelation；Usekarnaugh-maptominimizethelogicexpression；Givethecircuitdiagram29.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.Exp2：alarmcircuit—

alarmcircuitWINDOWDOORGARAGEALARMPANIC1ENABLE1EXITING0SECUREnoSECURE=WINDOW·DOOR·GARAGE31.2、circuitmanipulations从真值表或后面将要讲述的方法所得到的组合电路均是“与—或”、“或—与”结构。从CMOS电路的实现上来说，带“非”的门的速度要快些，因而在具体实现时，往往需要将所得的电路作一些电路的等效变换，成为能用带“非”的门实现。32.3、combinational-circuitminimizationMinimizingbyswitchingalgebraMinimizingbykarnaughmapMinimizationmethods：Minimizingthenumberoffirst-levelgatesMinimizingthenumberofinputsoneachfirst-levelgatesMinimizingthenumberofinputsonthesecond-levelgatesBasingon：T10、T10’X·Y+X·Y’=X；（X+Y）·（X+Y’）=X33.4、KarnaughMap

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

F（X，Y）FX0101FX0101Y0123eachcellhasanumberwhichcorrespondtoamintermnumberinatruthtable.34.3-vark-map

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

F（W,X,Y,Z）FXY000101Z012311106745ZXYFWX000101YZ45111012138932671514111000011110WYXZXYisarrangedinGraycode.thecontentsisoutputvaluecorrespondingtoeachinputcombination35.②fillinthek-mapforagiventruthtable编号相同的真值表的每一行与卡诺图的方格是一一对应的。将真值表各行的输出值填入卡诺图的对应方格中。Exp：F=∑X,Y,Z（1,2,5,7）truthtablek-map？XYZF00000011010101101000101111001111FXYZ

1

1

0

1

0

0

1

000011110XY01Z36.③fillinthek-mapforalogicexpression一般步骤：先将所求积之和式变换为标准和式，每个最小项代表了真值表中令输出为1的输入组合，按照最小项编号依次将对应的卡诺图方格中填1。Exp：F=A’·B’·C’·D+A’·B·D’+A·C·D+A·B’,representitbyk-map.solution：F=？=∑ABCD（？）37.00011110F1001101010101100ABCD000111ACDB1038.5、minimizingsumsofproductsbaseon：T10、T10’

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

combinetwoadjacent“1”cellintoaproducttermandeliminateoneliteral.（1）adjacent

inputcombinationsofadjacentcellonlydifferinonevariable，thatisalsocalledwrapround.39.FXY0001Z011110ZXYFWX0001YZ111000011110WYXZadjacentadjacentadjacentadjacent40.（2）methodsofminimizationcircle2iadjacent“1”cells,itwillbeanewproducttermwith(n-i)literals.thecirclemustbepromisedthebiggestone,ifenlargethecircle,then“0”cellmaybeincluded。thecombinedproducttermiscalledprimeimplicant，PI）。1001101000011110F10101100WXYZ000111WYZ10X41.deriveprimeimplicantinareascoveredbythecirclewhere①avariableis0,thenitiscomplementedintheproductterm.②avariableis1,thenitisuncomplementedintheproductterm.③avariableis0aswellasareawhereitis1,thenitisn’tappear.42.Exp1001101000011110F10101100WXYZ000111WYZ10XW·X’X’·Y’·ZW’·X·Z’W·Y·Z43.completesum—sumofallprimeimplicants.

F=X’Y’Z+W’XZ’+WYZ+WX’needtofindtheminimalsumfindthedistinguished“1”cellmakesuretheEssentialPrimeImplicant,EPI）minimalsumisthesumofEPI.44.1001101000011110F10101100WXYZ000111WYZ10Xdistinguished“1”cell45.

Exp1：111101100110000000011110FWXYZ000111WYZXcompletesum：F=Y’Z+XZ’+XY’minimalsum：F=Y’Z+XZ’46.Exp2：derivetheminimalsumbyk-map.F=AC’+A’C+B’C+BC’FABC

1

0

1

1

1

1

1

000011110AB01Crules：按照表达式中出现的变量确定变量的个数，画好方格图；再按照每个积项确定方格图中的主蕴含项；确定主蕴含项时，由积项中出现的变量因子对应于图中的区域的交叉部分填入“1”即可。47.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.CombinationalcircuitdesignexampleExp.2：designa3-bitGraycode–binarycodedecoder.LetGraycode:G2G1G0Binarycode:B2B1B0G2G1G0B2B1B000000000100101101001001111010011110110111010011149.CombinationalcircuitdesignexampleExp3：designa3-bitmajority-rulecircuit,thattheoutputvalueissameasthemostofinputbits.ABCF0000001001000111100010111101111100100111FABCCAB50.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，FB=F1+F2。51.（3）k-mapmorethan4-variable5-variable，32cells，letvariablesareV、W、X、Y、Z041282428201615139252921173715112731231926141026302218FVWXYZ00000101101011011110110000011110ZYVWXNumberofcellArrangeInGraycode52.DividingintotwopartAdjacent：eachcellisadjacentto5cells.913518124000011110F1101462111573WXYZ000111WYZX10V=0252921172428201600011110F22630221827312319WXYZ000111WYZX10V=153.例：写出下列逻辑函数的最小积之和，F=∑VWXYZ（7,8,9,10,11,12,23,24,26,28）111111WXYZWYZXV=01111WXYZWYZXV=154.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.7、“don’t-care”inputcombinationsTheoutputdoesn’tmatterforcertaininputcombination(maybeneveroccur).Thesearecalleddon’tcareterms.Usesymbol“d”、“×”、“Φ”

torepresenttheoutputvalue.Inminimization,don’tcaretermcouldbeusedas“1”or“0”ifnecessary.56.Exp.100011110F1d110d0000d11000ABCD000111ACDB10F=C’·D+A·B’·D+A’·C·D57.Exp.2：aBCDprime-numberdetector.0000~1001:validinputBCD;1010~1111:invalidinput,sooutputdon’tcare。BCD

prime-numberdetectorBCDinputResultYes:F=1No:F=0FN3N2N1N0N3N1N2N011dd111ddddF=N3’·N0+N2’·N1458.Exp.3：minimizingthefollowingexpressiontominimalsumand“NAND-NAND”representation.

F=A’B’C’+A’BD’+A’CD+ABCAB’+AC’=0(约束项)约束无关项—输入变量的取值组合受到约束，这些输入组合对应的输出也是任意的。59.dd1dd11Fd11d111ABCDACDBAC’AB’don’tcaretermdd1dd11Fd11d111ABCDACDBthek-mapminimization60.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.(2)Findthecommonterms,thesynthesisagainAlgorithm①findthem-productfunctionofalloutput.②circlethem-product’sEPI.(thecommonpart)③findtheEPIintheleaving“1”cell.④combiningstep②、③,getthefinalcircuit.F·GXYZ001

0000

000011110XY01ZX’·Y·Z62.FXYZ0110010000011110XY01ZGXYZ0011000100011110XY01ZF·GXYZ

00

1

0

0

0

0

000011110XY01ZX’·Y·ZF=X·Y+X’·Y·ZG=X’·Y’+X’·Y·Z重新划出质主蕴含项63.列表法主蕴含项最小项01367F{3,7}√√{6,7}√√G{0,1}√√{1,3}√√64.4.5TimingHazardsAStaticHazardisdefinedwhenasinglevariablechangeattheinputcausesamomentarychangeinanothervariable[theoutput].ADynamicHazardoccurswhenachangeintheinputcausesmultiplechangesintheoutput.keywords：glitch、hazardreason:delayStaticHazard:static-1,static-0hazards65.1、statichazards①static—1hazardsdefinition：apairofinputcombination（a）differinonlyonevariable（b）bothoutput1

whentheinputchange,amomentary0outputmaybeoccurred.Exp：F=X·Z’+Y·Z，assumeeachgatehasthesamepropagationdelay.66.whenX·Y·Z=111→110FXYZ01101

1

0

000011110XY01ZXYZZ’X·Z’Y·Z