Narrow Wallace multiplier

Details Narrow Wallace multiplier Narrow Wallace multiplier

1999-01-29

2002-08-13

Ngo, Chuong Dinh (Department: 2121)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

C708S627000, C708S632000

Reexamination Certificate

active

06434586

ABSTRACT:

FIELD OF THE INVENTION
Embodiments of the present invention are directed generally to methods and apparatuses for providing digital multiplication, and more specifically to methods and apparatuses that use Wallace multipliers. Embodiments of the invention relate to a multiplier partitioned into two sections wherein one section generates partial products that represent low order bits and a second section that generates partial products that represent high order bits.
BACKGROUND OF THE INVENTION
Many techniques for providing fast multiplication in various computer systems have been proposed. In general, these techniques are used for integer multiplication or for generating the mantissa in floating point multiplication. The following is a description of the prior art techniques that effect processing speeds in digital multipliers.
In the most basic case, the product of two N-bit binary operands (one a multiplicand, and the other a multiplier) is obtained by using a sum of partial products wherein the partial products, representing an interim result, are obtained by separately multiplying each bit of the multiplier by all the bits in the multiplicand and repeating this step with the next most significant bit of the multiplier until each bit in the multiplier has been used. As each partial product is obtained, it is offset by one bit to the left from the preceding partial product, and then the partial products as a whole are summed. The resulting summation of partial products generates the final product. This summation of partial products technique is typically referred to as long-hand multiplication. The technique is slow and requires the use of several internal registers in a computer system to perform the arithmetic.
As a result, most digital multipliers in a computer system typically add only two partial products at a time, and each partial sum is then added to the sum of the previous partial products. Such a technique reduces process time and memory allocation. However, in creating fast digital multipliers more efficient techniques like Booth's algorithm or Wallace trees may be employed. The use of Booth's algorithm allows a fast digital multiplier to reduce the number of partial products by using a method of recoding or encoding one of the operands (e.g., the multiplier). Essentially, by using Booth recoding, one is able to accelerate the addition and the formation of partial products.
Booth's algorithm (also referred to as modified Booth recoding) essentially recodes a multiplier in order to effectively reduce the number of partial products. By reducing the number of required partial products and the associated additions, the speed of performing a multiplication operation may be increased by a factor of about two. The techniques of Booth's algorithm and/or modified Booth recoding are described in “A Signed Binary Multiplication Technique” by Andrew Booth, Q. J. Mech. Appl. Math. 4:236-240 (1951); and a “Booth Encoded Multiplier Generator Using Optimized Wallace Trees”, by Fadavi-Ardekani, J., IEEE Trans. on VLSI Systems 1(2), p120-125 (1993) which are incorporated herein by reference.
Fast multipliers that use Wallace trees to speed up the summation of partial products are well known. In these fast multipliers, a Wallace tree is used to perform the summation of partial products in a multiplication process.
FIG. 1
shows a Wallace tree
43
that includes seven levels of full adders or carry save adders (CSA's numbering one through eighteen), plus a carry propagate adder
41
. In a Wallace tree, a full adder or CSA takes three one-bit binary numbers, and generates one two-bit binary number. The two-bit binary number may either be used as an input to another CSA or used to represent the sum of previous inputs. In order to generate the first layer of the tree, the partial products are separated into columns, and bits with the same weighting average are grouped together (i.e., 1's, 2's, 4's, etc). Next, the columns are divided into threes. Each group of three bits is fed to a full adder, which creates a two bit output. The output from the first layer of the tree represents the same sum as the partial product, however, there are only two-thirds as many bits.
The remaining layers of the Wallace tree are generated by repeating the same process described for building the first layer by separating the bits into columns of equal weight, separating the columns into groups of three bits, and summing them with full adders. This results in an even smaller group of bits. Layers are repeatedly added until each layer reduces the number of bits to two bits per column, at which point two rows of bits are added with the carry propagate adder
41
. By using a Wallace tree method, computer processing time may be reduced from being directly proportional to N (the number of bits) to having a Log
3/2
N proportionality. This process is discussed by C. S. Wallace in an article entitled “A Suggestion for a Fast Multiplier” in IEEE Transactions on Electronic Computers February (1964) which is incorporated herein by reference.
Referring to
FIG. 1
, an example of a Wallace multiplier
43
with twenty inputs labeled W
1
to W
39
is shown. The Wallace multiplier
43
includes eighteen three input adders forming seven levels of adders. The various inputs labeled W
1
to W
39
represent data inputs to the adders. Note that the outputs from each of the adders reduce three initial inputs to two outputs (3:2). The outputs are then provided as inputs to a succeeding adder. As an example, the inputs W
3
, W
5
, and W
7
(collectively the “three summands”) will be traced through the system. The three summands are inputs to a carry save adder
18
on level seven of the Wallace tree. The three summands are compressed into two outputs representing a sum (s) bit and a carry (c) bit. The sum (s) bits and carry (c) bits become inputs to a carry save adder
12
on level six of the Wallace tree
43
. The carry save adder
12
receives a third input W
9
. Therefore, the carry save adder
12
has three inputs and compresses those inputs into two outputs, namely, another carry (c) and sum (s) bit.
The outputs from the carry save adder
12
become inputs to another carry save adder
8
on level five of the Wallace tree
43
. In addition, the carry bit from a carry save adder
13
on level six of the Wallace tree
43
completes the third input for the carry save adder
8
on level five of the Wallace tree
43
. The three inputs for the carry save adder
5
on level four of the Wallace tree
43
includes the carry bit and sum bit from the carry save adder
8
from level five of the Wallace tree
43
, and the input W
1
. The three inputs of the carry save adder
5
on level four are compressed into two outputs, a sum bit and a carry bit. The two outputs from the carry save adder
5
become inputs to another carry save adder
3
located on level three of the Wallace tree. A third input for the carry save adder
3
is obtained from the carry bit of another carry save adder
6
on level four of the Wallace tree
43
. The three inputs to the carry save adder
3
are compressed into two outputs, a carry bit and sum bit.
The sum bit and the carry bit from the carry save adder
3
are provided as inputs to different carry save adders. The sum bit from the carry save adder
3
is provided as an input to another carry save adder
2
located on level two of the Wallace tree. The remaining two inputs to the carry save adder
2
are obtained from the carry and sum bits of a carry save adder
4
located on level three of the Wallace tree. The carry bit of the carry save adder
3
located on level three of the Wallace tree is provided as an input to a carry save adder
1
located on level one of the Wallace tree. The remaining two inputs to the carry save adder
1
are the carry and sum bits obtained from a carry save adder
2
located on level two of the Wallace tree. Finally, the three inputs to the carry save adder
1
located on level one of the Wallace tree are compressed into a sum and carry bi

Affiliated with

Also associated with

Rating

Narrow Wallace multiplier does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Narrow Wallace multiplier, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Narrow Wallace multiplier will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2972654