Multiplier circuit having an optimized booth encoder/selector

Details Multiplier circuit having an optimized booth encoder/selector Multiplier circuit having an optimized booth encoder/selector

1999-03-29

2001-10-09

Mai, Tan V. (Department: 2121)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

C708S629000

Reexamination Certificate

active

06301599

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to multiplier circuits. More particularly, the present invention pertains to an improved Booth encoder/selector having an extremely fast critical path.
BACKGROUND OF THE INVENTION
Multiplier circuits are found in virtually every computer, cellular telephone, and digital audio/video equipment. In fact, essentially any digital device used to handle speech, stereo, image, graphics, and multimedia content contains one or more multiplier circuits. The multiplier circuits are usually integrated within microprocessor, media co-processor, and digital signal processor chips. These multipliers are used to perform a wide range of functions such as address generation, discrete cosine transformations (DCT), Fast Fourier Transforms (FFT), multiply-accumulate, etc. As such, multipliers play a critical role in processing audio, graphics, video, and multimedia data.
It is of utmost importance that a multiplier circuit be designed to operate as fast as possible. This is because vast amounts of digital data must be processed within an extremely short amount of time. For example, generating a frame's worth of data for display onto a computer screen or digital camera entails processing upwards of over a million pixels. Often, several multiplication functions must be invoked just to rasterize a single one of these final pixel values. And for real-time applications (e.g., flight simulators, speech recognition, video teleconferencing, computer games, streaming audio/video, etc.), the overall system performance is dramatically dependent upon the speed of its multipliers.
Unfortunately, multiplication is an inherently slow operation. Adding two numbers together requires a single add operation. In contrast, multiplication requires that each of the digits of the multiplicand be multiplied by each digit of the multiplier to arrive at the partial products. The partial products must then be added together to find the final solution. For example, 123×456 requires the addition of the three partial products of (123×400)=49200+(123×50)=6150+(123×6)=738 to find the final answer of 56088. As applied to binary numbers, multiplying two 32-bit numbers would necessitate that thirty-two partial products be calculated and then thirty-two add operations need to be performed to add together all of the partial products to find the final solution. Thus, multiplications are relatively time-consuming.
A more efficient method for multiplying together two digital numbers entails the use of a Booth encoder/selector. The concept behind Booth encoder/selectors is to subdivide the multiplier into groups of bits. These bits are then encoded and used to select the appropriate bit patterns which reduces the number of partial products. An example of a prior art Booth encoder/selector is shown in FIG.
1
. Although a multiplier utilizing this prior art Booth encoder/selector is faster than a conventional multiplier, it nevertheless takes a certain amount of time for the signals to be processed by the Booth encoder/selector. For instance, this prior art Booth encoder/selector design has a critical path which takes approximately an equivalent of nine NAND gate delays to complete. The critical path is defined as the logical flow through a circuit which takes the longest time to complete. The critical path is the limiting factor for how fast a circuit can complete its processing and is used as a measure of that circuit's speed.
Some designers have attempted to shorten the critical path by optimizing the encoder section. However, an optimized encoder comes at the expense of shifting some of the computational burden onto the selector. Others have attempted to optimize the selector. Again, this comes at the expense of increasing the delay associated with the other parts of the multiplier.
Thus, what is needed is a Booth encoder/selector circuit which has an optimized critical path such that the overall speed of the multiplier is improved. The present invention provides a novel solution whereby the logical design of the Booth encoder/selector according to the present invention is such that the critical path is upwards of twice as fast as typical prior art Booth encoder/selectors. Thereby, multipliers using the present invention's Booth encoder/selector design can operate at a much faster speed.
SUMMARY OF THE INVENTION
The present invention pertains to an improved Booth encoder/selector circuit having an optimized critical path. In one embodiment, the Booth encoder is comprised of a number of inverters coupled to several of the input multiplier bits. The inverted
on-inverted multiplier bits are then fed as inputs to NAND gates as well as a series of pass gates. The outputs of the pass gates are then fed as inputs to other NAND gates. The output from the NAND gates serve as control signals for controlling the Booth selector. In one embodiment, the control signals indicate a multiply by zero, a multiply by one, a multiply by negative one, a multiply by two, and a multiply by negative two operation. The Booth selector is comprised of inverters and pass gates. Multiplicand bits are input to the pass gates. The control signals are selectively coupled to the inverters and pass gates such that they control which one of the multiplicand bits are selected for output. Basically, the Booth selector functions as a multiplexer whereby one of the following is output: the multiplicand bit is multiplied by zero, multiplied by one, multiplied by negative one, multiplied by two, or multiplied by negative two. The Booth encoder/selector is used in a multiplier circuit to minimize the number of partial products. An adder is then used to sum all of the partial products to arrive at the final answer.
In the present invention, the critical path has been optimized. In one embodiment, it is traced as follows: a first inverter accepts a multiplier bit; a first transistor having a gate is coupled to an output of the first transistor; a NAND gates has an input coupled to the first transistor; a second inverter has an input coupled to an output from the NAND gate; a second transistor has a gate coupled to an output from the second inverter; and a third inverter has an input coupled to the second transistor. This critical path has a delay of approximately the equivalent of four 2-input NAND gates. And because the critical path is much shorter and faster than that of the prior art, the multiplier circuit can perform muliplications much more quickly. In turn, this enables computer and electronics systems to process multimedia, graphics, audio, and video data with greater throughput and efficiency.


REFERENCES:
patent: 4813008 (1989-03-01), Shigehara et al.
patent: 5151875 (1992-09-01), Sato
patent: 5231415 (1993-07-01), Hagihara
patent: 5325321 (1994-06-01), Ishida
patent: 5734601 (1998-03-01), Chu
A. Farooqui et al.; “Multiplexer Based Adder for Media Signal Processing”; LSI System Laboratory, SONY US Research Laboratories, San Jose, CA; Integration Corp., Berkeley, CA (undated).
A. Farooqui et al.; “VLSI Implementation of Early Branch Prediction Circuits for High Performance Computing”; Dept. of Electrical and Computer Eng., University of CA, Davis, CA; Integration Berkeley, CA; 1999 IEEE.

Affiliated with

Also associated with

Rating

Multiplier circuit having an optimized booth encoder/selector does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Multiplier circuit having an optimized booth encoder/selector, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiplier circuit having an optimized booth encoder/selector will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2552520