Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1998-12-07
2001-04-10
Mai, Tan V. (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S710000, C340S146200
Reexamination Certificate
active
06216147
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to digital computing, and more particularly to an apparatus and method for a magnitude comparator.
2. Description of the Related Art
An often-useful degenerate form of an adder is a magnitude comparator, which detects whether one number has a greater or lesser value than another. Comparators are particularly useful in bounds checking situations, where only a binary relationship between two numbers is necessary, since comparators are considerably less complex than full adders. Because a comparator does not utilize sum logic but rather comprises only carry chain logic, it is simpler in structure than a full adder. (An example of a full adder is set forth in co-pending application, U.S. Pat. App. Ser. No. 09/206,463, filed Dec. 7, 1998, and entitled “Method and Apparatus for 3-stage 32-bit Adder/Subtractor,” hereinafter referred to as “the 3-stage Adder Application.”)
Traditional Binary Addition
In most computer systems, addition and subtraction of numbers is supported. The present invention requires support of the subtraction function. The following discussion of addition sets the foundation for the subtraction discussion that follows.
In systems using traditional binary logic, the truth table for one-bit addition is set forth in Table 1.
TABLE 1
A
B
A + B
0
0
0
0
1
1
1
0
1
1
1
0*
In the last row of Table 1, a carry condition occurs. That is, the result is 0, but a carry into the next-higher-order bit position, corresponding to a decimal value of 2, has conceptually occurred.
In addition to single bits, the addition operation may be performed on multiple bits, including addition of two two-bit values. The truth table for such an operation is set forth in Table 2, where the first operand A is a two-bit value comprising bits A
0
and A
1
. The second operand, B, is a two-bit value comprising bits B
0
and B
1
.
TABLE 2
A =
B =
A + B =
Decimal
Decimal
Dec.
A
1
A
0
B
1
B
0
Value
Value
A + B
Value
0
0
0
0
0
0
00
0
0
0
0
1
0
1
01
1
0
0
1
0
0
2
10
2
0
0
1
1
0
3
11
3
0
1
0
0
1
0
01
1
0
1
0
1
1
1
10
2
0
1
1
0
1
2
11
3
0
1
1
1
1
3
00*
0
1
0
0
0
2
0
10
2
1
0
0
1
2
1
11
3
1
0
1
0
2
2
00*
0
1
0
1
1
2
3
01*
1
1
1
0
0
3
0
11
3
1
1
0
1
3
1
00*
0
1
1
1
0
3
2
01*
1
1
1
1
1
3
3
10*
2
Each output value in the “A+B” column of Table 2 indicated with an asterisk denotes a carry condition where a one has conceptually carried into the next-higher-order bit (the bit position corresponding to a decimal value of four).
N-nary Logic
The present invention utilizes N-NARY logic. The N-NARY logic family supports a variety of signal encodings, including 1-of-4. The N-NARY logic family is described in a copending patent application, U.S. patent application Ser. No. 09/019,355, filed Feb. 5, 1998, now U.S. Pat. No. 6,066,965, and titled “Method and Apparatus for a N-Nary logic Circuit Using 1-of-4 Encoding”, which is incorporated herein for all purposes and hereinafter referred to as “The N-NARY Patent.” In 1-of-4 encoding, four wires are used to indicate one of four possible values. In contrast, traditional static design uses two wires to indicate four values, as is demonstrated in Table 2. In Table 2, the A
0
and A
1
wires are used to indicate the four possible values for operand A: 00, 01, 10, and 11. The two B wires are similarly used to indicate the same four possible values for operand B. “Traditional” dual-rail dynamic logic also uses four wires to represent two bits, but the dual-rail scheme always requires two wires to be asserted. In contrast, N-NARY logic only requires assertion of one wire. The benefits of N-NARY logic over dual-rail logic, such as reduced power and reduced noise, should be apparent from a reading of The N-NARY Patent.
All signals in N-NARY logic, including 1-of-4, are of the 1-of-N form where N is any integer greater than one. A 1-of-4 signal requires four wires to encode four values (0-3 inclusive), or the equivalent of two bits of information. More than one wire will never be asserted for a 1-of-N signal. Similarly, N-NARY logic requires that a high voltage be asserted for all valid values, even 0. (Some versions of N-NARY logic allow a “null” case, where no high voltage is asserted for an N-NARY signal, which indicates that the N-NARY signal has not yet evaluated, and is not required).
Any one N-NARY gate may comprise multiple inputs and/or outputs. In such a case, a variety of different N-NARY encodings may be employed. For instance, consider a gate that comprises two inputs and two outputs, where the inputs are a 1-of-4 signal and a 1-of-2 signal and the outputs comprise a 1-of-4 signal and a 1-of-3 signal. Various variables, including P, Q, R, and S, may be used to describe the encoding for these inputs and outputs. One may say that one input comprises 1-of-P encoding and the other comprises 1-of-Q encoding, wherein P equals two and Q equals four. Similarly, the variables R and S may be used to describe the outputs. One might say that one output comprises 1-of-R encoding and the other output comprises 1-of-S encoding, wherein R equals four and S equals 3. Through the use of these, and other, additional variables, it is possible to describe multiple N-NARY signals that comprise a variety of different encodings.
SUMMARY OF THE INVENTION
The preferred embodiment of the present invention comprises a three-stage 32-bit magnitude comparator that receives as inputs two 32-bit 1-of-4 operands, A and B, and produces a 1-of-2 output. In the first level of logic, the Subtraction Logic, the first operand is subtracted from the second, and an HPG carry propagate indicator is generated for each dit of the difference between the two operands. In the second level of logic, the Block HPG Logic, an HPG carry propagate signal is generated for each five-dit block of the difference between the two operands. In the third level of logic, the Comparison Logic, a 1-of-2 carry out indicator is generated to indicate whether the subtraction of A operand from the B operand has generated a carry.
REFERENCES:
patent: 4163211 (1979-07-01), Miura
patent: 5463571 (1995-10-01), Kim et al.
patent: 5463572 (1995-10-01), Kim et al.
Blomgren James S.
Petro Anthony M.
Booth Matthew J.
Booth & Wright, L.L.P.
Intrinsity, Inc.
Mai Tan V.
LandOfFree
Method and apparatus for an N-nary magnitude comparator 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 an N-nary magnitude comparator, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for an N-nary magnitude comparator will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2545957