DescriptionQ909
Q909ArchASIC interview problem
Rotate a tile in place with one memory port
TechniquesMatrix rotationSingle-port SRAMAddress generationFSM
DifficultyMedium
TopicMemory Systems
LanguageSystemVerilog
Requirements5 checkpoints
01
Problem
Rotate a loaded square pixel tile 90 degrees clockwise in place when the local row-major memory permits only one synchronous read or one write per cycle.
Example input and output
Use this case to check your interpretationInput
N=2; row-major tile = [1, 2, 3, 4]Output
row-major tile after rotation = [3, 1, 4, 2]Explanation
Saving the complete four-pixel cycle before any write prevents the single-port in-place update from destroying a later source pixel.
02
Requirements (5)
- Support N from 1 to 8 and exactly N times N pixels loaded in row-major order.
- Use the mapping (row, col) -> (col, N - 1 - row) without allocating a second tile.
- Save all four pixels in a cycle before writing any of them back.
- Use only a constant number of pixel registers and block external reads during rotation.
- After done, provide one-cycle external reads of the rotated row-major tile.