Binary multiplication

Pre-requisites

The solution to this problem is going to be to use a sequential circuit and to divide the work into several stages, one stage for each clock pulse.

The algorithm we are going to use is the same one that is used in ordinary binary multiplication, only we change the order of the operations slightly. In ordinary multiplication, we compute all the partial results of multiplying the first factor with each binary digit of the second factor. Then we add each partial result together to obtain the final result. In the modified verson, we keep an accumulator containing the sum of all the partial results computed so far. When we have computed the last partial result, we have also computed the final result.

To see how this can be done, notice that the result of multiplying two n-digit positive binary numbers, the result may be as long as 2n digit long.

Let us denote the first factor by x, the second by y, and the result by r. We first write y as y_n-12^n-1+y_n-22^n-2+...+y₀2⁰. At any point i in time, the result will contain x times y_i-12^n-1+y_i-22^n-2+...+y₀2^n-i. Obviously, when i=n we have our final result. To get from step i to step i+1, we need to divide the result by 2 and add x times y_i2^n-1. But this is the same as first adding x times y_i2ⁿ and then dividing the result by 2. This process must be repeated n times.

Here is our first attempt at a circuit for multiplication:

This circuit works fine, but it is wasteful. First, notice that the lower part of the adder always adds r₃, r₂, r₁, and r₀ with 0. Using an adder is therefore not necessary, and we can simplify the circuit like this:

Next, since r₃ (or r_n-1 in general) contains 0 initially, the rightmost D-flip-flop always contains 0 as well, which is fortunate, because we never use it. We obtain this circuit:

For our final simplification, notice how the flip-flops containing r_n-1 to r₀ and the n upper flip-flops never simultaneously contains any information. Initially, all of the upper flip-flops contain useful information, and none of the n rightmost bottom flip-flops do. After step one, r_n-1 contains useful information, and the leftmost of the upper flip-flops no longer does, etc. We can therefore use only one set of n flip-flops to hold both y and the lower n digits of the result. Here is the final circuit: