4. Basic Digital Circuits

An alternative design for the 3-input NAND gate uses CMOS transistors as building blocks, as shown in Figure 4.2. This circuit needs only 6 transistors, ... «  3.MethodofLogicalEffort   ::   Contents   ::   5.CombinationalLogic  » 4.BasicDigitalCircuits¶ Digitalcircuitsarecompositionsoflogicgates.Asmallnumberof digitalcircuitsoccurfrequentlyinlargerdigitaldesigns,suchas multiplexers,encoders,decoders,andmemoryelements.Inthis chapter,weusethemethodoflogicaleffortto studythosebasicdigitalcircuitsthatserveasbuildingblocksfor theconstructionoflargerdigitalsystems. 4.1.LogicGates¶ InSectionLogicGates,weintroducelogicgates withoneandtwoinputs.Often,weneedgateswithmorethan2 inputs,orwishtodesignnewlogicgatesforspecificlogicfunctions ortimingbehavior.Inthefollowingwestudythedesignand characterizationoflogicgatesaselementarybuildingblocksfor digitalcircuits. 4.1.1.LogicGateswithMultipleInputs¶ AssumewedesignadigitalcircuitandneedaNANDgatewith3inputs. Wemayassemblethe3-inputNANDgateusing2-inputNAND gatesandaninverterasbuildingblocks, seeFigure4.1.UsingBooleanalgebra,itis straightforwardtoshowthatthiscircuitimplementsthelogic function\(Y=\overline{A\,B\,C}.\)Thereareseveralproblems withthisimplementation,though.First,thedelayfrominputs \(A\)and\(B\)to\(Y\)islargerthanfrominput \(C.\)Suchasymmetriescanbeconfusingwhendesigninglarger circuitswithdelayconstraints.Second,thedelayofthelongest pathislargerthannecessary,and,third,theCMOSimplementation needs10transistors,whichisalsomorethannecessary. Figure4.1:3-inputNANDgatebuiltfrom2-inputNANDgates. Analternativedesignforthe3-inputNANDgateusesCMOStransistors asbuildingblocks,asshowninFigure4.2.This circuitneedsonly6transistors,andissymmetricw.r.t.itsinputs. Output\(Y\)is0onlyifallinputsare1. A=0    B=0    C=0 Figure4.2:CMOScircuitof3-inputNANDgateandinteractiveswitchmodel. ThecircuittopologyinFigure4.2extendsto \(n\)-inputNANDgatesfor\(n\ge2\):compose\(n\)pMOS transistorsinparalleland\(n\)nMOStransistorsinseries.[1]TheseriescompositionofthenMOStransistorsdetermines theon-resistanceofthepull-downpath.Thelargernumberofinputs, thesmallerthepull-downcurrentand,hence,thelargerthedelayof thegate.Themodeloflogicaleffortreflects thisdependenceofdelayonthenumberofinputsinthelogicaleffort ofthegate.Thematched\(n\)-inputNANDgateincreasesthe widthofthenMOStransistorstomatchthedrivecurrentofthe referenceinverter.Increasingthetransistorwidthsreducesthe on-resistanceattheexpenseofincreasingtheinputcapacitanceof thegate.Thistransistorsizingdoesnotsolvetheproblemthatthe delayincreaseswithincreasingnumbersofinputs.Itmerelyshifts theburdenfromthegateitselftoitsdriver. Todeterminethelogicaleffortandparasiticdelayofthe3-input NANDgate,wesizethetransistorstomatchtheoutputcurrentofthe referenceinverter.Figure4.3showsthematched3-input NANDgatewithtransistorwidths.Whenallinputsare1,allthree nMOStransistorsareswitchedon.Theseriesofon-resistancessums toatotalof\(3R_n(nand).\)Tobeequaltoon-resistance \(R_n(inv)\)ofthereferenceinverter,weneedtotriplethe widthsofthenMOStransistorsoftheNANDgate,\(W_n(nand)=3 W_n(inv)=3.\)IfoneoftheNANDinputsis0,thenonepMOS transistorisswitchedon.Tomatchtheon-resistanaceofthe referenceinverter,weassignthesamewidth\(W_p(nand)= W_p(inv)=2\)tothepMOStransistorsoftheNANDgate.Ifmorethan oneNANDinputis0,thentheparallelcompositionofpMOStransistors hasaloweron-resistancethanforasingleinput.Thecorresponding pull-updelayissmallerifonlyoneinputis0.Therefore,using normalizedpMOSwidthsof2unitsmatchesthereferenceinverterin theworstcasewhenthepull-updelayoftheNANDgateislargest. Figure4.3:Matched3-inputNANDgate. Thematched3-inputNANDgateenablesustodeterminethelogical effortofa3-inputNANDgatebymeansofthenormalizedinput capacitances.Eachinput,e.g.input\(A,\)drivestwoparallel gatecapacitancesofonepMOSandonenMOStransistor: \[C_{in}(A)=W_p(A)+W_n(A)=2+3=5\,.\] Therefore,thelogicaleffortofthe3-inputNANDgateis \[g_{nand3}=\frac{C_{in}(A)}{C_{in}(inv)}=\frac{5}{3}\] perinput.Notethatthelogicaleffortofthe3-inputNANDgateisby \(1/3\)largerthanthelogicaleffortofthe2-inputNANDgate. Furthermore,wedeterminetheparasiticdelayofthe3-inputNANDgate bycalculatingthenormalizedoutputcapacitance: \[C_{out}(nand3)=W_p(A)+W_p(B)+W_p(C)+W_n(A)=3\cdot2+3=9\,.\] Thus,theparasiticdelayofa3-inputNANDgateis \[p_{nand3}=\frac{C_{out}(nand3)}{C_{out}(inv)}=\frac{9}{3}=3\,.\] Wefindthattheparasiticdelayofthe3-inputNANDgateisbyone delayunitlargerthanthatofthe2-inputNANDgate. ForNANDgateswith\(n\)inputs,thematchedgatehasnMOS transistorsofwidth\(n\)andpMOStransistorsofwidth2. Therefore,thelogicaleffortofthe\(n\)-inputNANDgateis (1)\[g_{nandn}=\frac{n+2}{3}\] perinput,andhasparasiticdelay (2)\[p_{nandn}=\frac{n\cdot2+n}{3}=n\,.\] Thelargerthenumberofinputs\(n,\)thelargerthelogical effortandtheparasiticdelayoftheNANDgate.Asaconsequence, themoreinputsthegatehas,thesloweritis,or,fromthecircuit designerperspective,themoreeffortweneedtoinvestinthedriver circuittokeepthepathdelaylow. Thedesignofan\(n\)-inputNORgateprocedesanalogouslytothe\(n\)-inputNANDgate. The\(n\)-inputNORgatehas\(n\)parallelnMOStransistors and\(n\)pMOStransistorsinseries.Thematched\(n\)-input NORgatehasnMOStransistorsofwidth\(W_n=1\)andpMOS transistorsofwidth\(W_p=2n.\)Asaresulteachinputofthe \(n\)-inputNORgatehaslogicaleffort \[g_{norn}=\frac{2n+1}{3}\,,\] andtheparasiticdelayofthegateis \[p_{norn}=\frac{n\cdot1+2n}{3}=n\,.\] Forexample,a3-inputNORgatehaslogicaleffort\(g_{nor3}= 7/3\)perinputandparasiticdelay\(p_{nor3}=3.\)Thelogical effortofan\(n\)-inputNORgateislargerthanthelogicaleffort ofan\(n\)-inputNANDgate.Thus,ifwehavethechoiceto implementthelogicofacircuitpathwithNANDgatesorNORgates, wecommonlypreferNANDgates,becausetheytendtoyieldlowerpath delays. 4.1.2.Tree-StructuredLogicGates¶ Whenthenumberofinputsoflogicgatesislarge,tree-structured gatesoffersuperiorperformancecomparedtoCMOSgates.Asa concreteexample,considera16-inputNANDgate.Thelogicaleffort ofaCMOSNANDgatewithapull-downnetworkof16nMOStransistorsin seriesis\(g_{nand16}=6\)accordingtoEquation(1), andtheparasiticdelayis\(p_{nand16}=16\)accordingto Equation(2).Figure4.4showsanalternative, tree-structuredimplementationthatuses2-inputNANDgatesand invertersasbuildingblocks.Thetreehasapathlogicaleffortof \(G=g_{nand2}^4g_{inv}^3=3.16,\)andapathparasiticdelay of\(P=4p_{nand2}+3p_{inv}=11.\)Thetreestructure improvesbothquantities. Figure4.4:Atree-structured16-inputNANDgateusing2-inputNANDgatesand invertersasbuildingblocks. ThetreestructureoftheNANDcircuitisinspiredbyBooleanalgebra,more succinctlytheassociativityoftheANDoperation: \[(A\cdotB)\cdotC=A\cdot(B\cdotC)\,.\] Associativityimpliesthatwecanparenthesizeanexpressionanyway wewantto.Wemayevenomittheparenthesesaltogetherbecause, mathematically,theparenthesizationdoesnotaffectthevalueofthe expression.Fromtheperspectiveofthecircuitdesigner,however, parenthesesexpressanevaluationorder.Forexample,givena binaryANDoperationand8operands\(A_0,A_1,\ldots,A_7,\) therearemanydifferentevaluationorders.Oneofthemcorrespondsto theleft-skewedparenthesization \[(((((((A_0\cdotA_1)\cdotA_2)\cdotA_3)\cdotA_4)\cdotA_5)\cdotA_6)\cdotA_7)\,,\] whichgroupstheoperationssuchthatall7ANDoperationsmustbe executedoneaftereachother.Thecorrespondingcircuithasa depthof7operations.Incontrast,thetree-structured parenthesizationyieldstheminimumdepthof\(\log_28=3\) operations: \[(((A_0\cdotA_1)\cdot(A_2\cdotA_3))\cdot((A_4\cdotA_5)\cdot(A_6\cdotA_7)))\,.\] Figure4.5showsthecorrespondingcircuits.Wenotethat thetreestructureisasymptoticallyoptimal,i.e.foralargeenough numberofinputs\(n,\)noothercircuittopologyhasadepth smallerthan\(\log_2n,\)uptoconstantfactors.Theconstants dependonthenumberofinputsofthebuildingblocks.Forexample, ifwereplacesubtreesofthree2-inputANDgateswithone4-inputAND gate,thedepthofthetree-structuredANDgateinFigure4.5 decreasesfrom3to2levels. Figure4.5:Left-skewed(a)andtree-structured(b)conjunctionof8inputswith7binaryANDoperators. Givenatree-structured\(n\)-inputANDgate,weobtainan \(n\)-inputNANDgatebycomplementingtheoutput.The16-input NANDgateinFigure4.4implementseach2-inputANDgateof thetreewitha2-inputCMOSNANDcircuitfollowedbyaninverter.To complementtheoutput,weomittheinverterattherootofthetree. The3-inputNANDgateinFigure4.1isanexampleofan unbalancedNANDtree,wherethenumberofinputsisnotapowerof 2.Incontrast,thetreesinFigure4.4andFigure4.5 arebalanced,becauseeachpathfrominputtooutputhasthesame depth,ornumberofgates. 4.1.3.AsymmetricGates¶ Anasymmetricgatehasinputswithdifferentlogicalefforts. Asymmetricgatesrequireadditionalattentionfromthecircuit designer,butfacilitatefastercircuitsifusedappropriately.The asymmetrymaybecausedbythecircuittopologyorbydeliberate transistorsizingtoreducethedelayofthecriticalpath.We designamajoritygatetomotivateasymmetriccircuittopologies, andthendiscusshowtotradelogicaleffortbetweeninputs. MajorityGate¶ ThemajorityoperationisaternaryBooleanoperation, cf.majorityfunction: (3)\[M(A,B,C)=AB+AC+BC\,.\] Intermsofatruthtablethemajorityoperationisspecifiedas: 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 Asthenamesuggests,theoutputofthemajorityoperationisthe valuethatoccursmoreoftenininputs\(A,\)\(B,\)and \(C.\)Theinverting3-inputmajoritygateinFigure4.6computesthecomplement\(Y=\overline{M}.\) A=0    B=0    C=0 Figure4.6:SymmetricCMOScircuitofinverting3-inputmajoritygateandinteractiveswitchmodel. Wecharacterizethedelayofthemajoritygatebyderivingitslogical effortandparasiticdelay.Themajoritygatehassixarms,each ofwhichisaseriescompositionoftwotransistors.Tomatchthe on-resistancesofthereferenceinverter,wemakethetransistorsin eacharmofthemajoritygatetwiceaswideasthoseofthereference inverter.Thus,asshowninFigure4.7,allpMOS transistorshavewidth\(W_p=4\)andallnMOStransistorshave width\(W_n=2.\)Thesetransistorwidthsmatchthereference inverterforallcombinationsofinputvalues,exceptwhenallinput valuesareequal.Inthiscaseallthreearmsofeitherpull-upor pull-downnetworkareswitchedon,suchthattheparallelcomposition yieldsathreetimessmallerequivalenton-resistance.Weclassify theseinputcombinationsasexceptionallyfast,analogoustothe exceptionalinputcombinationsoftheNANDorNORgates. Figure4.7:Matchedinvertingmajoritygate. EachinputofthemajoritygatedrivestwopMOSandtwonMOS transistors.Therefore,allthreeinputs\(A,\)\(B,\)and \(C\)havelogicaleffort \[g_M(A)=g_M(B)=g_M(C)=\frac{2W_p+2W_n}{C_{in}(inv)}=4\,.\] Thenormalizedoutputcapacitanceofthemajoritygateconsistsof threepMOSandthreenMOStransistors.Therefore,theparasiticdelay ofthemajoritygateis \[p_{M}=\frac{3W_p+3W_n}{C_{out}(inv)}=6\,.\] ComparedtoaNANDorNORgate,themajoritygateisrelativelyslow. Oneoptionforreducingthelogicaleffortandparasiticdelayofthe majoritygateistransistorsharing.ObserveinFigure4.7thatthetwopMOStransistorsthatoneinputdrivesinthe pull-upnetworkareindistinctarms.Thepull-downnetworkexhibits thesamestructureonlywithnMOStransistors.Iftwoarmsshareone transistor,wecanreducethelogicaleffortbyreducingthenumberof transistorsfromtwotoone.Thisdoesnotworkforallinputs simultaneously.AsshowninFigure4.8,ifwesharethetransistorsofinput\(A,\)we cannotalsosharethetransistorsofinputs\(B\)and\(C\) acrossarmswithoutalteringthelogicfunction.However,sharingthe transistorsofinput\(A\)reducesitslogicaleffort,andalso theparasiticdelayoftheentiregate. A=0    B=0    C=0 Figure4.8:Asymmetricinverting3-inputmajoritygatewithtransistorsharingandinteractiveswitchmodel. Sharingthetransistorsofinput\(A,\)asshownin Figure4.8,doesnotaffectthe transistorwidthsofthematchedmajoritygate.Apathfromsupply railtooutputconsistsofaseriescompositionoftwotransistors, eitherinthepull-uporpull-downnetwork,justlikein Figure4.7.Theexceptionalcase,whenallthree inputvaluesareequal,hasalargerequivalenton-resistancethanthe gateinFigure4.7,butisstillfasterthanthe regularcase.Thus,thematchedversionofthemajoritygatein Figure4.8hastransistorwidths \(W_p=4\)and\(W_n=2.\)Whilethelogicaleffortsof inputs\(B\)and\(C\)remainunchanged,transistorsharing halvesthelogicaleffortofinput\(A\): \[\begin{eqnarray*} g_{Masym}(A)&=&\frac{W_p+W_n}{C_{in}(inv)}\=\2\,,\\ g_{Masym}(B)=g_{Masym}(C)&=&\frac{2W_p+2W_n}{C_{in}(inv)}\=\4\,. \end{eqnarray*}\]Sincethelogicaleffortofinput\(A\)differsfromthelogical effortofinputs\(B\)and\(C,\)themajoritygatein Figure4.8isanasymmetricgate. Incontrast,themajoritygateinFigure4.6isa symmetricgate,becauseallinputshaveequallogicaleffort. Ratherthancharacterizinganasymmetricgatebylistingthelogical effortsforallinputs,itissometimessufficienttouseasingle numberinstead.Thetotallogicaleffortisthesumofthe logicaleffortsofallinputs.Forexample,thetotallogicaleffort permitsaquantitativecomparisonofthesymmetricandasymmetric majoritygates.Thesymmetricmajoritygatehastotallogicaleffort \(g_{M}=g_{M}(A)+g_{M}(B)+g_{M}(C)=3\cdot4=12.\) Transistorsharingreducesthetotallogicaleffortoftheasymmetric gateto\(g_{Masym}=2+2\cdot4=10.\) Sharingthetransistorsofinput\(A\)reducesnotonlythe logicaleffortbutalsotheoutputcapacitanceand,thus,the parasiticdelayoftheasymmetricmajoritygate: \[p_{Masym}=\frac{2W_p+2W_n}{C_{out}(inv)}=4\,.\] Notethatwecanconstructalternativegatedesignsbysharingthe transistorsofinput\(B\)orofinput\(C.\)Theresulting asymmetricgatesdonotreducetheoutputcapacitance,however.Only sharingthetransistorsdrivenbyinput\(A\)reducesthe parasiticdelay.Thus,ifwehavethechoice,weprefersharingthose transistorsconnectedtotheoutputofthegateinorderto reducetheparasiticdelayasaddedbenefit. AsymmetricTransistorSizing¶ Theasymmetricmajoritygatesacrificesthesymmetryofthecircuit topologyforareducedlogicaleffortofoneinputwithoutaffecting thelogicaleffortoftheotherinputs.Thebenefitofthereduced logicaleffortisareducedgatedelayforsignaltransitionsonthe correspondinginput.Evenwithasymmetricgatetopology,inherentto NANDandNORgatesforinstance,wecantradelogicaleffortbetween inputsbytransistorsizing.Theresultingasymmetrymaybedesirable tospeedupthecriticalpathofacircuit. Asanexample,considerthe2-inputNANDgateinFigure4.9.Assumethatinput\(A\)iscritical,andwewishto reduceitsdelay.Thus,ourgoalistominimizethelogicaleffortof input\(A,\)whichmeanstoreduce\(g_{nand2}(A)\)from4/3 tothatofareferenceinverter\(g_{inv}=1.\) Figure4.9:MatchedasymmetricNANDgatewithnMOSscalingfraction\(\alpha.\) SincethematchedNANDgatehasnormalizednMOStransistorwidths \(W_n(A)=W_n(B)=2,\)reducingwidth\(W_n(A)\)to1 reducestheinputcapacitanceofinput\(A\)asdesired.However, ifallwedoisreducetheinputcapacitanceofinput\(A,\)the gatebecomesmismatchedw.r.t.thereferenceinverter.Infact, halvingthewidthofthenMOStransistordoublesitson-resistance, whichresultsinasmalleroutputcurrent.Consequently,thegate wouldbeslowerratherthanfasterasplanned.Toobtainadelay reduction,weneedtoreducethelogicaleffort,i.e.wewishto reducetheinputcapacitanceofinput\(A\)withoutchangingthe equivalenton-resistanceofthepull-downnetwork.Transistorsharing inthemajoritygatehasexactlythiseffect. Incaseofthe2-inputNANDgate,wecanbalanceachangeofwidth \(W_n(A)\)byacorrespondingchangeof\(W_n(B)\)sothatthe pull-downnetworkoftheasymmetricNANDgateremainsmatchedtothe referenceinverter.Morespecifically,matchinganasymmetric2-input NANDgaterequiresthatequivalenton-resistance\(R_n(A)+ R_n(B)\)oftheseriescompositionofnMOStransistorsmustbeequalto on-resistance\(R_n(inv)\)ofthereferenceinverter: \[R_n(A)+R_n(B)=R_n(inv)\,.\] Sincetheon-resistanceisindirectlyproportionaltothetransistor width,weobtainthismatchingconstraintfortheasymmetricNANDgate: \[\begin{split}\begin{eqnarray*} \frac{1}{W_n(A)}+\frac{1}{W_n(B)}&=&\frac{1}{W_n(inv)}\\ \Leftrightarrow\qquadW_n(A)+W_n(B)&=&W_n(A)W_n(B)\,, \end{eqnarray*}\end{split}\] becausethereferenceinverterhasannMOStransistorofwidth \(W_n(inv)=1.\)Wecanfulfillthisconstraintwithascaling fraction\(\alpha,\)\(0.Forexample,for \(n=3,\)function\(Y=A\oplusB\oplusC\)equals1if thenumberof1-inputsis1or3.Thetruthtableshowsthe3-input XORfunctionorodd-parityfunction. 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 1 Theodd-paritypropertysuggestsadesignforanXORCMOScircuit.To buildan\(n\)-inputXORgate,weneed\(2^n\)armswith \(n\)transistorseach.Halfofthearmsareinthepull-up network,oneperminterm,andeachhasanoddnumberofcomplemented inputs.Theotherhalfofthearmsareinthepull-downnetwork.For eachcombinationofinputvalues,exactlyonearmisswitchedon. Figure4.16showstheCMOScircuitfora3-input XORgate.Wheneveryoutoggleoneoftheinputsoutput\(Y\) toggles,becausechangingoneinputchangestheparityfromoddto evenorviceversa. A=0    B=0    C=0 Figure4.16:CMOScircuitof3-inputXORgateandinteractiveswitchmodel. Thematched3-inputXORgatehaspMOStransistorsofwidth\(W_p =6\)andnMOStransistorsofwidth\(W_n=3.\)Eachofthesix inputs\(A,\)\(\overline{A},\)\(B,\) \(\overline{B},\)\(C,\)and\(\overline{C}\)drivestwo pMOSandtwonMOStransistors,resultinginalogicaleffortof \(g_{xor3}=6\)perinput.TheoutputisconnectedtofourpMOS andfournMOStransistors,thatcontributetotheoutputcapacitance andparasiticdelay\(p_{xor3}=12.\)Sincethegatetopology generalizesto\(n\)inputs,wefindthatthe\(n\)-input XORgatehaslogicaleffort \[g_{xorn}=\frac{2^{n-2}\cdot2n+2^{n-2}\cdotn}{3}=n2^{n-2}\] perinput.Theparasiticdelayofthe\(n\)-inputXORgate amountsto \[p_{xorn}=\frac{2^{n-1}\cdot2n+2^{n-1}\cdotn}{3}=n2^{n-1}\,.\] Theexponentialgrowthofbothlogicaleffortandparasiticdelayin thenumberofinputs\(n\)limitstheapplicabilityofthisCMOS circuittosmall\(n.\)Forlargernumbersofinputs tree-structuredtopologiesbasedon2-input XORgatesasbuildingblocksarefaster. AsymmetricXORGates¶ WecanreducethelogicaleffortandparasiticdelayoftheXORgate bytransistorsharing.Noticein Figure4.16thateachinputdrivestwopMOSand twonMOStransistors.Iftwoarmsshareonetransistor,wecanreduce thelogicaleffortofthecorrespondinginput.Sharingdoesnotwork forallinputssimultaneously.AsshowninFigure4.17wesharethetransistorsofinputs\(A\)and \(\overline{A}\)toreducetheirlogicaleffortsandtheparasitic delayoftheentiregate.Then,wecanalsosharethetransistorsof inputs\(C\)and\(\overline{C},\)butnotthoseofinputs \(B\)and\(\overline{B}\)withoutalteringthelogic function. A=0    B=0    C=0 Figure4.17:AsymmetricCMOScircuitof3-inputXORgateandinteractiveswitchmodel. TomatchtheXORgate,observethatanypathfromsupplytooutput consistsofaseriescompositionof3transistors,justlikeanarmin Figure4.16.Therefore,sharingtransistors doesnotaffectthetransistorwidthsofthematchedgate.Likethe symmetricXORgate,allpMOStransistorsofthematchedgatehave width\(W_p=6\)andallnMOStransistorswidth\(W_n=3.\) Asaresult,theXORgateinFigure4.17is asymmetric.Thelogicaleffortsofinputs\(A,\) \(\overline{A},\)\(C\)and\(\overline{C}\)are \[g_{xor3asym}(A)=g_{xor3asym}(\overline{A})=g_{xor3asym}(C)=g_{xor3asym}(\overline{C})=\frac{W_p+W_n}{3}=3\,,\] whilethelogicaleffortsofinputs\(B\)and\(\overline{B}\)remain unchangedcomparedtothesymmetricdesign: \[g_{xor3asym}(B)=g_{xor3asym}(\overline{B})=\frac{2Wp+2W_n}{3}=6\,.\] Sharingthetransistorsconnectedtotheoutputofthegatehalvesthe outputcapacitance,andtherefore,theparasiticdelayofthe asymmetricXORgateis \[p_{xor3asym}=\frac{2W_p+2W_n}{3}=6\,.\] TheasymmetricXORgatehassmallertotallogicaleffortandsmaller parasiticdelaythanthesymmetricgate. XORGatesandDuality¶ Thesymmetric2-inputXORgateinFigure4.15violatesthe principleofduality,becausethepull-upandpull-downnetworksare notdualsofeachother.Inthissection,weusethe2-inputXOR gatetodemonstratethatdualityisasufficientbutnotanecessary propertyofCMOSgates. Recallthetruthtableofthe2-inputXORgate,\(Y=A\oplusB\): 0 0 0 0 1 1 1 0 1 1 1 0 TheSOPnormalformfortheXORfunctionis \[Y=\overline{A}B+A\overline{B}\,.\] Interpretthisequalityas\(Y=1\)if\(A=0\)AND\(B=1\) ORif\(A=1\)AND\(B=0.\)Negatepredicates\(B=1\) and\(A=1\)to\(\overline{B}=0\)and\(\overline{A}=0,\) tosimplifytheargumentfortheswitchmodelofpMOStransistors. Then,weobtaintheequivalentXORlogic: \(Y=1\)if(\(A=0\)AND\(\overline{B}=0\))ORif(\(\overline{A}=0\)AND\(B=0\)). TheBooleanexpressionconsistsofANDandORoperations,which translatesdirectlyintotheseries-parallelpull-upnetworkin Figure4.18(a).Giventhepull-upnetwork, wecanderivethepull-downnetworkbyformingthedual,asshownin Figure4.18(b).Wetransformtheparallel armsofthepull-upnetworkintoaseriescompositionofparallelnMOS transistors.Theinteractiveswitchmodelenablesyoutoverifythe truthtableoftheXORgate. A=0    B=0 Figure4.18:2-inputXORgate:(a)pull-upnetworkderivedfromlogicfunction,(b)thepull-downnetworkisthedualofthepull-upnetwork,and(c)interactiveswitchmodel. TheXORgateinFigure4.18hasthesame pull-upnetworkasouroriginalXORgateinFigure4.15,up totheorderofthepMOSgateinputs.However,thepull-downnetworks aredifferent.ToarriveattheXORgateinFigure4.15, considerthetruthtableoftheXORgateagain,nowwiththegoalto derivethepull-downnetworkfromthelogicfunction.Weseethat \(Y=0\)if\(A=0\)AND\(B=0\)ORif\(A=1\)AND \(B=1.\)TofittheswitchmodelofnMOStransistors,negatethe predicates\(A=0\)and\(B=0\)to\(\overline{A}=1\)and \(\overline{B}=1,\)andwefindtheXORlogic: \(Y=0\)if(\(\overline{A}=1\)AND\(\overline{B}=1\))ORif(\(A=1\)AND\(B=1\)). ThisBooleanexpressiontranslatesdirectlyintotheseries-parallel pull-downnetworkinFigure4.19(a).Deriving thedualofthepull-downnetworkyieldsthepull-upnetworkin Figure4.19(b). A=0    B=0 Figure4.19:2-inputXORgate:(a)pull-downnetworkderivedfromlogicfunction,(b)thepull-upnetworkisthedualofthepull-downnetwork,and(c)interactiveswitchmodel. TheXORgateinFigure4.19hasthesame pull-downnetworkasouroriginalXORgateinFigure4.15, butadifferentpull-upnetwork.However,wearriveattheXORgate designinFigure4.15bycombiningthepull-upnetworkof Figure4.18withthepull-downnetworkof Figure4.19.Thisdesignsavesawireand issimplerthanthedesignswithdualnetworks,becausethefourarms areindependent.Furthermore,theXORgatedemonstratesthatCMOS gatesdonotnecessarilyhavepull-upandpull-downnetworksthatare dualsofeachother.The3-inputXORgatesandthemajoritygate areexamplesofCMOSgateswhosepull-upandpull-downnetworksare notdualseither. XORCMOSCircuits¶ The2-inputXORgateinFigure4.15requirescomplementedand uncomplementedinputs.Infact,wemayspecifythisCMOSgateasa logicfunctionoffourinputs,XOR\((A,B,C,D),\)withthe additionalconstraints\(C=\overline{A}\)and\(D= \overline{B},\)thatthedrivingcircuithastoobey.Theinput specificationdistinguishestheXORgatefromotherCMOSgates,the NANDandNORgatesforexample.The2-inputNANDandNORgateshave twoinputsnotonlybecausetheyrealizebinarylogicfunctionsbut alsointermsofthenumberofinputwiresthattheirCMOS implementationshave.Incontrast,wedefinetheXORgateasabinary logicfunction,drawtheXORgatesymbolwithtwo inputs,butourCMOSgateinFigure4.15requiresfourinputs.The reasonisthatthereexistsno2-inputCMOSgateforthe2-inputXOR logicfunction,becauseCMOSgatescanimplementmonotonically decreasingfunctionsonly.Hence,implementinga2-inputXORlogic gaterequiresaCMOScircuitratherthanaCMOSgate.Inthis section,wediscussseveralCMOSimplementationsofthe2-inputXOR logicgate. WebeginwithastraightforwardextensionoftheCMOSgatein Figure4.15.Toobtaina2-inputXORgate,wegeneratethe complementsofinputs\(A\)and\(B\)bymeansofinverters. TheresultingimplementationoftheXORlogicgateisshownin Figure4.20. Figure4.20:2-inputXORgatewithinputinverters. Ifwewishtousethe2-inputXORgateinFigure4.20asa buildingblockfortheconstructionoflargercircuits,weneedto characterizeitsdelayasafunctionoftheelectricaleffort.Since theXORlogicgateconsistsofinvertersandanXORCMOSgate,wecan scaletheinvertersandtheXORCMOSgateindependentlytominimize itsdelay.SincetheXORcircuitisareconvergingbranch,wecould applythe2d-analysismethodtodeterminethe scalefactorsforagivenelectricaleffort.However,acloselook revealswhya2d-analysismaynotyieldthefastestdesign.First, noticethatthecircuitissymmetricininputs\(A\)and \(B,\)ifweuseasymmetricXORCMOSgate.Thus,thecircuithas onepathofinterest,sayfrominput\(A\)tooutput\(Y.\) Assumetheinverterhasinputcapacitance\(C_1.\)TheXORCMOS gateimposesaloadofonepMOSandonenMOSgatecapacitanceoneach legofaforkdrivenbyinput\(A.\)Let\(C_2\)betheinput capacitanceofinputs\(A\)and\(\overline{A}\)oftheXOR CMOSgate,thenourXORcircuitincludesa1-forkwithequalloads,as showninFigure4.21. Figure4.21:Thepathofinterestof2-inputXORgateinFigure4.20 includesa1-forkwithequalloads. Recallthatweshouldavoid1-forks,butletusignorethislessonfor amoment.Instead,weinsistonminimizingthedelayofthepathfrom inputtooutputinFigure4.21givenelectricaleffort\(H.\) Noticethatthecircuitdoesnotpermitequalizingthedelaysofthe legsofthefork.Instead,thepaththroughtheinverterlegaddsthe inverterdelaytothedelaythroughtheXORCMOSgate.Thus,allwe candobygatesizingistominimizethedelayoftheslowerlegwith theinverter.Thisleavesuswiththeoptimizationproblemofhow muchinputcapacitancetoassigntotheon-pathinverterversusthe off-pathXORCMOSgate.Asdiscussedinforkdesign,weintroducefactor\(\alpha\)inrange\(0< \alpha<1\)tosplittheinputcapacitancebetweentheinverterand theXORCMOSgate: \[C_1=\alphaC_{in}\,,\qquadC_2=(1-\alpha)C_{in}\,,\] suchthat\(C_1+C_2=C_{in}.\)Then,thestageefforts oftheinverterandtheXORCMOSgateare: \[f_{inv}=g_{inv}h_{inv}=g_{inv}\,\frac{C_2}{C_1}=\frac{1-\alpha}{\alpha}\,,\qquadf_{xor2}=g_{xor2}h_{xor2}=g_{xor2}\,\frac{HC_{in}}{C_2}=2\,\frac{H}{1-\alpha}\,.\] Now,thelowerlegoftheforkhasdelay \[D_l=f_{xor2}+p_{xor2}=2\,\frac{H}{1-\alpha}+4\,,\] andtheupperleghasdelay \[D_u=(f_{inv}+p_{inv})+(f_{xor2}+p_{xor2})=\frac{1-\alpha}{\alpha}+2\,\frac{H}{1-\alpha}+5\,,\] where\(D_u=(f_{inv}+p_{inv})+D_l.\)Wecanminimize \(D_u\)bysettingthederivative\(dD_u/d\alpha\)tozero, andfind \[\alpha=\frac{\sqrt{2H}-1}{2H-1}\,.\] ThuswhenusingtheXORlogicgateaspartofalargercircuit,wecan choose\(\alpha\)dependingonelectricaleffort\(H\)to minimizeitsdelay. IfwewishtominimizethedelayoftheXORlogicgatefurther,we couldmaketheXORCMOSgateasymmetricsuchthatthelogicaleffort ofthecomplementedinput\(\overline{A}\)issmallerthanthat oftheuncomplementedinput,soastospeedupthepaththroughthe inverterleg.Alternatively,wemayrecallourlessonthata2-fork ispreferabletoa1-fork.Hence,oursecondattemptforanXORlogic gateuses2-forkstogeneratethecomplementedanduncomplemented inputs,asshowninFigure4.22. Figure4.22:2-inputXORgatewith2-forkinputs. WecananalyzethisXORcircuitwithour2d-analysismethod.ThepathofinterestisshowninFigure4.23,witheffortdelay\(d_1\)assignedtotheinvertersof the2-fork,andeffortdelay\(d_2\)fortheXORCMOSgate. Figure4.23:Thepathofinterestofthe2-inputXORgateinFigure4.22includesa2-forkwithequalloads. The2d-analysisenablesustoexpresseffortdelay\(d_2\)asa functionof\(d_1\): \[d_2=2H\Bigl(\frac{4}{d_1^2}+\frac{1}{d_1+1}\Bigr)\,,\] suchthatthepatheffortdelaybecomes \[D=d_1+d_2=d_1+\frac{8H}{d_1^2}+\frac{2H}{d_1+1}\,.\] Minimizingthepatheffortdelaybysettingthederivative\(\partialD/\partiald_1\)tozeroyieldsthepolynomialin\(d_1\): \[d_1^5+2d_1^4+(1-2H)d_1^3-16Hd_1^2-32Hd_1-16H\,.\] Foragivenelectricaleffort\(H,\)wedeterminedelay \(d_1\)byfindingthepositiverealrootofthepolynomial. Then,theminimumdelayoftheXORlogicgateis\(\hat{D}=d_1 +d_2+P,\)where\(P=2p_{inv}+p_{xor2}=6.\) Figure4.28belowcomparesthedelaysofthetwoXOR gateswith1-forkand2-forkinputsasafunctionofelectricaleffort \(H.\)Notunexpectedly,forall\(H\)the2-forkdesignis fasterthanthe1-forkdesign.Furthermorethe1-forkdesignslows downmuchmorerapidlythanthe2-forkdesignforincreasing \(H.\) Thespeeddifferencebetweenthe1-forkand2-forkXORgatedesigns motivatesthesearchforevenfasterXORgatecircuits.Inthe following,wepresentthreealternativedesigns.Webeginwiththe reconvergingNANDcircuitinFigure4.24ontheleft. UsingBooleanalgebra,itisstraightforwardtoverifythatthis circuitimplementsthe2-inputXORfunction.Duringourstudyof reconvergingbranches,wehave identifiedthe2-forkstylemodificationinFigure4.24ontherightassuperiorbecauseitisfaster.Thecomparison ofthedelaysinFigure4.28showsthatthe reconvergingNANDcircuitisslowerthanthe2-forkXORgatecircuit upto\(H=47.\)Forlargerelectricalefforts,thereconverging NANDcircuitisfaster. Figure4.24:Thereconvergingbranchcircuit implementsa2-inputXORgate(left).The2-forkstyle(right) yieldsafastercircuit. SinceNANDgateshavenotonlyarelativelysmalllogicaleffortbut alsosmallparasiticdelaycomparedtoother2-inputgates,a2-level NANDcircuitisanothertopcontenderforanXORgate.Again,wemay usea1-forkorthe2-forkshowninFigure4.25to generatethecomplementedanduncomplementedinputs.The2-forkis fasterthanthe1-fork,asusual.TheresultingXORcircuithasfour stagesonthe2-inverterleg,sothatweexpectthiscircuittobe bettersuitedforlargerelectricalefforts. Figure4.25:A2-levelNANDcircuitwith2-forkinputsimplementsa2-inputXORgate. Todeterminetheminimumdelayasafunctionofelectricaleffort \(H,\)weapplythe1d-analysismethodwith effortdelay\(d\)assignedtothegatesasshownin Figure4.26.The1d-analysisofthecircuit yieldsthepolynomial \[d^5+\frac{1}{2}d^4-\frac{8}{9}Hd^2-\frac{16}{9}Hd-\frac{8}{9}H\,.\] Givenelectricaleffort\(H,\)thepositiverealrootofthe polynomalequalseffortdelay\(d,\)forwhichthecircuithas minimumpathdelay\(\hat{D}=4d+6.\) Figure4.28plots\(\hat{D}\)overelectrical effort\(H.\)Weseethatthe2-forkXORgateisfasterupto \(H=14.\)For\(H\ge15,\)the4-stageNANDcircuitis faster. Figure4.26:Pathofinterestof2-levelNANDcircuitwith2-forkinputs. Compoundgatesenableustoimplementtwo-levellogicinacompact fashion.Thus,wemayimplementanXORgateusingOAIorAOIcompound gates.Figure4.27showsontheleftanXORcircuitdesignbased onanOAIgate.ThiscircuitusesaNANDgatethatbehaveslikethe inverterofa1-forkdrivingtheOAIgate.Thiscircuitisindeed slowerthanthemorecomplexversionontherightofFigure4.27 thatusesa2-forkstructureattheinputsandaAOIgate. Figure4.27:2-inputXORgatebasedonanOAIcompoundgate(left),andwith2-forkinputsandanAOIcompoundgate(right). WeanalyzetheAOIcircuitusinga2d-analysis, byassigningeffortdelay\(d_1/2\)totheNANDgateandthe inverterintheupperlegandeffortdelay\(d_1+2\)tothelower legofthefork,andeffortdelay\(d_2\)totheAOIgate.Then, the2d-analysispermitsexpressing\(d_1\)asafunctionof \(d_2.\)Minimizingthepatheffortdelaybysettingits derivativew.r.t.\(d_1\)tozeroyieldspolynomial \[d_1^5+4d_1^4+(4-2H)d_1^3-\frac{160}{9}Hd_1^2-\frac{640}{9}Hd_1-\frac{640}{9}H\,.\] Givenelectricaleffort\(H,\)thepositiverealrootsofthe polynomialyieldminimumpathdelay\(\hat{D}=d_1+d_2+ 16/3,\)whichisplottedinFigure4.28asafunctionof \(H.\)WefindthattheAOIcircuithascompetitivedelays xacrosstherangeof\(H,\)butforno\(H\)istheAOIcircuit thefastestXORgate. Figure4.28:MinimumdelaysofXORcircuitsoverelectricaleffort. ThecomparisoninFigure4.28suggeststhatthefastestXOR implementationdependsonelectricaleffort\(H.\)Inparticular, amongthestudiedalternatives,the2-forkXORcircuitof Figure4.22isfastestfor\(H<12,\)whereasfor \(H\ge12,\)thetwo-levelNANDcircuitofFigure4.25isfastest. XNORGates¶ TheXNORgateisverysimilartotheXORgate.Logically,theXNOR gateproducesthecomplementoftheXORgate.Thus,an\(n\)-input XNORgateimplementstheeven-parityoperation,whichoutputs1if thenumberofinputswithvalue1iseven.Thetruthtablebelow showstheXNORfunctionfor\(n=3,\)\(Y=\overline{A\oplusB \oplusC},\)whichequals1ifthenumberof1-inputsis0or2. 0 0 0 1 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 0 TheCMOSimplementationofa2-inputXNORgateisshownin Figure4.29.Likethe2-inputXORgate,it consistsoffourarms.Thepull-upandpull-downnetworksarenot dualsofeachother.NoteworthyisthefactthatXORandXNORCMOS gateshavethesametopology.Inparticular,wedonotneedanoutput invertertoimplementthecomplement,asrequiredfortheANDandOR gates. A=0    B=0 Figure4.29:CMOScircuitforXNORgateandinteractiveswitchmodel. SincethetopologyoftheXNORgateequalsthatoftheXORgate,both logicaleffortandparasiticdelayoftheXNORgateareequaltothose oftheXORgate: \[g_{xnor2}=2\,,\qquadp_{xnor2}=4\,.\] XNORgateswithmorethantwoinputscanbeconstructedanalogousto theXORgate.AlsoanalogoustotheXORlogicgatearethedesign issuesofCMOScircuitsfora2-inputXNORlogicgate. 4.1.6.SkewedGates¶ Whenoptimizingacircuitforspeed,wemaywantthefalling transitionofasignalfromhightolowvoltagetobefasterthanthe risingtransitionfromlowtohighvoltageorviceversa.Inthis section,wediscussskewedgateswhosecriticaltransitionis fasterthanthenoncriticaltransition.Incontrast,CMOSgates withequalrisingandfallingdelaysareunskewedornormal-skew gates.WedistinguishbetweenHI-skewgatesandLO-skew gates.InaHI-skewgatetherisingoutputtransitionisthe faster,criticaltransition,andinLO-skewgatesthefallingoutput transitioniscritical. DesignandAnalysis¶ Wecanskewagatebytransistorsizing.Forexample,considerthe matched2-inputNANDgateinFigure4.30(a).By definition,thetransistorsofthematchedNANDgatearesizedto provideequaldrivecurrentsfortherisingandfallingtransitions. Furthermore,thedrivecurrentsareequaltothoseofthereference inverter.Sincethedelayofagatedependsonitsdrivecurrent,the risingandfallingdelaysareequalifthemagnitudesofthedrive currentsofthecorrespondingtransitionsareequal.Thekeyinsight fordesigningaskewedgateistoshrinkthetransistorsintheCMOS networkthatdrivestheuncriticaltransition.Forexample,ifwe wishtospeeduptherisingtransitionoftheNANDgate,weshrink thenMOStransistorsofthepull-downnetwork.Theeffectisthatthe pMOStransistorsdeliverthesamedrivecurrentasthematchedNAND gateontherisingtransition,butsmallernMOStransistorsreducethe logicaleffortofthegate,resultinginafastertransition.For example,theHI-skewNANDgateinFigure4.30(b) halvesthewidthsofthenMOStransistorscomparedtothematchedNAND gatetospeeduptherisingtransition. Figure4.30:Skewinga2-inputNANDgate:(a)matchedgate,(b)HI-skewgate,(c)down-scaledgate. TocharacterizethedelayoftheHI-skewNANDgate,wedetermineits logicaleffortandparasiticdelay.However,duetotheunmatched transistorsizes,logicaleffortandparasiticdelaydifferforthe risingandfallingtransitions.Weuse\(g_u\)and\(p_u\)to denotethelogicaleffortandparasiticdelayoftherisingoutput transitiondrivenbythepull-upnetwork,and\(g_d\)and \(p_d\)forthefallingoutputtransitiondrivenbythepull-down network.Thenthedelaysoftherisingandfallingtransitionsof askewedgateare: \[\begin{eqnarray} d_u&=&g_uh+p_u\,,\\ d_d&=&g_dh+p_d\,,\\ \end{eqnarray}\]where\(h\)istheelectricaleffortofthegate. Weconsidertherisingoutputtransitionfirst.Theoutputofa 2-inputNANDgatetransitionsfrom0to1ifinitiallybothinputs \(A\)and\(B\)are1,andoneoftheinputsswitchesfrom1 to0.ThecorrespondingpMOStransistorinthepull-upnetworkdrives theoutput.WhichoneofthetwopMOStransistorsswitchesdoesnot matterinthisexample,becausetheNANDgateissymmetric.Sincethe widthofthepMOStransistorsoftheHI-skewgateequalsthewidthin thematchedNANDgate,bothgatesproducethesamedrivecurrent. Furthermore,becausethematchedNANDgatehasthesamepull-updrive currentasthereferenceinverter,weconcludethattheHI-skewgate hasthesamepull-updrivecurrentasthereferenceinverter.Now, recallourdefinitionofthelogicaleffortofaCMOSgateasthe ratioofitsinputcapacitancetothatofthereferenceinverter, assumingthattheCMOSgateissizedtodeliverthesamedrivecurrent asthereferenceinverter.Sincethedrivecurrentsareequal,the logicaleffort\(g_u\)oftherisingtransitionoftheHI-skew gateistheratiooftheinputcapacitanceoftheHI-skewgateandthe inputcapacitanceofthereferenceinverter.Accordingto Figure4.30(b),eachinputhasinputcapacitance \(C_{in}(hi)=W_p+W_n=3,\)because\(W_p=2\)and \(W_n=1,\)sothat \[g_u=\frac{C_{in}(hi)}{C_{in}(inv)}=\frac{3}{3}=1\,.\] Shrinkingthepull-downtransistorsoftheHI-skewgateretainsthe drivecurrentthroughthepull-upnetworkwhilereducingtheinput capacitance.Asaresultlogicaleffort\(g_u=1\)isless thanthelogicaleffortofthematchedgate\(g_{nand2}=4/3.\) Similarly,theparasiticdelayoftherisingtransitionoftheHI-skew gateis \[p_u=\frac{C_{out}(hi)}{C_{out}(inv)}=\frac{2\cdot2+1}{3}=\frac{5}{3}\,.\] Wefindthatparasiticdelay\(p_u\)islessthanthatofthe matchedgate\(p_{nand2}=2.\) Next,wedetermine\(g_d\)and\(p_d\)ofthefalling transitionoftheHI-skewgate.Toapplythedefinitionoflogical effort,weconstructthedown-scaledNANDgateshownin Figure4.30(c).Thedown-scaledgatehasthe samenMOStransistorwidthsastheHI-skewgate,sothattheirdrive currentsareequal.Wehalvethewidthofthepull-uptransistors,so thatthedown-scaledgateisascaledversionofthematchedNANDgate withscalefactor\(\gamma=1/2.\)Now,wecanarguethatthe HI-skewNANDgatehasthesamepull-downdrivecurrentasthematched NANDgatescaledby\(\gamma=1/2,\)whichinturnhasthesame pull-downdrivecurrentasareferenceinverterscaledby \(\gamma=1/2.\)Therefore,thelogicaleffortofthefalling transitionoftheHI-skewgateistheratiooftheinputcapacitance oftheHI-skewgateandtheinputcapacitanceofthescaledreference inverter: \[g_d=\frac{C_{in}(hi)}{\gammaC_{in}(inv)}=\frac{3}{\frac{1}{2}\cdot3}=2\] foreachinput.Thecostofthereducedlogicaleffort\(g_u= 1\)oftherisingtransitionisanincreasedlogicaleffort\(g_d =2\)ofthefallingtransition,comparedto\(g_{nand2}=4/3\)of thenormal-skewgate.Analogously,theparasiticdelayofthefalling transitionoftheHI-skewgateis \[p_d=\frac{C_{out}(hi)}{\gammaC_{out}(inv)}=\frac{5}{\frac{1}{2}\cdot3}=\frac{10}{3}\,.\] Therisingandfallinglogicaleffortsandparasiticdelaysare relatedthroughscalefactor\(\gamma\)ofthedown-scaledmatched gate:\(g_u=\gammag_d\)and\(p_u=\gammap_d.\)Notice thatscalefactor\(\gamma=2\)isalsothescalefactorbywhich weshrankthepull-downnMOStransistorsoftheHI-skewgatetobegin with.Thisobservationsimplifiesthedesignandanalysisofaskewed gatebasedthemodeloflogicaleffort.Belowistheprocedureto designandanalyzeaHI-skewgate;theprocedurefora LO-skewgatecanbeviewedasdual: Chooseascalefactor\(\gamma\)forthenMOStransistorsofthe pull-downnetworkofthematchedgate. Thelogicaleffort\(g_u\)oftherisingtransitionisthe ratiooftheinputcapacitanceoftheHI-skewgateandthe referenceinverter.Thefallingtransitionhaslogicaleffort \(g_d=g_u/\gamma.\) Theparasiticdelay\(p_u\)oftherisingtransitionisthe ratiooftheoutputcapacitanceoftheHI-skewgateandthe referenceinverter.Thefallingtransitionhasparasiticdelay \(p_d=p_u/\gamma.\) TofacilitateacomparisonbetweenaHI-skewandnormal-skewgates, weusetheaverageoftherisingandfallingquantities: \[g_{hi}=\frac{g_u+g_d}{2}\,,\qquadp_{hi}=\frac{p_u+p_d}{2}\,.\] Theaverageprovidesanaccuratemeasureofthetransitiondelayofa gateovertime.Whenthegateisinoperationaspartofalarger circuit,halfofalloutputtransitionsarerisingandtheotherhalf arefallingtransitions.FortheHI-skewNANDgateinFigure4.30,theaveragelogicaleffortis\(g_{hi}=3/2\)andthe averageparasiticdelay\(p_{hi}=5/2.\)Thus,althoughour HI-skewNANDgatehasafasterrisingtransitionthantheunskewed gate,bothaveragelogicaleffortandparasiticdelayarelargerthan \(g_{nand2}=4/3\)and\(p_{nand2}=2\)oftheunskewed gate. FastSkewedGates¶ OurobservationthattheHI-skewNANDgatehasalargeraveragedelay thantheunskewedNANDraisesthequestionwhetheraskewedgate existsthatisfasterthanitsunskewedversion.Thisisthecase indeed.TheLO-skew2-inputNORgateinFigure4.31(b) hasasmalleraveragelogicaleffortandsmalleraverage parasiticdelaythanthenormal-skewNORgate. Figure4.31:Skewinga2-inputNORgate:(a)matchedgate,(b)LO-skewgate,(c)up-scaledgate. TheLO-skewNORspeedsupthefallingtransitionbyshrinkingthe pull-uppMOStransistors.InFigure4.31,wescalethepMOS transistorsofthematchedNORgatewithfactor\(\gamma=3/4\) toobtaintransistorwidth\(W_p=3.\)SincethenMOS transistorsareunchangedcomparedtothematchedNORgate,thedrive currentofthefallingtransitionthroughthepull-downnetworkofthe LO-skewgateisthesameasthepull-downdrivecurrentofthematched NORgateandthereferenceinverter.Therefore,thelogicaleffortof thefallingtransitionis\(g_d=C_{in}(lo)/C_{in}(inv)= 4/3.\)Thelogicaleffortoftherisingtransitionisthen\(g_u =g_d/\gamma=16/9.\)Notethat\(g_u\)istheratioofthe inputcapacitancesoftheLO-skewgateandthe\(\gamma\)-scaled referenceinverter,and\(\gamma=3/4\)isequaltothescalefactorof theup-scaledmatchedNORgateinFigure4.31(c). TheaveragelogicaleffortoftheLO-skewNORgateis\(g_{lo}= 14/9,\)whichislessthanthelogicaleffort\(g_{nor2}=5/3\)of thenormal-skewgate.Similarly,wefindtheparasiticdelays \(p_d=5/3\)and\(p_u=20/9.\)Theaverageparasiticdelay of\(p_{lo}=35/18\)unitsislessthantheparasiticdelay \(p_{nor2}=2\)ofthenormal-skewNORgate. Weconcludethatforallelectricalefforts\(h,\)theaverage delayoftheLO-skewNORgate,\(d_{lo}(h)=(14/9)h+35/18,\) isslightlylessthanthedelayofthenormal-skewNORgate, \(d_{nor2}(h)=(5/3)h+2.\)Wecanformulateaminimization problemtodeterminescalefactor\(\gamma\)fortheLO-skewNOR gatesuchthattheaveragedelayassumesitsminimum.Usingcalculus, wefindthatscalefactor \[\gamma=\frac{1}{2}\sqrt{\frac{h+2}{h+1}}\] minimizestheaveragedelayifitischosenasafunctionof electricaleffort\(h.\)For\(h\ge1,\)therangeof \(\gamma\)isverysmall,\(1/2B\)or \(A\leB,\)arecommonlyimplementedwithanarithmetic circuit.However,fortwospecialcases, equalitycomparisonandequalitytozero,simplercircuitsexist. 4.2.1.EqualitytoZero¶ Givenan\(n\)-bitsignal\(A,\)wewishtodeterminewhether \(A=0\)istrueorfalse.Equality\(A=0\)istrue,if foreachsignal\(A_i,\)\(0\lei0,\)evenif\(n\)isnotapowerof2.Ifweare willingtogenerateoneselectsignalperdatainput,e.g.bymeansof adecoder,wecanreplicatetheselectarm\(n\)timesto constructthe\(n\)-waymultiplexerinFigure4.36. Selectarm\(i\)drivesthecomplementof\(D_i\)ontooutput \(Y,\)ifselectinput\(S_i=1.\)Allotherselectsignals \(S_j,\)\(j\nei,\)mustbe\(S_j=0.\)Otherwise,two enabledselectarmsmightdrivedifferentvaluesonoutput\(Y,\) effectivelyshortcircuiting\(V_{DD}\)andGND. Figure4.36:An\(n\)-waymultiplexerwithoneselectarmperdatainput. SinceeachselectarmconsistsoftwoseriespMOStransistorsinthe pull-upnetworkandtwoseriesnMOStransistorsinthepull-down network,thematched\(n\)-waymultiplexerhaspMOSwidth \(W_p=4\)andnMOSwidth\(W_n=2.\)Therefore,the logicaleffortofeachdatainputis\(g_{mux}(D_i)=2,\) independentofthenumberofinputs.Thispropertyisuniquefeature ofthemultiplexercircuit.Unfortunately,theparasiticdelay \(p_{mux}(n)=2n\)growsproportionaltothenumberofinputs \(n.\)Nevertheless,wenotethattheeffortdelayofthe multiplexercircuitisindependentofitsfan-in. Forlargernumbersofinputs\(n,\)theparasiticdelayofthe \(n\)-waycircuitinFigure4.36maydominatethetotal delay.Inthiscase,tree-structuredmultiplexers provideafastalternative.Asanexample,considera4:1multiplexer withfourdatainputsandtwoselectinputs,asshownontheleftin Figure4.37.The4:1multiplexersteersdatainput \(D_i\)tooutput\(Y\)iftheselectsignalequals\(i\) inbinaryformat.Notethat\(k\)selectinputsenableusto selectoneof\(n=2^k\)datainputs,becauseabinarynumber with\(k\)bitscanrepresentunsignednumbersinrange\([0, 2^k-1].\)Inparticular,eachofthe\(k\)selectsignalsmaybe usedasselectinputforoneof\(k\)levelsinabinarytreeof 2:1muxeswith\(n=2^k\)datainputs.Themultiplexertreeon therightinFigure4.37has\(4=2^k\)inputsand \(k=2\)levels. Figure4.37:A4:1multiplexer(left)builtasatreeof2:1multiplexers(right). Thefunctionalityofthe4:1multiplexeriseasytoverifybyperfect induction.Forexample,if\(S=01,\)i.e.\(S_1=0\)and \(S_0=1,\)thenthelevel-1outputmuxsteersits 0-inputto\(Y,\)because\(S_1=0.\)The0-input ofthelevel-1muxisdrivenbythetoplevel-0mux,whichsteers \(D_1\)toitsoutput,because\(S_0=1.\)Thereforeoutput \(Y=D_1\)for\(S=01.\)Weargueanalogouslyaboutthe othercasesoftheperfectinduction: 0 0 \(D_0\) 0 1 \(D_1\) 1 0 \(D_2\) 1 1 \(D_3\) Adelayanalysisrevealsthata\(4\)-waymuxwithindependent selectarmshasadelayof\(D_{4way}=2H+8\)perdatainput, whereasthe4:1treemuxwithtwo2-waymuxesonitscriticalpathhas aminimumdelayof\(\hat{D}_{tree}=4\sqrt{H}+8\)delayunits perdatainput.Thus,thetreemuxisfasterthanthe4-waycircuit forelectricaleffort\(H>4.\)Thisdelayanalysisneglectsthe factthatthe4-waymuxcircuitisinvertingwhereasthetreemuxis not.Wemayalsodesigntree-structuredmultiplexerswith4-wayor 8-waymuxesasbuildingblocks.Duetotheflexibilityofthe \(n\)-waymuxcircuit,thedesignspacefortree-structuredmuxes isquitelarge.Ithasbeenshown,however,that4-waymuxesas buildingblocksproducegenerallythefastesttreestructuresfor \(n\ge8\)datainputs.Chapter11of[SSH99]studiestree structuresinmoredetail. 4.4.TristateInverterandTransmissionGates¶ AsingleselectarmofthemultiplexercircuitinFigure4.36 isatristateinverter.Thenametristatereferstothefact thattheoutputcanassumeathirdstateinadditiontotheusual binarystates0and1.Inthethirdstate,output\(Y\)ofthe tristateinverterisconnectedneitherto\(V_{DD}\)norGND. Therefore,theoutputhasanundeterminedvoltage.Wesaytheoutput floats,anddenotethisthirdstatewithletterZ. Figure4.38showsthattheoutputofthe selectarmfloatsifselectsignal\(S=0.\)Otherwise,if \(S=1,\)thearmfunctionslikeaninverter,i.e.\(Y= \overline{D}.\) S=0    D=0 Figure4.38:Interactiveswitchmodelofonemultiplexerselectarm. Inamultiplexercircuit,allbutoneselectarmfloat.Theselected armdoesnotfloat,anddrivesoutput\(Y.\)Inafigurative sense,thefloatingarmsshutup,leavingthewordtotheonly selectedarm.Inan\(n\)-waymultiplexerwith\(n=2^k\) arms,thereisalwaysoneselectedarm,andtheoutputneverfloats. Ingeneral,thisistheexpectedbehaviorfromamultiplexer,thatan implementationwithlogicgatesproducesaswell.Tristateinverters expandtheapplicabilityofselectarms,forexampleasdriversfor sharedbuseswhereallarmsmayfloat. Toarriveatthetraditionalcircuitrealizationofatristate inverter,weplaythefollowingcircuittrick.Notethatwecan introduceanewwireintheselectarm,shownin Figure4.39(b),withoutaffectingits functionality.Now,imaginewecouldpulloutput\(Y\)tothe rightlikearubberband.Then,weobtainthetopologically equivalentcircuitinFigure4.39(c). Figure4.39:Threeequivalentcircuits:(a)selectarm,(b)selectarmwithadditionalwire\(X,\)(c)inverterdrivingatransmissiongate. TheparallelcompositionofannMOSandpMOStransistorin Figure4.39(c)isatransmissiongate withthefunction: \[\begin{split}Y=\begin{cases} X\,,&\text{if}\S=1\,,\\ Z\,,&\text{if}\S=0\,. \end{cases}\end{split}\] Thetransmissiongatedisconnectsitstwoterminals,if\(S=0,\) andconnectsitstwoterminalsif\(S=1.\)In Figure4.39(c),terminal\(X\)is drivenbyaninverter,suchthat\(X=\overline{D}.\)If \(S=0,\)output\(Y\)isdisconnectedfrom\(X,\)and floats.Otherwise,if\(S=1,\)output\(Y\)isconnectedto terminal\(X,\)andtheinverterdrivesoutput\(Y= \overline{D}\)throughthetransmissiongate. Thiscircuitiscalledtristateinverter,andiscommonlydefinedasa 2-inputgate,withadistinguishedenableinput.Thesymbolofthe tristateinverterisshownontheleft.Itassumesthattheenable signaliscomplementedinternally.Thefunctionofthetristate inverterisdefinedas \[\begin{split}Y=\begin{cases} A\,,&\text{if}\EN=1\,,\\ Z\,,&\text{if}\EN=0\,. \end{cases}\end{split}\] Toanalyzethelogicaleffortofthetristateinverterin Figure4.39(c),weneedtounderstandthe passcharacteristicsofthetransmissiongate.Tothatend,we introducearefinementofoursimpletransistorswitchmodel.Thekeytounderstandingthetransmissiongateis thethresholdvoltage\(V_t,\)whichisacharacteristic processparameterofatransistor.Fortoday’snMOStransistors, \(V_{tn}=+V_t\)isinrange\(V_{DD}/4\lesssimV_t \lesssimV_{DD}/3\)andforpMOStransistors\(V_{tp}\approx -V_t\)hasoppositepolarity. Figure4.40:RefinedswitchmodelofMOStransistorsforONposition.Duetoa thresholdvoltage(\(V_t\))drop,nMOStransistorspassaweak 1andpMOStransistorsaweak0.However,sincenMOStransistors passastrong0theyaresuitedforpull-downnetworks,andsince pMOStransistorspassastrong1theyaresuitedforpull-up networksofCMOScircuits. AnnMOStransistorisswitchedoffifthevoltagebetweengateand sourceissmallerthanthethresholdvoltage,\(V_{gs}-V_t.\)ThepMOStransistorpullsthe sourceterminaltoaweak0atthedrain,becausetheminimum sourcevoltageisby\(V_t\)largerthan\(V_d=0,\)see Figure4.40ontheleft.However,apMOS transistorpullsthedrainterminaltoastrong1atthesource, becausethemaximumdrainvoltageis\(V_{DD}\)if\(V_{gs}= -V_{DD}\)whichissmallerthan\(-V_t,\)seeFigure4.40ontheright.Thus,pMOStransistorsasuitedfor pull-upbutnotforpull-downnetworksofCMOScircuits. Figure4.41:Thepasstransistormodelabstractstherefinedswitchmodelin Figure4.40. Figure4.41showsthepasstransistormodelas aconvenientabstractionoftherefinedswitchmodel.Wesaythatan nMOStransistorpassesastrong0frominput(source)tooutput (drain),butaweak1.Analogously,apMOStransistorpassesa strong1frominput(drain)tooutput(source),butaweak0.Since transistorsaresymmetric,sourceanddraincanbeused interchangeablyasinputsoroutputs.Accordingtothepass transistormodelwecanuseeitherannMOSorapMOStransistorasa switchtopassaninputsignaltotheoutput.However,neitherpasses bothinputs0and1stronglytotheoutput.Thetransmissiongate usesaparallelcompositionofnMOSandpMOStransistors,sothatone ofthetransistorspassestheinputstrongly,see Figure4.42. Figure4.42:Thetransmissiongatepassesbothastrong0viathenMOSanda strong1viathepMOStransistor. Whenatransistorpassesastrong0or1,itactslikeaclosedswitch intheRCmodel.Current\(I_{ds}\)is determinedbytheon-resistance.However,whenpassingaweak0or1, current\(I_{ds}\)iseffectivelysmallerthanpassingastrong0 or1.Wemodelthisbehaviorbymeansofanincreasedon-resistance. Asareasonableestimate,weassumethattheon-resistanceistwiceas largewhenpassingaweakversusastronginput.Then,given on-resistances\(R_n\)and\(R_p\)ofthesimpleswitchmodel, wedefinetheweakandstrongon-resistancesas \[\begin{eqnarray*} R_{n,strong}\=\R_n\,,&\quad&R_{n,weak}\=\2R_n\,,\\ R_{p,strong}\=\R_p\,,&\quad&R_{p,weak}\=\2R_p\,. \end{eqnarray*}\]Theon-resistancesenableustomodelthetransmissiongateasa resistiveswitchcircuit,asshowninFigure4.43. Figure4.43:Resistiveswitchmodeloftransmissiongatepassinga0(left)and a1(right),assumingnormalizedwidths\(W_p=W_n=1.\) Givenunit-sizedtransistors,wehave\(R_p=2R_n,\)becauseof mobilityratio\(\mu_n/\mu_p=2.\)Theneffectiveon-resistance forpassing0is: \[R_{on}(0)=\frac{2R_pR_n}{2R_p+R_n}=\frac{4}{5}R_n\,,\] andforpassing1: \[R_{on}(1)=\frac{R_p2R_n}{R_p+2R_n}=R_n\,.\] Sincethedifferenceissmall,weapproximatetheon-resistanceofthe transmissiongatewithunit-sizedtransistorstobe\(R_n\)in bothcaseswhenpassing0or1.Withthisapproximation,wearriveat thematchedtristateinvertershownontheright.Theequivalent tristateinvertercircuitinFigure4.39(c)consistsofaseriescompositionofaninverteranda transmissiongate.Bydoublingthesizeofboth,thetristate inverterhasthesamepull-upandpull-downdrivecurrentsasthe referenceinverter.Thus,thelogicaleffortofthetristateinverter is\(g_{tri}(A)=2\)forinput\(A,\)and\(g_{tri}(EN) =g_{tri}(\overline{EN})=2/3\)forthecomplementedand uncomplementedenableinputs.Theparasiticdelayis\(p_{tri}= 4/3.\) 4.5.Encoder¶ Inthebroadsense,anencoderisacircuitthattransformsitsinputs intoacodewordofagivencode.Inthenarrowsenseofdigital circuits,anencodercommonlydenotesacircuitthattransformsa one-hotcodedwordintoabinarycodedword.Inthissection,we discusstheone-hottobinaryencoderandanotherusefulcircuit,the priorityencoder. 4.5.1.One-HottoBinaryEncoder¶ Theone-hotcodewith\(n\)bits\(x_i,\)where\(0 \lei14.\)TheopaqueD-latch storesinputvalue\(D=1.\) GiventheD-latchtransistorsizesinFigure4.58anda loadcapacitanceof\(C_L=12,\)thedelaysofthecircuit elementsoftheD-latchare: \(d_{D\rightarrowX}\):\(\quad\phi\)-armdelay;\(d_{D\rightarrowX}=d_{mux}=6\) \(d_{X\rightarrowY}\):\(\quad\)feedbackinverterdelay;\(d_{X\rightarrowY}=6/3+1=3\) \(d_{Y\rightarrowX}\):\(\quad\overline{\phi}\)-armdelay;\(d_{Y\rightarrowX}=d_{mux}=6\) \(d_{X\rightarrowQ}\):\(\quad\)outputinverterdelay;\(d_{X\rightarrowQ}=d_{inv}=C_L/3+1=5\) Withtheseelementdelays,wecanexpressthepropagationdelayofthe transparentD-latchas\(d_{D\rightarrowQ}=d_{D\rightarrowX} +d_{X\rightarrowQ}=11.\)Thewaveformdiagramshowsthe correspondingtransitions.Initially,theD-latchistransparent because\(\phi=1,\)andthe\(\phi\)-armisclosedwhereas the\(\overline{\phi}\)-armisopen.Attime\(t=0,\)the \(D\)-inputchangesfrom0to1.Output\(Q\)willfollow \(D\)aftertheinputhaspropagatedthroughthe\(\phi\)-arm tointernalnode\(X\)at\(t=6,\)andthenthroughthe outputinverterattime\(t=11.\)Thechangeofinternal node\(X\)alsoaffectsnode\(Y,\)whichchangesattime \(t=9\)from0to1afterpropagationdelay \(d_{X\rightarrowY}\)ofthefeedbackinverter. WhentheD-latchbecomesopaqueattime\(t=14,\)itstores value\(Q=1.\)Clocksignal\(\phi=0\)closes,orturns on,the\(\overline{\phi}\)-armandopens,orturnsoff,the \(\phi\)-arm.Thus,aftertheclocktransitionat\(t=14,\) signal\(Y=1\)takespropagationdelay\(d_{Y\rightarrowX}= 6\)timeunitsthroughtheinverting\(\overline{\phi}\)-armto reinforceinternalnode\(X=0\)attime\(t=20.\)Itis thisswitchingdelayofthemultiplexerthatcancausetrouble.In particular,thetransitionofinput\(D\)mustoccurbya sufficientlylongtimeperiodbeforethenegativetransitionofclock \(\phi\)tostabilizeinternalnode\(Y\)throughthefeedback inverter,becausethefeedbackloopisbistableonlyif\(X= \overline{Y}.\)Ifweforce\(X=Y,\)thefeedbackloopwill assumeanunpredictablestate.Thiscanhappen,ifthetimeinterval \(d_{D\rightarrow\phi}\)betweenthetransitionsofinputs \(D\)and\(\phi\)istoosmall.Figure4.60illustratesthetimingproblemsofaD-latch. Figure4.60:D-latchtimingproblems:(left)incornercase \(d_{D\rightarrow\phi}=d_{D\rightarrowX}+d_{X\rightarrow Y}\)theD-latchstorestheinputafter\(d_{D\rightarrowQ}= d_{D\rightarrowX}+d_{X\rightarrowQ},\)(middle) \(d_{D\rightarrowX}15.\)Timeinterval \(d_{D\rightarrow\phi}=d_{D\rightarrowX}+d_{X\rightarrow Y}\)isthesmallestintervalfortheD-latchtocaptureinput \(D\)safely. ThewaveformdiagraminthemiddleofFigure4.60assumesthatinterval\(d_{D\rightarrow\phi}\)is smaller,thatis\(d_{D\rightarrowX}