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

Generate four partial-product bits with AND gates:The binary multiplication expansion is $XY=p_{00}+2(p_{10}+p_{01})+4p_{11}$. Add the two weight-two bits with a half adder, then add its carry to $p_{11}$ with a second half adder. The complete combinational logic isThus four AND gates for the partial products and two half adders suffice. Each half adder contains one exclusive or gate and one AND gate. In the largest case $3\times 3=9$, these equations produce $1001$, including the necessary fourth output bit.

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.

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.

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.

Reset selects IDLE and clears the digital registers. Set $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 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\le i\le 8$, the loop invariant isso $P_i+M_i{Q}_i=X_0{Y}_0$. Writing $Q_i=2q+b$, the next accumulation adds $b{M}_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 $Z=P_8=X_0{Y}_0$. The largest product is $255^2=65025<2^{16}$, so the accumulator fits. Even the final shifted multiplicand is $256X_0\le 65280$, so it also fits.