THE MAGAZINE FOR COMPUTER APPLICATIONS
Circuit Cellar Online offers articles illustrating creative solutions
and unique applications through complete projects, practical
tutorials, and useful design techniques.

MULTIPLIER TRICKS

by Ingo Cyliax

Start ı Implementing ı Optimization ı Signed and Unsigned Multipliers ı Sources and PDF

OPTIMIZATION

As I mentioned, parallel multipliers get big when the word width goes up. In some applications, a fast multiplier may not be needed. When a compact multiplier is required, a sequential multiplier can be used. A naive sequential multiplier does exactly what is done when a person multiplies by long hand, except itıs easier in binary.

You start with a structure like the one shown in Figure 4. There are two shiftersıone is the right multiplier and one is for the product. When the least significant bit of the right multiplier is one, you add the multiplicand to the product. After each step, you shift the multiplier and product to the right. Of course, the product register has to be twice the size of the multiplier, and it takes n steps to compute.

Figure 4ıSequential multipliers use a simple adder and a combination of storage registers for the multiplicand and shift registers for the multiplier and product. They work, but youıd have to do the multiplying (except in binary).

There are a couple of optimizations here. One is that, when the least significant bit of the multiplier is zero, there is no adder operation necessary. If adding is expensive, then you can gain speed by skipping these steps. On average, this reduces the number of steps by half because statistics state half of the bits to be zero.

Another optimization, which is found in the Booth algorithm, exploits the fact that most adders can also subtract. In this case, the algorithm looks at two bits in one of the multipliers at a time. If the bits indicate the start of a run of ones, subtract the multiplicand from the product. If itıs the end of a run of ones, add the multiplicand. In the middle of a run of zero or ones, you simply perform the shifting operation. You should be convinced by this example:

Optimization of sequential algorithms rely on being able to perform shifts faster than performing an addition (or subtraction). Of course, designing a digital circuit that will be optimized for this is a bit trickier than doing it in software or microcode, for which these algorithms were originally designed. Still, implementing a sequential multiplier that isnıt optimized is pretty compact for large bit sizes, especially if you already have an adder designed into the circuit.

PREVIOUS • NEXT