Logic Design - Finite-State Machines in Verilog

[Edit of Image1]

Introduction

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

but what's more interesting is combining those two aspects into one.

---

FSM Types

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.

---

State Encoding

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

State Encoding

Encoding 7 states using one-hot encoding looks like this:

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;

whilst binary encoding results in:

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;

State Register

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;

Combinational Section

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

Moore

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

Mealy

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

Separate output

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:

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

I don't think that it makes much sense to split in a Moore FSM.

Sequential Section

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...

---

RESOURCES:

References

1. http://www.asic-world.com/verilog/veritut.html
2. https://www.chipverify.com/verilog/verilog-tutorial
3. https://www.javatpoint.com/verilog

Images

1. https://www.flickr.com/photos/creative_stock/5227842611

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...

See Ya!

Keep on drifting!