Report

STATE DIAGRAM AND STATE TABLES Copyright 2012 - Joanne DeGroat, ECE, OSU 2 Problem Statement specifies the desired relationship between the input and output sequences. Sometimes called the specification. First step is to translate this specification into a state table or state graph. In the HDL world, there is a style that allows creation of the next state specification that does not require either a state graph or state table. 9/2/2012 – ECE 3561 Lect 6 DERIVATION OF STATE GRAPHS STATE DIAGRAM State transition diagram a circle: a state a directed lines connecting the circles: the transition between the states Each directed line is labeled “inputs/outputs” state: A B input: x FLIP-FLOP INPUT EQUATIONS The part of circuit that generates the inputs to flip-flops Also called excitation functions DA = Ax +Bx DB = A'x The Ax Ax +Bx Bx A 'x output equations to fully describe the sequential circuit y = (A+B)x' A+B ANALYSIS WITH D FLIP-FLOPS The input equation DA=A⊕x⊕y The state equation A(t+1)=A⊕x⊕y ANALYSIS WITH JK FLIP-FLOPS Determine the flip-flop input function in terms of the present state and input variables Used the corresponding flip-flop characteristic table to determine the next state Fig. 5-18 Sequential circuit with JK flip-flop JA = B KA= Bx' JB = x ' KB = A'x + Ax ' STATE TABLE FOR FIG. 5-18 JA = B, KA= Bx' JB = x ', KB = A'x + Ax ' State Transition Diagram for Fig. 5-18 Method 1 The characteristic equation of JK FF is A(t 1) JA K A B(t 1) JB K B State equation for A and B : A(t 1) BA ( Bx) A AB AB Ax , , B(t 1) xB ( A x)B Bx ABx ABx State Transition Diagram for Fig. 5-18 Method 2 x AB00 A(t +1) 01 11 10 0 0 1 0 1 AB’ 1 0 1 1 1 A’B Ax Using K-map, we also can derive A(t+1). A(t +1)=A ’B+AB ’+Ax ANALYSIS WITH T FLIP-FLOPS The characteristic equation Q(t+1)= T⊕Q = TQ'+T'Q The specification Copyright 2012 - Joanne DeGroat, ECE, OSU 11 The circuit will examine a string of 0’s and 1’s applied serially, once per clock, to the X input and produce a 1 only when the prescribed input sequence occurs. Any sequence ending in 101 will produce and output of Z=1 coincident with the last 1 input. The circuit does not reset when a 1 output occurs so when ever a 101 is in the data stream a 1 is output coincident with the last 1. 9/2/2012 – ECE 3561 Lect 6 A SEQUENCE DETECTOR EXAMPLE 9/2/2012 – ECE 3561 Lect 6 GENERAL FORM OF THE CIRCUIT The circuit has the general form X – serial input stream Z – serial output stream Clk – the clock 12 Copyright 2012 - Joanne DeGroat, ECE, OSU Here meaning of starting state can be The system has been reset and this is the initial state A sequence of 2 or more 0’s has been received Copyright 2012 - Joanne DeGroat, ECE, OSU 13 Choose a starting state and a meaning for that state. The starting state is typically a reset state. 9/2/2012 – ECE 3561 Lect 6 START CONSTRUCTION OF THE GRAPH. Now add state S1 Copyright 2012 - Joanne DeGroat, ECE, OSU 14 Meaning – a sequence of 0…01 has been received when coming from state S0 Meaning – the first 1 has been received. 9/2/2012 – ECE 3561 Lect 6 ADD THE NEXT STATE What happens when in S1 Copyright 2012 - Joanne DeGroat, ECE, OSU 15 A 0 input causes transition to a new state S2 with new meaning A 1 keeps you in S1 where the first 1 of a possible 101 sequence has occurred. 9/2/2012 – ECE 3561 Lect 6 TRANSITIONS FROM S1 State S2 – what is the meaning of being here? Copyright 2012 - Joanne DeGroat, ECE, OSU 16 When transition is from S1 it means we have receive an input stream of xxx10. 9/2/2012 – ECE 3561 Lect 6 STATE S2 Are currently in S2 A 1 arrives and now have a sequence of 101 Action – Output a 1 and have the first 1 of a new sequence, i.e., transition to S1 A 0 arrives – now have a sequence of 100 Action – Move back to state S0 where you do not even have the start of a sequence, i.e., one or more 0 inputs. Copyright 2012 - Joanne DeGroat, ECE, OSU 17 9/2/2012 – ECE 3561 Lect 6 TRANSITIONS FROM S2 The now completed diagram state 9/2/2012 – ECE 3561 Lect 6 THE FULL STATE DIAGRAM 18 This can now be used to generate a state table – more on that later Copyright 2012 - Joanne DeGroat, ECE, OSU Copyright 2012 - Joanne DeGroat, ECE, OSU 19 Problem Statement: The circuit has the same form as before and shown below. The circuit will detect input sequences that end in 010 or 1001. When a sequence is detected the output Z is 1, otherwise Z is 0. 9/2/2012 – ECE 3561 Lect 6 ANOTHER EXAMPLE Copyright 2012 - Joanne DeGroat, ECE, OSU 20 The RESET state – have no inputs yet Then if you have a 0 input the output is 0 – transition to S1 If you have a 1 input the output is 0 and transition to S2 9/2/2012 – ECE 3561 Lect 6 THE INITIAL STATE 9/2/2012 – ECE 3561 Lect 6 MEANING OF STATES S0 – Reset S1 – 0 but not 10 S4 – 1 but not 01 21 Copyright 2012 - Joanne DeGroat, ECE, OSU Copyright 2012 - Joanne DeGroat, ECE, OSU 22 Add S2 having meaning that a 01 sequence has been received. Add S3 having meaning that the sequence 10 has been received 9/2/2012 – ECE 3561 Lect 6 MORE STATES S0 – Reset S1 – 0 but not 10 S2 – Sequence of 01 S3 – Sequence of 10 S4 – 1 but not 01 9/2/2012 – ECE 3561 Lect 6 MEANING OF STATES AFTER S2 S3 23 Copyright 2012 - Joanne DeGroat, ECE, OSU Copyright 2012 - Joanne DeGroat, ECE, OSU 24 In S2 (01) and get a 0 – Transition to S3 (10) – output a 1 In S3 (10) and get a 1 – Transition to S2 (01) 9/2/2012 – ECE 3561 Lect 6 CONSIDER INPUTS WHEN IN S2, S3 S5 – Have received input sequence 100 9/2/2012 – ECE 3561 Lect 6 ADD A NEW STATE S5 25 Copyright 2012 - Joanne DeGroat, ECE, OSU 9/2/2012 – ECE 3561 Lect 6 WHEN IN S5 In S5 Input of a 1 means you have had a input of 1001 so transition to S2 as the input sequence now ends in 01 while Z is 1. 26 Copyright 2012 - Joanne DeGroat, ECE, OSU 9/2/2012 – ECE 3561 Lect 6 ADD OTHER TRANSITIONS Complete the transitions not yet covered Each state should have an output transition for both a 0 and a 1. 27 Copyright 2012 - Joanne DeGroat, ECE, OSU 9/2/2012 – ECE 3561 Lect 6 THE MEANING OF THE STATES S0 – Reset S1 – 0 (but not 10) S2 – Sequence of 01 S3 – Sequence of 10 S4 – 1 (but not 01) S5 – Sequence of 100 28 Copyright 2012 - Joanne DeGroat, ECE, OSU Guidelines for Construction of State Graphs Copyright 2012 - Joanne DeGroat, ECE, OSU 29 First, construct some sample input and output sequences to make sure you understand the problem (ref slides 5 and 13) Determine under what conditions the circuit is in reset state. If only one or two sequences lead to a 1 output construct a partial state graph. OR determine what sequences or groups of sequences must be remembered When adding transitions see if you transition to a defined state or a new state is to be added Make sure all state have a transition for both a 0 and a 1 but only 1! Add annotation or create a table to expound the meaning of each state. 9/2/2012 – ECE 3561 Lect 6 GUIDELINES MOORE MACHINE MEALY MACHINE VS. MOORE MACHINE Modern Design Register-transfer-level block diagram C: Combinational circuit S: Sequential circuit C Q S D S . . C C Q D S Control Unit C C Datapath FSM DESIGN D or JK or T ?? current state register next state In ？ DX clk QXcurrent state Out QY ？ DY clk next state logic output logic 34 The same sequence detector to detect a sequence ending in 101 but this time a Moore machine implementation. Moore machine implementation is much the same except that the output designation is now indicated within the state. 9/2/2012 – ECE 3561 Lect 7 CONSIDER THE SEQUENCE DETECTOR Copy right 2012 Joan ne DeGr oat, ECE, 35 S0 –a state where you have received a non middle 0 or a long string of 0s. Output is 0. Output is indicated within the state not on the transition. 9/2/2012 – ECE 3561 Lect 7 START IN S0 Copy right 2012 Joan ne DeGr oat, ECE, 36 On a 0 you stay in state 1 On a 1 you transition to state S1. Meaning of S1 – have the 1st 1 of the sequence 9/2/2012 – ECE 3561 Lect 7 TRANSITIONS FORM STATE 1 Copy right 2012 Joan ne DeGr oat, ECE, 37 On a 1 have the first 1 of a sequence – stay in S1. On a 0 now have a sequence that ends in 10 so define a new state S2 and transition to it. 9/2/2012 – ECE 3561 Lect 7 TRANSITION FROM S1 Copy right 2012 Joan ne DeGr oat, ECE, 38 S2 has meaning that you have an input sequence that ends in 10 so far. Transitions from S2 9/2/2012 – ECE 3561 Lect 7 STATE S2 0 input – Back to S0 1 input – Valid sequence go to new state S3 which outputs a 1 Copy right 2012 Joan ne DeGr oat, ECE, 39 S3 – have received input sequence that ends in 101. Next input 9/2/2012 – ECE 3561 Lect 7 STATE S3 0 – end of seq (10 so back to S2) 1 – back to S1 (11 so 1st 1) Copy right 2012 Joan ne DeGr oat, ECE, Easy to convert state graph to state table 40 Moore machine note output is function of the state 9/2/2012 – ECE 3561 Lect 7 STATE TABLE FROM STATE GRAPH Copy right 2012 Joan ne DeGr oat, ECE, Mealy machine state graph and state table 41 In Mealy machine the output is a function of the state and the current input 9/2/2012 – ECE 3561 Lect 7 CONTRAST THIS TO MEALY MACHINE Copy right 2012 Joan ne DeGr oat, ECE, Detect the sequences 010 and 1001 and on those output a 1. 9/2/2012 – ECE 3561 Lect 7 NOW ON TO THE OTHER EXAMPLE 42 Starting state on reset is S0 On a 0 transition to S1 - output 0 Have a first 0 On a 1 transition to S3 - output 0 Have a first 1 Copy right 2012 Joan ne DeGr oat, ECE, State S1 have the first 0 of a possible 010 43 On a 1 now have 01 Transition to a new state S2/0 with meaning that you have 01 On a 0 stay in S1/0 9/2/2012 – ECE 3561 Lect 7 IN S1/0 Copy right 2012 Joan ne DeGr oat, ECE, 44 S2/0 has meaning that you have 01 so far 9/2/2012 – ECE 3561 Lect 7 FROM S2/0 Input is a 0 – Need a new state S4 with meaning that you have received 010 (so output is a 1) and have a 10 for a start of that string. Input is a 1 so the input is 011 – Go to S3 where as this is the first 1. Copy right 2012 Joan ne DeGr oat, ECE, S3/0 has meaning that you have the first 1 of the 1001 sequence. 45 Input is a 0 – Go to S5 – meaning have 10 Input is a 1 – stay in S3 9/2/2012 – ECE 3561 Lect 7 FROM S3/0 Copy right 2012 Joan ne DeGr oat, ECE, 46 S4/1 had meaning that the sequence has been 010 so far. 9/2/2012 – ECE 3561 Lect 7 ADD TRANSITIONS FROM S4/1 Input is a 0 – Now have 100 – Need a new state with this meaning – S6/0 Input is a 1 – Now have 101 so go back to S2/0 Copy right 2012 Joan ne DeGr oat, ECE, S5/0 means you have 10 so far 47 Input is a 0 – transition to S6/0 – have 100 so far Input is a 1 – now have 101 or the 01 which is the meaning of S2/0 9/2/2012 – ECE 3561 Lect 7 TRANSITIONS FROM S5/0 Copy right 2012 Joan ne DeGr oat, ECE, Input is a 1 so have 1001 – a new state S7/1 to signal the sequence 1001. Input is a 0 so have 1000 and back to S1 as you have a first 0. 48 S6/0 has meaning that you have a sequence of 100 so far 9/2/2012 – ECE 3561 Lect 7 STATE S6/0 Copy right 2012 Joan ne DeGr oat, ECE, Input is a 0 so have 010 – go to S4/1 Input is a 1 so have 011 – go to S3 as you have a first 1. 49 S7 has meaning of 1001 so you also have the 01 for the start of that sequence 9/2/2012 – ECE 3561 Lect 7 FROM S7/1 Copy right 2012 Joan ne DeGr oat, ECE, 9/2/2012 – ECE 3561 Lect 7 THE STATE TABLE FOR EACH For the Mealy Machine 50 Present State S0 S1 S2 S3 S4 S5 X=0 S1 S1 S3 S5 S3 S1 NEXT STATE X=1 S4 S2 S4 S2 S4 S2 OUTPUT X=0 X=1 0 0 0 0 1 0 0 0 0 0 0 1 Copy right 2012 Joan ne DeGr oat, ECE, Present State S0 S1 S2 S3 S4 S5 S6 S7 Next State X=0 S1 S1 S4 S5 S6 S6 S1 S4 Next State X=1 S3 S2 S3 S3 S2 S2 S7 S3 Output Z 0 0 0 0 1 0 0 1 51 The state table for the Moore machine – output is associated with the state. 9/2/2012 – ECE 3561 Lect 7 FOR THE MOORE MACHINE Copy right 2012 Joan ne DeGr oat, ECE, 52 The next step to implementation is state assignment In state assignment the binary code for each state is chosen. 9/2/2012 – ECE 3561 Lect 7 THE NEXT STEP Copy right 2012 Joan ne DeGr oat, ECE, 53 Choosing one state assignment versus another can have significant implications for circuit implementation. But first – how do you reduce the number of states in the state table? 9/2/2012 – ECE 3561 Lect 7 EFFECT OF CHOOSING STATE ASSIGNMENT Copy right 2012 Joan ne DeGr oat, ECE, Programmed Example 14.2 9/2/2012 – ECE 3561 Lect 7 EXAMPLE THAT HAS SINK STATE 54 Copy right 2012 Joan ne DeGr oat, ECE, The start of the state graph 9/2/2012 – ECE 3561 Lect 7 INITIAL STATES 55 Copy right 2012 Joan ne DeGr oat, ECE, More states 9/2/2012 – ECE 3561 Lect 7 STEP 2 56 Copy right 2012 Joan ne DeGr oat, ECE, 9/2/2012 – ECE 3561 Lect 7 COMPLETE STATE GRAPH 57 Copy right 2012 Joan ne DeGr oat, ECE, From the state graph the state table can be generated 9/2/2012 – ECE 3561 Lect 7 CORRESPONDING STATE TABLE 58 Copy right 2012 Joan ne DeGr oat, ECE, 59 Have covered state graphs for Mealy and Moore machines Have covered how to transition from state graphs to state tables. 9/2/2012 – ECE 3561 Lect 7 LECTURE SUMMARY Copy right 2012 Joan ne DeGr oat, ECE,