State machine
Summary
Digital hardware are composed of 2 different kinds of components;
- Combinational Logic
- State machine
State machine is quite important to make complicated hardware like multiplier, divider, control logic of the processor (CPU), and so on. In this section, an overview of the state machine, and how it’s described with HDL (Hardware Description Language) will be explained.
Overview
As the name suggest, state machine has its “state”. In figure 1, there are 5 different state;
- Initial state (Initial in the figure)
- Calculation 1 (Calc1 in the figure)
- Calculation 2, step 1 (Calc2–1 in the figure)
- Calculation 2, step 2 (Calc2–2 in the figure)
- Calculation Done (Done in the figure)
The state can be one of those at one point in time, and the state changes according to the input signals; “trigger”, and “calc”.
- State: Initial
If “trigger” signal equals to 0, it stays in “Initial” state.
If “trigger” signal is 1, and “calc” signal is 0, the state will change to “Calc1”.
If “trigger” signal is 1, and “calc” signal is 1, the state will change to “Calc2–1”.
- State: Calc1
The next state will always be “Done” state (input doesn’t matter).
- State: Calc2–1
The next state will always be “Calc2–2” state (input doesn’t matter).
- State: Calc2–2
The next state will always be “Done” (input doesn’t matter).
- State: Done
The next state will always be “Initial” (input doesn’t matter).
The state “Initial” has double-circle, and this has special meaning. When this hardware is powered, very first state will be “Initial” state. To guarantee this, there’s another (hidden) input “reset” is used. Everytime “reset” signal is active, the next state will always be “Initial” state.
Usage
How this will be used is, for example, the control circuit of “multiplier”. Unless you use “array multiplier”, it takes several cycles to calculate the result. This state machine will be used to control multiplier, like below.
- At “Initial” state
This will accept 2 inputs. For example, multiplicand and multiplier. When “trigger” is 1, those 2 inputs will be “latched” in registers.
2. At “Calculation” state
This might take multiple cycles. For example, “Calc2–1” and “Calc2–2” in figure 1. Those states tend to be used to synchronize the calculation circuit, and input/output timings.
3. At “Done” state
Calculation has been done, and output is ready in this state. So the output will usually be latched to “output” register, and this will be available from external modules.
Timing chart
This “state transition” happens periodically. The periodical signal “clock” must be present in state machine. Clock signal is usually named like “clk”. Also, as I mentioned above, “reset” signal is important too to guarantee the very first state after power on is always the same. “reset” signal is active right after power on, until certain time, then, deactivated at one point to start the calculation. Also, when error happens, or something goes wrong, “reset” might become active to reset entire circuit.
State transition happens specifically on “rising edge” or “falling edge” of clock signal (in most cases, this is true since flip-flops are usually “edge-triggered”). Figure 2 shows the example of the timing chart of a state machine.
First rising edge of the “clk” signal, “trigger” signal is “low” (this signal becomes “high” right after this rising edge). So the next state is “0x0” and stays as “Initial” state.
On second rising edge of “clk”, “trigger” signal is “high”, and “calc” signal is low. So the next state will be determined as “Calc1” (0x1).
On third rising edge of “clk”, state will be determined as “Done” (0x4), since this transition is not depending on any input signals.
On forth rising edge of “clk”, state will be determined as “Initial” (0x0).
This is how state machine works.
HDL description of the state machine
In HDL, state machine can be described as “its behaviour”, and importantly, that is NOT describing the actual digital hardware.
Table 1 shows the HDL description of the example state machine.
Table 1. HDL description of the example state machine
module state_machine_example (
input wire reset,
input wire clk,
input wire trigger,
input wire calc,
output wire state_out
);
localparam STAT_INIT = 3'h0;
localparam STAT_CALC1 = 3'h1;
localparam STAT_CALC2_1 = 3'h2;
localparam STAT_CALC2_2 = 3'h3;
localparam STAT_DONE = 3'h4; // This will hold the state
reg state[2:0]; // This is behavioural description of the state machine
always @(posedge clk) begin
if (!reset) begin
state <= STAT_INIT;
end else begin
case (state)
// When state is "Initial"
STAT_INIT: begin
if (trigger == 1) begin
if (calc == 0) begin
state <= STAT_CALC1;
end else begin
state <= STAT_CALC2_1;
end
end else begin
state <= STAT_INIT;
end
end // When state is "Calc1"
STAT_CALC1: begin
state <= STAT_DONE;
end // When state is "Calc2-1"
STAT_CALC2_1: begin
state <= STAT_CAL2_2;
end // When state is "Calc2-2"
STAT_CALC2_2: begin
state <= STAT_DONE;
end // When state is "Done"
STAT_DONE: begin
state <= STAT_INIT;
end
endcase
end
end
assign state_out = state;
endmodule
“State” of the state machine must be stored in register. So a register “state” is declared at the beginning. Then, the value of “state” register will be changed in “always” block. The braces after “always” keyword is called “sensitivity list”. Usually, clock signal name and whether this transition happens on “rising edge” of the clock, or “falling edge” of the clock are described. Basically, this “always” block describes the behaviour on every rising edge of “clk” signal in this example.
In “always” block, there’s “if” which is checking whether “reset” signal is set. This describes the “behaviour in case of reset”. This is quite important because, as I mentioned above, very first state right after power on must be determined. Otherwise, the behaviour of this state machine might become undefined.
Because this “always” block is a description of the “behaviour” of the state machine, we can use branches like “if-else” and “case (equivalent to “switch” in C)”. If you are familiar with programming languages, this can be intuitive. But confusion happens outside of “always” block. There might be multiple “always” blocks, which describe behaviour of other state machines, and those are working “at the same time”. So this is not “programming order”. But, if you are familiar with “event driven” programming, this might make sense since “always” describes the behaviour “in case” clock signal gets activated.
One more important thing is, outside “always” block, for example, “assign” keyword is used with “=”, but in “always” block, “<=” is used instead of “=”, which means, “=” and “<=” are not the same. Regular “=” is called “blocking” assignment, which means, this assignment happens in programming order. For example,
assign a = b;
assign c = a;
assign d = c;In this case, outputs “a”, “b”, “c”, and “d” will become the same value, because, you can think it in this way, it gets executed in programming order. But, all “<=” assignment is called “non-blocking” assignment, and it happens at the same time. What this means is that, these non-blocking assignments are usually used in “always” statement, and this assigns the value “according to the right hand values after previous rising edge”. This assignment does not depend on any other assignments described together. …is it confusing? You can think it in this way; always use “<=” in always block.
This is the overview, and HDL description of the state machine.
