Basics of State Machine DesignFinite-State Machines (FSMs)Need a Better Way to Design Sequential CircuitsDescribing the Behavior of a Sequential Circuit: FSMFSM Example: 0,1,1,1,repeatExtend FSM to Three-Cycle Laser TimerFSM Simplification: Rising Clock Edges ImplicitFSM DefinitionFSM Example: Secure Car KeyFSM Example: Secure Car Key (cont.)FSM Example: Code DetectorImprove FSM for Code DetectorCommon Pitfalls Regarding Transition PropertiesVerifying Correct Transition PropertiesEvidence that Pitfall is CommonDesign Process using FSMsExample Design 1Steps 1 & 2Step 3Step 4State Diagram / State TableGeneral Form of DesignStep 5D Flip-Flop Input MapsD Flip-Flop ImplementationA Different State AssignmentResulting D Flip-Flop Input MapsNew D Flip-Flop ImplementationMoore FSMMealy FSMMealy Design Example 1Slide 37State TableOutput LogicSlide 40Converting Mealy to MooreModified Mealy  Moore DesignVerilog for FSMCAD Automation of DesignRepeat of Design PrinciplesVerilog for Moore Style FSMsCoding StyleAn Alternate Moore Coding StyleRegister Swap ControllerBus ControllerBus Controller FSMComplete FSM for Bus ControllerIdle Cycle in DesignPermitting PreemptionSlide 57Preemption Without the Idle CycleVending MachineVerilog for Mealy Style FSMsBasics of State Machine DesignFinite-State Machines (FSMs)Want sequential circuit with particular behavior over timeExample: Laser timerPush button: x=1 for 3 clock cyclesHow? Let’s try three flip-flopsb=1 gets stored in first D flip-flopThen 2nd flip-flop on next cycle, then 3rd flip-flop on nextOR the three flip-flop outputs, so x should be 1 for three cyclesControllerxbclklaser patientD Q D Q D QclkbxNeed a Better Way to Design Sequential CircuitsTrial and error is not a good design methodWill we be able to “guess” a circuit that works for other desired behavior?How about counting up from 1 to 9? Pulsing an output for 1 cycle every 10 cycles? Detecting the sequence 1 3 5 in binary on a 3-bit input?And, a circuit built by guessing may have undesired behaviorLaser timer: What if press button again while x=1? x then stays one another 3 cycles. Is that what we want?Combinational circuit design process had two important things:1. A formal way to describe desired circuit behaviorBoolean equation, or truth table2. A well-defined process to convert that behavior to a circuitWe need those things for sequential circuit designDescribing the Behavior of a Sequential Circuit: FSM4Finite-State Machine (FSM)A way to describe desired behavior of sequential circuitAkin to Boolean equations for combinational behaviorList states, and transitions among statesExample: Make x change toggle (0 to 1, or 1 to 0) every clock cycleTwo states: “Off” (x=0), and “On” (x=1)Transition from Off to On, or On to Off, on rising clock edgeArrow with no starting state points to initial state (when circuit first starts)Outputs: xOnOffx=0 x=1clk^clk^OffOnOffOnOffOnOff Oncycle 1Off OffOn Oncycle 2 cycle 3 cycle 4clkstatexOutputs:FSM Example: 0,1,1,1,repeat5Want 0, 1, 1, 1, 0, 1, 1, 1, ...Each value for one clock cycleCan describe as FSMFour statesTransition on rising clock edge to next stateOff OffOn1On1On2 On2On3 On3OffclkxStateOutputs:Outputs: xOn1Off On2 On3clk^clk^clk^x=1x=1x=0 x=1clk^Extend FSM to Three-Cycle Laser Timer6Four statesWait in “Off” state while b is 0 (b’) When b is 1 (and rising clock edge), transition to On1Sets x=1On next two clock edges, transition to On2, then On3, which also set x=1So x=1 for three cycles after button pressedDescription is explicit about what happens in “repeat input” case!Off OffOn1Off Off Off On2 On3OffclkStateOutputs:Inputs:xbOn2On1 On3Offclk^clk^x=1x=1x=1x=0clk^b’*clk^b*clk^Inputs: b; Outputs: xFSM Simplification: Rising Clock Edges Implicit7Showing rising clock on every transition: clutteredMake implicit -- assume every edge has rising clock, even if not shownWhat if we wanted a transition without a rising edgeWe don’t consider such asynchronous FSMs -- less common, and advanced topicOnly consider synchronous FSMs -- rising edge on every transitionNote: Transition with no associated condition thus transistions to next state on next clock cycleOn2On1 On3Offx=1x=1x=1x=0b’bInputs: b; Outputs: xOn2On1 On3Offx=1x=1x=1x=0b’clk^clk^^clk *clk^*clk^bInputs: b; Outputs: xFSM Definition8FSM consists ofSet of statesEx: {Off, On1, On2, On3}Set of inputs, set of outputsEx: Inputs: {b}, Outputs: {x}Initial stateEx: “Off”Set of transitionsDescribes next statesEx: Has 5 transitionsSet of actionsSets outputs while in statesEx: x=0, x=1, x=1, and x=1Inputs: b; Outputs: xOn2On1 On3Offx=1x=1x=1x=0b’bWe often draw FSM graphically, known as state diagramCan also use table (state table), or textual languagesFSM Example: Secure Car Key9Many new car keys include tiny computer chipWhen car starts, car’s computer (under engine hood) requests identifier from keyKey transmits identifier4-bits, one bit at a timeIf not, computer shuts off carFSMWait until computer requests ID (a=1)Transmit ID (in this case, 1101)K1 K2 K3 K4r=1 r=1 r=0 r=1Waitr=0Inputs: a; Outputs: ra’aFSM Example: Secure Car Key (cont.)10Nice feature of FSMCan evaluate output behavior for different input sequenceTiming diagrams show states and output values for different input waveformsK1 K2 K3 K4r=1 r=1 r=0 r=1Waitr=0Inputs: a;Outputs: ra’aWait Wait K1 K2 K3 K4 Wait WaitclkInputsOutputsStatearclkInputsaK1Wait Wait K1 K2 K3 K4 WaitOutputStaterQ: Determine states and r value for given input waveform:FSM Example: Code Detector11Unlock door (u=1) only when buttons pressed in sequence: start, then red, blue, green, redInput from each button: s, r, g, bAlso, output a indicates that some colored button is being pressedFSMWait for start (s=1) in “Wait”Once started (“Start”)If see red, go to “Red1”Then, if see blue, go to “Blue”Then, if see green, go to “Green”Then, if see red, go to “Red2”In that state, open the door (u=1)Wrong button at any step, return to “Wait”, without opening doorStartRedGreenBluesrgbaDoorlockuCodedetectorQ: Can you trick this FSM to open the door, without knowing the code?A: Yes, hold all buttons simultaneouslyWaitStartRed1 Red2GreenBlues’a’ar’ ab’ ag’ ar’a’abagara’