'1011' Overlapping (Mealy) Sequence Detector in Verilog

Question

I'm designing a "1011" overlapping sequence detector,using Mealy Model in Verilog.

The FSM that I'm trying to implement is as shown below :-

Verilog Module :-

`timescale 1ns / 1ps

module seq_detector(
input x,clk,reset,
output reg z
);

parameter S0 = 0 , S1 = 1 , S2 = 2 , S3 = 3 ;
reg [1:0] PS,NS ;

    always@(posedge clk or posedge reset)
        begin
            if(reset)
                PS <= S0;   
            else    
                PS <= NS ;
        end             

    always@(PS or x)
        begin 
            
            case(PS)
                S0 : begin 
                            z = 0 ;
                            NS = x ? S1 : S0 ;
                            $display(PS);
                        end
                S1 : begin 
                            z = 0 ;
                            NS = x ? S1 : S2 ;
                            $display(PS);
                        end
                S2 : begin 
                            z = 0 ;
                            NS = x ? S3 : S0 ;
                            $display(PS);
                        end 
                S3 : begin 
                            z = x ? 1 : 0 ; 
                            NS = x ? S1 : S2 ;
                            $display(PS);
                        end

            endcase
        end
endmodule

Testbench :-

`timescale 1ns / 1ps

module testbench;
    // Inputs
    reg x;
    reg clk;
    reg reset;
    // Outputs
    wire z;
    // Instantiate the Unit Under Test (UUT)
    seq_detector uut (
        .x(x), 
        .clk(clk), 
        .reset(reset), 
        .z(z)
    );
    
initial
    begin
        clk = 1'b0;
        reset = 1'b1;
        #15 reset = 1'b0;
    end

always #5 clk = ~ clk;  

initial begin
        #12 x = 0;#10 x = 0 ; #10 x = 1 ; #10 x = 0 ;
        #12 x = 1;#10 x = 1 ; #10 x = 0 ; #10 x = 1 ;
        #12 x = 1;#10 x = 0 ; #10 x = 0 ; #10 x = 1 ;
        #12 x = 0;#10 x = 1 ; #10 x = 1 ; #10 x = 0 ;
        #10 $finish;
    end
      
    
endmodule

Simulation Output :-

The issue is that, I'm getting the number of '1011' detected to be correct (i.e. 3 according to the testbench). But the timing where the output is going high is wrong. The output 'z' is going high when '101' is being detected, when it's expected to go high when '1011' occurs. What's the possible modification that I'd have to do, so as to eliminate this error ?

Answer 1

The error is caused by mixing the combinational State assignment block with the sequential output block. The combinational state assignment block and the sequential output block have different sensitivity lists.

Following these guidelines helped me design glitch-gree FSMs.

1. Sequential blocks use nonblocking assignments.
2. Combinational blocks use blocking assignments.
3. It's better to use registered outputs.
4. Use combinational logic for the state assignment block

Link to the design on EDA Playground

Design:

`timescale 1ns / 1ps

 module seq_detector(
 input x,clk,reset,
 output reg z
 );

 parameter S0 = 0 , S1 = 1 , S2 = 2 , S3 = 3 ;
 reg [1:0] PS,NS ;

 //sequential state register block
 always @ (posedge clk or posedge reset)
   if (reset)
     PS <= S0;  
   else
     PS <= NS;
   
 //sequential output block
 always @ (posedge clk or posedge reset)
   if (reset)
     z <= 1'b0;
   else
     z <= (PS == S3) && x;
 
 //combinational state assignment block  
 always @ (*)
  begin
    case(PS)
        S0 : NS = x ? S1 : S0 ;
        S1 : NS = x ? S1 : S2 ;
        S2 : NS = x ? S3 : S0 ;
        S3 : NS = x ? S1 : S2 ;
    endcase
  $monitor(PS);
  end
  
 endmodule

Testbench:

`timescale 1ns / 1ps

 module testbench;
 // Inputs
 reg x;
 reg clk;
 reg reset;
 // Outputs
 wire z;
 // Instantiate the Unit Under Test (UUT)
 seq_detector uut (
    .x(x), 
    .clk(clk), 
    .reset(reset), 
    .z(z)
);



always #5 clk = ~ clk;  

initial begin
$dumpfile("dump.vcd");
$dumpvars(1, testbench);
fork 
    clk = 1'b0;
    reset = 1'b1;
    #15 reset = 1'b0;
begin  
    #12 x = 0;#10 x = 0 ; #10 x = 1 ; #10 x = 0 ;
    #12 x = 1;#10 x = 1 ; #10 x = 0 ; #10 x = 1 ;
    #12 x = 1;#10 x = 0 ; #10 x = 0 ; #10 x = 1 ;
    #12 x = 0;#10 x = 1 ; #10 x = 1 ; #10 x = 0 ;
    #10 $finish;
end
join   
end  
endmodule

Waveform: https://www.edaplayground.com/w/x/3Pj

Answer 2

Great answers by Shashank, but I would like to highlight a subtle issue with registered outputs, i.e. a delay of one clock cycle between the change of state and the change of outputs. This is easy to overcome by slightly rearranging the logic. This rearranged topology keeps the outputs synchronised to both the clock and the change of state. It works by calculating the next outputs from the next state (which is subtly different from calculating the present outputs from the present state). Then the next state and the next outputs are clocked through together at the next positive clock edge.

