Finite State Machines for Logic Circuits
"Explore the concept of Finite State Machines (FSM) in designing logic circuits with state transitions, covering types like Mealy and Moore machines. Discover examples such as a Serial Adder and Digital Door Lock to grasp the application of FSM. Learn about the abstract and automata models of FSM, emphasizing the interplay between inputs, outputs, and states for effective circuit design."
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Finite State Machines Hakim Weatherspoon CS 3410 Computer Science Cornell University The slides are the product of many rounds of teaching CS 3410 by Professors Weatherspoon, Bala, Bracy, and Sirer.
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
Next Goal How do we design logic circuits with state?
Finite State Machines An electronic machine which has external inputs externally visible outputs internal state Output and next state depend on inputs current state
Abstract Model of FSM Machine is S: I: O: : M = ( S, I, O, ) Finite set of states Finite set of inputs Finite set of outputs State transition function Next state depends on present input and present state
Automata Model Finite State Machine Current State Output Registers Comb. Logic Input Next State inputs from external world outputs to external world internal state combinational logic
FSM Example down/on down/on input/output up/off B A start state state up/off up/off Legend up/off C D down/off down/off Input: up or down Output: on or off States: A, B, C, or D
FSM Example down/on down/on input/output up/off B A start state state up/off up/off Legend up/off C D down/off down/off Input: = up or = down Output: = on or = off States: = A, = B, = C, or = D
FSM Example 1/1 1/1 0/0 i0i1i2 /o0o1o2 01 00 S1S0 S1S0 0/0 0/0 Legend 0/0 10 11 1/0 Input: 0=up or 1=down Output: 1=on or 0=off States: 00=A, 01=B, 10=C, or 11=D 1/0
Mealy Machine General Case: Mealy Machine Current State Registers Output Comb. Logic Input Next State current state and input Outputs and next state depend on both
Moore Machine Special Case: Moore Machine Comb. Logic Current State Registers Output Comb. Logic Input Next State Outputs depend only on current state
Moore Machine FSM Example down down input up B on A off state out start out down up Legend up C off D off up down Input: up or down Output: on or off States: A, B, C, or D
Mealy Machine FSM Example down/on down/on input/output up/off B A start state state down/off up/off Legend up/off C D up/off down/off Input: up or down Output: on or off States: A, B, C, or D
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? Draw and Fill in FSM diagram Sum: output 10110 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
FSM: State Diagram 10110 00101 01111 states: Inputs: ??? and ??? Output: ??? .
FSM: State Diagram __/_ __/_ __/_ S1 S0 __/_ __/_ __/_ __/_ __/_ 10110 00101 01111 states: Inputs: ??? and ??? Output: ??? .
FSM: State Diagram __/_ __/_ __/_ S1 S0 __/_ __/_ __/_ __/_ __/_ ?? ?? Current state ? Next state (2) Write down all input and state combinations
FSM: State Diagram __/_ __/_ __/_ S1 S0 __/_ __/_ __/_ __/_ __/_ ?? ?? Current state ? Next state (3) Encode states, inputs, and outputs as bits
FSM: State Diagram ?? ?? Current state ? Next state (4) Determine logic equations for next state and outputs
Example: Digital Door Lock Digital Door Lock Inputs: keycodes from keypad clock Outputs: unlock signal display how many keys pressed so far
Door Lock: Inputs Assumptions: signals are synchronized to clock Password is B-A-B K A B Meaning 0 0 0 (no key) K A B 1 1 0 A pressed 1 0 1 B pressed
Door Lock: Outputs Assumptions: High pulse on U unlocks door LED dec 4 8 D3D2D1D0 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 outputs
Door Lock: Simplified State Diagram (1) Draw a state diagram (e.g. Moore Machine)
Door Lock: Simplified State Diagram any Output Cur. State (2) Write output and next-state tables
Door Lock: Simplified State Diagram Cur. State Cur. State Input Input Next State Next State G3 B G2 2 else 3 , U any (2) Write output and next-state tables
Door Lock: Implementation 4 dec D3-0 S2-0 3bit Reg U clk S2-0 K S 2-0 S2 S1 S0 D3D2D1D0U A B (4) Determine logic equations for next state and outputs
Door Lock: Implementation S2S1S0 K A B S 2S 1S 0 4 dec D3-0 S2-0 3bit Reg U clk S2-0 K S 2-0 A B (4) Determine logic equations for next state and outputs
Door Lock: Implementation 4 dec D3-0 S2-0 3bit Reg U clk S2-0 K S 2-0 A 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 outputs
Door Lock: Implementation Comb. Logic Current State Registers Output Comb. Logic Input Next State Moore Machine 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 outputs
Goals for today Review Finite State Machines
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
