Slide 1AnnouncementsAnnouncementsGoals for Today: Stateful ComponentsUnstable DevicesBistable DevicesBistable DevicesSR LatchUnclocked D LatchUnclocked D LatchD Latch with ClockClocksEdge-triggeringEdge-Triggered D Flip-FlopClock DisciplinesRegistersMetastability and Asynchronous InputsMetastability and Asynchronous InputsAn ExampleClock MethodologySlide 21Finite State MachinesAbstract Model of FSMVoting MachineAutomata ModelFSM ExampleFSM Example DetailsMealy MachineMoore MachineMoore Machine ExampleDigital Door LockDoor Lock: InputsDoor Lock: OutputsDoor Lock: Simplified State DiagramDoor Lock: Simplified State DiagramDoor Lock: Simplified State DiagramDoor Lock: Simplified State DiagramState Table EncodingDoor Lock: ImplementationSummaryState & Finite State MachinesHakim WeatherspoonCS 3410, Spring 2011Computer ScienceCornell UniversitySee P&H Appendix C.7. C.8, C.10, C.112AnnouncementsMake sure you areRegistered for classCan access CMSHave a Section you can go toHave a project partnerSections are on this weekHW 1 out later todayDue in one week, start earlyWork aloneUse your resources•Class notes, book, Sections, office hours, newsgroup, CSUGLab3AnnouncementsCheck online syllabus/schedule Slides and Reading for lecturesOffice HoursHomework and Programming AssignmentsPrelims: Evening of Thursday, March 10 and April 28thSchedule is subject to changeHW1 Correction:Hint 1: Your ALU should use your adder and left shifter as components. But, as in class, your ALU should only use a single adder component to implement both addition and subtraction. Similarly, your ALU should use only a single left shifter component to implement all of the shift operations. For instance, left right shifting can be accomplished by transforming the inputs and outputs to your left shifter. You will be penalized if your final ALU circuit uses more than one adder or left shifter. Of course, always strive to make your implementationclear, but do not duplicate components in an effort to do so.4Goals for Today: Stateful ComponentsUntil now is combinatorial logic•Output is computed when inputs are present•System has no internal state•Nothing computed in the present can depend on what happened in the past!Need a way to record dataNeed a way to build stateful circuitsNeed a state-holding deviceFinite State MachinesInputsCombinationalcircuitOutputsNM5Unstable DevicesBACBistable DevicesABA Simple Device•Stable and unstable equilibria?Bistable Devices•In stable state, A = B•How do we change the state?ABAB1AB100A Simple Device•Stable and unstable equilibria?8SR LatchSet-Reset (SR) LatchStores a value Q and its complement QS R Q Q0 00 11 01 1SRQQSRQQ9Unclocked D LatchData (D) LatchD Q Q01SRDQQ10Unclocked D LatchData (D) LatchD Q Q0 011 10SRDQQData Latch•Easier to use than an SR latch•No possibility of entering an undefined stateWhen D changes, Q changes–… immediately (after a delay of 2 Ors and 2 NOTs)Need to control when the output changes11D Latch with ClockSRDclkQQclkDQLevel Sensitive D LatchClock high: set/reset (according to D)Clock low: keep state (ignore D)12ClocksClock helps coordinate state changes•Usually generated by an oscillating crystal•Fixed period; frequency = 1/period10Edge-triggering•Can design circuits to change on the rising or falling edge•Trigger on rising edge = positive edge-triggered•Trigger on falling edge = negative edge-triggered•Inputs must be stable just before the triggering edgeinputclock14Edge-Triggered D Flip-FlopD Flip-Flop•Edge-Triggered•Data is captured when clock is high•Outputs change only on falling edgesD QQD QQcFL LclkDFQcQQDclk15Clock DisciplinesLevel sensitive•State changes when clock is high (or low)Edge triggered•State changes at clock edgepositive edge-triggerednegative edge-triggered16RegistersRegister•D flip-flops in parallel •shared clock•extra clocked inputs:write_enable, reset, …clkD0D3D1D2444-bitreg17Metastability and Asynchronous Inputs1-bitregClk18Metastability and Asynchronous InputsQ: What happens if input changes near clock edge?A: Google “Buridan’s Principle” by Leslie Lamport1-bitregClk0119An Example32-bitregClk+1RunWE RReset20Clock MethodologyClock Methodology•Negative edge, synchronous–Signals must be stable near falling clock edge•Positive edge synchronous•Asynchronous, multiple clocks, . . .clkcompute savetsetuptholdcompute save computetcombinationalFinite State Machines22Finite State MachinesAn electronic machine which has•external inputs•externally visible outputs•internal stateOutput and next state depend on•inputs•current state23Abstract Model of FSMMachine isM = ( S, I, O, )S: Finite set of statesI: Finite set of inputsO: Finite set of outputs: State transition functionNext state depends on present input and present state24Voting Machinemux32...regdetectenc3decoder (3-to-8)32 3232LED dec3WE+1regWEregWEregWEmuxDV25Automata ModelFinite State Machine•inputs from external world•outputs to external world•internal state•combinational logic Next StateCurrent StateInputOutputRegistersComb.Logic26FSM ExampleLegendstateinput/outputstartstateABC Ddown/onup/ofdown/ondown/ofup/ofdown/ofup/ofup/ofInput: up or downOutput: on or ofStates: A, B, C, or D27FSM Example DetailsLegendS1S0i0i1i2…/o0o1o2…S1S0000110 111/10/01/11/00/01/00/00/0Input: 0=up or 1=downOutput: 1=on or 0=offStates: 00=A, 01=B, 10=C, or 11=D28General Case: Mealy MachineOutputs and next state depend on bothcurrent state and inputMealy MachineNext State Current StateInputOutputRegistersComb.Logic29Moore MachineSpecial Case: Moore MachineOutputs depend only on current stateNext StateCurrent StateInputOutputRegistersComb.LogicComb.Logic30Moore Machine ExampleLegendstateoutinputstartoutA ofBonC ofD ondownupdowndownupdownupupInput: up or downOutput: on or ofStates: A, B, C, or D31Digital Door LockDigital Door LockInputs: •keycodes from keypad•clockOutputs: •“unlock” signal•display how many keys pressed so far32Door Lock: InputsAssumptions:•signals are synchronized to clock•Password is B-A-BKABK A B Meaning0 0 0 Ø (no key)1 1 0 ‘A’ pressed1 0 1 ‘B’ pressed33Door Lock: OutputsAssumptions:•High pulse on U unlocks doorUD3D2D1D04LEDdec834Door Lock: Simplified State DiagramIdleG1”0”ØG2G3B1 B2”1” ”2””3”, U”1” ”2”Ø ØØ Ø“B”“A” “B”elseelseanyanyelseelseB3”3”else35Door Lock: Simplified State DiagramIdleG1”0”ØG2G3B1 B2”1”
View Full Document
Unlocking...