Hardware interview practice
Search a synchronous calibration ROM
Search a nondecreasing local calibration table through a one-cycle synchronous read-only memory (ROM) port. Report whether the key exists and, for duplicates, return its lowest index.
Reviewed example
Work through one case
Input
ROM=[2,4,4,4,9]; search key=4Expected output
found=1; index=1An equal comparison records a candidate but continues the binary search left, with each ROM issue separated from its next-cycle comparison.
What to cover
Requirements
- Support N >= 1 even when N is not a power of two.
- Separate the ROM read-issue cycle from the comparison cycle.
- Continue toward the left boundary after an equal comparison.
- Return found = 0 and index zero for a miss, and pulse done after a finite search.