FINITE STATE MACHINE
Hola Amigos!!
I got a mail regarding Finite State Machine Code in verilog. Well I have prepared my own truth table set and sequence but it will sure help you all guys to design your own code of FSM.
A finite state machine is a state level design used to program such modules which require a decision on each step. We can take a game like GTA V. The game waits for the user for the directions so when we move the mouse towards right the game loads a scenario. When you turn the mouse towards left it loads a different scenario. It is basically like if "YES" I'll do this else i'll do that. Thus at a moment of time only a single state can be achieved and each state has two possibilities. It is the true or the false.
Machines are of two types.
a. Mealey Machine
b. Moore Machine
A mealey machine is an algorithm that depends on its present state as well as the present inputs on it. It has basically has these parameters.
Qn represents the current state of machine.
Qn+1 represents the next state of machine.
Z represents the output of the machine.
X represents the input of the machine.
An example elaborating the working of Mealey Machine in a simple way :)
We have 4 states in the Mealey Machine above. These are Q0, Q1, Q2 and Q4. In the above diagram numerator represents input and denominator represents the output.
Let us proceed with steps.
Let us choose initial state as Q0. If we get an input x = 0 then output will be z = 0 and the machine will jump to state Q1.
If the input x = 1 the output is z = 0 and will jump to state Q2.
Similarly from state Q1 if input is x = 1 the output will be 1 and will jump to the state Q3 else will jump to Q2 with output z = 0.
Similarly if at Q3 we recieve an input x = 0 the output is z = 0 and will jump to the state Q3 itself or else if x = 1 then machine will jump to Q0 with output as 0.
The important thing to be noted is that Q0 -> Q1 is called a transition or from any
Qn -> Qn' is called a transition and is regarded as a sub- term for the Mealey Machine.
Making the truth table we get this
A mealey machine will have 6 columns. The first 3 and the last 3 are the same however the first 3 are for input X = 0 and the next three are for X = 1. What we have observed here is that every state will certainly have two output atmost and atmost N inputs where N is total number of states present in the mealey machine. According to the table we see that any state depends on X also as well as its current state. A Q0 will jump to Q1 only if it has an input X = 0 and this will only happen when state is at Q0.
A moore machine is an algorithm which depends only on the current state of the machine regardless of the input. It too has same set of terms as
Qn for the current state of machine.
Qn+1 for the next state of machine.
Z for the output and yes! a single output.
Transition as the sub terms.
An example elaborating the working of Moore Machine
Lets us assume the initial state to be Q1. At Q1 the output will be 0 regardless of the input. If Q1 recieves input 1 it will jump to the state Q3 and output will be 0 or else it will jump to Q2 and output will be 1. Each state here has its own ouput and remains fixed irrespective of the input.
Similarly considering the case for Q3. If it recieves 0 then it will jump to Q3 with output as 0 or else it will jump to Q0 with output as 0.
The truth table specific to Moore Machine is
Next state depends on the input as specified.
NOTE - It is the output which is dependent on present state. Do not confuse it with next state.
I am using Mealey Machine Design for this example
I got a mail regarding Finite State Machine Code in verilog. Well I have prepared my own truth table set and sequence but it will sure help you all guys to design your own code of FSM.
A finite state machine is a state level design used to program such modules which require a decision on each step. We can take a game like GTA V. The game waits for the user for the directions so when we move the mouse towards right the game loads a scenario. When you turn the mouse towards left it loads a different scenario. It is basically like if "YES" I'll do this else i'll do that. Thus at a moment of time only a single state can be achieved and each state has two possibilities. It is the true or the false.
Machines are of two types.
a. Mealey Machine
b. Moore Machine
Mealey Machine
A mealey machine is an algorithm that depends on its present state as well as the present inputs on it. It has basically has these parameters.Qn represents the current state of machine.
Qn+1 represents the next state of machine.
Z represents the output of the machine.
X represents the input of the machine.
An example elaborating the working of Mealey Machine in a simple way :)
We have 4 states in the Mealey Machine above. These are Q0, Q1, Q2 and Q4. In the above diagram numerator represents input and denominator represents the output.
Let us proceed with steps.
Let us choose initial state as Q0. If we get an input x = 0 then output will be z = 0 and the machine will jump to state Q1.
If the input x = 1 the output is z = 0 and will jump to state Q2.
Similarly from state Q1 if input is x = 1 the output will be 1 and will jump to the state Q3 else will jump to Q2 with output z = 0.
Similarly if at Q3 we recieve an input x = 0 the output is z = 0 and will jump to the state Q3 itself or else if x = 1 then machine will jump to Q0 with output as 0.
The important thing to be noted is that Q0 -> Q1 is called a transition or from any
Qn -> Qn' is called a transition and is regarded as a sub- term for the Mealey Machine.
Making the truth table we get this
If input X = 0 | If input X = 1 | ||||
Present State Qn | Next State Qn+1 | Output Z | Present State Qn | Next State Qn+1 | Output Z |
Q0 | Q1 | 0 | Q0 | Q2 | 0 |
Q1 | Q2 | 0 | Q1 | Q3 | 1 |
Q2 | Q0 | 1 | Q2 | Q3 | 0 |
Q3 | Q3 | 0 | Q3 | Q0 | 0 |
Moore Machine
A moore machine is an algorithm which depends only on the current state of the machine regardless of the input. It too has same set of terms asQn for the current state of machine.
Qn+1 for the next state of machine.
Z for the output and yes! a single output.
Transition as the sub terms.
An example elaborating the working of Moore Machine
Lets us assume the initial state to be Q1. At Q1 the output will be 0 regardless of the input. If Q1 recieves input 1 it will jump to the state Q3 and output will be 0 or else it will jump to Q2 and output will be 1. Each state here has its own ouput and remains fixed irrespective of the input.
Similarly considering the case for Q3. If it recieves 0 then it will jump to Q3 with output as 0 or else it will jump to Q0 with output as 0.
The truth table specific to Moore Machine is
Present State Qn | Next State Qn+1 | Output Z | |
X = 0 | X = 1 | ||
Q0 | Q1 | Q2 | 0 |
Q1 | Q2 | Q3 | 1 |
Q2 | Q0 | Q3 | 0 |
Q3 | Q3 | Q0 | 0 |
NOTE - It is the output which is dependent on present state. Do not confuse it with next state.
Difference between Mealey and Moore Machine
Mealey Machine vs Moore Machine | |
Mealey Machine | Moore Machine |
Output depends on both present state as well as input | Output depends only on the state |
Circuit complexity is less as compared to Moore | Circuit complexity is more as compared to Mealey |
Runs only on positive or negative edges of clock | Runs as soon as input is changed |
Has few number of states compared to Moore | Has more number of states compared to Mealey |
It has two outputs for input 0 and for input 1 | It has a single output for each state. |
Thus outputs are determined by both current state and current inputs.
Here is the question
Thus you can easily see the required sequence is 1101
Let me explain a bit.
Initially we will always be at state A. When we receive input as 1 the we found the 1st correct bit of 1101. But still we didn't get 1101 thus for input 1 from state A output will be 0 and will jump to state B. If we get 0 then it is different from what we want hence machine will remain at state A with output 0. Now if we recieve 1 then we have found 11 of 1101 thus jumps to state C still output is zero since 11 is not equal to 1101. Similarly if we get input 0 then we have found 110 of 1101 thus machine jumps to state D with still output 0 as 110 is not equal to 1101. If inputis zero then will remain at state C. Now if we get input 1 at state D then we get our sequence 1101. Hence output is 1. The next state is B. However if we get input 0 then machine will jump from state D to state A.
I hope it is clearly understood.
Heres the code-
module FSM(a,q,clk);
input [15:0]a; //THIS IS INPUT
output reg q; //THIS IS OUTPUT
input clk; //CLOCK
reg [1:0] state; //STATE
reg [15:0] c;
integer flag = 0;
initial begin
q = 0;
state = 2'b00; //initially at state A-00
end
always @(posedge clk)begin
if(flag==0)
c <= a;
flag = flag + 1;
end
always @(posedge clk)begin
$display("State = %d Bit = %b Q = %b",state,c[15],q);
if(state==2'b00 && c[15]==0)begin
state <=2'b00; // state A-00
q <= 0;
end
else if(state==2'b00 && c[15]==1) begin
state <=2'b01; // state B-01
q <= 0;
end
else if(state==2'b01 && c[15]==0)begin
state <=2'b00; //state A-00
q <= 0;
end
else if(state==2'b01 && c[15]==1) begin
state <=2'b10; //state C-10
q <= 0;
end
else if(state==2'b10 && c[15]==0) begin
state <= 2'b11; //state D-11
q <= 0;
end
else if(state==2'b10 && c[15]==1) begin
state=2'b10; //state C-10
q <= 0;
end
else if(state==2'b11 && c[15]==0) begin
state=2'b00; //state A-00
q <= 0;
end
else if(state==2'b11 && c[15]==1) begin
state=2'b01 ;
q <= 1;
end
c = c<<1; //to get the MSB of 16bit input which has to be checked with MSB of 1101
end
endmodule
TestBench-
module FSM_Mealey();
reg a;
reg clk;
wire q;
integer i;
reg [15:0] inp;
FSM finite(inp,q,clk);
initial begin
clk = 0;
inp <= 16'b1101_0010_1101_0000; //input sequence
end
always
#2 clk = !clk;
endmodule
Waveform Output
Output Table
The moment 1101 is obtained Q is 1
You can mail me at shashisuman17@aol.com for any queries
So Long
No comments:
Post a Comment