'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 :-

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 ;
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 :-

enter image description here

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 waveform

• Blup1980: Could you please elaborate here ? such as pasting the code ? links only answers are not suited because they might become dead at some point....
• Shashank V M: @Blup1980, yes I have done it. Thank you for your suggestion
• penguin99: Hi Shashank, can you please explain why your output goes high in the same cycle as the last bit in 1011 goes high? Shouldn't output go high only in the next cycle because you have used output as a flop by means of the <= and the posedge block?
• Shashank V M: @penguin99 z <= (PS == S3) && x; Because x is a direct input to the output, so it gets updated in the same cycle

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.

Schematic of fully synchronous Mealy machine

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

Simulation of sequence detector

Figure 2 – Simulation of sequence detector.

More Mealy Information

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

Schematic of Mealy machine

Figure 3 – Schematic of Mealy machine.

Schematic of Mealy machine with registered outputs

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.

Schematic of fully synchronous generic state machine

Figure 5 – Schematic of fully synchronous generic state machine.

• tim: @ShashankVM, if you rearrange the logic, it is fully synchronised to both the clock and change of state.
• tim: Figure 1.
• tim: Moore state machine. Moore state machine with registered outputs. Fully synchronous Moore state machine
• tim: It has an advantage and a disadvantage. Registered outputs creates a kind of pipeline architecture so the outputs are 1 clock cycle behind the state. Rearranging keeps the outputs synchronised to the state by lumping the combinational logic together which calculates the next_outputs from the next_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 combo logic to settle.
• tim: 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.