Q043FreeSystemVerilog
Verify a dictionary-order permutation streamer
Interview prompt
Question
Complete the supplied fixed seven-lane checker for a single-request block that streams dictionary-order permutations of accepted bytes. Observe signals immediately before rising-edge updates; rst_n is known at every sampled edge. After at least one sampled reset, snapshot known count and active bytes on req_valid && req_ready; live request fields may then change. Bytes are unsigned values 0 through 255, including zero. Unused request lanes are ignored. No response can belong to a request accepted on that same edge. A sampled rst_n=0 cancels the device stream and all checker work; active handshake controls are known.
Candidate starting point
Implementation scaffold
module permutation_checker #(parameter int FIRST_BOUND=32,GAP_BOUND=8)(
input logic clk,rst_n,req_valid,req_ready,
input logic [3:0] count,input logic [7:0] item[7],
input logic out_valid,out_ready,out_last,out_error,
input logic [7:0] permutation[7],input logic [3:0] out_count
);
typedef logic [6:0][7:0] permutation_t;
permutation_t expected[$];
bit pending,expected_error,held;
int unsigned owned_count,beat_index;
longint unsigned gap_age,total_age,total_bound;
logic [61:0] held_fields;
wire [61:0] output_fields={out_last,out_error,out_count,
permutation[6],permutation[5],permutation[4],permutation[3],
permutation[2],permutation[1],permutation[0]};
initial if(FIRST_BOUND<1 || GAP_BOUND<1)$fatal(1,"Require positive progress bounds");
function automatic bit next_permutation(ref byte unsigned values[$]);
// TODO: advance to the next dictionary ordering, or return 0 at the last.
endfunction
function automatic int unsigned factorial(input int unsigned n);
// TODO: return the factorial count for the stated legal domain.
endfunction
task automatic predict_permutations(
input logic [7:0] accepted[7],input int unsigned n,
output permutation_t result[$],output bit error_value
);
// TODO: validate, copy, sort and generate fixed seven-lane results or one error.
endtask
task automatic check_cycle();
// TODO: implement sampled ownership/reset, exact outputs, held bundle and progress.
endtask
task automatic check_finished();
// TODO: report unfinished owned work.
endtask
always @(posedge clk) check_cycle();
final check_finished();
endmodule
Reviewed example
Trace one case
Input
Accept bytes [b,a,c] with count=3 at C0, where a,b,c are ASCII bytes.Expected output
Accept [abc,acb,bac,bca,cab,cba] in that order. Each result has out_count=3, out_error=0 and four zero unused lanes; only cba has out_last=1.Sorting the owned copy establishes the first result. Stalls may delay acceptance, but cannot change the current result or advance the queue; req_ready stays low through the final acceptance.
What to cover
Requirements
- For count=1 through 7 with distinct active bytes, copy and sort the accepted values, then expect exactly count! results in strict unsigned dictionary order. The first token is permutation[0]. Every accepted result has out_count=count, out_error=0, and all unused lanes zero. Expected counts for 1..7 are 1,2,6,24,120,720,5040.
- A duplicate active byte or count outside 1 through 7 owns exactly one final error beat: all seven payload lanes and out_count are zero, out_error=1 and out_last=1. It must not produce a smaller successful permutation set. Compare every accepted payload lane, count and marker using four-state equality; ignored request lanes cannot invalidate a legal request.
- Only one request is active. req_ready stays low through the final response accepting edge; admit a replacement only on a later edge. Reject any unowned out_valid, including blocked output. Count only subsequent out_ready=1 opportunities: first acceptance is due by FIRST_BOUND (default 32), each later acceptance within GAP_BOUND (default 8) further opportunities, and total completion within FIRST_BOUND+(expected beat count-1)*GAP_BOUND. Bounds are positive, acceptance at the bound wins, and out_ready=0 pauses all progress counters.
- Hold out_valid, all seven payload lanes, out_count, out_last and out_error through a stall and its accepting edge. Assert out_last only on the final result. Sampled reset cancels ownership, held-output history and deadlines. Report unfinished work at test end. Payload/count/markers are meaningful only when out_valid=1. Without response IDs, an identical old result after a new request cannot be distinguished, so the device must flush canceled work on reset.