= Solution
Use unsigned inputs as in the preceding parts. Store a 16-<bit> accumulator $P$, a 16-<bit> shifted multiplicand $M$, an eight-<bit> multiplier $Q$, and a three-<bit> iteration <binary counter> $k$. The <sequential circuit> has one 16-<bit> <adder>, a 16-<bit> <multiplexer> selecting $M$ or zero from $Q_0$, fixed one-place <bit shifts>, and load/hold selection for the <digital registers>. The input values are captured when `start` is accepted, so later input changes cannot alter the operation.
\Image[/past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2016/digital-main-sequential-multiplier.png]
{title=The shift-and-add <binary multiplier> reuses one 16-bit <adder> for eight iterations}
Use three control states with the following synchronous transition table. All assignments in a row use the old <digital register> values and occur together at the active <clock edge>.
|| State
|| Condition
|| Register updates
|| Next state
| IDLE
| `start = 0`
| Hold all <digital registers>
| IDLE
| IDLE
| `start = 1`
| $P\gets0$, $M\gets\operatorname{zeroextend}_{16}(X)$, $Q\gets Y$, $k\gets0$
| RUN
| RUN
| $k<7$
| $P\gets P+(Q_0?M:0)$, $M\gets M\ll1$, $Q\gets Q\gg1$, $k\gets k+1$
| RUN
| RUN
| $k=7$
| $P\gets P+(Q_0?M:0)$, $M\gets M\ll1$, $Q\gets Q\gg1$; hold $k$
| DONE
| DONE
| `start = 1`
| Hold all <digital registers>
| DONE
| DONE
| `start = 0`
| Hold all <digital registers>
| IDLE
Reset selects IDLE and clears the <digital registers>. Set \b[$Z=P$ and `done = 1` exactly in DONE]. A `start` pulse in IDLE launches one multiplication; further pulses during RUN are ignored. Holding `start` high cannot repeatedly launch operations: DONE waits for it to go low before rearming. The product remains stored while waiting and through the following IDLE state. There are \b[eight RUN <clock edges> after the loading edge]; the last addition is captured before `done` becomes high.
For correctness, let $X_0,Y_0$ denote the captured values. After $i$ iterations, for $0\leq i\leq8$, the <loop invariant> is
$$
P_i=X_0(Y_0\bmod2^i),\quad M_i=2^iX_0,\quad Q_i=\lfloor Y_0/2^i\rfloor,
$$
so $P_i+M_iQ_i=X_0Y_0$. Writing $Q_i=2q+b$, the next accumulation adds $bM_i$, the <left bit shift> doubles $M_i$, and the <logical right shift> changes $Q_i$ to $q$. Hence the invariant is preserved. At $i=8$, $Q_i=0$, giving \b[$Z=P_8=X_0Y_0$]. The largest product is $255^2=65025<2^{16}$, so the accumulator fits. Even the final shifted multiplicand is $256X_0\leq65280$, so it also fits.
Back to article page
