Browse Prior Art Database

Partial Product Array for High Speed Multiply Using Adders for Multiple Additions

IP.com Disclosure Number: IPCOM000074887D
Original Publication Date: 1971-Jun-01
Included in the Prior Art Database: 2005-Feb-24
Document File: 4 page(s) / 119K

IBM

Related People

Singh, S: AUTHOR [+2]

Abstract

The problem of multiplying two numbers in a computer is characteristically solved by shifting and adding. The straight-forward approach is for the multiplicand to be multiplied by each bit position of the multiplier in turn, starting at the low-order bit of the multiplier. As the result is obtained for each multiplier bit, it is shifted the appropriate amount and added to the previous result. Improved speed is obtained by means of two well known algorithms, shift over zeros and shift over ones.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 4

Partial Product Array for High Speed Multiply Using Adders for Multiple Additions

The problem of multiplying two numbers in a computer is characteristically solved by shifting and adding. The straight-forward approach is for the multiplicand to be multiplied by each bit position of the multiplier in turn, starting at the low-order bit of the multiplier. As the result is obtained for each multiplier bit, it is shifted the appropriate amount and added to the previous result. Improved speed is obtained by means of two well known algorithms, shift over zeros and shift over ones.

To describe this improved multiplication process, consideration is given to the general case of multiplying an n bit number by an m bit number. Fig. A illustrates the long hand process of this procedure. The array of partial products formed in this process is important to this multiplication technique. Once the Partial Product Array (PPA) is established, the product is obtained by summing the rows of this array. Here is where the Adders for Multiple Additions (AMA) are used. This adder is constructed to add several numbers simultaneously. It outputs two numbers which must then be fed through a Carry Look-ahead Adder. The use of the adder for multiple additions is what makes this technique practical.

The AMA is partitioned, for example, so that it is capable of handling a maximum of nine rows of 3-bit binary numbers. When adding in parallel, one column from each 3-column partition set at a time, three cycles of add are required for each nine rows of the PPA (Fig. A). The results of this operation are then fed into a Carry Look-ahead Adder to yield the final result. This operation takes one additional cycle.

The Partial Product Array may be established in one parallel operation, as shown in Fig. B. A skewed array is established where each cell position consists of an AND circu...