4-Bit population count circuit

Details 4-Bit population count circuit 4-Bit population count circuit

2000-10-24

2002-08-06

Lam, Tuan T. (Department: 2816)

Electrical pulse counters, pulse dividers, or shift registers: c

Pulse counting or dividing chains

Using bistable semiconductors having at least three...

C708S210000

Reexamination Certificate

active

06430251

ABSTRACT:

TECHNICAL FIELD OF THE INVENTION
The present invention generally relates to semiconductor devices and more particularly, to an electronic counter for counting the number of set bits in a vector.
BACKGROUND OF THE INVENTION
In a microprocessor architecture that focuses on rapid and efficient processing of a relatively small set of simple instructions, such as a Reduced Instruction Set Computing (RISC) Architecture, it is often useful to determine the number of set bits in an input vector, namely, how many bits have a value of “1.” Knowing the number of set bits in a vector allows a RISC microprocessor to bypass instructions or data in a register that does not have the required number of set bits. Consequently, the number of clock cycles necessary to process a fetch operation may be reduced.
Classically, a population count of set bits in a vector requires at least three full gate delays before a count is asserted. Although current microprocessor clock rates help to mitigate any loss of processing efficiency caused by a population count taking at least three full gate delays, the ultimate goal of any RISC microprocessor architecture is to optimize each and every instruction so that it can be completed within a single clock cycle. The burden of additional propagation delay in a counter circuit results in a RISC microprocessor design and architecture that is not optimized to carry out instructions in the least number of clock cycles possible.
SUMMARY OF THE INVENTION
The present invention addresses the above-described limitations of conventional population bit counter circuits that require at least three full gate delays to assert a count. The present invention provides an approach to enable an electronic population counter to assert a count of an input vector in less than three full gate delays.
In one embodiment of the present invention, a counter circuit is provided having a dynamic counting circuit adapted to count the number of set least significant bits in an input vector, and a second static counter circuit adapted to count the number of set most significant bits in the input vector. Further, the counter circuit provides an array of pass gates to combine the count of the dynamic counting circuit and the count of the static counting circuit and to assert a count of set bits in the input array.
The above-described approach benefits the RISC architecture of a microprocessor in that a population count of an input vector may be performed in less than three full gate delays. As a result, the RISC microprocessor may perform a population count instruction in a more efficient manner, thus decreasing required processing time.
In accordance with another aspect of the present invention, a method is performed in an electronic counter for counting a number of set bits in an input vector. The counter performs a count of the set least significant bits in the input array using dynamic logic components and performs a count of the set most significant bits in the input vector using static logic gates. The static logic elements assert a count to an array of pass transistors before the dynamic logic elements assert their count to the array of pass transistors. As a result, a count corresponding to the number of set bits in an input vector is asserted in less than three full gate delays.


REFERENCES:
patent: 3711692 (1973-01-01), Batcher
patent: 4189716 (1980-02-01), Krambeck
patent: 5541865 (1996-07-01), Ashkenazi

Affiliated with

Also associated with

Rating

4-Bit population count circuit does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with 4-Bit population count circuit, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and 4-Bit population count circuit will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2916838