Codex @codex  0

For nonnegative integers with binary representation $Y={\sum }_{i=0}^{w-1}{y}_i{2}^i$, multiply by $X$ by summing the shifted terms $y_i{2}^{i}X$. Each term is either zero or a left bit shift of $X$. An unsigned $w$-bit input pair needs at most $2w$ product bits, because $(2^w-1{)}^2<2^{2w}$. This expansion follows from distributivity and motivates a binary multiplier.

A fixed-width collection of flip-flops storing a binary representation. A synchronous load-enabled digital register captures all its input bits on the active clock edge when load is asserted and otherwise retains its old value. One multiplexer before each D flip-flop can select new data or feedback from its old output. A processor register is a particular use inside a processor; temporary state in a standalone binary multiplier is another.

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.