Home  Products Tutorials Schematics Robotics Resources  Radio Stuff  Components Career  Download   Link Exchange   Sitemap


Add your Link (FREE)

Schematics and Circuits

Electronic Tutorials

Practical Experiments

More Resources

Computer Architectures - Digital Circuits - Binary multiplication

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:

 


 

Home  Tutorials Schematics Robotics Resources  Radio Stuff  Components Career  Download   Link Exchange   Sitemap


Terms & Conditions  Privacy Policy and Disclaimer
[email protected]