Finite State Machine

Finite state machine is a mathematical model that represents multiple states and the jump relation between states.

There are two kinds of state machines commonly used in digital circuits, one is a Mealy state machine, the other is a Moore state machine.

Mealy state machine & Moore state machine

The structure of mealy-type state machine is shown in the following figure (image source network) :

The structure of a Moore state machine is as follows:

By contrast, both circuits are composed of three parts: the state register is the core, and the timing circuit represents the current state. The secondary state is determined by the input and the current state of the combined circuit. The only difference is in the combinatorial logic that produces the output. The output of the Moore state machine is determined only by the current state, while the output of the Mealy state machine is determined by the current state and the current input.

Mili state machine has fewer states than mole state machine in some cases, because mili state machine can combine input and state as output, that is, (input + state) can be considered as a new “state”.

State machine in FPGA

Generally speaking, there are many ways to write the state machine in FPGA, and there are one-stage, two-stage and three-stage state machines commonly used on the Internet.

A one-step state machine, in which the entire state machine is written into an ALWAYS module, is used for simple state machine implementations.
A two-stage state machine that writes inputs and state jumps to one module and outputs to another.
The three-stage state machine is written according to the structure diagram of the state machine, namely, the input part, the state jump part and the output part.

In principle, there is no problem with the state machine of the three forms as long as the corresponding requirements can be realized. The three state machines differ only in form, but are essentially the same. The logic structure of one-paragraph and two-paragraph is not as clear as that of three-paragraph, which seems to be a bit confusing in front of the more complex state machine (it will be very complicated when constructing the state machine, and the logic is mixed together). The three-stage state machine is mainly introduced here. The three-stage state machine is written in accordance with the mathematical model, with clear structure and convenient debugging.

Task

The hexadecimal input sequence is checked for AABBCCH in the input sequence. The width of the input data is 8 bits, and the output is 1 bit flag bit. When it is detected that the input end has received AABBCCH, the output is a cycle of high pulse.

Moore state machine

Before drawing the state transition diagram, the state must be determined first. The output of Moore state machine is completely determined by the current state, so the output can be determined according to the current state.

According to requirements, four states can be determined, which are ① other states, ② AAH detected, ③ BBH detected, and ④ CCH detected. The four states are named idle, AA, BB, and CC respectively. Then the following state transition diagram can be drawn according to requirements.

Suppose the input sequence is… AABBCCBBAABBCCAABBAABBCCCC… H, the output should have 3 positive pulses.

FSM_Moore.v

// The state machine is written according to the mathematical model. It is divided into three parts
module FSM_Moore(           // FSM_Moore fsm(
    input wire clk,         // .clk ( ),
    input wire rst_n,       // .rst_n( ),
    input wire [7:0] data,  // .data ( ),
    output reg flag         // .flag ( )
);                          / /);

// ===== Moore ===== //
reg [1:0] c_state,n_state;

localparam 
    idle  =  'b00,
    aa    =  'b01,
    bb    =  'b10,
    cc    =  'b11;

