/ fsm

Finite state machines in verilog

Almost always when that you think in a way to solve a problem, if you take notes of the thoughts, you'll amaze that you are actually thinking in finite state machines. By general, any sort of problem related to closed flow of data could be represented by some flowchart of states. The diagram with circles in arcs invented by Mealy and Moore describe some of the basic concepts of theory of computation.

According to Mealy:

...Mealy machine is a finite-state machine whose output values are determined both by its current state and the current inputs

...and according to Moore:

...Moore machine is a finite-state machine whose output values are determined only by its current state

So, in basics they mean that we can have two definitions for finite state machines, and in practice you could implement both for all kind of problems.
But in fact, what exactly changes between this implementations?, the answer is a trade-off as always in the electronics that determines if you would spend more time/effort to develop such solution. Being more straight, the difference is that a Moore machine in general needs more states to define the same logic that a Mealy machine could represent. Why? It's because in this case, you'll need to define a single state for each event purpose output, simplifying the behavior. See the example below for a door opening process with two buttons, one to open and other to close.
moore
In the Moore FSM above, the next state for the first state will be always the state 2, where it's triggered when the user press the close button. The same happens in the opposite way with closed door and the open button. By this sequence of states we could easily observe the actual state of the system.
mealy
The Mealy FSM above differs basic by the implicit states of opening and closing that're part of the states 1 and 2. This indicates that if we do not receive any feedback from the door sensors, the door will be locked in the actual state that could be opened/closed. This means that it'll be hard to understand a machine like this, if the logic would a little more complicated.

Example to code

Despite the implicit states and the complexity to understand sometimes, the Mealy FSM is the most used approach because in many machine cases, more states means more registers, what means more flip-flops and then more area/power to implement controllers. So, to save such metrics, we usually try to aggregate the inputs in the FSM logic. As the main objective of this post, I implemented in verilog a FSM for the diagram below:
fsm
The double circle represents the reset state and it defines that we start from this point after a reset. Considering the diagram above, I coded it in three different always blocks that makes easier to understand each of the operations:

  1. Update the main register that controls the actual state;
  2. Decide what will be the next state based on the actual state and the inputs;
  3. Update the outputs according to the state;

Remember that this is my way to implement, if you are more comfortable to use a different approach, fell free to choose. Follow the code block below to see my version:

module fsm_controller (
 clock,
 in_1,
 reset_n,
 out_1,
 out_2,
 out_3,
 out_4
 );

 input clock;
 input in_1;
 input reset_n;

 // It's always a good approach to register the outputs
 output reg out_1;
 output reg out_2;
 output reg out_3;
 output reg out_4;

 // At least 5 states for our machine, thus 2^3=8
 reg [2:0] state, next_state;

 // We will use a local parameter to use alias instead of numbers
 localparam [2:0] IDDLE = 3'd000,
                  START = 3'd001,
                  ADD   = 3'd010,
                  INC   = 3'd011,
                  COM   = 3'd100;
                  
 // 1) Update the main register that controls the actual state;
 always @ ( posedge clock ) begin
  // Our reset will be active on zero='0' and synchronous
  if (~reset_n) begin
   state <= IDDLE; // be careful to use non-blocking on seq. always
  end else begin
   state <= next_state;
  end
 end

 // 2) Decide what will be the next state based on the actual state and the inputs;
 always @ ( * ) begin
  case (state)
   IDDLE:
    next_state = START; // Be careful to use blocking on comb. always
   START:
    next_state = ADD;
   ADD:
    if (~in_1)
     next_state = INC;
    else
     next_state = IDDLE;
   INC:
    if (~in_1)
     next_state = INC;
    else
     next_state = COM;
   COM:
    if (~in_1)
     next_state = START;
    else
     next_state = COM;
   default: // If you forget to declare the default case,
            // you could create a latch on synthesis in a always comb.
     next_state = IDDLE;
   endcase
 end

 // 3) Update the outputs according to the state;
 always @ ( * ) begin
  case (state)
   IDDLE: begin
    out_1 = 1'd0;
    out_2 = 1'd0;
    out_3 = 1'd0;
    out_4 = 1'd0;
   end
   START: begin
    out_1 = 1'd1;
    out_2 = 1'd0;
    out_3 = 1'd0;
    out_4 = 1'd0;
   end
   ADD: begin
    out_1 = 1'd1;
    out_2 = 1'd1;
    out_3 = 1'd1;
    out_4 = 1'd0;
   end
   INC: begin
    out_1 = 1'd0;
    out_2 = 1'd0;
    out_3 = 1'd0;
    out_4 = 1'd1;
   end
   COM: begin
    out_1 = 1'd1;
    out_2 = 1'd0;
    out_3 = 1'd1;
    out_4 = 1'd0;
   end
   default: begin
    out_1 = 1'd0;
    out_2 = 1'd0;
    out_3 = 1'd0;
    out_4 = 1'd0;
   end
   endcase
 end
endmodule

Remember that's an example, thus it's so general and has no specific configurations in this FSM. If you wanna test it, try to check out this website that has a tool to compile the module/testbench and simulate it online. If you like this post, please share/subscribe in the newsletter below to receive new updates.
ddd

References
Finite state machines in verilog
Share this

Subscribe to @aignacio's