Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-12-27
2004-09-21
Malzahn, David H. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C340S146200
Reexamination Certificate
active
06795842
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to the field of digital signal processing involving computer arithmetic, and more specifically relates to a system and method for comparing two binary numbers with a power-of-two threshold.
BACKGROUND OF THE INVENTION
Binary comparators for comparing two or more binary numbers are well known in the art, as are methods for increasing the speed and efficiency of the comparison process. However, a more difficult problem is that of comparing two numbers with a threshold, namely, the result of the relation y<x+k, where x and y are two numbers to be compared and k is a threshold. A typical solution to this problem is to compute the sign of −y+x+k. One conventional approach to performing this sign computation has been to use a layer of full-adders in order to generate sum and carry_out signals (s and c, respectively) such that s+c=−y+x+k, followed by a fast carry generation scheme, such as carry-lookahead or carry-select, to generate the output carry of the addition s+c. This output carry is the result of the comparison. An implementation of this conventional scheme is illustrated in
FIGS. 1A through 1D
.
With reference to the overall conventional system block diagram shown in
FIG. 1D
, two n-bit binary numbers, x and y (in this case, n=8), are first pre-added with a power-of-two threshold, in this case a threshold of 16, by a conventional adder stage
102
(designated as “BOX A”). The details of the adder stage
102
are illustrated in
FIG. 1A
, wherein corresponding bits of the two input numbers x and y are connected to inputs “A” and “B” of a full adder circuit
110
and the threshold bit is connected to the carry_in input of the full adder
110
. The full adder circuit
110
generally includes at least one exclusive-OR gate, along with other logic gates, to generate sum and carry out outputs, s and c, respectively. The use of exclusive-OR gates adds significant cost and delay to the overall circuit and is thus not desirable. The sum and carry_out signals generated for each of the corresponding bits of the input numbers x and y are subsequently fed to n+1 kill-propagate (or generate-propagate) stages
104
(designated as “BOX B”). Each kill-propagate stage
104
receives as inputs a sum signal associated with a particular bit, b, and a carry_out signal associated with a preceding bit, b−1, of the input numbers. The details of the kill-propagate stage
104
are shown in
FIG. 1B
, wherein a generate output, g, is generated as a logical AND
112
of the two input signals and a kill or propagate signal, k, is generated as a logical OR
114
of the two input signals.
With continued reference to the conventional example of
FIG. 1D
, the generate and kill signals from the kill-propagate stages
104
are subsequently fed to a compare tree consisting of recursive kill-propagate stages
106
(designated as “BOX C”), the details of which are shown in FIG.
1
C. The number of generate and kill outputs are successively reduced at each level of recursive stages
106
, until a single output corresponding to the desired result y>x+16 is obtained.
An interesting special case occurs when the threshold in the comparison is a power of two (i.e., 2
k
). This case appears in the add-carry-select structure of a maximum-likelihood detector when the inputs have been properly scaled. The add-carry-select circuit is critically flawed, however, in the sense that it cannot be easily pipelined. Moreover, the extra addition required to initially reduce the three input numbers into two numbers is costly in terms of circuit complexity and speed, among other factors, since this topology requires three-input exclusive-OR (XOR) gates. In fact, approximately one third of the total propagation delay of the circuit can be attributed to the XOR gates employed in the conventional architecture.
There is a need, therefore, in the field of computer arithmetic involving the comparison of two binary numbers with a power-of-two threshold, to provide an architecture and method which avoids the extra level of addition, thereby eliminating the use of exclusive-OR logic gates, and which may be easily pipelined.
SUMMARY OF THE INVENTION
The present invention provides methods and apparatus for comparing two numbers having a power-of-two threshold, y>x+2
k
, that does not require the two numbers and the threshold to be pre-added. In this manner, the present invention eliminates the need for exclusive-OR (XOR) logic gates which are costly and add significant propagation delay to the overall circuit.
In one illustrative aspect of the invention, an architecture is provided which addresses the issue of comparing two binary numbers with a power-of-two threshold by employing a comparator circuit which provides an output signal corresponding to the relation y>x+2
k
. By defining new relations, namely, much_greater_than (gg
i
) and equal_to (nq
i
), based at least in part on generate (gt) and propagate (eq) signals created for each bit of the binary numbers to be compared, and by applying recursion in order to reduce the set of input signals at subsequent nodes or levels of recursion by a predetermined number, the XOR gates may be eliminated, thereby significantly reducing the overall cost of the circuit and essentially eliminating other disadvantages present in conventional methods and apparatus.
These and other objects, features and advantages of the present invention will become apparent from the following detailed description of illustrative embodiments thereof, which is to be read in connection with the accompanying drawings.
REFERENCES:
patent: 6114945 (2000-09-01), Houston
patent: 6470373 (2002-10-01), Moller
Dang Thu Ann
International Business Machines - Corporation
Malzahn David H.
Ryan & Mason & Lewis, LLP
LandOfFree
Method and apparatus for comparing two binary numbers with a... 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 apparatus for comparing two binary numbers with a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for comparing two binary numbers with a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3224045