Digital Logic Design - Lecture 26: Finite State Machine Design Procedure

DLDLecture 26Finite State Machine Design ProcedureOverviewDesign of systems that input flip flops and combinational logicSpecifications start with a word descriptionCreate a state table to indicate next statesConvert next states and outputs to output and flip flop input equationsReduce logic expressions using truth tablesDraw resulting circuits. Concept of the State MachineComputer Hardware = Datapath + ControlRegistersCombinational Functional Units (e.g., ALU)BussesFSM generating sequencesof control signals Instructs datapath what to do nextQualifiersControlControlDatapathStateControlSignalOutputsQualifiersandInputsCombinationalLogicStorage ElementsOutputsState OutputsState InputsInputsDivide circuit into combinational logic and stateLocalize feedback loops and make it easy to break cyclesImplementation of storage elements leads to various forms of sequential logicConcept of the State MachineDesigning Finite State MachinesSpecify the problem with words(e.g. Design a circuit that detects three consecutive 1 inputs)Assign binary values to statesDevelop a state tableUse K-maps to simplify expressionsFlip flop input equations and output equationsCreate appropriate logic diagramShould include combinational logic and flip flopsExample: Detect 3 Consecutive 1 inputsState S0 : zero 1s detectedState S1 : one 1 detectedState S2 : two 1s detectedState S3 : three 1s detected0Note that each state has 2 output arrowsTwo bits needed to encode stateState Table for Sequence DetectorSequence of outputs, inputs, and flip flop states enumerated in state tablePresent state indicates current value of flip flopsNext state indicates state after next rising clock edgeOutput is output value on current clock edgePresent StateNext StateA B x A B y 0 0 0 0 0 0 0 0 1 0 1 00 1 0 0 0 00 1 1 1 0 01 0 0 0 0 0 1 0 1 1 1 01 1 0 0 0 11 1 1 1 1 1OutputInputS0 = 00S1 = 01S2 = 10S3 = 11Finding Expressions for Next State and Output ValueCreate K-map directly from state table (3 columns = 3 K-maps)Minimize K-maps to find SOP representationsSeparate circuit for each next state and output valueCircuit for Consecutive 1s DetectorNote location of state flip flopsOutput value (y) is function of stateThis is a Moore machine.Concept of the State MachineExample: Odd Parity CheckerAssert output whenever input bit stream has odd # of 1'sStateDiagramSymbolic State Transition TableEncoded State Transition TableNote: Present state and output are the same value Moore machineConcept of the State MachineExample: Odd Parity CheckerNext State/Output FunctionsNS = PS xor PI; OUT = PSD FF ImplementationTiming Behavior: Input 1 0 0 1 1 0 1 0 1 1 1 0NSPSPIConcept of the State MachineExample: Odd Parity CheckerNext State/Output FunctionsNS = PS xor PI; OUT = PSD FF ImplementationTiming Behavior: Input 1 0 0 1 1 0 1 0 1 1 1 0NSPSPIMealy and Moore MachinesSolution 1: (Mealy)0/0EvenOdd1/11/00/10Even110Reset[0]Odd [1]OutputInputOutputInputTransition ArcOutput is dependent only on current stateO/P is dependenton current state andinput in MealySolution 2: (Moore)Mealy Machine: Output is associated with the state transition- Appears before the state transition is completed (by the next clock pulse).Moore Machine: Output is associatedwith the stateAppears after the state transition takes place.Vending Machine FSM Step 1. Specify the problemDeliver package of gum after 15 cents depositedSingle coin slot for dimes, nickelsNo changeDesign the FSM using combinational logic and flip flopsVending Machine FSM State DiagramReuse stateswhenever possibleSymbolic State TableVending Machine FSM State EncodingHow many flip-flops are needed?Vending Machine FSM Determine F/F implementationK-map for OpenK-map for D0 K-map for D1Q1 Q0D NQ1Q0DNQ1 Q0D NQ1Q0DNQ1 Q0D NQ1Q0DND Q QRD Q QRQ0NNQ0Q1NQ1DD0D1Q1OPENDCLKCLKVending machine FSM implementation based on D flip-flops(Moore).Q1Q0ResetResetMinimized ImplementationCount Sequence Design ProcedureComplex Count SequenceStep 1: Derive the State Transition DiagramCount sequence: 000, 010, 011, 101, 110More Complex Count SequenceDesign ProcedureComplex Count SequenceDesign ProcedureComplex Count SequenceDesign ProcedureDesign ProcedureComplex Count SequenceDesign ProcedureComplex Count Sequence