Finite State Machines - Cornell University

Finite State Machines - Cornell University

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

Recently Viewed Presentations

  • Entrance Hymn SING TO THE MOUNTAINS Sing to

    Entrance Hymn SING TO THE MOUNTAINS Sing to

    Thanksgiving Hymn. On Eagle's Wings. You who dwell in the shelter of the Lord, Who abide in His shadow for life, ... And He will raise you up on eagle's wings,Bear you on the breath of dawn,Make you to shine...
  • Albert Einstein's Legacy

    Albert Einstein's Legacy

    We may all be happy and grateful that destiny gifted us with such an enlightened contemporary, a role model for the generations to come." 1931 "If I had known they were going to do this, I would have become a...
  • Macromizer Wheelbase Design 9.28.07 EJL 0.3125 wheel mount

    Macromizer Wheelbase Design 9.28.07 EJL 0.3125 wheel mount

    (gives 1cm above aluminum plate). Preferences: Soft pads to maximize shock absorption. Swivel pads to allow for angle compensation and floor irregularities. Recommended: Swivel Leveling Mount with Vibration Damping Pad (p1247) 3/8"-16 thread size, 1.875 in. pad diameter, 995lb. max...
  • Scaffolding Large Genomes Using Integer Linear Programming

    Scaffolding Large Genomes Using Integer Linear Programming

    Comparative biology. Re-sequencing and gap filling. Structural variation! gene XYZ. 3' UTR. 5' UTR. Sanger Sequencing. gene XYZ. 3' UTR. 5' UTR. Biologist: There are holes in my genes! Why Scaffolding? Annotation. Comparative biology. Re-sequencing and gap Filling.
  • Titanic 100 year commemoration th Blackmoor Park Junior

    Titanic 100 year commemoration th Blackmoor Park Junior

    The year was 1912 and the photos on this powerpoint will help you with ideas. We look forward to seeing your costumes! RMS Titanic RMS Titanic sank on April 15th 1912 on its maiden voyage from Southampton to New York...
  • 投影片 1 - Evergreen Shipping Agency Philippines Corporation

    投影片 1 - Evergreen Shipping Agency Philippines Corporation

    ShipmentLink Sailing Schedule www.shipmentlink.com ShipmentLink provides e-commerce services for Evergreen Line Thank You! For any question, please contact us at [email protected] ShipmentLink Sailing Schedule Thank You!
  • What is Syntax? - Columbia University

    What is Syntax? - Columbia University

    Preposing and postposing: Under a tree is a yellow dog. A yellow dog is under a tree. But not: *Under, is a yellow dog a tree. *Under a is a yellow dog tree. Prepositional phrases notable for ambiguity in attachment....
  • Chapter 2: Defining Communication as an Element of Culture

    Chapter 2: Defining Communication as an Element of Culture

    Race has been defined from two perspectives: biological and sociohistorical . Race as a sociohistorical concept: explaining how racial categories have varied over time, between cultures . The meaning of race has been debated in societies, and new categories have...