A 1011 Sequence Detector with Overlap

Where the interviewer goes next. Open a node to practise that follow-up.

What IfProve ItBreak ItCompare

1. A 1011 Sequence Detector with Overlap
2. CompareMoore vs Mealy for the Same DetectorL0 FresherL1 Junior

   Compare a Moore version of the 1011 detector with the Mealy one. What changes?

   Reveal the Model Answer

   The Moore version needs a fifth state, "1011 seen", and match comes from that state alone. So it rises one cycle later, after the edge that enters the state. The Mealy output rises in the cycle of the last bit. But it can also glitch with the input.

   RUNIcarus Verilog · in your browser

   Edit the code, then run it

   OutputWaves

   RunReset codeExpected: cycle 3 din=1 mealy=1 moore=0 cycle 4 din=0 mealy=0 moore=1

   Self-Check

   Tick each key point you covered in your answer.

   Key point 1 The Moore version needs a fifth state, "1011 seen", and match comes from that state alone. Key point 2 So it rises one cycle later, after the edge that enters the state. Key point 3 The Mealy output rises in the cycle of the last bit. Key point 4 But it can also glitch with the input.

   Misconception

   "Moore and Mealy detectors need the same number of states."

   The Moore output needs its own state for "pattern seen", so this detector needs five states, not four.

   Source Sutherland, RTL Modeling with SystemVerilog (2017) ch. 8.2.1 Mealy and Moore FSM architectures

   • Lesson R3.1Moore, Mealy and When the Output Changes
3. Break ItThe Detector That Missed 1011 Inside 11011L1 Junior

   A detector passes the stream 1011 but misses the mark in 11011. Which transition is wrong?

   S1:   if (din) nxt = S0; else nxt = S10;   // in state "1", another 1 arrives

   Reveal the Model Answer

   In state 1, another 1 still leaves a 1 as the newest bit. So the machine must stay in S1. Going to S0 throws away a valid start, and 11011 never reaches S101.

   Self-Check

   Tick each key point you covered in your answer.

   Key point 1 In state 1, another 1 still leaves a 1 as the newest bit. Key point 2 So the machine must stay in S1. Key point 3 Going to S0 throws away a valid start, and 11011 never reaches S101.

   Missed Corner

   "If 1011 passes, every stream passes."

   One stream exercises only some transitions. The twin shows 11011 failing because S1 on 1 is never taken by 1011.

   Run It

   The detector with S1 on 1 going to S0.

   RUNIcarus Verilog · in your browser

   Edit the code, then run it

   OutputWaves

   RunReset codeExpected: stream 11011: 0 matches FAIL: a 1 after a 1 must keep the S1 state; restarting misses 1011 inside 11011

   See the Fix

   module det1011 (input logic clk, rst_n, din, output logic match);
     typedef enum logic [1:0] {S0, S1, S10, S101} state_t;   // the longest prefix of 1011 seen so far
     state_t state, nxt;
     always_ff @(posedge clk or negedge rst_n)
       if (!rst_n) state <= S0; else state <= nxt;
     always_comb begin
       nxt = S0; match = 0;
       case (state)
         S0:   if (din) nxt = S1;   else nxt = S0;
         S1:   if (din) nxt = S1;   else nxt = S10;
         S10:  if (din) nxt = S101; else nxt = S0;
         S101: begin
                 match = din;
                 if (din) nxt = S1; else nxt = S10;   // the last 1 can start the next 1011
               end
       endcase
     end
   endmodule
   module tb;
     logic clk = 0, rst_n = 0, din = 0, match;
     logic [0:4] stream = 5'b11011;
     int hits = 0;
     det1011 d (.*);
     always #5 clk = ~clk;
     initial begin
       @(negedge clk) rst_n = 1;
       for (int i = 0; i < 5; i++) begin
         din = stream[i];
         #1 if (match) begin hits++; $display("match after bit %0d", i); end
         @(negedge clk);
       end
       $display("stream 11011: %0d matches", hits);
       if (hits == 1) $display("PASS: 1011 found inside 11011");
       else $display("FAIL: expected 1 match");
       $finish;
     end
   endmodule
   

   Prints: PASS: 1011 found inside 11011

