Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-06-01
2004-08-03
Ingberg, Todd (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S160000
Reexamination Certificate
active
06772187
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to digital logic circuitry. More particularly, the present invention relates to an apparatus and method for determining whether one number is greater than another number or whether they are equal.
2. The Prior Art
A frequent requirement of computer applications is to determine whether one number is greater than or equal to another number. Determining whether one number is greater than another number or equal to that number has been accomplished in the past by rudimentary methods. However, as microprocessors become faster and circuitry becomes more complex, a need exists to accomplish tasks such as this as quickly and efficiently as possible.
The conventional way of comparing two numbers to determine if the first is greater than the second is to subtract the second from the first, and then examine the result as depicted in FIG.
1
. Essentially, a first number A and a second number B are input into a subtractor. An output Z (where Z=A−B) is obtained and an analyzer circuit determines whether A is greater than or equal to B based on whether Z is positive, negative, or zero. A truth table for such a method is provided at Table 1.
TABLE 1
Z
RESULT
+
A > B
−
B > A
0
A = B
The problem with a system such as that depicted in FIG.
1
and Table 1 is that subtractors are notoriously slow, and the problem is compounded as the numbers A and B become larger in value. Though this method obtains desired results, it is merely a brute force method, and thus, gives up speed and processor efficiency for its crude simplicity.
Another method of comparing two numbers is to use a TTL comparator. For example, a four-bit magnitude comparator such as the 5485/7485 series performs comparison of straight binary and straight BCD (8-4-2-1) codes. As described in The TTL Data Book, Texas Instruments, Inc., 1976, p. 7-57, “Three fully decoded decisions about 4-bit words (A, B) are made and are externally available at three outputs. These devices are fully expandable to any number of bits without external gates. Words of greater length may be compared by connecting comparators in cascade. The A>B, A<B, and A=B outputs of a stage handling less significant bits are connected to the corresponding A>B, A<B, and A=B inputs of the next stage handling more-significant bits. The stage handling the least-significant bits must have a high-level voltage applied to the A=B input in addition for the ′L85, low level voltages applied to the A>B and A<B inputs.” While this method may be able to perform the task for words of greater length than 4 bits, unless the top set of 4 bits is the significant bit set, this method is slow because it analyzes each lower set of bits in order.
BRIEF DESCRIPTION OF THE INVENTION
To overcome these and other shortcomings of the prior art, disclosed herein is a system for determining whether a first number is greater than or equal to a second number. Generally, this system compares each bit pair simultaneously.
For each set of four bit pairs (or pairs of nibbles related to each number), the hardware determines: if any of the bit pairs within the nibble do not match (either a=1, b=0, or a=0, b=1) a “nibble not equal” or NNE output is indicated; for the highest mismatching bit pair within the nibble, whether the bit corresponding to the first number A is equal to one (1). Hence, if a nibble not equal is indicated, and A is equal to one, then logically A is greater than B, an outcome sought by this analysis. The results of the nibble's NNE are fed into a priority encoder. The results of each nibbles A greater than B determination are fed into a multiplexer. The output of the priority encoder selects which of the multiplexer inputs to output (the highest order A greater than B nibble result). The output of the multiplexer is the “greater than” result from the highest level (in the bit string) mismatched nibbles. This indicates whether the number A is greater than B. Additionally, the nibbles' NNEs can be NORed together to determine if the two numbers are equal. Thus, allowing for at least the determination of “A greater than B” (A>B), “A greater than or equal to B” (A≧B), “A equal to B” (A=B), “A less than B” (A<B), and “A less than or equal to B” (A≦B).
More particularly, Two bit string numbers may be divided into a plurality of nibbles (smaller bit strings) and each nibble analyzed to determine whether the contents of one number's nibble is greater than or equal to the comparable nibble in the other number. By utilizing such a scheme and employing digital logic devices, all nibbles of a plurality of bits may be compared simultaneously and system performance enhancements may be obtained thereby.
For instance, each bit within comparable nibbles of two numbers are input into nibble logic gate arrays simultaneously; the results indicating whether the nibble includes unequal values and whether one nibble input is greater than the other nibble input for each nibble pair. The results obtained thereby are simultaneously fed into a priority encoder, a multiplexer, and a NOR gate as follows. Values corresponding to whether the comparable nibbles are unequal are fed into the priority encoder to determine which highest level nibble pairs include unequal values. The priority encoder output then becomes the select line for the multiplexer. The multiplexer, then, has as its input the “greater than” nibble results for each nibble. The multiplexer output, thus, will indicate whether a first number is greater than a second number.
On the other hand, and simultaneously with the above, the same results from the nibble logic that are fed into the priority encoder are fed into the NOR gate. If all of the nibbles indicate that they are not unequal, then the resulting output for this element will indicate that the numbers are equal.
By utilizing digital logic and analyzing small (nibble) size pieces of the numbers, processing time is minimized and processing resources are optimized. As will be understood by the detailed disclosure below, although an application to 32 bit numbers having eight 4 bit nibbles is discussed, the same logic may be applied to any bit-length number having any logical number of bits within a nibble.
REFERENCES:
patent: 4441165 (1984-04-01), Coleman et al.
patent: 4998219 (1991-03-01), Frauenglass
patent: 5010508 (1991-04-01), Sit et al.
patent: 5289156 (1994-02-01), Ganmukhi
patent: 5630160 (1997-05-01), Simpson et al.
patent: 5905428 (1999-05-01), Bechade
patent: 6018756 (2000-01-01), Wolrich et al.
Chng Choon Ping
Ott Michael L.
Tzeng Tzungren Allen
Do Chat C
Ingberg Todd
Martine & Penilla LLP
Sun Microsystems Inc.
LandOfFree
Parallel greater than analysis method and apparatus does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Parallel greater than analysis method and apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parallel greater than analysis method and apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3342574