Skip to question

Q144FreeSystemVerilog

Count target-sum bursts

Difficulty
Medium
Topic
Hardware Algorithms
Language
SV
Interview prompt

Question

Count every nonempty contiguous range in a frame of signed occupancy changes whose sum equals a programmable target. Overlapping ranges and multiple matches ending at one sample all count. Pulse start only while idle, after reset or acceptance of the previous result. Capture target_k on that start edge; it need not remain fixed afterward. Then supply 1 through 32 accepted deltas with in_last only on the final accepted delta.

Candidate starting point

Implementation scaffold

module target_sum_burst_counter (
  input  logic               clk,
  input  logic               rst_n,
  input  logic               start,
  input  logic signed [12:0] target_k,
  input  logic               in_valid,
  input  logic               in_last,
  input  logic signed [7:0]  delta,
  input  logic               result_ready,
  output logic               in_ready,
  output logic               result_valid,
  output logic [9:0]         match_count
);
  typedef enum logic [1:0] {S_IDLE, S_INPUT, S_SCAN, S_RESULT} state_t;
  state_t state_q;

  logic signed [12:0] prefix_mem_q [0:32];
  logic signed [12:0] prefix_sum_q, new_prefix_q, target_q;
  logic [5:0] sample_count_q, scan_q;
  logic [9:0] running_count_q, result_count_q;
  logic pending_last_q;

  logic signed [12:0] accepted_prefix;
  logic signed [13:0] sought_prefix, scanned_prefix;
  logic scan_match;

  always_comb begin : compute_prefix_lookup
    // TODO: Implement compute_prefix_lookup using the supplied state and interface.
  end

  assign in_ready     = (state_q == S_INPUT);
  assign result_valid = (state_q == S_RESULT);
  assign match_count  = result_count_q;

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

Trace one case

Input
signed deltas = [1, -1, 1, -1]; target=0
Expected output
matching contiguous ranges=4

Prefix values are [0,1,0,1,0]; equal-prefix pairs contribute three zero-prefix pairs and one one-prefix pair.

What to cover

Requirements

  1. Support 1 to 32 signed eight-bit deltas, a signed 13-bit target, and a 10-bit result up to 528.
  2. Insert the initial zero prefix before processing the first sample.
  3. Count every previous occurrence of current_prefix - target, including repeated equal prefixes.
  4. Sign-extend to 14 bits for the subtraction and comparison so the lookup key cannot wrap.
  5. Use fixed bounded storage and hold the final count stable under backpressure.
Continue practicing
Q023 · RTL DatapathsFind a target-sum operand pairMediumQ153 · RTL ArithmeticInterpret one mixed-sign addition explicitlyMediumQ1110 · RTL DesignImplement Signed Eight-Bit Add/Subtract with OverflowEasyP