Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-11-08
2003-04-15
Malzahn, David H. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06549927
ABSTRACT:
BACKGROUND
1. Field of the Present Invention
The present invention generally relates to the field of digital circuits and more particularly to a circuit for adding multiple vectors.
2. History of Related Art
In VLSI design, occasions frequently arise in which the sum of multiple binary vectors is required such as in the alignment of operands for multiply-add instructions. Frequently, the sum generated by such an operation is used to steer data. As processor speeds increase into and beyond 1 GHz, it becomes highly desirable to generate the necessary sum with a minimum of delay. Typically, however, adder circuits are designed for use with only a pair of input vectors. If the number of input vectors increases, a performance penalty is paid to incorporate the additional operands into the final result. In addition, these circuits typically implement multiple “vertical” levels of logic to generate a result. Each level of logic adds delay to the time required to generate a result. In addition, traditional adder circuits typically produce a binary encoded result that must be manipulated before it can be used as the select signal suitable for steering data. Therefore it would be highly desirable to implement a circuit for computing a multiple vector summation with a delay that does not increase significantly with the number of input vectors. Moreover, it would be desirable if the implemented solution generated a result that was suitable for use with a multiplexer or other selection circuitry.
SUMMARY OF THE INVENTION
The problems identified above are in large part addressed by a method and calculation circuit suitable for adding multiple binary vectors. The method includes receiving a set of input vectors and generating a set of decoded summation vectors. Each of the set of decoded summation vectors indicates the value of at least a portion of the vector sum. The method further includes generating a set of decoded carry vectors. Each carry vector is used to select the summation vector for an adjacent portion of the vector sum from a set of preliminary vectors. In one embodiment, the method further includes counting the number of high bits in each bit position of the input vectors and generating decoded high bit vectors based upon the counting to facilitate the generation of decoded summation vectors. In one embodiment, the set of preliminary vectors includes an initial preliminary summation vector. In another embodiment, the invention contemplates a method of adding multiple binary vectors in which a first decoded summation vector indicative of a first portion of a vector sum is generated and a first decoded carry vector indicative of the carry from a first portion of the vector sum is generated. An initial second decoded summation vector corresponding to a second portion of the vector sum is then generated and a set of preliminary summation vectors generated from the initial second summation vector. Each of the preliminary summation vectors is rotated by one bit position from adjacent vectors in the set of preliminary summation vectors. One of the set of preliminary summation vectors is then selected as the second summation vector based upon the value of the first carry vector. In one embodiment, the value indicated by the first carry vector indicates the number of times the selected second summation vector was rotated from the initial summation vector. The method may further include selecting a second carry vector from a set of preliminary second carry vectors with the first carry vector.
REFERENCES:
patent: 3603776 (1971-09-01), Weinberger
patent: 3636334 (1972-01-01), Svoboda
patent: 3675001 (1972-07-01), Singh
patent: 3723715 (1973-03-01), Chen et al.
patent: 5036483 (1991-07-01), Virtue
patent: 5097436 (1992-03-01), Zurawski
patent: 5471413 (1995-11-01), Sali et al.
Erle Mark Alan
Kelly Michael Robert
Emile Volel
Lally Joseph P.
Malzahn David H.
Tyson Tom
LandOfFree
Circuit and method for summing multiple binary vectors does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Circuit and method for summing multiple binary vectors, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Circuit and method for summing multiple binary vectors will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3052608