DescriptionQ512
Q512DesignASIC interview problem
Track divisibility by three in an MSB-first stream
TechniquesModuloRemainder FSMSerial arithmeticMinimum states
DifficultyMedium
TopicFSMs
LanguageSystemVerilog
Requirements4 checkpoints
01
Problem
Receive a binary number most-significant bit first and report whether the accepted prefix is divisible by three. Use the minimum number of remainder states and support valid gaps plus an explicit start-of-number marker.
Example input and output
Use this case to check your interpretationInput
start an MSB-first number with accepted bits [1,1,0] (binary 6)Output
remainders=[1,0,0]; divisible outputs=[0,1,1] with out_valid on each accepted prefixExplanation
Applying (2r+b) mod 3 gives the minimum three-state remainder machine and consumes the start bit as part of the new number.
02
Requirements (4)
- Use one state for each remainder 0, 1, and 2.
- For each accepted bit b, update remainder with (2 x remainder + b) mod 3.
- start resets the arithmetic history before consuming the current valid bit.
- Pulse out_valid only when a bit is accepted, so reset, an empty stream, or a valid gap is not mistaken for a new result.