Skip to question

Q121FreeSystemVerilog

Compare packet-symbol multisets

Difficulty
Medium
Topic
RTL Datapaths
Language
SV
Interview prompt

Question

Determine whether two bounded packet descriptors contain the same 4-bit symbols with the same multiplicities, regardless of ordering. Assume static MAX_LEN >= 1 and caller-provided active lengths from zero through MAX_LEN.

Candidate starting point

Implementation scaffold

module packet_multiset_matcher #(
  parameter int MAX_LEN = 16,
  localparam int LEN_W = (MAX_LEN < 1) ? 1 : $clog2(MAX_LEN + 1),
  localparam int COUNT_W = (MAX_LEN < 1) ? 1 : $clog2(MAX_LEN + 1)
) (
  input  logic                 clk,
  input  logic                 rst_n,
  input  logic                 start,
  input  logic [LEN_W-1:0]     len_a,
  input  logic [LEN_W-1:0]     len_b,
  input  logic [3:0]           symbol_a [MAX_LEN],
  input  logic [3:0]           symbol_b [MAX_LEN],
  output logic                 busy,
  output logic                 done,
  output logic                 same_multiset
);
  logic [LEN_W-1:0] len_a_q, len_b_q;
  logic [3:0] symbol_a_q [MAX_LEN];
  logic [3:0] symbol_b_q [MAX_LEN];
  logic signed [COUNT_W:0] histogram [16];
  logic same_next;

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

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

Trace one case

Input
A length4=[1,2,1,3]; B length4=[3,1,2,1]; inactive suffixes contain unrelated data
Expected output
same_multiset=1

Both active prefixes have counts {1:2,2:1,3:1}; ordering and inactive lanes do not affect the 16-bin comparison.

What to cover

Requirements

  1. Support active lengths from zero through MAX_LEN and ignore inactive slots.
  2. Treat the 4-bit alphabet as exactly 16 possible symbols.
  3. Different active lengths must yield same_multiset=0 at the normal result edge; no early-completion or bad_length output is required.
  4. Capture both lengths and active data when start is sampled while idle. Publish done and same_multiset on the following edge, pulse done for one cycle, and clear per-request counting state.
Continue practicing
Q543 · Reference ModelsVerify a programmed minimum trace windowHardPQ100 · Hardware-Software IntegrationPredict and safely read a build-tag prefix serviceMedium