// State transition condition substate combination circuit
always@ (*)begin
    //n_state = c_state ; // If the conditional options are not fully considered, an initial value can be assigned to remove the latch
    case(c_state)
        idle: begin
            if(data == 'haa) n_state = aa;
            else n_state = idle;
        end
        aa  : begin
            if(data == 'haa) n_state = aa;
            else if(data =='hbb) n_state = bb;
            else n_state = idle;
        end
        bb  : begin
            if(data == 'haa) n_state = aa;
            else if(data == 'hcc) n_state = cc;
            else n_state = idle;
        end
        cc  : begin
            if(data  ==  'haa) n_state = aa;
            else n_state = idle;
        end
        default: n_state  =  idle;
    endcase
end
// State transition timing section
always@ (posedge clk or negedge rst_n) begin
    if(~rst_n) c_state <=  idle;
    else c_state <= n_state;
end

// Output part of the combined circuit
always@ (*)begin
    if (c_state == cc) flag = 1'b1;
    else flag = 1'b0;
end
endmodule
Copy the code

tb.v

`timescale 1ns/1ns
`define CLOCK_PERIOD 10
module tb();
reg clk;
reg rst_n;
always #(`CLOCK_PERIOD/2) clk<=~clk;

reg [7:0] data_i;
wire flag;

FSM_Moore fsm(
    .clk  (clk      ),
    .rst_n(rst_n    ),
    .data (data_i   ),
    .flag (flag     )
);

initial begin
    $dumpfile("./dumpfile.vcd");
    $dumpvars;
    clk<=1'b1;
    rst_n<=1'b0;
    data_i<='hff;
    #`CLOCK_PERIOD
    rst_n<=1'b1;
    #`CLOCK_PERIOD
    #`CLOCK_PERIOD data_i<='haa;
    #`CLOCK_PERIOD data_i<='hbb;
    #`CLOCK_PERIOD data_i<='hcc;
    #`CLOCK_PERIOD data_i<='hbb;
    #`CLOCK_PERIOD data_i<='haa;
    #`CLOCK_PERIOD data_i<='hbb;
    #`CLOCK_PERIOD data_i<='hcc;
    #`CLOCK_PERIOD data_i<='haa;
    #`CLOCK_PERIOD data_i<='hbb;
    #`CLOCK_PERIOD data_i<='haa;
    #`CLOCK_PERIOD data_i<='hbb;
    #`CLOCK_PERIOD data_i<='hcc;
    #`CLOCK_PERIOD data_i<='hcc;
    #(`CLOCK_PERIOD * 4)
    $finish;
end
endmodule
Copy the code

The simulated waveform is shown as follows:

Note:

(1), where the input sequence for FFAABBCCBBAABBCCAABBAABBCCH sequence, when the input data changes, produce n_state combinational logic will change, such as at 30 ns time, input into AAH, then n_state immediately change of 01 state at this time, Then c_state happens to meet the rising edge, that is, it also changes to 01. After c_state changes, n_state changes again. At this time, the input is AA, and the state is 01, and the output is still 01. And the next period, same thing, data becomes BBH, changes n_state, c_state follows n_state, and then in turn changes n_state to 00. This is why only 00 and 01 states appear later.

② As the rising edge of the clock approaches, it is theoretically impossible for the state machine to pick up the input if it changes exactly at the same time as the delay (strictly aligned changes). The secondary state of the state machine depends on the input in the established time that determines which secondary state it is a short time before the rising edge arrives. For example, at 30ns, in theory, c_state should change the value of n_state at the previous 30ns moment to the value of the next period, i.e. 00 state, but here it goes directly to 01 state. The reason for this phenomenon is that, on the one hand, there is no static timing constraint, and on the other hand, computer simulation is ideal simulation, that is, simulation without actual circuit information. Hence the instantaneous change of state.

Mealy state machine

By converting a Moore state machine to a Mealy state machine, cc state can be removed and the state transformation diagram as follows can be obtained.

The input sequence is unchanged, and the code is as follows:

FSM_Mealy.v

// The state machine is written according to the mathematical model. It is divided into three parts
module FSM_Mealy(           // FSM_Mealy fsm(
    input wire clk,         // .clk ( ),
    input wire rst_n,       // .rst_n( ),
    input wire [7:0] data,  // .data ( ),
    output reg flag         // .flag ( )
);                          / /);


// ===== three-stage state machine Mealy ===== //
reg [1:0] c_state,n_state;

localparam 
    idle  =  'b00,
    aa    =  'b01,
    bb    =  'b10;

// State transition timing section
always@ (posedge clk or negedge rst_n) begin
    if(~rst_n) c_state <=  idle;
    else c_state <= n_state;
end

// State transition condition substate combination circuit
always@ (*)begin
    case(c_state)
        idle: begin
            if(data == 'haa) n_state = aa;
            else n_state = idle;
        end
        aa  : begin
            if(data == 'haa) n_state = aa;
            else if(data =='hbb) n_state = bb;
            else n_state = idle;
        end
        bb  : begin
            if(data == 'haa) n_state = aa;
            else if(data == 'hcc) n_state = idle;
            else n_state = idle;
        end
        default: n_state  =  idle;
    endcase
end

// Output part of the combined circuit
always@ (*)begin
    if (c_state == bb && data == 'hcc ) flag = 1'b1;
    else flag = 1'b0;
end
endmodule
Copy the code

tb.v

`timescale 1ns/1ns
`define CLOCK_PERIOD 10
module tb();

reg clk;
reg rst_n;
always #(`CLOCK_PERIOD/2) clk<=~clk;

reg [7:0] data_i;
wire flag;

FSM_Mealy fsm(
    .clk  (clk      ),
    .rst_n(rst_n    ),
    .data (data_i   ),
    .flag (flag     )
);

initial begin
    $dumpfile("./dumpfile.vcd");
    $dumpvars;
    clk<=1'b1;
    rst_n<=1'b0;
    data_i<='hff;
    #`CLOCK_PERIOD
    rst_n<=1'b1;
    #(`CLOCK_PERIOD + 1 ) // The purpose of this writing is to avoid too ideal edge changes in the simulation process
    #`CLOCK_PERIOD data_i<='haa;
    #`CLOCK_PERIOD data_i<='hbb;
    #`CLOCK_PERIOD data_i<='hcc;
    #`CLOCK_PERIOD data_i<='hbb;
    #`CLOCK_PERIOD data_i<='haa;
    #`CLOCK_PERIOD data_i<='hbb;
    #`CLOCK_PERIOD data_i<='hcc;
    #`CLOCK_PERIOD data_i<='haa;
    #`CLOCK_PERIOD data_i<='hbb;
    #`CLOCK_PERIOD data_i<='haa;
    #`CLOCK_PERIOD data_i<='hbb;
    #`CLOCK_PERIOD data_i<='hcc;
    #`CLOCK_PERIOD data_i<='hcc;
    #(`CLOCK_PERIOD * 4)
    $finish;
end
endmodule
Copy the code

Simulation results are as follows

It can be found that the Output of Mealy state machine is good.

twitter

A state machine is essentially a record of historical input. For every valid input signal, the state machine changes.

Problems encountered in the simulation process, such as whether to carry circuit information, can be verified by the actual circuit. When writing the test, attention should also be paid to the data input jump time should not be aligned with the edge of the clock as far as possible, so as to ensure certain robustness.

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

The FPGA | finite state machine FSM

Finite State Machine

Mealy state machine & Moore state machine

State machine in FPGA

Task

Moore state machine

FSM_Moore.v

tb.v

Mealy state machine

FSM_Mealy.v

tb.v

twitter

The FPGA | finite state machine FSM

Finite State Machine

Mealy state machine & Moore state machine

State machine in FPGA

Task

Moore state machine

FSM_Moore.v

tb.v

Mealy state machine

FSM_Mealy.v

tb.v

twitter

Related Posts

Potential memory leak of thread ContextClassLoader ContextClassLoader

Interns looking for Java Web work often encountered training classes how to break?

Refactoring Code design essentials | Java Debug Notes