Browse Prior Art Database

Fast Multiply Circuit

IP.com Disclosure Number: IPCOM000053089D
Original Publication Date: 1981-Aug-01
Included in the Prior Art Database: 2005-Feb-12
Document File: 4 page(s) / 71K

Publishing Venue

IBM

Related People

Hitchcock, RB: AUTHOR

Abstract

The apparatus herein shown and described will allow a multiply to take place in a time proportional to: (N(1) log(2) log(2)n) +N(2) (1) where n = the number of bits in the multiplier and multiplicand. N(2)= the number of logic levels in an adder. N(1)= the number of levels in a special multivalued logic circuit that performs k-level majority logic and k ". residues by using a matrix adder.

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

Fast Multiply Circuit

The apparatus herein shown and described will allow a multiply to take place in a time proportional to: (N(1) log(2) log(2)n) +N(2) (1) where n = the number of bits in the multiplier and multiplicand. N(2)= the number of logic levels in an adder. N(1)= the number of levels in a special multivalued logic circuit that performs k-level majority logic and k ". residues by using a matrix adder.

When a column of K bits is summed up, the sum takes at most log(2) K bits. Utilizing this fact, a matrix is reduced step by step from K rows (K bits in each column) to log(2) K rows to log(2) (log(2) K) rows, and so on, combine the three rows and a full adder to complete the process.

The number of steps required to reduce K rows to 2 rows (assuming we did not stop at 3) is log log K. Therefore, the whole multiply operation can be performed in the time specified by (1).

The simplest form of multiply is done via a shift and add of the multiplier under the control of the bits in the multiplicand.

Another way to view this algorithm is show in Fig. 1 for seven-bit multiplier/multiplicands. The bits in the multiplier are stored in each of the stacks for which the corresponding bits in the multiplicand were one. If all the entries in this array were then added, the result value would be produced, as show in Fig. 1A, directly. Since this is not currently possible, designers have combined subsets of these stacks by using cascades of half adders, reducing the number of stacks to be combined stage after stage until there are just two stacks to be passed through a full adder.

For cases where'the number of bits in the columns of this stack array are small, a multivalued logic element capable of forming small sums of many bits very rapidly can be used. The bit representations of these sums are then stored in the form indicated in Fig. 1B. Note that since the number of bits in the multipliers was 7, the maximum sum size was three and consequently the sums can be stored in an array with only 3 rows. Similarly, the next sum can be stored in two rows, Fig. 1C which can then go into a full adder.

The key element in the column sum is a circuit that can add up bit signals an...