Circuit and method for summing multiple binary vectors

Abstract

A method and circuit for summing multiples vectors is disclosed. 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 summation 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 count 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 and a set of adjacent summation vectors. In this embodiment each adjacent summation vector is achieved with a 1-bit rotation of the preceding adjacent 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 the 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.

Dependencies are inferred from the claim text.