ECE2030 Introduction to Computer Engineering Lecture 16 Finite State Machines Prof Hsien Hsin Sean Lee School of Electrical and Computer Engineering Georgia Tech Mealy and Moore Machines MEALY MACHINE Inputs X t MOORE MACHINE Outputs Z t Inputs X t Combinational circuits Storage Element S t Z t S t X t Combinational circuits Storage Element S t Outputs Z t Z t S t 2 State and State Diagram A state represents the machine snapshot at a given clock period A clock is typically used to synchronize the state transition A graph consists of a set of Circles Each represents a state Use double circle to represent the initial state Directed arc each represents a state transition Inputs outputs Mealy machine Label input output along each arc Moore machine Label input along each arc Label output inside the circle i e state 3 State Diagrams a p b p Sk a b Sj a q Sk p b q Sj q a b A Mealy machine example A Moore machine example Example State S t Sk Sj Inputs X t a b Outputs Z t p q Initial state S 0 Sk 4 State Diagram Examples Mealy 0 0 S0 S1 1 0 0 0 1 1 0 0 S0 0 0 1 1 S1 1 0 5 State Diagram Examples Moore 0 S0 1 S1 0 1 0 1 0 S0 0 0 1 S1 1 1 6 Design Example Sequence Recognizer A sequential circuit that recognizes the occurrence of a particular bit sequence Input X t 0 1 Output Z t 0 1 1 if X t 3 t 1101 Z t 0 Otherwise 7 Sequence Recognizer 1 if X t 3 t 1101 Z t 0 Otherwise Time X t Z t 0 1 0 1 0 0 2 0 0 3 1 0 4 0 0 5 1 0 6 1 0 7 0 0 8 1 1 9 10 11 12 13 14 15 16 0 1 1 0 1 1 0 1 0 0 0 0 1 0 0 1 8 Sequence Recognizer 1 if X t 3 t 1101 Z t 0 Otherwise Time X t Z t 0 1 0 1 0 0 2 0 0 3 1 0 4 0 0 5 1 0 6 1 0 7 0 0 8 1 1 9 10 11 12 13 14 15 16 0 1 1 0 1 1 0 1 0 0 0 0 1 0 0 1 1 1 1 0 S0 0 0 S1 0 0 0 0 1 0 S2 S3 1 0 0 0 A Meanly Machine 9 State Table 1 1 1 0 00 01 10 11 1 0 0 0 0 0 0 0 1 0 0 0 Present State P1 P0 Input X Next State N1 N0 Outpu t Z 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 1 1 0 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 0 0 0 0 10 Logic Circuits Design Steps Generate a Boolean function for Each external output Each state encoded bit Simplify the Boolean functions Draw a D F F or register for each state encoded bit Draw logic circuits for External outputs Each inputs of state encoded bits Input of state encoded bits the next state Output of state encoded bits the current state 11 Logic Circuits Design Present State P1 X Next State X P0 Z N1 N0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 1 1 0 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 0 0 0 0 1 1 1 0 1 1 X P1P0 N1 00 01 11 10 0 0 0 0 1 1 0 1 0 1 P1P0 N1 XP1P0 P1P0 N0 00 01 11 10 0 0 0 0 1 N0 XP1P0 XP1P0 XP1P0 1 1 0 1 0 X P1 P0 XP1P0 Z XP1P0 12 Logic Circuits Design N0 X P1 P0 XP1P0 Z XP1P0 N1 XP1P0 P1P0 X N0 D0 F F P0 1 2 Z N1 D1 F F P1 1 2 13 Example 2 Input X t a b c Output Z t q p q when input sequence has even of a s and odd of b s Z t p Otherwise 14 State Diagram q when input sequence has even of a s and odd of b s Z t p Otherwise b c a c SEE p b b C SEO q SOO p a b SOE p c a a A Moore Machine 15 State Table b c a c b C 00 p 01 q b 10 p a a SEE 00 SEO 01 SOO 10 SOE 11 a 00 b 01 c 10 p 0 q 1 b Present State 11 p c a Input a b c Next State Outpu t P1 P0 X1 X0 N1 N0 Z 0 0 0 0 1 1 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0 0 1 0 1 0 1 0 1 0 0 1 0 1 1 0 0 1 1 1 0 0 0 0 1 0 1 0 0 1 1 1 0 1 0 1 0 1 0 0 1 1 0 0 0 0 0 1 1 0 1 1 0 0 1 1 1 0 1 1 0 16 Logic Circuit Design Present State Input Next State Output N1 X1X0 P1P0 00 01 11 10 00 1 0 X 0 01 1 0 X 0 P1 X1 X0 P1 X0 X1 11 0 1 X 1 P1 X1 X0 10 0 1 X 1 P1 P0 X1 X0 N1 N0 Z 0 0 0 0 1 1 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0 0 1 0 1 X1X0 P1P0 00 01 11 10 0 1 0 1 0 0 1 00 1 1 X 0 0 1 1 0 0 1 1 01 0 0 X 1 1 0 0 0 0 1 0 11 0 0 X 1 1 0 0 1 1 1 0 10 1 1 X 0 1 0 1 0 1 0 0 01 11 10 N1 P1X1X0 P1X0 P1X1 N0 Z 1 1 0 0 0 0 0 X1X0 P1P0 00 1 1 0 1 1 0 0 00 0 0 X 0 1 1 1 0 1 1 0 01 1 1 X 1 11 0 0 X 0 10 0 0 X 0 N0 P0X1 P0X1 P0 X1 Z P1P0 17 Logic Circuit Design N1 P1 X1 X0 X1 Z P1P0 N0 P0 X1 N0 D0 F F P0 1 2 X0 N1 D1 F F Z P1 1 2 18 Vending Machine State Machine Dispense a Coke when depositing 15 Inputs 5 a nickel 10 a dime BC bad coin including quarters in this example Outputs R reject C coke N …
View Full Document
Unlocking...