1Finite State Recognizers and Sequence DetectorsECE 152A – Summer 2009August 10, 2009ECE 152A - Digital Design Principles2Reading AssignmentBrown and Vranesic8 Synchronous Sequential Circuits8.4 Design of Finite State Machines Using CAD Tools8.4.1 Verilog Code for Moore-Type FSMs8.4.2 Synthesis of Verilog Code8.4.3 Simulating and Testing the Circuit8.4.4 Alternative Styles of Verilog Code8.4.5 Summary of Design Steps When Using CAD Tools8.4.6 Specifying the State Assignment in Verilog Code8.4.7 Specification of Mealy FSMs Using Verilog2August 10, 2009ECE 152A - Digital Design Principles3Reading AssignmentRoth14 Derivation of State Graphs and Tables14.1 Design of a Sequence Detector14.2 More Complex Design Problems14.2 Guidelines for Construction of State GraphsAugust 10, 2009ECE 152A - Digital Design Principles4Mealy and Moore MachinesMealy MachineOutput is a function of present state and present inputOutputs valid on clock edge (transition)Simpler (possibly)Faster (possibly)Outputs “glitch”Used for synchronous (clocked) designs3August 10, 2009ECE 152A - Digital Design Principles5Mealy and Moore MachinesMoore MachineOutput is a function of present state onlyOutputs valid after state transitionMore “stable” than Mealy machineOutputs do not glitchAsynchronous (no clock) or synchronous designsAugust 10, 2009ECE 152A - Digital Design Principles6Deterministic RecognizersState DiagramAlso referred to as Deterministic Transition GraphNext state transition is determined uniquely by present state and present inputDeterministic RecognizerClassifies input strings into two classes:Those it acceptsThose it rejects4August 10, 2009ECE 152A - Digital Design Principles7Deterministic RecognizersSequential Lock AnalogyAccepted string corresponds to of the combination of the lockAccepted string opens the lockRejected string leaves the lock closedProvides a basis for general purpose, finite state machine (FSM) designControllers, peripheral interfaces, etc.August 10, 2009ECE 152A - Digital Design Principles8Deterministic RecognizersDefinition of statesStarting (or initial) state must be definedThe states whose assigned output is 1 are referred to as accepting (or terminal) statesThe states whose assigned output is 0 are called rejecting (or nonterminal) statesAbove definition of states and control implies a Moore finite-state machine With the requirement of a defined initial state5August 10, 2009ECE 152A - Digital Design Principles9Deterministic RecognizersDefinition of acceptance and recognitionA string is accepted by a machine if and only if the state that the machine enters after having read the rightmost symbol is an accepting stateOtherwise, the string is rejectedThe set of strings recognized by a machine thus consists of all the input strings that take the machine from its starting state to an accepting stateAugust 10, 2009ECE 152A - Digital Design Principles10Regular ExpressionsConcerned here with the characterization of sets of strings recognized by finite automataA compact language for describing such sets of strings is known as the language of regular expressionsExample 01(01)* describes the set consisting of those strings that can be formed by concatenating one or more 01 strings01 + 0101 + 010101 + 01010101 + ...6August 10, 2009ECE 152A - Digital Design Principles11Design ExampleDesign a Moore machine that recognizes the input string ending with 101Any string ending in 101 will be acceptedRegular expression is (1+0)*(101)111101 recognizes (accepts) string on sixth inputThe machine’s output goes to one each time the sequence 101 is detected10101 recognizes (accepts) string on the fifth inputCircuit’s output goes high on third input and fifth inputAugust 10, 2009ECE 152A - Digital Design Principles12Design ExampleState Diagram0020103100001111Starting StateAccepting State7August 10, 2009ECE 152A - Digital Design Principles13Design ExampleState table with secondary state assignment01100102101101130011001100100000ZA+B+A+B+ABx=1x=0PSNSAugust 10, 2009ECE 152A - Digital Design Principles14Design ExampleNext State MapsABx00 010111 10ABx00 010111 10111A+= x’B + xAB’B+= x1 111z=AB (from state table)8August 10, 2009ECE 152A - Digital Design Principles15Design ExampleDesign can now be implemented In discrete hardware, directly from next state maps with D flip-flops or using excitation tables for T or JK flip-flopsIn Verilog directly from state tableVerilog implementation followsAugust 10, 2009ECE 152A - Digital Design Principles16Moore Machine – Verilog Implementation Verilog Codestate[1] = state variable A state[0] = state variable BSymbolic states zero, one, two, three9August 10, 2009ECE 152A - Digital Design Principles17Moore Machine – Verilog ImplementationTiming SimulationInput sequence1 1 0 1 0 1 1 0 0terminal statestring acceptedMoore output (stable for following period)August 10, 2009ECE 152A - Digital Design Principles18Conversion to Mealy MachineRecall difference between Mealy and Moore machine is in generation of outputNote state table for design example01100102101101130011001100100000ZA+B+A+B+ABx=1x=0PSNSNext states are the same, butoutput is different10August 10, 2009ECE 152A - Digital Design Principles19Conversion to Mealy MachineAssign Moore output (state) to Mealy transition01100102101101130011001100100000ZA+B+A+B+ABx=1x=0PSNS11,100,010201,010.011301,010,001101,000,0000A+B+, ZA+B+, ZABx=1x=0PSNSAugust 10, 2009ECE 152A - Digital Design Principles20Conversion to Mealy MachineNote that rows 1 and 3 of the state table are identicalIdentical rows can be combined into a single state11,100,010201,010.011301,010,001101,000,0000A+B+, ZA+B+, ZABx=1x=0PSNS01,100,010201,010,001101,000,0000A+B+A+B+ABx=1x=0PSNS11August 10, 2009ECE 152A - Digital Design Principles21Conversion to Mealy MachineBecause outputs in a Mealy machine are associated with the transition and not the next state, states 1 and 3 can be combinedCall combined state “state 1” and eliminate state 3New state 1 entered with output of 0 from old state 1New state 1 entered with output of 1 from unchanged state 2Technically, no longer a finite state recognizer because of Mealy implementationNo longer an acceptance “state”August 10, 2009ECE 152A - Digital