Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-11-30
2004-09-21
Mai, Tan V. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06795839
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates in general to digital computing and communication systems, and more particularly to a method for counting the number of ones in a word such as for processing communication packets of information.
2. Description of Related Art
Modern computing systems typically operate using a binary counting system where numbers are represented by a string of ones and/or zeros. Communication systems, such as used in networks, the Internet, and wireless communication, to name just a few, process information that is typically organized as data packets. Devices in a communication system, such as network routers, repeaters, and relay stations, normally must quickly analyze received data packets to classify the data packets to determine further processing requirements and a further destination to send the data packets. This packet classification process is often a complex task that has to be performed at nearly the speed of the communication data packets to maintain a throughput in a communication system. In a very high speed communication system, for example such as the Internet, the data packets may be processed at up to 30 million packets per second. A bit rate of 10 gigabits per second is not uncommon in processing data packets in such a network.
Accordingly, it is imperative that any operation on the bits of any data packet in such a high speed communication system must be very fast and efficient to keep up with the communication bit rate for such data packets. One common operation comprises bit counting. That is, for example, as part of classifying data packets a computing system commonly has to count bits in a data packet. The speed of bit counting must be kept to nearly the bit rate of the communication of the data packets to minimize the impact of the counting operation on the speed of communication of the data packets across the network.
A typical software based implementation for counting bits may include nested loops of software that include shifting data words in registers, adding registers, testing registers, and branch instructions. For a given 32 bit word length, for example, the total number of processor cycles may approach a multiple of three (3) times the number of bits in the word. For example, for a 32 bit word the counting may require up to three (3) times thirty-two (32) processor cycles. This is a significant time delay that in many high speed communication systems, such as for an IP router, would be unacceptable.
Thus, there is a need to overcome the disadvantages of the prior art, such as discussed above, and in particular to improve the processing speed of bit counting circuits in computing systems such as required by high speed communication of data packets.
REFERENCES:
patent: 4989168 (1991-01-01), Kuroda et al.
patent: 5541865 (1996-07-01), Ashkenazi
patent: 5717616 (1998-02-01), Morris
patent: 6070237 (2000-05-01), Peleg et al.
Karim Faraydon O.
Mellan Alain
Bongini Stephen
Jorgenson Lisa K.
Mai Tan V.
STMicroelectronics Inc.
LandOfFree
Method and device for computing the number of bits set to... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and device for computing the number of bits set to..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and device for computing the number of bits set to... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3212637