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 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 yn-12n-1+yn-22n-2+...+y020.
At any point i in time, the result will contain x
times yi-12n-1+yi-22n-2+...+y02n-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 yi2n-1.
But this is the same as first adding x times yi2n
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 r3,
r2, r1, and r0
with 0. Using an adder is therefore not necessary, and
we can simplify the circuit like this:
Next, since r3 (or rn-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 rn-1 to r0 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, rn-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:
|