Embedded Files
FSM is a computational model used to design systems that have a finite number of distinct states. It is used to model systems that can be in one state at a time, and can transition from one state to another based on inputs and rules defined by the system's design.
Key Components of an FSM:
Key Components of an FSM:
States: A finite set of conditions or modes that the system can be in at any given time.
Transitions: Rules that dictate when and how the system changes from one state to another, usually based on inputs.
Input: A signal or condition that triggers state transitions.
Output: The result or action that the system produces based on its current state and input (this may be optional depending on the FSM type).
Start State: The state the machine begins in when it starts operating.
Accepting or Final States: States where the machine completes a process or achieves its goal.
Types of FSMs:
Types of FSMs:
Deterministic Finite State Machine (DFA): For each state and input, there is exactly one possible transition. The system's behavior is fully predictable.
Non-Deterministic Finite State Machine (NFA): For a given state and input, there could be multiple possible transitions. This adds some unpredictability or flexibility to the system's behavior.
Types Based on Output:
Types Based on Output:
Mealy Machine: The output depends on both the current state and the input.
Moore Machine: The output depends only on the current state, not on the input.
Example:
Example:
Consider a simple turnstile that accepts a coin and allows access through a gate:
States:
Locked (initial state)
Unlocked
Inputs:
Coin inserted
Push on the turnstile arm
Transitions:
From Locked to Unlocked if a coin is inserted.
From Unlocked to Locked if the turnstile is pushed.
Applications of FSMs:
Applications of FSMs:
Control Systems: For example, in traffic lights, elevators, and vending machines.
Software Design: For modeling user interfaces, parsing input, or game logic.
Digital Circuits: Used in designing sequential circuits where the output depends on the previous inputs (e.g., counters, sequence detectors).
Protocol Design: In communication protocols, where systems need to be in specific states to send or receive messages correctly.
A sequence detector for the non-overlapping sequence "001" can be implemented using both Mealy and Moore state machines. The goal is to design a finite state machine (FSM) that detects the sequence "001" in a stream of binary input.
Definitions:
Definitions:
Mealy Machine: The output depends on both the current state and the input.
Moore Machine: The output depends only on the current state.
States and Transitions:
States and Transitions:
Let's break down the states and transitions required for detecting the non-overlapping sequence "001". We will create FSMs for both Mealy and Moore designs.
Moore Machine Design for Sequence "001"
In a Moore machine, the output depends only on the state. We'll define the states as follows:
State S0: Initial state, no input matched yet.
State S1: '0' has been detected.
State S2: '00' has been detected.
State S3: Sequence "001" has been detected (accepting state).
State Diagram:
S0 (Initial state):
On input 0, transition to S1, output 0 (sequence not detected yet).
On input 1, stay in S0, output 0 (no match).
S1 (One '0' detected):
On input 0, transition to S2, output 0 (sequence "00" detected).
On input 1, go back to S0, output 0.
S2 (Two '0's detected):
On input 0, stay in S2, output 0 (still detecting "001").
On input 1, transition to S3, output 1 (sequence "001" detected).
S3 (Sequence "001" detected):
On input 0, transition back to S1 (restart sequence detection), output 0.
On input 1, transition back to S0, output 0.
Code in Verilog:
`timescale 1ns / 1ps
//////////////////////////////////////////////////////////////////////////////////
// Company:
// Engineer:
//
// Create Date: 12/15/2024 02:29:01 PM
// Design Name:
// Module Name: mooremachine
// Project Name:
// Target Devices:
// Tool Versions:
// Description:
//
// Dependencies:
//
// Revision:
// Revision 0.01 - File Created
// Additional Comments:
//
//////////////////////////////////////////////////////////////////////////////////
module mooremachine(det,inp,clk,reset);
input clk,inp, reset;
output reg det;
parameter s0=2'b00 ,s1=2'b01, s2=2'b10,s3=2'b11;
reg [1:0]pr_state,nxt_state;
//////////////////////
always@(posedge clk)
if(reset)
pr_state<=s0;
else
pr_state<=nxt_state;
//////////////////
always@(inp,pr_state)
case(pr_state)
s0:if(inp)
nxt_state=s0;
else
nxt_state=s1;
s1:if(inp)
nxt_state=s0;
else
nxt_state=s2;
s2:if(inp)
nxt_state=s3;
else
nxt_state=s2;
s3: if(inp)
nxt_state=s0;
else
nxt_state=s1;
default: nxt_state=s0;
endcase
////////////////////
always@(inp,pr_state)
case(pr_state)
s0:det=0;
s1:det=0;
s2:det=0;
s3:det=1;
default: det=0;
endcase
endmodule
Mealy Machine Design for Sequence "001"
In a Mealy machine, the output depends on both the current state and the input. We'll define the states similarly but adjust the output logic.
State S0: Initial state, no input matched yet.
State S1: '0' has been detected.
State S2: '00' has been detected.
State S3: Sequence "001" has been detected (accepting state).
State Diagram:
S0 (Initial state):
On input 0, transition to S1, output 0 (sequence not detected yet).
On input 1, stay in S0, output 0 (no match).
S1 (One '0' detected):
On input 0, transition to S2, output 0 (sequence "00" detected).
On input 1, go back to S0, output 0.
S2 (Two '0's detected):
On input 0, stay in S2, output 0 (still detecting "001").
On input 1, transition to S3, output 1 (sequence "001" detected).
S3 (Sequence "001" detected):
On input 0, transition back to S1 (restart sequence detection), output 0.
On input 1, transition back to S0, output 0.
Code in Verilog:
`timescale 1ns / 1ps
//////////////////////////////////////////////////////////////////////////////////
// Company:
// Engineer:
// JATIN KATIYAR
// Create Date: 12/15/2024 01:27:49 PM
// Design Name:
// Module Name: mealymachine
// Project Name:
// Target Devices:
// Tool Versions:
// Description:
//
// Dependencies:
//
// Revision:
// Revision 0.01 - File Created
// Additional Comments:
//
//////////////////////////////////////////////////////////////////////////////////
module mealymachine(det,inp,clk,reset);
input clk,inp, reset;
output reg det;
parameter s0=2'b00 ,s1=2'b01, s2=2'b10;
reg [1:0]pr_state,nxt_state;
//////////////////////
always@(posedge clk)
if(reset)
pr_state<=s0;
else
pr_state<=nxt_state;
//////////////////
always@(inp,pr_state)
case(pr_state)
s0:if(inp)
nxt_state=s0;
else
nxt_state=s1;
s1:if(inp)
nxt_state=s0;
else
nxt_state=s2;
s2:if(inp)
nxt_state=s0;
else
nxt_state=s2;
default: nxt_state=s0;
endcase
////////////////////
always@(inp,pr_state)
case(pr_state)
s0:det=0;
s1:det=0;
s2:if(inp)
det=1;
else
det=0;
default: det=0;
endcase
endmodule
Summary of Differences:
Summary of Differences:
Moore Machine: Output is associated with states. It only produces output when entering state S3.
Mealy Machine: Output is associated with transitions. It can produce output as soon as the sequence "001" is detected, even before transitioning to the next state.
Both designs accomplish the task of detecting the non-overlapping sequence "001". The choice between Mealy and Moore depends on the specific requirements of your design, like timing or responsiveness to inputs.
Page updated
Google Sites
Report abuse