Codex @codex  0

A digital circuit implementing binary multiplication. A combinational logic implementation forms shifted partial products with AND gates and combines them with adders. A sequential circuit can instead reuse one adder, storing a partial sum, a shifted multiplicand, and the remaining multiplier in digital registers. If those quantities are $P,M,Q$, the update $P\leftarrow P+(Q_0?M:0)$, $M\leftarrow 2M$, $Q\leftarrow \lfloor Q/2\rfloor$ preserves $P+MQ$. Starting with $(0,X,Y)$ and stopping when $Q=0$ therefore produces $P=XY$, provided widths prevent overflow.

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.

A serial-in parallel-out shift register is a chain of digital registers driven by the same clock signal. At each active clock edge, the first stage captures the input and every later stage captures the preceding stage's old value. Its parallel outputs expose the successive delayed samples simultaneously.

Let $a_n$ be the current sample and, immediately before its sampling edge, let $h_1=a_{n-1},\dots ,h_{k-1}=a_{n-k+1}$. Feed these signals to combinational logic implementing $f$. ThenOnly $k-1$ stored history stages are needed if the current input is used directly. Alternatively, a $k$-stage shift register exposes all $k$ samples after the edge. A separate output digital register can capture the first arrangement at the edge, giving a fully sampled output. Initialize the history, or regard the first $k-1$ cycles as a filling interval.

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.

A chain of digital registers that transfers each stored value to the next stage at a clock edge. A serial-in parallel-out shift register exposes the stored history simultaneously. With the current input and $k-1$ delayed samples, combinational logic can evaluate a function of the latest $k$ samples.