EECS150Section 7Finite State Machine Case StudiesFall 2001EECS150 - Fall 2001 1-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 logicEECS150 - Fall 2001 1-3Finite String Pattern Recognizer 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 seen Step 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 …EECS150 - Fall 2001 1-4Finite String Pattern Recognizer 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]resetEECS150 - Fall 2001 1-5Finite String Pattern Recognizer 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...010EECS150 - Fall 2001 1-6Finite String Pattern RecognizerS2 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...1011EECS150 - Fall 2001 1-7Mode 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)EECS150 - Fall 2001 1-8Complex Counter 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]reset0000000011111111EECS150 - Fall 2001 1-9"puppet""puppeteer who pulls the strings"controldata-pathstatus info and inputscontrol signal outputsstateDatapath and ControlDigital hardware systems = data-path + controlDatapath: registers, counters, combinational functional units (e.g., ALU), communication (e.g., busses)Control: FSM generating sequences of control signals that instructsdatapath what to do nextEECS150 - Fall 2001 1-10Digital Combinational Lock Door Combination Lock:Punch in 3 values in sequence and the door opens; if there is an error the lock must be reset; once the door opens the lock must be resetInputs: sequence of input values, resetOutputs: door open/closeMemory: must remember combination or always have it availableOpen questions: how do you set the internal combination?Stored in registers (how loaded?)Hardwired via switches set by userEECS150 - Fall 2001 1-11Implementation in Softwareinteger combination_lock ( ) {integer v1, v2, v3;integer error = 0;static integer c[3] = 3, 4, 2;while (!new_value( ));v1 = read_value( );if (v1 != c[1]) then error = 1;while (!new_value( ));v2 = read_value( );if (v2 != c[2]) then error = 1;while (!new_value( ));v3 = read_value( );if (v2 != c[3]) then error = 1;if (error == 1) then return(0); else return (1);}EECS150 - Fall 2001 1-12resetvalueopen/closednewclockSpecification How many bits per input value? How many values in sequence? How do we know a new input value is entered? What are the states and state transitions of the system?EECS150 - Fall 2001 1-13State DiagramStates: 5 statesRepresent point in execution of machineEach state has outputsTransitions: 6 from state to state, 5 self transitions, 1 globalChanges of state occur when clock says its okBased on value of inputsInputs: reset, new, results of comparisonsOutput: open/closedclosed closedclosedC1==value& newC2==value& newC3==value& newC1!=value& newC2!=value& newC3!=value& newclosedresetnot newnot newnot newS1 S2 S3 OPENERRopenEECS150 - Fall 2001 1-14DatapathStorage registers for combination valuesMultiplexerComparatorControlFinite-state machine controllerControl for data-path (which value to compare)resetopen/closednewC1 C2 C3comparatorvalueequalmultiplexercontrollermux controlclock44444Datapath and Control StructureEECS150 - Fall 2001 1-15State Table for Combination Lock Finite-State MachineRefine state diagram to take internal structure into accountState table ready for encodingreset new equal state state mux open/closed1–––S1C1closed00–S1S1C1closed010S1ERR–closed011S1S2C2closed...011S3OPEN–open...nextEECS150 - Fall 2001 1-16reset new equal state state mux open/closed1–––0001 001 00 0 – 0001 0001 001 00 1 0 0001 0000 – 00 1 1 0001 0010 010 0...0 1 1 0100 1000 – 1...nextmux is identical to last 3 bits of stateopen/closed is identical to first bit of state therefore, we do not even need to implement FFs to hold state, just use outputsresetopen/closednewequalcontrollermux controlclockEncodings for Combination LockEncode state tableState can be: S1, S2, S3, OPEN, or ERRNeeds at least 3 bits to encode: 000, 001, 010, 011, 100And as many as 5: 00001, 00010, 00100, 01000, 10000Choose 4 bits: 0001, 0010, 0100, 1000, 0000Output mux can be: C1, C2, or C3Needs 2 to 3 bits to encodeChoose 3 bits: 001, 010, 100Output open/closed can be: open or closedNeeds 1 or 2 bits to encodeChoose 1 bit: 1, 0EECS150 - Fall 2001 1-17C1 C2
View Full Document
Unlocking...