DescriptionQ425
Q425ArchASIC interview problem
Count target-sum bursts
TechniquesPrefix sumSigned arithmeticBounded scanMultiplicity
DifficultyMedium
TopicHardware Algorithms
LanguageSystemVerilog
Requirements5 checkpoints
01
Problem
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.
Example input and output
Use this case to check your interpretationInput
signed deltas = [1, -1, 1, -1]; target=0Output
matching contiguous ranges=4Explanation
Prefix values are [0,1,0,1,0]; equal-prefix pairs contribute three zero-prefix pairs and one one-prefix pair.
02
Requirements (5)
- Support 1 to 32 signed eight-bit deltas, a signed 13-bit target, and a 10-bit result up to 528.
- Insert the initial zero prefix before processing the first sample.
- Count every previous occurrence of current_prefix - target, including repeated equal prefixes.
- Sign-extend to 14 bits for the subtraction and comparison so the lookup key cannot wrap.
- Use fixed bounded storage and hold the final count stable under backpressure.