Finite State Machines Hakim Weatherspoon CS 3410 Computer Science Cornell University [Weatherspoon, Bala, Bracy, McKee, and Stateful Components Combinationial logic Output computed directly from inputs System has no internal state Nothing depends on the past! Inputs Need: N Combinational circuit M Outputs To record data
To build stateful circuits A state-holding device Sequential Logic & Finite State Machines 2 Goals for Today Finite State Machines (FSM) How do we design logic circuits with state? Types of FSMs: Mealy and Moore Machines Examples: Serial Adder and a Digital Door Lock 3 Next Goal How do we design logic circuits with state? 4 Finite State Machines 5 Finite State Machines An electronic machine which has external inputs externally visible outputs
internal state Output and next state depend on inputs current state 6 Abstract Model of FSM Machine is M = (S, I, O, ) S: Finite set of states I: Finite set of inputs O: Finite set of outputs : State transition function Next state depends on present input and present state 7 Automata Model Registers Finite State Machine
Current State Inpu t Comb . Logic Output Next State inputs from external world outputs to external world internal state combinational logic 8 FSM Example input/ output stat e up/off
B A star t stat e Legen d down/ on up/off up/ off C Input: up or down Output: on or off States: A, B, C, or D down/ on
up/off D down/off down/ off 9 FSM Example i0i1i2/ o0o1o2 0/ 0 S1S S1 S 0 0 Legen d 1/1
0 1 0 0 0/0 0/ 1 1 0 Input: 0=up or 1=down 1/0 Output: 1=on or 0=off States: 00=A, 01=B, 10=C, or 11=D 1/ 1 0/ 0 1 1 1/0
10 Mealy Machine Registers General Case: Mealy Machine Current State Inpu t Comb . Logic Output Next State Outputs and next state depend on both current state and input 11 Moore Machine Registers
Special Case: Moore Machine Current State Inpu t Comb. Logic Comb. Logic Output Next State Outputs depend only on current state 12 Moore Machine FSM Example input stat e out u p star
tout Legen d A off dow n up up Input: up or down Output: on or off States: A, B, C, or D C off down B on dow n u
p D off down 13 Mealy Machine FSM Example input/ output stat e up/off B A star t stat e Legen d down/ on
up/off up/ off C Input: up or down Output: on or off States: A, B, C, or D down/ on up/off D down/off down/ off 14 Activity#2: Create a Logic Circuit for a Serial Adder Add two infinite input bit streams
streams are sent with least-significant-bit (lsb) first How many states are needed to represent FSM? 10110 Draw and Fill in FSM diagram Sum: output 00101 01111 Strategy: (1) Draw a state diagram (e.g. Mealy Machine) (2) Write output and next-state tables (3) Encode states, inputs, and outputs as bits (4) Determine logic equations for next state and outputs 15 Activity#2: Create a Logic Circuit for a Serial Adder Add two infinite input bit streams streams are sent with least-significant-bit (lsb) first 10110 01111 Sum: output 00101
16 Strategy for Building an FSM (1) Draw a state diagram (e.g. Mealy Machine) (2) Write output and next-state tables (3) Encode states, inputs, and outputs as bits (4) Determine logic equations for next state and outputs (5) Draw the Circuit 17 FSM: State Diagram 10110 01111 00101 2 states ___ and ___ Inputs: ___ and ___ Output: ___ 18 FSM: State Diagram
__/_ __/_ S0 __/_ __/_ __/_ S1 __/_ __/_ __/_ a10110 b01111 00101z 2 states ___ and ___ Inputs: ___ and ___ Output: ___ 19 Serial Adder: State Table
__/_ a b Curre nt state z Next state __/_ S0 __/_ __/_ __/_ S1 __/_
__/_ __/_ (2) Write down all input and state combinations 20 Serial Adder: State Table __/_ a b Curre nt state z Next state __/_ S0 __/_
__/_ __/_ S1 __/_ __/_ __/_ (3) Encode states, inputs, and outputs as bits 21 Serial Adder: State Assignment __/_ __/_ S0 __/_ a b s
z s' 0 0 0 0 0 0 1 0 1 0 1 0
0 1 0 1 1 0 0 1 0 0 1 1 0 0 1
1 0 1 1 0 1 0 1 1 1 1 1 1 __/_
__/_ S1 __/_ __/_ __/_ (4) Determine logic equations for next state and outputs 22 Serial Adder: State Assignment a b s z s' 0
0 0 0 0 0 1 0 1 0 1 0 0 1 0 1
1 0 0 1 0 0 1 1 0 0 1 1 0 1
1 0 1 0 1 1 1 1 1 1 (4) Determine logic equations for next state and outputs 23 Example: Digital Door Lock Digital Door Lock
Inputs: keycodes from keypad clock Outputs: unlock signal display how many keys pressed so far 24 Door Lock: Inputs Assumptions: signals are synchronized to clock Password is B-A-B K A B K 0 1 1
A 0 1 0 B 0 0 1 Meaning (no key) A pressed B pressed 25 Door Lock: Outputs Assumptions: High pulse on U unlocks door D3D2D1D0 4
LED 8 dec U Strategy: (1) Draw a state diagram (e.g. Moore Machine) (2) Write output and next-state tables (3) Encode states, inputs, and outputs as bits (4) Determine logic equations for next state and 26 outputs Door Lock: Simplified State Diagram (1) Draw a state diagram (e.g. Moore Machine)27 Door Lock: Simplified State Diagram Cur. Output State (2) Write output and next-state tables 28
Door Lock: Simplified State Diagram Cur. Input State (2) Write output and next-state tables Next State 29 3bit Reg S2-0 D3-0 4 de c Door Lock: Implementation U clk
S2-0 K A S2-0 S2 S1 S0 D3 D2 D1 D0 U B (4) Determine logic equations for next state and outputs 30 Door Lock: Implementation 3bit Reg S2-0 D3-0 4 A B
S2 S1 S0 de c S2 S1 S0 K U clk S2-0 K A S2-0 B (4) Determine logic equations for next state and outputs 31 3bit Reg S2-0 D3-0
4 de c Door Lock: Implementation U clk S2-0 K A S2-0 B Strategy: (1) Draw a state diagram (e.g. Moore Machine) (2) Write output and next-state tables (3) Encode states, inputs, and outputs as bits (4) Determine logic equations for next state and 32 Registers Door Lock: Implementation Current
State Inpu t Comb. Logic Comb. Logic Output Next State Strategy: (1) Draw a state diagram (e.g. Moore Machine) (2) Write output and next-state tables (3) Encode states, inputs, and outputs as bits (4) Determine logic equations for next state and 33 Summary We can now build interesting devices with sensors Using combinational logic We can also store data values Stateful circuit elements (D Flip Flops, Registers, )
State Machines or Ad-Hoc Circuits 34
