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.
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.
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:
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:
- Update the main register that controls the actual state;
- Decide what will be the next state based on the actual state and the inputs;
- 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.
Subscribe to @aignacio's
Get the latest posts delivered right to your inbox