Sequential Logic ImplementationAbstraction of State ElementsForms of Sequential LogicFinite State Machine RepresentationsExample Finite State Machine DiagramCan Any Sequential System be Represented with a State Diagram?Counters are Simple Finite State MachinesHow Do We Turn a State Diagram into Logic?FSM Design ProcedureFSM Design Procedure: State Diagram to Encoded State Transition TableImplementationImplementation (cont'd)Another ExampleMore Complex Counter ExampleMore Complex Counter Example (cont’d)Self-Starting Counters (cont’d)Self-Starting CountersState Machine ModelState Machine Model (cont’d)Example: Ant Brain (Ward, MIT)Ant BehaviorDesigning an Ant BrainSynthesizing the Ant Brain CircuitTransition Truth TableSynthesisSynthesis of Next State and Output FunctionsCircuit ImplementationDon’t Cares in FSM SynthesisState MinimizationAnt Brain RevisitedNew Improved BrainNew Brain ImplementationMealy vs. Moore MachinesSpecifying Outputs for a Moore MachineSpecifying Outputs for a Mealy MachineComparison of Mealy and Moore MachinesMealy and Moore ExamplesMealy and Moore Examples (cont’d)Registered Mealy Machine (Really Moore)Example: Vending MachineExample: Vending Machine (cont’d)Slide 42Slide 43Slide 44Slide 45Equivalent Mealy and Moore State DiagramsExample: Traffic Light ControllerExample: Traffic Light Controller (cont’)Slide 49Slide 50Slide 51Logic for Different State AssignmentsVending Machine Example (PLD mapping)Vending Machine (cont’d)Vending Machine (Retimed PLD Mapping)Finite State Machine OptimizationAlgorithmic Approach to State MinimizationState Minimization ExampleMethod of Successive PartitionsMinimized FSMMore Complex State MinimizationSlide 62Minimizing Incompletely Specified FSMsMinimizing States May Not Yield Best CircuitAnother Implementation of Edge DetectorState AssignmentState Assignment StrategiesOne-hot State AssignmentHeuristics for State AssignmentGeneral Approach to Heuristic State AssignmentOutput-Based EncodingCurrent State Assignment ApproachesSequential Logic Implementation SummaryCS 150 - Fall 2000 - Sequential Logic Implementation - 1Sequential Logic ImplementationSequential CircuitsPrimitive sequential elementsCombinational logicModels for representing sequential circuitsFinite-state machines (Moore and Mealy)Representation of memory (states)Changes in state (transitions)Basic sequential circuitsShift registersCountersDesign procedureState diagramsState transition tableNext state functionsCS 150 - Fall 2000 - Sequential Logic Implementation - 2Abstraction of State ElementsDivide circuit into combinational logic and stateLocalize feedback loops and make it easy to break cyclesImplementation of storage elements leads to various forms of sequential logicCombinationalLogicStorage ElementsOutputsState OutputsState InputsInputsCS 150 - Fall 2000 - Sequential Logic Implementation - 3Forms of Sequential LogicAsynchronous sequential logic – state changes occur whenever state inputs change (elements may be simple wires or delay elements)Synchronous sequential logic – state changes occur in lock step across all storage elements (using a periodic waveform - the clock)ClockCS 150 - Fall 2000 - Sequential Logic Implementation - 4In = 0In = 1In = 0In = 1100010110111001Finite State Machine RepresentationsStates: determined by possible values in sequential storage elementsTransitions: change of stateClock: controls when state can change by controlling storage elementsSequential LogicSequences through a series of statesBased on sequence of values on input signalsClock period defines elements of sequenceCS 150 - Fall 2000 - Sequential Logic Implementation - 5Example Finite State Machine DiagramCombination lock from first lectureresetS3closedclosedmux=C1equal& newnot equal& newnot equal& newnot equal& newnot newnot newnot newS1 S2 OPENERRclosedmux=C2equal& newclosedmux=C3equal& newopenCS 150 - Fall 2000 - Sequential Logic Implementation - 6Can Any Sequential System be Represented with a State Diagram?Shift RegisterInput value shownon transition arcsOutput values shownwithin state node1001101110111010100000010111111100000100D Q D Q D QINOUT1 OUT2 OUT3CLKCS 150 - Fall 2000 - Sequential Logic Implementation - 70101001100110010001011113-bit up-counterCounters are Simple Finite State MachinesCountersProceed thru well-defined state sequence in response to enableMany types of counters: binary, BCD, Gray-code3-bit up-counter: 000, 001, 010, 011, 100, 101, 110, 111, 000, ...3-bit down-counter: 111, 110, 101, 100, 011, 010, 001, 000, 111, ...CS 150 - Fall 2000 - Sequential Logic Implementation - 8How Do We Turn a State Diagram into Logic?CounterThree flip-flops to hold stateLogic to compute next stateClock signal controls when flip-flop memory can changeWait long enough for combinational logic to compute new valueDon't wait too long as that is low performanceD Q D Q D QOUT1 OUT2 OUT3CLK"1"CS 150 - Fall 2000 - Sequential Logic Implementation - 9FSM Design ProcedureStart with countersSimple because output is just stateSimple because no choice of next state based on inputState diagram to state transition tableTabular form of state diagramLike a truth-tableState encodingDecide on representation of statesFor counters it is simple: just its valueImplementationFlip-flop for each state bitCombinational logic based on encodingCS 150 - Fall 2000 - Sequential Logic Implementation - 100101001100110010001011113-bit up-countercurrent state next state0 000 001 11 001 010 22 010 011 33 011 100 44 100 101 55 101 110 66 110 111 77 111 000 0FSM Design Procedure: State Diagram to Encoded State Transition TableTabular form of state diagramLike a truth-table (specify output for all input combinations)Encoding of states: easy for counters – just use valueCS 150 - Fall 2000 - Sequential Logic Implementation - 11C3 C2 C1 N3 N2 N10 0 0 0 0 10 0 1 0 1 00 1 0 0 1 10 1 1 1 0 01 0 0 1 0 11 0 1 1 1 01 1 0 1 1 11 1 1 0 0 0N1 := C1'N2 := C1C2' + C1'C2:= C1 xor C2N3 := C1C2C3' + C1'C3 + C2'C3:= C1C2C3' + (C1' + C2')C3:= (C1C2) xor C3notation to showfunction represent input to D-FFImplementationD flip-flop for each state bitCombinational logic based on encoding0 00 11 10 1C1C2C3N30 11 01 00 1C1C2C3N21 10 01 10 0C1C2C3N1CS 150 - Fall 2000 - Sequential Logic Implementation - 12D QQImplementation
View Full Document
Unlocking...