Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-08-31
2002-05-21
Mai, Tan V. (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06393454
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the field of math processors in computers, and more particularly, to Booth multipliers used in math processors to perform high speed multiplication of numbers.
2. Description of Related Art
One of the primary functions of most computer systems is to perform a large number of mathematical operations at a speed much faster than a human being could perform the operations. Since a computer devotes a considerable amount of its processing time to performing mathematical operations, an improvement in the speed of a math processor of the computer for performing a particular type of operation will increase the overall speed of the computer.
A known method of performing multiplication in a math processor is by array multiplication using a parallel multiplier. The parallel multiplication process is based on the fact that partial products in multiplication can be independently computed in parallel. An example of multiplication by partial products is shown below in Table 1 for two 4-bit numbers.
TABLE 1
4-bit Multiplier Partial Products
X3
X2
X1
X0
Multiplicand
Y3
Y2
Y1
Y0
Multiplier
X3Y0
X2Y0
X1Y0
X0Y0
X3Y1
X2Y1
X1Y1
X0Y1
X3Y2
X2Y2
X1Y2
X0Y2
X3Y3
X2Y3
X1Y3
X0Y3
P7
P6
P5
P4
P3
P2
P1
P0
Product
A parallel multiplier is normally implemented as a square array of adders. In what is known as a Radix-2 scheme, the partial products are computed by observing one bit of the multiplier at a time. A higher radix multiplier, such as a Radix-4 multiplier, or a “Booth recoding multiplier”, reduces the number of adders (and therefore the delay required to produce the partial sums) by examining a plurality of bits at a time. In conventional Booth recoding, the multiplier bits are divided into two-bit pairs, and a total of three bits are scanned at a time. These three bits are: the two bits from the present pair; and a third bit from the high order bit of an adjacent lower-order pair. After examining each triplet of bits, Booth recoding logic converts the triplet into a set of five control signals used by the adder cells in the array to control the operations performed by the adder cells.
In a conventional 16×16 Booth multiplier, such as that shown in the prior art multiplier of
FIG. 1
, the array comprises eight rows (or “stages”) of adder cells. Only eight stages are needed in the array since a plurality of bits of the multiplier are examined in each stage.
The high performance of the Booth multiplier does not come without cost, however, in the form of relatively high power consumption. This is due in part to the large number of adder cells (15 cells for 8 rows=120 core cells) that consume power. Each of the adder cells normally includes a 5-input multiplexer controlled by the five control signals generated by the Booth recoding logic. In Booth multipliers that use conventional Booth recoding logic to generate the control signals, short-circuit paths can be created by one of the control signals turning off after another signal has turned on to select one of the inputs. These temporary short-circuit paths dissipate power and increase the power consumption of a Booth multiplier.
Another large consumer of power in Booth multiplier arrangements is the input bus that provides one of the numbers (the multiplicand) to each of the eight stages (or rows) in the array. Using the same input to drive all eight stages means that there is a very large load on the multiplexers in the first stage of the array. Due to this load, the input to the array must be buffered. However, in order to provide high-speed multiplier performance, the first stage needs to receive the input with very little delay. Prior Booth multipliers therefore provided high-speed buffers to the first input stage, but these buffers consumed a sizable amount of power.
SUMMARY OF THE INVENTION
There is a need for a Booth multiplier with reduced power consumption that is achieved without decreasing the speed of the Booth multiplier.
This and other needs are met by the present invention which provides a Booth multiplier for multiplying a first number with a second number to produce a product. The Booth multiplier of the present invention comprises an array of adder cells arranged in a plurality of rows of adder cells. The adder cells perform addition on bits of the first and second numbers. One of the adder cells of each row is a left-most cell for that row. Each row of adder cells receives Booth recoded control signals formed from a different subset of bits of the second number, and each of the adder cells in each row receives a different bit of the first number. The Booth multiplier also comprises a plurality of Booth recoding logic cells, each Booth recoding logic cell coupled to the left-most cell of a different one of the rows. The Booth recoding logic cells receive different subsets of bits of the second number and generate the Booth recoded control signals as a function of the received subset of bits. Each Booth recoding logic cell includes balanced logic circuitry for generating all of the Booth recoded control signals from that Booth recoding logic cell at the same time.
The balanced logic circuitry of the Booth recoding logic cells minimizes temporary short-circuit paths in multiplexers that are located in the adder cells in the array. This minimization of the short-circuit paths greatly reduces the power consumption of the Booth multiplier.
The earlier stated needs are also met by another aspect of the present invention which provides a Booth multiplier for multiplying a first number with a second number to produce a product, comprising an array of adder cells arranged in a plurality of rows of adder cells. The adder cells perform addition on bits of the first and second numbers, the results of the additions being propagated through the array from higher rows to lower rows, a highest row being a top row of the array. Each row of adder cells receives Booth recoded control signals formed from a different subset of bits of the second number, each of the adder cells in each row receiving a bit of the first number. A split bus provides the first number to the array, this split bus including a first branch that provides the first number unbuffered to the top row of the array, and a second branch having a buffer circuit and providing the first number buffered to the other rows of the array.
The splitting of the input bus carrying the multiplicand allows the inputs to the top row of the array to be provided quickly, while the inputs to the remaining rows of the array are provided more slowly through the input buffer circuitry that is required due to the load on the multiplexers in the adder cells. Since buffer circuitry is not required before the top row, the buffer circuitry is implementable with lower-speed, lower-power buffers. This reduces the power consumption substantially in comparison to the prior art in which high-speed, high-power buffers are located before the top row of the array. The present invention therefore takes advantage of the fact that the inputs of the multiplicand to the lower rows of the array do not have to be provided until after the top row has generated its addition results.
The foregoing and other features, aspects and advantages of the present invention will become more apparent from the following detailed description of the present invention when taken in conjunction with the accompanying drawings.
REFERENCES:
patent: 4573137 (1986-02-01), Ohhashi
patent: 4575812 (1986-03-01), Kloker et al.
patent: 4644488 (1987-02-01), Nathan
patent: 4813008 (1989-03-01), Shigehara et al.
patent: 4817029 (1989-03-01), Finegold
patent: 4887233 (1989-12-01), Cash et al.
patent: 5040139 (1991-08-01), Tran
patent: 5146421 (1992-09-01), Adiletta et al.
patent: 5181184 (1993-01-01), Shim et al.
patent: 5231415 (1993-07-01), Hagihara
patent: 5325321 (1994-06-01), Ishida
patent: 5343417 (1994-08-01), Flora
patent: 5818743 (1998-10-01), Lee et al.
patent: 61-156433 (1986-07-01), None
Waser, High-Speed Monolithic Multipliers for Real-Time Digita
Cirrus Logic Inc.
Mai Tan V.
Skjerven Morrill Macpherson LLP
LandOfFree
Booth multiplier with low power, high performance input... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Booth multiplier with low power, high performance input..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Booth multiplier with low power, high performance input... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2915169