Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Digital systems, linear algebra, introduction to formal proof / 2 / b / Solution

Split the four-bit unsigned inputs into two-bit halves: $X=4X_H+X_L$ and $Y=4Y_H+Y_L$. Use four copies of the two-bit binary multiplier to compute $P_{LL}=X_L{Y}_L$, $P_{HL}=X_H{Y}_L$, $P_{LH}=X_L{Y}_H$, and $P_{HH}=X_H{Y}_H$. ThenThe extreme terms occupy disjoint output positions: $P_{LL}$ uses positions zero to three and $16P_{HH}$ uses positions four to seven. Form $W$ by concatenating their four-bit outputs, with $P_{HH}$ in the upper half and $P_{LL}$ in the lower half. This needs wiring alone, so $W=16P_{HH}+P_{LL}$ without an adder.

Use the first eight-bit adder to form $R=P_{HL}+P_{LH}$ after zero-extension, and the second to form $Z=W+(R\ll 2)$. Thus four two-bit binary multipliers and two eight-bit adders suffice. The fixed left bit shift is also wiring alone.

The middle sum can reach $9+9=18$, so preserve all five of its potentially nonzero bits; retaining only four would be wrong. Its shifted value is at most 72. The final result is at most $15\times 15=225$, so both additions fit in eight bits. Concatenating the disjoint extreme terms is what saves an addition.