As we mentioned multiplication
are (currently, at least) too complicated for a combinatorial
circuit.
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 ndigit 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_{n1}2^{n1}+y_{n2}2^{n2}+...+y_{0}2^{0}.
At any point i in time, the result will contain x
times y_{i1}2^{n1}+y_{i2}2^{n2}+...+y_{0}2^{ni}.
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_{i}2^{n1}.
But this is the same as first adding x times y_{i}2^{n}
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_{3},
r_{2}, r_{1}, and r_{0}
with 0. Using an adder is therefore not necessary, and
we can simplify the circuit like this:
Next, since r_{3} (or r_{n1}
in general) contains 0 initially, the rightmost Dflipflop
always contains 0 as well, which is fortunate, because
we never use it. We obtain this circuit:
For our final simplification, notice how the flipflops
containing r_{n1} to r_{0} and
the n upper flipflops never simultaneously contains any
information. Initially, all of the upper flipflops contain useful
information, and none of the n rightmost bottom flipflops
do. After step one, r_{n1} contains useful
information, and the leftmost of the upper flipflops no longer
does, etc. We can therefore use only one set of n
flipflops to hold both y and the lower n digits
of the result. Here is the final circuit:
