[Edit of Image1]
Hey it's a me again @drifter1!
Today we continue with the Logic Design series on Verilog to get into Finite-State Machines (FSMs). The article will start out with a small theoretical explanation of what FSMs are, and afterwards we will get in-depth into how they can be modeled using Verilog. Actual implementation examples will come in a follow-up article though.
So, without further ado, let's get straight into it!
Finite-State Machine (FSM)
State machines are an important part of any digital design. The "current" state of a circuit is stored in memory elements like DFFs. Using those states and the transitions between them, its possible to control the behavior of the circuit.
Up to this point we covered:
- Combinational logic elements, where the output depends on the current inputs of the circuit, and
- Sequential logic elements, where the output depends on the current inputs and also previously "stored" values
There are two main types (or models) of state machines:
- Moore FSM
- Outputs depend on the current state
- Synchronous machine
- Mealy FSM
- Outputs depend on the current state and the inputs
- Asynchronous machine
Graphically, the FSM's of these two models are also quite easy to distinguish.
Just remember the following:
In Moore FSMs the outputs are a "part" of the state, whilst in Mealy FSMs they are a "part" of the transition.
Any logic circuit can be described by either of the two models and converting from one to the other is also not that complicated. But, generally speaking Mealy FSMs need less states than Moore FSMs.
Many different encoding styles can be used for the states, such as:
- Binary encoding : count up binary numbers (000, 001, 010, 011, ...)
- One-hot encoding : only one bit is '1' in each state
- One-cold encoding : only one bit is '0' in each state
- Gray encoding : only one bit changes each time (000, 001, 011, 010, 110, ...)
I tend to use one-hot encoding when the number of states is small. Otherwise, I like using simple binary encoding, mostly specified as an hexadecimal.
Modeling FSMs in Verilog
When modeling an FSM in Verilog, remember that three separate sections are needed:
- State encoding section - define constants (parameter or localparam keywords) for the states
- Combinational section for next state logic - modeled by an always block or assign statement
- Sequential section for state register logic - mostly modeled by an always block
The output logic is mainly a part of the combinational logic section. When the FSM is small it's sometimes even possible to combine the combinational and sequential parts into one always block. The "one block to rule them all" as I like to call it. Sometimes it's even possible to have three separate always blocks:
- state register logic
- next state logic
- output logic
Encoding 7 states using one-hot encoding looks like this:
whilst binary encoding results in:
localparam [6 : 0] s0 = 7'b000_0001, s1 = 7'b000_0010, s2 = 7'b000_0100, s3 = 7'b000_1000, s4 = 7'b001_0000, s5 = 7'b010_0000, s6 = 7'b100_0000;
localparam [2 : 0] s0 = 3'b001, s1 = 3'b010, s2 = 3'b011, s3 = 3'b100, s4 = 3'b101, s5 = 3'b110, s6 = 3'b111;
Of course, decimals and hexadecimals can also be used. Specifying the bit length is also not necessary. Thus, the binary encoding can also be written using hexadecimal number format as follows:
localparam [2 : 0] s0 = 'h1, s1 = 'h2, s2 = 'h3, s3 = 'h4, s4 = 'h5, s5 = 'h6, s6 = 'h7;
The current state is stored within a regitser, which can be defined as:
reg [N - 1 : 0] state_reg;
Sometimes having a register for the next state is also useful:
reg [N - 1 : 0] state_next;
The next state logic is modeled using a combinational block. If the number of states is small its possible to use an assign block with nested conditional operators:
assign state_next = s0 ? (condition) : s1 ? (condition) : s2;
But generally speaking, the preferred way is an combinational always block with a case statement:
always @ (state_reg, inputs) begin case (state_reg) s0: if (condition) state_next = s1; s1: if (condition) state_next = s0; else (condition) state_next = s2; s2: if (condition) state_next = s0; ... endcase end
In a Moore FSM, the output depends on the state. This allows us to include the output change in the individual cases like this:
s2: begin if(condition) state_next = s0; output = value; end
In a Mealy FSM, it depends on the state and input (the transition), leading to cases such as:
s1: begin if (condition) begin state_next = s0; output = value_X; end else begin state_next = s2; output = value_Y; end end
The output logic can also be completely separated from the next state logic. A Mealy FSM might include a separate always block of the form:
I don't think that it makes much sense to split in a Moore FSM.
always @ (state_reg, inputs) begin case (state_reg) s0: if (condition) output = value_X; s1: if (condition) output = value_Y; else (condition) output = value_Z; s2: if (condition) output = value_W; ... endcase end
The state register logic is defined within a procedural (sequential) always block. Any FSM needs a way to initialize and so a reset signal is needed in addition to the clock signal. For an asynchronous active-low reset, both these signals come in the sensitivity list. Thus, the state register logic block may look like this:
always @ (posedge clk or negedge reset) begin if (!reset) state_reg <= s0; else state_reg <= state_next; end
One Block To Rule Them All
Simple FSMs can be written using a single always block. A Moore type FSM looks like this:
always @ (posedge clk or negedge reset) begin if (!reset) begin state_reg = s0; output = value; end else begin case (state_reg) s0: begin if (condition) state_reg = s1; output = value_X; end s1: begin if (condition) state_reg = s0; else state_reg = s2; output = value_Y; end ... endcase end end
Of course this code is much more compact, but it suffers a lot in readability and understandability. I would suggest going the two always block route (one for combinational and one for sequential logic), which also means having two registers (one for the current state and one for the next). And for Mealy FSMs splitting the output logic from the next state logic might also be preferable sometimes. We will get into full-on examples next time, and then anyone can draw their own conclusions...
Block diagrams and other visualizations were made using draw.io
Previous articles of the series
- Verilog Introduction → Basic Syntax, Data Types, Operators, Modules
- Combinational Logic in Verilog → Assign Statement, Always Block, Control Blocks, Gate-Level Modeling and Primitives, User-Defined Primitives
- Combinational Logic Examples → One Circuit - Four Implementations, Encoder, Decoder, Multiplexer
- Sequential Logic → Procedural Blocks (Initial, Always), Blocking and Non-Blocking Assignments, Statement Groups
- Sequential Logic Examples in Verilog → Flip Flops (DFF, TFF, JKFF, SRFF), N-bit Counter, Single-Port RAM
Final words | Next up
And this is actually it for today's post!
Next time we will get into FSM Examples...
Keep on drifting!