'1011' Overlapping (Moore) Sequence Detector in Verilog

Question

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

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

enter image description here

Verilog Module :-

`timescale 1ns / 1ps
module seq_detector(
input x,clk,reset,
output reg z
);
parameter S0 = 0 , S1 = 1 , S2 = 2 , S3 = 3 , S4 = 4;
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 <= 0;
 NS <= x ? S4 : S2 ;
 $display(PS);
 end
 S4 : begin 
 z <= 1; 
 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 :- enter image description here

The issue is that, the output 'z' is staying low always, even when I've applied an input sequence which has three '1011' patterns in it . What's the possible modification that I'd have to do, so as to eliminate this error ?

• Transistor: This seems to be almost a duplicate of your previous question with exactly the same title. Can you edit to explain the difference and modify the title to show the difference. If not this is likely to be closed as a duplicate.
• Abhishek Chunduri: The state machine(previous was a Mealy design, whereas this is Moore) is different , and the error issue is different . The issue pointed in previous post, has been rectified in this (non-blocking assignment), but still the issue persists.
• Transistor: The title edit makes it very clear. Thanks.

Answer 1

In Moore Machines the output depends only on the current state. So when you are changing your output, (z in this case), the sensitivity list should be only the current state.

You should add the default case so that your FSM remains idle when there is no change in the current state.

In your combinational block, you should use blocking statements to prevent your simulation from running into infinite loops and getting locked up.

Simulate the circuit here on my 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 , S4 = 4;
reg [2:0] PS,NS ;
always @(posedge clk or posedge reset)
 begin
 if(reset)
 PS <= S0; 
 else 
 PS <= NS ; 
 end
always @(PS, x)
begin 
case(PS)
 S0 : begin
 NS = x ? S1 : S0 ;
 $display(PS);
 end
 S1 : begin 
 NS = x ? S1 : S2 ;
 $display(PS);
 end
 S2 : begin 
 NS = x ? S3 : S0 ;
 $display(PS);
 end 
 S3 : begin 
 NS = x ? S4 : S2 ;
 $display(PS);
 end
 S4 : begin 
 NS = x ? S1 : S2 ;
 $display(PS);
 end
 default: NS = S0; 
 endcase
 end
always @(PS)
begin
 case(PS)
 S4: z = 1;
 default: z = 0;
 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)
);
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/kk

enter image description here

---

There are totally 32 possibilities to test for this Overlapping FSM because there are 5 states. Alternative: Use a formal property to verify the FSM.

property CHK_SEQ_DETECT;
 @(posedge clk) disable iff (reset) x ##1 !x ##1 x[*2] |=> z;
endproperty;
ASSERT_CHK_SEQ_DETECT: assert property (CHK_SEQ_DETECT);

Add these lines in the design module, complete setup of formal tool and run it.

Note:

As mentioned in Coding And Scripting Techniques For FSM Designs With Synthesis-Optimized, Glitch-Free Outputs by Clifford Cummings, Sunburst Design, Inc,

The combinational outputs generated by these two coding styles (Example 1 and Example 2) suffer two principal disadvantages:

1. Combinational outputs can glitch between states.
2. Combinational outputs consume part of the overall clock cycle that would have been available to the block of logic that is driven by the FSM outputs.

When module outputs are generated using combinational logic, there is less time for the receiving module to pass signals through inputs and additional combinational logic before they must be clocked.

Hence, coding an overlapping Moore with registered output, in SystemVerilog, and with better signal names:

module seq_detector(
 input seq_in, clk, reset,
 output logic detect_out
);
 //one-hot encoding of FSM
 enum logic [4:0] {S0 = 5'b00001, S1 = 5'b00010, S2 = 5'b00100, S3 = 5'b01000, S4 = 5'b10000} state, next;
 //state registers
 always_ff @(posedge clk or posedge reset)
 if (reset) state <= S0; 
   else state <= next;
 // Next state assignment logic
 always_comb begin: set_next_state    
   next = state;
 unique case (state)
 S0 : if (seq_in) next = S1; else next = S0;
 S1 : if (seq_in) next = S1; else next = S2;  
    S2 : if (seq_in) next = S3; else next = S0;
 S3 : if (seq_in) next = S4; else next = S2;
 S4 : if (seq_in) next = S1; else next = S2;
   endcase 
   $monitor(state);
 end: set_next_state
 // Registered output logic
 always_ff @(posedge clk, posedge reset)
 if (reset) detect_out <= 1'b0;
 else detect_out <= (state == S4);
property CHK_SEQ_DETECT;
 @(posedge clk) disable iff (reset) seq_in ##1 !seq_in ##1 seq_in[*2] |=> ##1 detect_out;
endproperty;
ASSERT_CHK_SEQ_DETECT: assert property (CHK_SEQ_DETECT);
endmodule

As the input is not directly connected to the output, the FSM is free from being affected by glitches at the input.

• Elliot Alderson: Please don't hand out solutions to questions that are obviously homework. We don't want this site to become a homework answering service. Generally we prefer to give hints that guide the OP to finding their own solutions.
• Elliot Alderson: Also, non-blocking assignments are usually not recommended for combinational logic such as your next-state and output blocks. The @(*) event list is also preferred for combinational logic because it is less error-prone.
• Shashank V M: @ElliotAlderson, regarding answering homework questions, I don't answer them unless the asker has shown efforts. I follow the guidelines outlined in this answer electronics.meta.stackexchange.com/a/87/238188
• Elliot Alderson: Are you saying that we should not question the recommendations made by someone with a PhD? Here are recommendations from someone who wrote Verilog code professionally: sunburst-design.com/papers/CummingsSNUG2000SJ_NBA.pdf
• Elliot Alderson: Using @(*) would not have changed the behavior in any way...it would still be a Moore FSM. Rather, it would have made the simulation behavior consistent with the hardware behavior, and avoids the occasional error of forgetting to include all necessary signals in the event list. Synthesis tools typically ignore the event list for combinational blocks.

Answer 2

Your state variable is too small. You have 5 states, but your variable is only 2 bits wide. It must be at least 3 bits wide. Change:

reg [1:0] PS,NS ;

to:

reg [2:0] PS,NS ;

Now I see z go high 3 times.

---

Now that you have unused states (5-7), you should add a default to your case statement.