Q096FreeSystemVerilog
Count connected fault regions in a tile map
Interview prompt
Question
Accept a row-major fault bitmap up to 8 by 8 pixels and report how many 4-connected components contain a one. Diagonal contact alone does not connect regions. Accept width and height from 1 through 8 on cfg_valid && cfg_ready. Then supply exactly width*height pixels in row-major order, asserting pix_last only on the final accepted pixel. Pixel values are known 0/1 values.
Candidate starting point
Implementation scaffold
module fault_region_counter (
input logic clk,
input logic rst_n,
input logic cfg_valid,
output logic cfg_ready,
input logic [3:0] width,
input logic [3:0] height,
input logic pix_valid,
output logic pix_ready,
input logic pix_fault,
input logic pix_last,
output logic result_valid,
input logic result_ready,
output logic [6:0] component_count
);
typedef enum logic [2:0] {CONFIG, LOAD, SCAN, POP, EXPAND, RESULT} state_t;
state_t state_q;
logic [63:0] fault_q, visited_q;
logic [5:0] stack_q [0:63];
int unsigned width_q, height_q, total_q, load_q, scan_q, sp_q;
int unsigned current_q;
logic [1:0] direction_q;
int unsigned components_q;
logic neighbor_valid;
int unsigned neighbor_addr;
int unsigned current_col;
assign cfg_ready = (state_q == CONFIG);
assign pix_ready = (state_q == LOAD) && (load_q < total_q);
assign result_valid = (state_q == RESULT);
assign component_count = 7'(components_q);
always_comb begin : decode_neighbor
// TODO: Implement decode_neighbor using the supplied state and interface.
end
always_ff @(posedge clk) begin : load_and_count_regions
// TODO: Implement load_and_count_regions using the supplied state and interface.
end
endmoduleReviewed example
Trace one case
Input
width=3,height=3; row-major fault bitmap rows=[110,010,001]Expected output
component_count=2The upper three set cells are four-connected; the bottom-right bit touches only diagonally and therefore forms a second component.
What to cover
Requirements
- Capture a width and height from 1 through 8, followed by exactly width x height pixels.
- Use fixed-size frame storage, a visited bitmap, and a bounded stack or queue; do not use recursion or dynamic allocation.
- Check row and column boundaries before enqueuing each of the four neighbors.
- Mark a cell visited when it enters the work list so it cannot be inserted more than once.
- Hold component_count and result_valid stable under backpressure and complete internal work within 2048 cycles.
