Recurrent adrithmetical computation using carry-save arithmetic

U.S. Patent Number: 5751619

Abstract: An arithmetic unit keeps a result in carry-save form and uses this form of the result as an input to the next iteration in recurrent computations. The full adder in the recurrent path is eliminated by implementing multiplication by Y(i), where Y(i) is available only in carry-save form. The carry-save arithmetic unit generates a plurality of partial products whose sum is the product AXB, where A is one binary input and B is either a second binary input B' or the sum C'+S' of two binary inputs C' and S'. A selection is made as to whether B is equal to B' or C'+S'. The plurality of partial products and an addition input Z are compressed to two partial products C and S whose sum C+S equals the sum of the plurality of partial products and Z. The partial products C and S are added to produce a binary result X equal to A.times.B+Z. The full adder in the recurrent path is eliminated by a feedback path which returns the partial products C and S to the inputs C' and S' for a next iteration.

Inventors: Agarwal; Ramesh Chandra (Yorktown Heights, NY); Fleischer; Bruce Martin (Mt. Kisco, NY); Gustavson; Fred Gehrung (Briarcliff Manor, NY)

Assignee: International Business Machines Corporation (Armonk, NY)

Application Number: 08/589,770

Issued: 1998-05-12

Expired: 2006-05-12

Classes: 708/523 ; 708/629

Field of search: 364/736,754,757,758,759,760,752,753,765

Click the image above to view patent images at uspto.gov within a frame.

Click here for the fulltext page on uspto.gov within a frame.