Goals:

As novice cadence users, our primary goal for this project was more of academic nature. We focused mainly on:

-Accuracy of individual building blocks, as well as overall correct functionality.

-Understanding the basics of modern chip design and becoming well-familiarized with the cadence tool.

Background

The multiplier has M-bits X and N-bits Y as input and generate -bits output Z.

The output Z is computed by adding the partial product  together. The simplest implementation requires an N-bit adder and take M cycles to generate the output. Another implementation of multiplier is so called adder array multipliers which achieve higher speed at the cost of larger hardware.  Several other technologies have been developed to improve the speed and reduce the power consumption of multiplier.  There are two widely used approaches: booth algorithm and Wallace tree compressor.

Booth algorithm can do multiplication on both non-negative and negative operand by using 2’s complement number. Moreover, the booth algorithm can further decrease the number of partial product which can lead to substantially delay and area reduction. This can be demonstrated by the following example.

,

where X is the multiplicand. The number of partial product and hence the number of operations can be reduced to two by rewriting the equation as

Booth's algorithm follows this scheme by performing an addition when it encounters the first digit of a block of ones (0 1) and a subtraction when it encounters the end of the block (1 0). When the ones in a multiplier are grouped into long blocks, Booth's algorithm performs fewer additions and subtractions than the normal multiplication algorithm.

Wallace tree is a way of summing of partial product bits parallel. By using the Wallace method, both the critical path and the number of adders are reduced.  The basic idea is using a full adder as a 3-2 compressor to “reduce” the product matrix.