Figure 1 – Schematic of fully synchronous Mealy machine.

Fully Synchronous Mealy Machine of Sequence Detector in SystemVerilog

module SequenceDetector
#(
    parameter NUM_STATES = 4,
    parameter NUM_TRANSITIONS = 8,
    parameter NUM_INPUTS = 1,
    parameter NUM_OUTPUTS = 1
)
(
    input logic clock,
    input logic reset,
    output logic [$clog2(NUM_STATES) - 1 : 0] state,  // Optional feedback to outside world.
    input logic seq,
    output logic det
);

    typedef enum int unsigned
    {
        S0,
        S1,
        S2,
        S3
    } TState;

    localparam TState STATE_RESET = S0;
    localparam [0 : NUM_OUTPUTS - 1] OUTPUTS_RESET = 1'b0;

    TState present_state;
    TState next_state;
    logic [0 : NUM_INPUTS - 1] inputs;
    logic [0 : NUM_OUTPUTS - 1] outputs;
    logic [0 : NUM_OUTPUTS - 1] next_outputs;

    //
    // State register and outputs register
    //
    always_ff @(posedge clock or posedge reset)
    begin
        if (reset)
        begin
            state <= STATE_RESET;
            present_state <= STATE_RESET;
            outputs <= OUTPUTS_RESET;
        end
        else
        begin
            state <= next_state;          // Synchronised to clock.
            present_state <= next_state;  // Synchronised to clock.
            outputs <= next_outputs;      // Synchronised to clock and change of state.
        end
    end

    //
    // Next state logic
    //
    always_comb
    begin

        case (present_state)

            S0: case (inputs)
                    1'b1: next_state = S1;
                    1'b0: next_state = S0;
                    default: next_state = S0;
                endcase

            S1: case (inputs)
                    1'b0: next_state = S2;
                    1'b1: next_state = S1;
                    default: next_state = S1;
                endcase

            S2: case (inputs)
                    1'b1: next_state = S3;
                    1'b0: next_state = S0;
                    default: next_state = S2;
                endcase

            S3: case (inputs)
                    1'b1: next_state = S1;
                    1'b0: next_state = S2;
                    default: next_state = S3;
                endcase

            default
            begin
                $error("Reached invalid state.");
                next_state = STATE_RESET;
            end

        endcase;
    end

    //
    // Next outputs logic
    //
    always_comb
    begin
        if (present_state == S3 && next_state == S1)
            next_outputs = 1'b1;
        else
            next_outputs = 1'b0;
    end

    //
    // Input signals
    //
    assign inputs =
    {
        seq
    };

    //
    // Output signals
    //
    assign
    {
        det
    } = outputs;

endmodule

Test Bench

`timescale 1ns/10ps
module SequenceDetector_TB();

    localparam NUM_STATES = 4;
    localparam NUM_INPUTS = 1;
    localparam NUM_OUTPUTS = 1;

    logic sys_clock;
    logic reset;
    logic [0 : $clog2(NUM_STATES) - 1] state;

    //
    // Inputs
    //
    logic seq;

    //
    // Outputs
    //
    logic det;

    initial
    begin
        sys_clock = 1'b1;
        reset = 1'b0;
        seq = 1'b0;
    end

    //
    // Clock generator
    //
    always
    begin
       #5 sys_clock = ~sys_clock;
    end

    //
    // Stimulus
    //
    always
    begin
        #22 reset = 1'b1;
        #20 reset = 1'b0;
        { seq } = 0;
        #10 { seq } = { 1'b1 };
        #10 { seq } = { 1'b0 };
        #10 { seq } = { 1'b1 };
        #10 { seq } = { 1'b1 };
        #10 { seq } = { 1'b0 };
        #10 { seq } = { 1'b0 };
        #10 { seq } = { 1'b0 };
        #10 { seq } = { 1'b1 };

        #45;
        $stop;  // Stop the simulator.
    end

    //
    // Device under test
    //
    SequenceDetector SequenceDetector_Inst
    (
        .clock(sys_clock),
        .reset(reset),
        .state(state),
        .seq(seq),
        .det(det)
    );

endmodule

Simulation

Figure 2 – Simulation of sequence detector.

More Mealy Information

Compare the fully synchronous Mealy machine of Figure 1 with the following Mealy machines.

Figure 3 – Schematic of Mealy machine.

Figure 4 – Schematic of Mealy machine with registered outputs.

The registered outputs create a kind of pipeline architecture so the outputs are 1 clock cycle behind the state.

The rearranged topology of Figure 1 keeps the outputs synchronised to the state by lumping the combinational logic together which calculates the next_outputs from the next_state. To reiterate this subtle but important point: this is different from calculating the present outputs from the present state. A potential caveat of lumping the combinational logic together is that it removes the 'pipeline' so you might need a lower clock frequency to allow the combinational logic to settle.

As an example, full synchronisation is important for an IoT Factory 4.0 environment where a snapshot (state and outputs) of all the machines in a factory needs to be taken periodically.

You can redraw it like this fully synchronous generic state machine. Whether its Moore or Mealy fades into esoteric academicism. Just write the combinational logic for your requirements.

Figure 5 – Schematic of fully synchronous generic state machine.