4. Prove ItSolve R3.4.1: Frame Marks That OverlapSimulator-graded

   Show it, don't just say it: this Silicon Lab problem is graded by the simulator.

   Open Problem R3.4.1

5. What IfA Shift Register Instead of an FSML1 Junior

   Asked if they ask whether an FSM is needed at all

   What if you skip the FSM and keep the last bits in a shift register?

   Reveal the Model Answer

   Keep the last three bits and compare them, with the current bit, against 1011. Overlap needs no extra logic, because every window is checked. It costs one flop per pattern bit, while the FSM needs only enough flops to count its states. For long patterns, the FSM is smaller.

   RUNIcarus Verilog · in your browser

   Edit the code, then run it

   OutputWaves

   RunReset codeExpected: shift register: 3 matches in 1011011011

   Self-Check

   Tick each key point you covered in your answer.

   Key point 1 Keep the last three bits and compare them, with the current bit, against 1011. Key point 2 Overlap needs no extra logic, because every window is checked. Key point 3 It costs one flop per pattern bit, while the FSM needs only enough flops to count its states. Key point 4 For long patterns, the FSM is smaller.

   Half-Truth

   "The shift register is always the cheaper choice."

   It needs a flop for every pattern bit minus one. A 16-bit pattern needs 15 flops, but an FSM with 16 states needs only 4 in binary.

6. What IfThe Smallest Sequence Detector: A Rising EdgeL0 Fresher

   What if the pattern is only two bits long? Detect a rising edge on a signal already in the clock domain.

   Reveal the Model Answer

   Register the signal once and compare old with new: rise = sig & ~sig_q. It is a detector for the sequence 01. The pulse lasts one clock. If sig comes from another clock domain, synchronize it first.

   RUNIcarus Verilog · in your browser

   Edit the code, then run it

   OutputWaves

   RunReset codeExpected: pattern 0110101100: 3 rising edges counted PASS: one pulse per rising edge

   Self-Check

   Tick each key point you covered in your answer.

   Key point 1 Register the signal once and compare old with new: rise = sig & ~sig_q. Key point 2 It is a detector for the sequence 01. Key point 3 The pulse lasts one clock. Key point 4 If sig comes from another clock domain, synchronize it first.

   Misconception

   Writes rise = sig & ~sig with no flop.

   A signal ANDed with its own inverse is 0 in logic. An edge needs the value from the previous cycle, which only a flop holds.

   Run It

   The edge detector without the flop.

   RUNIcarus Verilog · in your browser

   Edit the code, then run it

   OutputWaves

   RunReset codeExpected: pattern 0110101100: 0 rising edges counted FAIL: sig & ~sig is always 0; an edge needs the old value from a flop

   See the Fix

   module rise_det (input logic clk, sig, output logic rise);
     logic sig_q = 0;
     always_ff @(posedge clk) sig_q <= sig;   // sig one cycle ago
     assign rise = sig & ~sig_q;   // high now, low last cycle
   endmodule
   module tb;
     logic clk = 0, sig = 0, rise;
     logic [0:9] pattern = 10'b0110101100;   // three rising edges
     int n = 0;
     rise_det r (.*);
     always #5 clk = ~clk;
     initial begin
       for (int i = 0; i < 10; i++) begin
         sig = pattern[i];
         #1 if (rise) n++;
         @(negedge clk);
       end
       $display("pattern 0110101100: %0d rising edges counted", n);
       if (n == 3) $display("PASS: one pulse per rising edge");
       $finish;
     end
   endmodule
   

   Prints: PASS: one pulse per rising edge

   • Lesson R2.5Synchronize, Debounce, Detect
   • Problem R2.5.1One Press, One Pulse
7. Prove ItSolve R2.5.1: One Press, One PulseSimulator-graded

   Show it, don't just say it: this Silicon Lab problem is graded by the simulator.

   Open Problem R2.5.1

8. Prove ItSolve R3.4.1: Frame Marks That OverlapSimulator-graded

   Show it, don't just say it: this Silicon Lab problem is graded by the simulator.

   Open Problem R3.4.1