Skip to question

Q045FreeSystemVerilog

Find a missing packet sequence ID

Difficulty
Medium
Topic
Streaming RTL
Language
SV
Interview prompt

Question

After an idle start, consume n distinct sequence IDs drawn from the inclusive range 0 through n and report the one missing value using constant word-sized state. Assume static MAX_N >= 0 and caller-provided 0 <= n <= MAX_N. The producer guarantees distinct in-range IDs.

Candidate starting point

Implementation scaffold

module missing_sequence_detector #(
  parameter int MAX_N = 16,
  localparam int ID_W = (MAX_N < 1) ? 1 : $clog2(64'(MAX_N) + 64'd1)
) (
  input  logic            clk,
  input  logic            rst_n,
  input  logic            start,
  input  logic [ID_W-1:0] n,
  input  logic            seq_valid,
  input  logic [ID_W-1:0] seq_id,
  output logic            seq_ready,
  output logic            result_valid,
  input  logic            result_ready,
  output logic [ID_W-1:0] missing_id
);
  logic active;
  logic [ID_W-1:0] n_q;
  logic [ID_W-1:0] accepted_count;
  logic [ID_W-1:0] xor_accum;

  function automatic logic [ID_W-1:0] xor_zero_to_n(
    input logic [ID_W-1:0] limit
  );
    // TODO: Return XOR of the inclusive range 0 through limit without unbounded signed iteration.
  endfunction

  assign seq_ready = active && !result_valid;

  always_ff @(posedge clk) begin : count_and_publish
    // TODO: Implement count_and_publish using the supplied state and interface.
  end
endmodule
Reviewed example

Trace one case

Input
n=4; accepted distinct sequence IDs=[4,1,0,3]
Expected output
missing_id=2

The XOR of 0 through 4 is 4. After accepted IDs 4, 1, 0, and 3, the running candidate is 0, 1, 1, and finally 2. Register 2 after the fourth transfer; input gaps must not change the count or accumulator.

What to cover

Requirements

  1. Use no bitmap or external memory.
  2. Accept start only while no sequence is active and no result is pending. Complete after exactly n accepted IDs and handle missing zero or missing n.
  3. For n equal to zero, return zero without waiting for input data.
  4. Hold the result until accepted and do not advance the count during input stalls.
Continue practicing
Q769 · Reference ModelsSkip a missing packet after timeoutMediumPQ500 · Computer ArchitectureReorder an eight-packet sequence windowHardPQ244 · Reliable RTLHandle wrapping 8-bit sequence numbersMediumPQ1091 · Bit ManipulationFind the single non-duplicateEasyP