Set_3_lec 4 FSM Design.pptx

Finite State Machine: Mealy & Moore Models Dr. Hani Saleh Outline FSM structure FSM Types: Moore & Mealy Common Pitfalls Regarding Transition Properties FSM with Counter and Decoder Unused States 2  3 Block...

Finite State Machine: Mealy & Moore Models Dr. Hani Saleh Outline FSM structure FSM Types: Moore & Mealy Common Pitfalls Regarding Transition Properties FSM with Counter and Decoder Unused States 2  3 Block Diagram of a Sequential Machine Figure 3.15 Block diagram of a sequential machine. FSM Definition FSM consists of Inputs: b; Outputs: x Set of states x=0 Ex: {Off, On1, On2, On3} Off b’ Set of inputs, set of outputs b Ex: Inputs: {b}, Outputs: {x} x=1 x=1 x=1 Initial state On1 On2 On3 Ex: “Off” Set of transitions We often draw FSM graphically, Describes next states known as state diagram Ex: Has 5 transitions Set of actions Can also use table (state table), or Sets outputs while in states textual languages Ex: x=0, x=1, x=1, and x=1 4  5 Finite State Machines: Mealy and Moore Figure 3.17 Block diagram structures of finite state machines: (a) a Mealy machine and (b) a Moore machine.  6 Sequential Machine Models Mealy Model: The outputs are functions of both the inputs and the internal state variables. On the Mealy state diagram the transition paths are labeled with the combination of input values causing the transition and the combination of output values resulting from the transition.  7 Mealy Model: 00/0 10/1 , 11/1 00/1 01/0 10/1 C S Fig.1: Mealy State Diagram 01/0 , 11/0 For JK Flip-Flop Xi Zk Inputs Combinational Outputs Logic for Outputs and Mealy Machine Block Next State Diagram State State Register Clock Feedback  8 Sequential Machine Models … Moore Model: The outputs are associated with particular states and so appear as labels along with the state name. The transitions are labeled only with the input combinations giving rise to the transition.  9 Moore Model: 00 10 , 11 00 01 S/1 10 C/0 Fig.3: Moore State Diagram 01 , 11 For JK Flip-Flop State Register Xi Comb. Combinational Inputs Logic for Logic for Outputs Next State (Flip-flop Zk Inputs) Outputs Clock Moore Machine Block state Diagram feedback  10 Moore v.s. Mealy Moore model tends to require more states to cater for all the output conditions, but the corresponding output functions are simpler since they are independent of the input variables. Moore machine outputs change synchronously with the state transition and the clock edge. Mealy machine outputs are asynchronous and can change in response to changes in the inputs, independent of the clock. Moore machines have the advantage of disciplined timing methodology compared with Mealy machines. Traditionally, Mealy models are used for synchronous design, and Moore models are used for asynchronous design.  11 Synchronous Mealy Machines Glitches in the output are inherent in the asynchronous nature of the Mealy machine. Some designers like to use Mealy machines because they result in fewer states, compared to Moore machines.  Moore outputs are glitch free To eliminate the glitch problem the Mealy machine output needs to be synchronized.  Becomes Moore Machine Synchronization of Mealy output is achieved by breaking the direct connection between inputs and outputs with the introduction of storage elements as shown in the next diagram.  12 Synchronous Mealy Machines … Clock Xi Zk Inputs Combinational Outputs Logic for Outputs and Next State State Register Clock state feedback Block Diagram Synchronous Mealy Machine FSM Example: Secure Car Key 13 FSM Example: Secure Car Key Many new car keys include tiny computer chip –When car starts, car’s computer (under engine hood) requests identifier from key –Key transmits identifier Inputs: a; Outputs: r 4-bits, one bit at a time If not, computer shuts off car Wait r=0 FSM a a’ –Wait until computer requests ID K1 K2 K3 K4 (a=1) r=1 r=1 r=0 r=1 –Transmit ID (in this case, 1101) 14  FSM Example: Secure Car Key (cont.) Nice feature of FSM n I puts: a;Outputs: r Wait –Can evaluate output behavior r=0 a a’ for different input sequence K1 K2 K3 K4 –Timing diagrams show states r=1 r=1 r=0 r=1 and output values for different input waveforms Q: Determine states and r value for given input waveform: K1 clk clk n I puts n I puts a a State Wait Wait K1 K2 K3 K4 Wait Wait State Wait Wait K1 K2 K3 K4 Wait 15 Outputs Output r r  FSM Example: Code Detector Unlock door (u=1) only when buttons Start s pressed in sequence: u r Door –start, then red, blue, green, red Red g Code lock Green detector Input from each button: s, r, g, b Blue b –Also, output a indicates that some a colored button is being pressed FSM Inputs: s,r,g,b,a; Outputs: u –Wait for start (s=1) in “Wait” Wait –Once started (“Start”) u=0 s s’ ar’ ab’ ag’ ar’ If see red, go to “Red1” Then, if see blue, go to “Blue” Start a’ Then, if see green, go to “Green” u=0 ar Then, if see red, go to “Red2” ab ag ar – In that state, open the door (u=1) Red1 Blue Green Red2 Wrong button at any step, return to a’ a’ a’ u=0 u=0 u=0 u=1 “Wait”, without opening door Q: Can you trick this FSM to open the door, without knowing the code? A: Yes, hold all buttons 16 simultaneously Improve FSM for Code Detector Inputs: s,r,g,b,a; Outputs: u Wait s’ ar’ ab’ ag’ ar’ Q: did that solve u=0 s all problems with this FSM? Start a’ We’ll discuss u=0 ar later ab ag ar Red1 Blue Green Red2 a’ a’ a’ u=0 u=0 u=0 u=1 New transition conditions detect if wrong button pressed, returns to “Wait” FSM provides formal, concrete means to accurately define desired behavior 17 Common Pitfalls Regarding Transition Properties a Only one condition should be b ab=11 – true next state? –For all transitions leaving a state a –Else, which one? a’b One condition must be true –For all transitions leaving a state –Else, where go? 18  Verifying Correct Transition Properties  Can verify using Boolean algebra Answer: a * a’b Only one condition should be true: AND of each condition pair (for = (a * a’) * b transitions leaving a state) should equal 0  proves pair can never =0*b simultaneously be true =0 OK! One condition must be true: OR of all conditions of transitions a + a’b leaving a state) should equal 1  proves = a*(1+b) + a’b a at least one condition must be true = a + ab + a’b Example = a + (a+a’)b a’b =a+b Fails! Might not Q: For shown transitions, prove whether: be 1 (i.e., a=0, * Only one condition true (AND of each pair is always 0) b=0) * One condition true (OR of all transitions is always 1) ab’ * ab’ (a’b’+a’b+ab) +a’b’+a’b+ab How to ab’ = (a * a’) *b’ = 0 * b’ solve the =0 =1 Pass! problem? a’b’+a’b+a OK! 19It is always 1 b  Evidence that Pitfall is Common Recall code detector FSM –We “fixed” a problem with the Wait transition conditions u=0 s s’ –Do the transitions obey the two Start required transition properties? a’ u=0ar Consider transitions of state ab ag ar Start, and the “only one true” Red1 Blue Green Red2 property u=0 a’ u=0 a’ u=0 a’ u=1 ar * a’ a’ * a(r’+b+g) ar * a(r’+b+g) Intuitively: press red and blue = (a*a’)r = 0*r = (a’*a)*(r’+b+g) = buttons at same time: conditions 0*(r’+b+g) = ar, and a(r’+b+g) will both be true. Which one should be (a*a)*r*(r’+b+g) = a*r*(r’+b+g) taken? =0 =0 = arr’+arb+arg = 0 + arb+arg Q: How to solve? = arb + arg A: ar should be arb’g’ = ar(b+g) (likewise for ab, ag, ar) Fails! Means that two of Start’s Note: As evidence the pitfall is common, the author of transitions could be true this example admitted the mistake was not intentional – A reviewer of his book20 caught it. Design Process using FSMs 1. Determine what needs to be remembered  What will be stored in memory? 2. Encode the inputs and outputs in binary (if necessary) 3. Construct a state diagram of the behavior of the desired device  Optionally – minimize the number of states needed 4. Assign each state a binary number (code) 5. Choose a flip-flop type to use  Derive the flip-flop input maps (In this course we’ll use D-FF only) 6. Produce the combinational logic equations and draw the schematic from them  22 Example: A synchronous sequential machine with two inputs (x,y) and one output (z) is required to detect the serial occurrence of the sequence pair of inputs 00, 00, 11, 10 on the two inputs and to give an output 1 during the final combination of the detected sequence.  Draw Mealy & Moore models of the machine.  Setup the state-transition table for both models.  23 Solution: Mealy Model & State Transition Table 00/0 00/0 11/0 00/0 01/0 10/0 11/0 2 3 4 1 01/0,10/0,11/0 10/0,01/0 00/0 10/1,01/0,11/0  24 Solution: … Next-State Output (z) Present State Inputs x,y Inputs x,y 00 01 11 10 00 01 11 10 1 2 1 1 1 0 0 0 0 2 3 1 1 1 0 0 0 0 3 3 1 4 1 0 0 0 0 4 2 1 1 1 0 0 0 1  25 Solution: Moore model & State Transition Table 10 5/1 01 10 00 00 11 11 00 00 01 10 01,10,11 2/0 3/0 4/0 1/0 11 10,01 00 01,11  26 Solution: … Next-State Output Present Inputs (x,y) (z) State 00 01 11 10 1 2 1 1 1 0 2 3 1 1 1 0 3 3 1 4 1 0 4 2 1 1 5 0 5 2 1 1 1 1  27 State Reduction State table/diagram may contain redundant states which should be eliminated as this will reduce the number of components required in the final implementation. State reduction is concerned with reducing the number of states in a state table/diagram while keeping the external input-output requirements unchanged. Many redundant states can be found from inspection of the state table: A pair of states can be merged if they have identical next-states and output entries for every input combination.  28 State Reduction … Example: Derive the state table corresponding to the synchronous machine with the state diagram shown below. The machine outputs a 1 when the serial pattern 101 is detected. 0/0 1/0 0/0 1/0 0/0 1/1 A B C D 1/0 0/0  29 Example … Present Next State/Output State In=0 In=1 A A/0 B/0 B C/0 B/0 C A/0 D/1 D A/0 B/0 Compare rows A & D. The entries are identical in all cases. Thus A & D can be MERGED, giving:  30 Example … Present Next State/Output State In=0 In=1 A A/0 B/0 B C/0 B/0 C A/0 A/1 The reduced state table can now be used to complete the solution leading to circuit implementation. FSM Alternative Design There are some other methods to implement a FSM; one of them is to use a a counter to store the current state and a decoder to generate signals corresponding to each state The counter can be incremented, cleared or loaded with a value to go from one state to another. Unlike the other methods, you don’t have to generate the same state value in order to remain in the same state; this can be accomplished by neither incrementing, clearing nor loading the counter  FSM with Counter and Decoder The counter plays the role of the register in Mealy and Moore designs, as well as a portion of the next state logic The state value is input to a decoder; each output of the decoder represents one state The decoder outputs and system inputs are input to the logic bloc that generates the system outputs and the information needed to generate the next state value FSM with Counter and Decoder If the system inputs are used to generate both the next state and the system outputs, this design can be used to implement a Mealy machine. If the system outputs are generated solely by using the state value, and the system inputs are used only to generate the next state, then it implements a Moore machine Modulo 6 counter Moore implementation using this approach Example: Modulo 6 Counter - Specification A module 6 counter is a 3-bit counter that counts through the following sequence: –000->001->010->011->100->101->000->… –0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 0 … It doesn’t use value 6 (110) nor 7 (111) It has an input U that controls the counter: –When U=1 the counter increments its value on the rising edge of the clock –When U=0 the counter retains its value on the rising edge of the clock The value of the count is represented as three bit value (V2V1V0) There is an additional output C (Carry) that is 1 when going from 5 to 0 and 0 otherwise (the C output remains 1 until the counter goes from 0 to 1) Modulo 6 Counter – Moore state diagram The outputs are represented adjacent to the state The inputs are represented on the arcs Modulo 6 Counter – State table Present U Next C V2V1V0 For each state examine what State State happens for all possible values S0 0 S0 1 000 of the inputs S0 1 S1 0 001 –In state S0 input U can be either S1 0 S1 0 001 0 or 1 S1 1 S2 0 010 –If U=0 the state machine remains S2 0 S2 0 010 in state S0 and outputs C=1 and V2V1V0=000 S2 1 S3 0 011 –If U=1 the state machine goes in S3 0 S3 0 011 state S1, outputs C=1 and S3 1 S4 0 100 V2V1V0=001 S4 0 S4 0 100 In the same manner, each state S4 1 S5 0 101 goes to the next state if U=1 S5 0 S5 0 101 and remains in the same state S5 1 S0 1 000 if U=0 Modulo 6 Counter Moore Implementation with Counter and Decoder The 3 bit counter holds the present state and sends its value to the decoder The output of the decoder represents the states: output 0 represents S0, and so on Since this is a Moore machine, only the state signals are combined to produce the outputs V2V1V0 and C The next state control, when U=1, the modulo 6 counter is incremented. When the output is 000, 001, 010, 011, 100 this is accomplished by incrementing the state counter. When the output is 101, incrementing the counter would result in a value of 110 of the state counter, which is not right, while 000 is the desired value. In this case, the counter is cleared. When U=0, no signal is activated and the counter retains its previous value, thus remaining in the same state. Unused States The FSM presented so far works well if it is in a known state There will be a problem if the machine enters an unused state, also called unknown state or undefined state This could be caused by a flaw in the design but most of the times, this is happening when the machine powers-up. Modulo 6 Counter Analysis The modulo 6 counter (consider Moore machine implementation) has six states with binary state values from 000 to 101 The state value is stored in the register of the finite state machine hardware; an unused state is entered when an unused state is stored in this register; The unused states for this design example are 110 and 111 Modulo 6 Counter – Revised (acceptable) diagram When present state is 110, the next state is 110 if U=0 or 111 if U=1 When present state is 111, the next state is 111 if U=0 or 000 if U=1 Modulo 6 Counter – Revised (wrong) diagram If a circuit that implements this diagram powers-up in state 110 or 111 will never reach a valid state Modulo 6 Counter – State diagram with dummy states Create dummy states for all unused states Each dummy state would go to a known state on the next clock cycle (usually to a reset state) Two dummy states: 110 and 111 By convention, the values 1 on the arcs indicate that the transfer is unconditional – that is always taken Note also the output values: C=0 and 111 indicates the user that the machine is in an invalid state (it is a design decision) BACKUP 43