Skip to question
SystemVerilogDesignVerificationFirmwareArchitectureASIC Interview Questions→
/Interview questions/Count connected fault regions in a tile map

Q096·Free·SystemVerilog

Count connected fault regions in a tile map

Difficulty
Medium
Topic
RTL Design
Language
SV
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

endmodule
Reviewed example

Trace one case

Input
width=3,height=3; row-major fault bitmap rows=[110,010,001]
Expected output
component_count=2

The upper three set cells are four-connected; the bottom-right bit touches only diagonally and therefore forms a second component.

What to cover

Requirements

  1. Capture a width and height from 1 through 8, followed by exactly width x height pixels.
  2. Use fixed-size frame storage, a visited bitmap, and a bounded stack or queue; do not use recursion or dynamic allocation.
  3. Check row and column boundaries before enqueuing each of the four neighbors.
  4. Mark a cell visited when it enters the work list so it cannot be inserted more than once.
  5. Hold component_count and result_valid stable under backpressure and complete internal work within 2048 cycles.
Exact question handoffPractice Q096

Solve it in the question bank, keep your progress, and reveal the reviewed solution when your access allows.

Open in question bank →
Solution accessEach time you open this Solution, one Practice Credit is used; it is not permanently unlocked. Premium Solution content also uses one credit per opening.
Continue learning

RTL Synthesis and Proof

Review widths, parameterization, memory inference, pipelining, implementation pressure, and proof evidence.

  • RTL Design
  • Flood fill
  • Visited bitmap
  • Bounded stack
RTL Synthesis and Proof →
Continue practicing

Related questions

Q076 · Hardware-Software IntegrationVerify a DMA flood-fill transactionHard→Q552 · Reference ModelsCompile, program, and verify a bounded pattern matcherHardP→
ASIC.FYI · Learn silicon end to end.info@asic.fyi