Sequential Logic ExamplesGeneral FSM Design ProcedureFinite String Pattern Recognizer (Step 1)Finite String Pattern Recognizer (Step 2)Finite String Pattern Recognizer (Step 2, cont’d)Slide 6Finite String Pattern Recognizer (Step 3)Finite String Pattern RecognizerComplex CounterComplex Counter (State Diagram)Complex Counter (State Encoding)Traffic Light Controller as Two Communicating FSMsCommunicating Finite State MachinesDatapath and ControlDigital Combinational LockImplementation in SoftwareDetermining Details of the SpecificationDigital Combination Lock State DiagramDatapath and Control StructureState Table for Combination LockEncodings for Combination LockDatapath Implementation for Combination LockDatapath Implementation (cont’d)Tri-State GatesTri-State and MultiplexingOpen-Collector Gates and Wired-ANDDigital Combination Lock (New Datapath)Section SummaryCS 150 - Spring 2001 - Sequential Logic Examples - 1 Sequential Logic ExamplesFinite State Machine ConceptFSMs are the decision making logic of digital designs Partitioning designs into datapath and control elementsWhen inputs are sampled and outputs assertedBasic Design Approach: 4-step Design ProcessImplementation Examples and Case StudiesFinite-string pattern recognizerComplex counterTraffic light controllerDoor combination lockCS 150 - Spring 2001 - Sequential Logic Examples - 2General FSM Design Procedure(1) Determine inputs and outputs(2) Determine possible states of machine– State minimization(3) Encode states and outputs into a binary code– State assignment or state encoding– Output encoding– Possibly input encoding (if under our control)(4) Realize logic to implement functions for states and outputs– Combinational logic implementation and optimization– Choices in steps 2 and 3 have large effect on resulting logicCS 150 - Spring 2001 - Sequential Logic Examples - 3Finite String Pattern Recognizer(Step 1)Finite String Pattern RecognizerOne input (X) and one output (Z)Output is asserted whenever the input sequence …010… has been observed, as long as the sequence 100 has never been seenStep 1: Understanding the Problem StatementSample input/output behavior:X: 0 0 1 0 1 0 1 0 0 1 0 …Z: 0 0 0 1 0 1 0 1 0 0 0 …X: 1 1 0 1 1 0 1 0 0 1 0 …Z: 0 0 0 0 0 0 0 1 0 0 0 …CS 150 - Spring 2001 - Sequential Logic Examples - 4Finite String Pattern Recognizer (Step 2)Step 2: Draw State DiagramFor the strings that must be recognized, i.e., 010 and 100Moore implementationS1[0]S2[0]01S3[1]0S4[0]10 or 1S5[0]00S6[0]S0[0]resetCS 150 - Spring 2001 - Sequential Logic Examples - 5Finite String Pattern Recognizer (Step 2, cont’d)Exit conditions from state S3: have recognized …010If next input is 0 then have …0100 = ...100 (state S6)If next input is 1 then have …0101 = …01 (state S2)1...01...010 ...100S4[0]S1[0]S0[0]S2[0]101reset0 or 1S3[1]0S5[0]00S6[0]Exit conditions from S1: recognizes strings of form …0(no 1 seen); loop back to S1 if input is 0Exit conditions from S4: recognizes strings of form …1 (no 0 seen); loop back to S4 if input is 1...1...010CS 150 - Spring 2001 - Sequential Logic Examples - 6Finite String Pattern Recognizer (Step 2, cont’d)S2 and S5 still have incomplete transitionsS2 = …01; If next input is 1,then string could be prefix of (01)1(00) S4 handles just this caseS5 = …10; If next input is 1,then string could be prefix of (10)1(0) S2 handles just this caseReuse states as much as possibleLook for same meaningState minimization leads tosmaller number of bits torepresent statesOnce all states have completeset of transitions we havefinal state diagram1...01...010 ...100S4[0]S1[0]S0[0]S2[0]101reset0 or 1S3[1]0S5[0]00S6[0]...1...010...1011CS 150 - Spring 2001 - Sequential Logic Examples - 7module string (clk, X, rst, Q0, Q1, Q2, Z);input clk, X, rst;output Q0, Q1, Q2, Z;reg state[0:2];‘define S0 = [0,0,0]; //reset state‘define S1 = [0,0,1]; //strings ending in ...0‘define S2 = [0,1,0]; //strings ending in ...01‘define S3 = [0,1,1]; //strings ending in ...010‘define S4 = [1,0,0]; //strings ending in ...1‘define S5 = [1,0,1]; //strings ending in ...10‘define S6 = [1,1,0]; //strings ending in ...100assign Q0 = state[0];assign Q1 = state[1];assign Q2 = state[2];assign Z = (state == ‘S3);always @(posedge clk) begin if rst state = ‘S0; else case (state) ‘S0: if (X) state = ‘S4 else state = ‘S1; ‘S1: if (X) state = ‘S2 else state = ‘S1; ‘S2: if (X) state = ‘S4 else state = ‘S3; ‘S3: if (X) state = ‘S2 else state = ‘S6; ‘S4: if (X) state = ‘S4 else state = ‘S5; ‘S5: if (X) state = ‘S2 else state = ‘S6; ‘S6: state = ‘S6; default: begin $display (“invalid state reached”); state = 3’bxxx; endcaseendendmoduleFinite String Pattern Recognizer (Step 3)Verilog description including state assignment (or state encoding)CS 150 - Spring 2001 - Sequential Logic Examples - 8Finite String Pattern RecognizerReview of ProcessUnderstanding problemWrite down sample inputs and outputs to understand specificationDerive a state diagram Write down sequences of states and transitions for sequences to be recognizedMinimize number of states Add missing transitions; reuse states as much as possibleState assignment or encoding Encode states with unique patternsSimulate realization Verify I/O behavior of your state diagram to ensure it matches specificationCS 150 - Spring 2001 - Sequential Logic Examples - 9Mode Input M0011100Current State000001010110111101110Next State001010110111101110111Complex CounterSynchronous 3-bit counter has a mode control MWhen M = 0, the counter counts up in the binary sequenceWhen M = 1, the counter advances through the Gray code sequencebinary: 000, 001, 010, 011, 100, 101, 110, 111Gray: 000, 001, 011, 010, 110, 111, 101, 100Valid I/O behavior (partial)CS 150 - Spring 2001 - Sequential Logic Examples - 10Complex Counter (State Diagram)Deriving State DiagramOne state for each output combination Add appropriate arcs for the mode controlS0[000]S1[001]S2[010]S3[011]S4[100]S5[101]S6[110]S7[111]reset00 0 0 000011111111CS 150 - Spring 2001 - Sequential Logic Examples - 11Complex Counter (State Encoding)Verilog description including state encodingmodule string (clk, M, rst, Z0, Z1,
View Full Document
Unlocking...