- Published: Wednesday, 18 April 2018 21:22
- Written by Timothy Chapman
Multiplication, at its core, is simply repeated addition. But if all you have in your circuit is an adder, then you will be waiting a very long time for the device to finish the multiplication problem. There are a lot of shortcuts that are available to speed-up the operation. We will go through three of them here. Note that the circuits described are so complex that we will be using almost exclusively block diagrams for all of the components used. I will be using Logisim Evolution Holy Cross Edition to demonstrate these circuits. One more thing before we get started: The size of the product in bits will be the sum of all of the input bits on both the A and B inputs.
The term "series" refers to a set of tasks being done one at a time. Multiplication, at its core, is repeated addition. And there are two primary ways we can achieve this: The first is by storing the result of our operation in a register, shifting it to the right, then adding the original number to the result. This method requires a clock signal and it a bit more complicated than it first appears. The second method simply uses layers of adders to compute the final product. No registers are used and no clock signal is required.
When adders are layered on top of each other, like what's shown in the block diagram below, all of the multiplication can (potentially) be done in one clock cycle depending on the propagation delay of the logic gates and the frequency of the clock. The sum of all of the gate delays must be less than the time between clock pulses in order for this to work. The number of adders needed is equal to the bit size of the adder (assuming that the number of A and B input bits match). The outputs are labeled P0-P7 where "P" stands for product.
On a side note, notice that the first Cin of each layer is tied to ground. It's always good practice to tie otherwise unused inputs either to ground or to the power rail so that they don't cause problems with the circuit. I have used ripple-carry adders in this example to demonstrate the concept. Each column of full adders represents a different layer. Carry-look-ahead adders can be used in each layer instead of ripple-carry adders.
There are a number of ways that you can use registers and shifters to do multiplication. The image above doesn't have a physical shifter, but each layer of adders is shifted left one bit from the previous layer. In the image below, a counter is used to determine when to stop adding and how much to shift the A and B inputs by. A register that is twice the bit width of the inputs is used to store the product of the multiplication. And finally, a single adder is used to add the shifted A input and the register together.
On a side note, because the counter in the above circuit has a load enable input tied to ground, there is no need to tie the D input to ground. Notice that there are two feedback loops in this circuit. The first feedback loop is the register's Q output going into an adder, then back into the register's D input. The second feedback loop is the counter's output going into a comparator, which goes into an AND gate that then stops the counter from counting any higher. In the above circuit, whenever a multiply operation is commanded, the Clr input needs to be set to 1 for a brief period of time, then set back to zero. Then the WE (write enable) needs to be set high and held high until the multiply operation is complete.
Using this method, the number of clock cycles it will take to finish a single multiply operation is equal to the bit width of the input. So an 8-bit multiplier would take 8 clock cycles to finish one multiply operation. And a 64-bit multiplier will take 64 clock cycles to finish a single multiply operation. The time it takes to complete the operation is constant when multipliers this "simple" are used.