Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-02-15
2004-01-27
Ngo, Chuong Dinh (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S625000, C708S620000
Reexamination Certificate
active
06684236
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates generally to Booth encoding, and more specifically, to efficiently performing computations through extended Booth encoding of the operands thereto.
2. Background
Many Digital Signal Processor (“DSP”) applications involve or require multiplying the sum or difference of two or more signed (two's-complement) binary numbers, (X±Y), by a third signed binary number, W, resulting in Z=W*(X±Y). In a symmetric finite impulse response (FIR) filter, for example, the separate multiplication of two samples, s
i
and s
j
, by the same coefficient, c
k
, can be replaced by the computation c
k
*(s
i
+s
j
), resulting in the savings of a multiplier. Similarly, in a multiplication of two complex numbers, each of the real and imaginary components of the product can be determined through three computations of the form C*(A+B), resulting in the saving of a multiplier. Each of these examples requires an addition before the multiplication.
In current practice, two numbers must be added in a carry-propagate adder before the multiplication can be efficiently performed. Carry-save adders are commonly used to sum multiple input vectors (K
0
+K
1
+ . . . +Kn) to produce sum and carry vectors, S and C. In current practice, S and C must be added in a carry propagate adder before the product, Z=W*(K
0
+K
1
+ . . . +Kn) can be efficiently produced.
Unfortunately, the carry-propagate adder required by these computations imposes a tradeoff between size and speed. A ripple carry adder, for example, is small but slow. In contrast, a carry-look-ahead adder, while fast, is large. No conventional adder is available which combines the size advantage of the ripple carry adder with the speed advantage of the carry lookahead adder.
Consequently, there is a need for a system for and method of performing the computation Z=W*(X±Y) which is not subject to the foregoing tradeoff between size and speed.
There is further a need for a system for and a method of performing such computations which overcomes one or more disadvantages of the prior art.
The objects and advantages of the subject invention include fulfillment of any of the foregoing needs, singly or in combination.
Additional objects and advantages will be set forth in the description which follows or will be apparent to those of skill in the art.
SUMMARY OF THE INVENTION
To achieve one or more of the foregoing objects, and in accordance with the invention as broadly described herein, there is provided, in a first embodiment of the subject invention, a system of and method for performing extended Booth encoding of two signed binary numbers, K and L. In one implementation, the extended Booth encoder converts the sum K[2n+1:2n]+L[2n+1], where L[2n]=0, into the Booth triplet M
2
[n], M
1
[n], and S[n]. In one application, this triplet can then combined with a third signed binary number W to form the partial-product vectors PP[n] which are summed to produce Z=(K+L)*W in the same manner that the triplet produced by a standard Booth encoder is used combine partial products.
A second embodiment of the subject invention comprises a system for and a method of multiplying the sum or difference of two signed binary numbers, X and Y, by a third signed binary number W.
In this embodiment, an extended Booth encoder is included for encoding the sum of the operands X and Y to form encoded data. Partial products circuitry, identical to that used with standard modified Booth encoding, is also included for forming, responsive to the encoded data, a plurality of partial products, PP. The partial products, PP, are then added or subtracted, again responsive to the encoded data, together to form Z.
REFERENCES:
patent: 3878985 (1975-04-01), Ghest et al.
patent: 4122527 (1978-10-01), Swiatowiec
patent: 4229800 (1980-10-01), Gregorian et al.
patent: 4748582 (1988-05-01), New et al.
patent: 4748584 (1988-05-01), Noda
patent: 4817029 (1989-03-01), Finegold
patent: 4868777 (1989-09-01), Nishiyama et al.
patent: 4879677 (1989-11-01), Shiraishi
patent: 5289398 (1994-02-01), Miyoshi et al.
patent: 5379244 (1995-01-01), Miyoshi et al.
patent: 5473559 (1995-12-01), Makino
patent: 5636155 (1997-06-01), Kabuo
patent: 5751619 (1998-05-01), Agarwal et al.
patent: 5835393 (1998-11-01), Melanson et al.
patent: 5941942 (1999-08-01), Kleine
patent: 5944776 (1999-08-01), Zhang et al.
patent: 6167422 (2000-12-01), Purcell et al.
patent: 6173304 (2001-01-01), Goldovsky et al.
Booth, Andrew D.,A Signed Binary Multiplication Technique; (Received Aug. 1, 1950), Quart. Journ. Mech. and Applied Math, vol. IV Pt.2, pp. 236-240, 1951.
Chen, C.H., ed.,Computer Engineering Handbook, McGraw-Hill, Inc., pp. 4.10-4.12, 14.9-14.12, Jul. 1992.
Weste, N.E.H. and Eshraghian, K.,Principles of CMOS VLSI Design: A System Perspective, Addison-Wesley Publishing Co., pp. 547-554, 2ndEd. 1993.
Mlynek, D. and Leblebici, Y.,Design of VLSI Systems, Chapter 6, “Arithmetic for Digital Systems”, Nov. 10, 1998, (41 pages), available at http://vlsi.wpi.edu/webcourse/ch06/ch06.html.
Conexant Systems Inc.
Do Chat C.
Howrey Simon Arnold & White , LLP
Ngo Chuong Dinh
LandOfFree
System of and method for efficiently performing computations... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System of and method for efficiently performing computations..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System of and method for efficiently performing computations... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3195855