B.
10
FiniteStateMachines
B-67
[Link],[Link], whodescribedamethodforcreatingsuchcodes.
B.10
FiniteStateMachines
B.10
As we saw earlier, digital logic systems can be classied as combinational or [Link] [Link] thecontentsoftheinternalmemory,[Link],asequentialsystem cannot be described with a truth table. Instead, a sequential system is described as a nite state machine (or often just state machine). A nite state machinehasasetofstatesandtwofunctionscalledthe next-statefunctionand the [Link] [Link],ifthereare nbitsofstorage,[Link],giventheinputsandthecurrent state,[Link] of outputs from the current state and the inputs. Figure B.10.1 shows this diagrammatically.
nitestatemachine A sequentiallogicfunctionconsistingofasetofinputsandoutputs,anext-statefunctionthat mapsthecurrentstateandthe inputstoanewstate,andan outputfunctionthatmapsthe currentstateandpossiblythe inputstoasetofasserted outputs. next-statefunction Acombinationalfunctionthat,giventhe inputsandthecurrentstate, determinesthenextstateofa finitestatemachine.
Next state Current state Next-state function
Clock Inputs
Output function
Outputs
FIGUREB.10.1 Astatemachineconsistsofinternalstoragethatcontainsthestateand twocombinationalfunctions: [Link],the outputfunctionisrestrictedtotakeonlythecurrentstateasitsinput;thisdoesnotchangethecapabilityof asequentialmachine,butdoesaffectitsinternals.
B-68
AppendixB
TheBasicsofLogicDesign
ThestatemachineswediscusshereandinChapters5and6are synchronous. Thismeansthatthestatechangestogetherwiththeclockcycle,andanewstateis computed once every clock. Thus, the state elements are updated only on the clockedge.WeusethismethodologyinthissectionandthroughoutChapters5 and 6, and we do not usually show the clock explicitly. We use state machines throughout Chapters 5 and 6 to control the execution of the processor and the actionsofthedatapath. Toillustratehowanitestatemachineoperatesandisdesigned,letslookata simpleandclassicexample: controllingatrafclight.(Chapters5and6contain moredetailedexamplesofusingnitestatemachinestocontrolprocessorexecution.)Whenanitestatemachineisusedasacontroller,theoutputfunctionis [Link] [Link] this book. If the outputfunction can depend on both the current state and the current input, the machine is called a Mealy machine. These two machines are equivalentintheircapabilities,andonecanbeturnedintotheothermechanically. The basic advantage of a Moore machine is that it can be faster, while a Mealy machinemaybesmaller,[Link] Chapter5,wediscussthedifferencesinmoredetailandshowaVerilogversionof nitestatecontrolusingaMealymachine. [Link],wewillconsideronlythegreen andredlights;[Link] cyclenofasterthan30secondsineachdirection,sowewillusea0.033Hzclockso that the machine cycles between states at no faster than once every 30 seconds. Therearetwooutputsignals:
NSlite: When this signal is asserted, the light on the north-south road is green;whenthissignalisdeassertedthelightonthenorth-southroadisred. EWlite: Whenthissignalisasserted,thelightontheeast-westroadisgreen; whenthissignalisdeassertedthelightontheeast-westroadisred. NScar: Indicates that a car is over the detector placed in the roadbed in frontofthelightonthenorth-southroad(goingnorthorsouth). EWcar: Indicates that a car is over the detector placed in the roadbed in frontofthelightontheeast-westroad(goingeastorwest).
Inaddition,therearetwoinputs: NScarandEWcar.
Thetrafclightshouldchangefromonedirectiontotheotheronlyifacariswaiting to go in the other direction; otherwise, the light should continue to show greeninthesamedirectionasthelastcarthatcrossedtheintersection.
B.10
FiniteStateMachines
B-69
Toimplementthissimpletrafclightweneedtwostates:
NSgreen: Thetrafclightisgreeninthenorth-southdirection. EWgreen: Thetrafclightisgreenintheeast-westdirection.
Wealsoneedtocreatethenext-statefunction,whichcanbespeciedwithatable:
Inputs Currentstate
NSgreen NSgreen NSgreen NSgreen EWgreen EWgreen EWgreen EWgreen
NScar
0 0 1 1 0 0 1 1
EWcar
0 1 0 1 0 1 0 1
Nextstate
NSgreen EWgreen NSgreen EWgreen EWgreen EWgreen NSgreen NSgreen
Notice that we didnt specify in the algorithm what happens when a car [Link],thenext-statefunctiongivenabove changesthestatetoensurethatasteadystreamofcarsfromonedirectioncannot lockoutacarintheotherdirection. Thenitestatemachineiscompletedbyspecifyingtheoutputfunction:
Outputs Currentstate
NSgreen EWgreen
NSlite
1 0
EWlite
0 1
Beforeweexaminehowtoimplementthisnitestatemachine,letslookata graphicalrepresentation,[Link],[Link] [Link]-state function,withlabelsonthearcsspecifyingtheinputconditionaslogicfunctions. FigureB.10.2showsthegraphicalrepresentationforthisnitestatemachine. Anitestatemachinecanbeimplementedwitharegistertoholdthecurrent state and a block of combinational logic that computes the next-state function [Link].10.3showshowanitestatemachinewith4 bitsofstate,andthusupto16states,[Link] machineinthisway,[Link] is called state assignment. For example, we could assign NSgreen to state 0 and
B-70
AppendixB
TheBasicsofLogicDesign
EWcar
NSgreen NSlite NScar EWlite
EWgreen
EWca
NScar
FIGUREB.10.2 Thegraphicalrepresentationofthetwo-statetrafclightcontroller. We simplied the logic functions on the state transitions. For example, the transition from NSgreen to EWgreeninthenext-statetableis ( NScar EWcar ) + ( NScar EWcar ),whichisequivalenttoEWcar.
[Link]-state functionwouldbegivenas NextState = ( CurrentState EWcar ) + ( CurrentState NScar ) whereCurrentStateisthecontentsofthestateregister(0or1)andNextStateisthe outputofthenext-statefunctionthatwillbewrittenintothestateregisteratthe [Link]: NSlite= CurrentState EWlite= CurrentState Thecombinationallogicblockisoftenimplementedusingstructuredlogic,such [Link]-stateandoutput function tables. In fact, there are computer-aided design (CAD) programs that takeeitheragraphicalortextualrepresentationofanitestatemachineandproduceanoptimizedimplementationautomatically.InChapters5and6,nitestate machines were used to control processor execution. AppendixC discusses the detailedimplementationofthesecontrollerswithbothPLAsandROMs. ToshowhowwemightwritethecontrolinVerilog,[Link],a Mealymachineisnotuseful,butthisstyleofspecicationisusedinChapter5to implementacontrolfunctionthatisaMealymachineandhasfewerstatesthan theMooremachinecontroller.
B.10
FiniteStateMachines
B-71
Outputs Combinational logic
Next state
State register
Inputs FIGURE B.10.3 A nite state machine is implemented with a state register that holds thecurrentstateandacombinationallogicblocktocomputethenextstateandoutput functions. The latter two functions are often split apart and implemented with two separate blocks of logic,whichmayrequirefewergates.
moduleTrafficLite(EWCar,NSCar,EWLite,NSLite,clock); inputEWCar,NSCar,clock; outputEWLite,NSLite; regstate; initialstate=0;//setinitialstate //followingtwoassignmentssettheoutput,whichisbasedonlyonthestate variable assignNSLite=~state;//NSLiteonifstate=0; assignEWLite=state;//EWLiteonifstate=1 always@(posedgeclock)//allstateupdatesonapositiveclockedge case(state) 0:state=EWCar;//changestateonlyifEWCar 1:state=NSCar;//changestateonlyifNSCar endcase endmodule
FIGUREB.10.4 AVerilogversionofthetrafclightcontroller.
B-72
AppendixB
TheBasicsofLogicDesign
Check Yourself
What is the smallest number of states in a Moore machine for which a Mealy machinecouldhavefewerstates? a. Two,sincetherecouldbeaone-stateMealymachinethatmightdothesame thing. b. Three,sincetherecouldbeasimpleMooremachinethatwenttooneoftwo [Link] simplemachine,atwo-stateMealymachineispossible. c. YouneedatleastfourstatestoexploittheadvantagesofaMealymachine overaMooremachine.
B.11
TimingMethodologies
B.11
Throughoutthisappendixandintherestofthetext,weuseanedge-triggered [Link], we explain this timing methodology in a little more detail and also [Link] theissueofasynchronoussignalsandsynchronizers,animportantproblemfor digitaldesigners. The purpose of this section is to introduce the major concepts in clocking [Link];ifyou areinterestedinunderstandingtimingmethodologyinmoredetail,consultone ofthereferenceslistedattheendofthisappendix. Weuseanedge-triggeredtimingmethodologybecauseitissimplertoexplain [Link],ifweassumethatall clocks arrive at the same time, we are guaranteed that a system with edge-triggeredregistersbetweenblocksofcombinationallogiccanoperatecorrectlywithout races, if we simply make the clock long enough. A race occurs when the contents of a state element depend on the relative speed of different logic elements. In an edge-triggered design, the clock cycle must be long enough to accommodate the path from one ip-op through the combinational logic to [Link].11.1 [Link] asystemtheclockperiod(orcycletime)mustbeatleastaslargeas t prop + t combinational + t setup fortheworst-casevaluesofthesethreedelays,whicharedenedasfollows:
B.11
TimingMethodologies
B-73
D C tprop
Q Flip-flop
Combinational logic block tcombinational tsetup
D C
Q Flip-flop
FIGUREB.11.1 Inanedge-triggereddesign,[Link]-ipoutputsis tprop;thesignalthentakes tcombinationaltotravelthrough thecombinationallogicandmustbevalidtsetupbeforethenextclockedge.
tpropisthetimeforasignaltopropagatethroughaipop;itisalsosometimescalledclock-to-Q. tcombinationalisthelongestdelayforanycombinationallogic(whichbydenitionissurroundedbytwoip-ops). tsetup is the time before the rising clock edge that the input to a ip-op mustbevalid.
We make one simplifying assumption: the hold-time requirements are satised,whichisalmostneveranissuewithmodernlogic. Oneadditionalcomplicationthatmustbeconsideredinedge-triggereddesigns is clock skew. Clock skew is the difference in absolute time between when two state elements see a clock edge. Clock skew arises because the clock signal will oftenusetwodifferentpaths,withslightlydifferentdelays,toreachtwodifferent [Link],itmaybepossibleforastateelementtochangeandcausetheinputtoanotherip-optochangebeforetheclock edgeisseenbythesecondip-op. FigureB.11.2illustratesthisproblem,[Link],theclockperiodisincreasedtoallow [Link],theclockperiodmustbelongerthan t prop + t combinational + t setup + t skew With this constraint on the clock period, the two clocks can also arrive in the opposite order, with the second clock arriving tskew earlier, and the circuit will work correctly. Designers reduce clock skew problems by carefully routing the [Link],smartdesignersalsoprovidesomemarginbymakingtheclockalittlelongerthantheminimum;[Link]
clockskew Thedifferencein absolutetimebetweenthetimes whentwostateelementsseea clockedge.
B-74
AppendixB
TheBasicsofLogicDesign
D Clock arrives at time t C
Q Flip-flop
Combinational logic block with delay time of
D Clock arrives after t + C
Q Flip-flop
FIGUREB.11.2 Illustrationofhowclockskewcancausearace,[Link] thetwoip-opsseetheclock,thesignalthatisstoredintotherstip-opcanraceforwardandchangetheinputtothesecondip-opbeforethe clockarrivesatthesecondip-op.
level-sensitiveclocking A
timingmethodologyinwhich statechangesoccurateither highorlowclocklevelsbutare notinstantaneous,assuch changesareinedge-triggered designs.
clockskewcanalsoaffectthehold-timerequirements,minimizingthesizeofthe clockskewisimportant. Edge-triggereddesignshavetwodrawbacks: theyrequireextralogicandthey [Link]-opversusthelevel-sensitive latch that we used to construct the ip-op shows that edge-triggered design [Link] changesinalevel-sensitivemethodologyarenotinstantaneous,alevel-sensitive schemeisslightlymorecomplexandrequiresadditionalcaretomakeitoperate correctly.
Level-SensitiveTiming
Inalevel-sensitivetimingmethodology,thestatechangesoccurateitherhighor lowlevels,[Link],[Link] ensure that a level-sensitive design will also work correctly if the clock is slow enough, designers use two-phase clocking. Two-phase clocking is a scheme that makes use of two nonoverlapping clock signals. Since the two clocks, typically called1and2,arenonoverlapping,atmostoneoftheclocksignalsishighatany giventime,[Link] thatcontainslevel-sensitivelatchesbutisfreefromanyraceconditions,justasthe edge-triggereddesignswere.
1 2
Nonoverlapping periods FIGUREB.11.3 Atwo-phaseclockingschemeshowingthecycleofeachclockandthe nonoverlappingperiods.
B.11
TimingMethodologies
B-75
D 1 Latch C
Combinational logic block
D 2 Latch C
Combinational logic block
D 1 Latch C
FIGURE B.11.4 A two-phase timing scheme with alternating latches showing how the system operates on both clock [Link],therstblockofcombinationalinputshasastableinputduring 2 anditsoutputislatchedby [Link](rightmost)combinationalblockoperatesinjusttheoppositefashionwithstableinputsduring 1. Thus,[Link].
Onesimplewaytodesignsuchasystemistoalternatetheuseoflatchesthatare [Link] atthesametime,aracecannotoccur.Iftheinputtoacombinationalblockisa1 clock,thenitsoutputislatchedbya2clock,whichisopenonlyduring2when [Link].11.4showshowa [Link]-triggereddesign,wemustpayattentiontoclockskew,particularlybetweenthetwo [Link],we [Link] correctly if each phase is long enough and there is large enough nonoverlap betweenthephases.
AsynchronousInputsandSynchronizers
Byusingasingleclockoratwo-phaseclock,wecaneliminateraceconditionsif clock skew problems are avoided. Unfortunately, it is impractical to make an entire system function with a single clock and still keep the clock skew small. WhiletheCPUmayuseasingleclock,I/Odeviceswillprobablyhavetheirown clock.Chapter8describedhowanasynchronousdevicemaycommunicatewith the CPU through a series of handshaking steps. To translate the asynchronous inputtoasynchronoussignalthatcanbeusedtochangethestateofasystem,we needtousea synchronizer,whoseinputsaretheasynchronoussignalandaclock andwhoseoutputisasignalsynchronouswiththeinputclock. Our rst attempt to build a synchronizer uses an edge-triggered D ip-op, whose D input is the asynchronous signal, as Figure B.11.5 shows. Because we communicatewithahandshakingprotocol(aswewillseeinChapter8),itdoes notmatterwhetherwedetecttheassertedstateoftheasynchronoussignalonone clockorthenext,sincethesignalwillbeheldasserteduntilitisacknowledged. Thus,youmightthinkthatthissimplestructureisenoughtosamplethesignal accurately,whichwouldbethecaseexceptforonesmallproblem. [Link],itis
metastability Asituationthat
occursifasignalissampled whenitisnotstableforthe requiredset-upandholdtimes, possiblycausingthesampled valuetofallintheindeterminate regionbetweenahighandlow value.
B-76
AppendixB
TheBasicsofLogicDesign
Asynchronous input Clock
D C
Q Flip-flop
Synchronous output
FIGUREB.11.5 AsynchronizerbuiltfromaDip-opisusedtosampleanasynchronous signaltoproduceanoutputthatissynchronouswiththeclock. Thissynchronizerwill not workproperly!
synchronizerfailure Asituationinwhichaflip-flopentersa metastablestateandwhere somelogicblocksreadingthe outputoftheflip-flopseea0 whileothersseea1.
[Link],thesituationisworse: whenthesignalthat issampledisnotstablefortherequiredset-upandholdtimes,theip-opmay go into a metastable state. In such a state, the output will not have a legitimate highorlowvalue,[Link],theip-opisnotguaranteedtoexitthisstateinanyboundedamountof [Link]-opmayseeitsoutput as0,[Link]. Inapurelysynchronoussystem,synchronizerfailurecanbeavoidedbyensuringthattheset-upandholdtimesforaip-oporlatcharealwaysmet,butthisis [Link],theonlysolutionpossibleis towaitlongenoughbeforelookingattheoutputoftheip-optoensurethatits output is stable, and that it has exited the metastable state, if it ever entered it. Howlongislongenough?Well,theprobabilitythattheip-opwillstayinthe metastablestatedecreasesexponentially,soafteraveryshorttimetheprobability that the ip-op is in the metastable state is very low; however, the probability neverreaches0!Sodesignerswaitlongenoughthattheprobabilityofasynchronizerfailureisverylow,andthetimebetweensuchfailureswillbeyearsoreven thousandsofyears. Formostip-opdesigns,waitingforaperiodthatisseveraltimeslongerthan [Link] clockrateislongerthanthepotentialmetastabilityperiod(whichislikely),thena safesynchronizercanbebuiltwithtwoDip-ops,[Link] areinterestedinreadingmoreabouttheseproblems,lookintothereferences.
D C Q Flip-flop C D Q Flip-flop
Asynchronous input Clock
Synchronous output
FIGUREB.11.6 Thissynchronizerwillworkcorrectlyiftheperiodofmetastabilitythat [Link]-op maybemetastable,itwillnotbeseenbyanyotherlogicelementuntilthesecondclock,whenthesecondD ip-opsamplesthesignal,whichbythattimeshouldnolongerbeinametastablestate.
B.12
FieldProgrammableDevices
B-77
Suppose we have a design with very large clock skewlonger than the register [Link] enoughtoguaranteethatthelogicoperatesproperly? a. Yes, if the clock is slow enough the signals can always propagate and the designwillwork,eveniftheskewisverylarge. b. No,sinceitispossiblethattworegistersseethesameclockedgefarenough apartthataregisteristriggered,anditsoutputspropagatedandseenbya secondregisterwiththesameclockedge.
Check Yourself
propagationtime Thetime requiredforaninputtoaflipfloptopropagatetotheoutputs oftheflip-flop.
B.12
FieldProgrammableDevices
B.12
Withinacustomorsemicustomchip,designerscanmakeuseoftheexibilityof the underlying structure to easily implement combinational or sequential logic. HowcanadesignerwhodoesnotwanttouseacustomorsemicustomICimplementacomplexpieceoflogictakingadvantageoftheveryhighlevelsofintegration available? The most popular components used for sequential and combinationallogicdesignoutsideofacustomorsemicustomICisa eldprogrammable device (FPD). An FPD is a integrated circuit containing combinationallogic,andpossiblymemorydevices,thatiscongurablebytheenduser. FPDs generally fall into two camps: programmable logic devices (PLDs), whicharepurelycombinational,and eldprogrammablegatearrays(FPGAs), which provide both combinational logic and ip-ops. PLDs consist of two forms: simplePLDs(SPLDs),whichareusuallyeitheraPLAoraprogrammable arraylogic(PAL),andcomplexPLDs,whichallowmorethanonelogicblockas [Link] PLD,wemeanaPLAwithuserprogrammableand-planeandor-plane.A PALis likeaPLA,exceptthattheor-planeisxed. BeforewediscussFPGAs,itisusefultotalkabouthowFPDsarecongured. Conguration is essentially a question of where to make or break connections. Gate and register structures are static, but the connections can be congured. Notice that by conguring the connections, a user determines what logic [Link]:bydeterminingwherethe connectionsareintheand-planeandtheor-plane,theuserdictateswhatlogical [Link] recongurable. Permanent connections involve the creation or destruction of a connection between two wires. Current FPLDs all use an antifuse technology, [Link] isdownloadedatpower-on,andthecontentscontrolthesettingofswitchesthat
eldprogrammabledevices (FPD) Anintegratedcircuit
containingcombinationallogic, andpossiblymemorydevices, thatisconfigurablebytheend user.
programmablelogicdevice (PLD) Anintegratedcircuit
containingcombinationallogic whosefunctionisconfiguredby theenduser.
eldprogrammablegate array Aconfigurableintegrated
circuitcontainingbothcombinationallogicblocksandflipflops.
simpleprogrammablelogic device(SPLD) Programmable
logicdeviceusuallycontaining eitherasinglePALorPLA.
programmablearraylogic (PAL) Containsaprogrammableand-planefollowedbya fixedor-plane.
antifuse Astructureinanintegratedcircuitthatwhenprogrammedmakesapermanent connectionbetweentwowires.
