G7.4.2 Break the Sequence Detectors

MediumBreak ItIcarus · browser samples / server checks5 hidden designsReview the topic

Write at most three bit streams that expose five faulty detectors for 11001: overlap, fallback, reset and output-timing bugs.

Hardware context: A serial receiver that marks each block with a short bit pattern, where marks may share bits. Write three streams that expose five faulty 11001 detectors.

Five teams handed in detectors for the frame mark 11001. All of them flag a clean 11001. Each one is wrong in one way. Before the chip is built, you must show each bug on a simulator.

This is a Break it problem. In the task stimulus, call try_stream once for each test stream, at most three times. A stream holds 1 to 32 bits; its leftmost bit arrives first.

Every stream runs through the correct detector and the five hidden ones. A hidden detector is caught when its flags differ from the correct ones in some cycle.

Signals in the Timeline

SignalWidthRole
hidden_bug8input of each check
Full specification
The correct detector (each hidden one is this function with one bug)
// The correct detector for 11001: Mealy output, overlapping matches. Bit n-1 of bits arrives first.
// It returns one flag per cycle: flag t is 1 when the bit of cycle t completes 11001.
function automatic logic [31:0] matches(input logic [31:0] bits, input int n);
  logic [2:0] st;            // 0 nothing, 1 "1", 2 "11", 3 "110", 4 "1100"
  logic [31:0] z;
  logic b;
  st = 0; z = 0;
  for (int t = 0; t < n; t++) begin
    b = bits[n - 1 - t];
    case (st)
      3'd0: st = b ? 3'd1 : 3'd0;
      3'd1: st = b ? 3'd2 : 3'd0;
      3'd2: st = b ? 3'd2 : 3'd3;
      3'd3: st = b ? 3'd1 : 3'd4;
      default: if (b) begin z[t] = 1'b1; st = 3'd1; end else st = 3'd0;
    endcase
  end
  return z;
endfunction
What you write
task automatic stimulus();
  try_stream(5'b11001, 5);   // bits, then how many: the leftmost bit is the first
endtask

Each stream starts from reset. A flag belongs to the cycle of the bit that completes 11001, and overlapping matches count.

Examples

Run samples checks your input rules and any explicitly public sample faults. Submit runs every hidden faulty copy on the server. The worked bug examples below describe Submit results.

Example 1

Your Streams Follow the Rules
Input
stimulus() makes 1 to 3 calls with 1 to 32 bits each
Output
inputs_legal = yes

The first row checks only the number of streams and their lengths.

Example 2

Hidden Detector 1 Is Caught
Input
Your streams, run on hidden detector 1
Output
caught = yes

A hidden detector is caught when, in some cycle of some stream, its flag differs from the correct one.

Example 3

Hidden Detector 2 Is Caught
Input
Your streams, run on hidden detector 2
Output
caught = yes

The same test for the next detector. Every hidden detector needs its own caught = 1.

Constraints and Contract

  • Call try_stream at most 3 times inside stimulus.
  • Each stream has 1 to 32 bits.

Hints

Hint 1

A clean 11001 takes only the forward arcs. Bugs live on the arcs that a clean pattern never takes.

Hint 2

Aim a stream at each arc: the arc after a match and a third 1 after 11. Also the first bit after reset, and the cycle after a match.

Hint 3

One stream can hold several tests. Start with a match, make the next match share its last 1, then add a run of three 1s.

What the grader checks: Your streams are recorded, then run through the correct detector and five hidden faulty ones as functions of the whole stream. A hidden detector is caught when its flags differ in some cycle.

6 checks on Icarus · browser samples / server checks. Run the examples first, then check the full regression. Full checks use the server judge. Downloads contain public samples only. A passing result establishes the tested cases, not a proof for all possible inputs.

See all 2 steps and the final capstone

Report a problem with this page

Your code SystemVerilogSaved locally
Ln 1, Col 1Tab indents · Ctrl/⌘ + Enter runs samples
Not run yet

Your Streams Follow the Rules

Input
stimulus() makes 1 to 3 calls with 1 to 32 bits each
Expected output
inputs_legal = yes

The first row checks only the number of streams and their lengths.

Run samples executes all 1 public checks. Check all tests runs 6 checks on the server.

Icarus · browser samples / server checks