Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1998-09-10
2001-04-17
Ngo, Chuong Dinh (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S493000
Reexamination Certificate
active
06219687
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 implementing carry-look-ahead logic in an N-NARY adder gate.
2. Description of the Related Art
Traditional Binary Addition
In most computer systems, addition and subtraction of numbers is supported. 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 value in 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 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 is 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 values, even 0. As illustrated in this specification and more thoroughly discussed in the N-NARY Patent, a 1 of N signal is used to convey multiple values of information in an integrated circuit. The 1 of N signal can convey information to and from an N-NARY logic circuit where an N-NARY logic circuit comprises a shared logic tree circuit that evaluates one or more 1 of N input signals and produces a 1 of N output signal. A single 1 of N signal comprises a bundle of N wires routed together between different cells (or different logic circuits) within a semiconductor device. A 1 of N signal uses a 1 of N encoding to indicate multiple values of information conveyed by the bundle of wires of the 1 of N signal where at most one and only one wire of the bundle of wires of the 1 of N signal is true during an evaluation cycle. The present invention further provides that the bundle of N wires may comprise a number of wires from the following group: a bundle of 3 wires, a bundle of 4 wires, a bundle of 8 wires, or a bundle of N wires. Additionally, the present invention may comprise a not valid value where zero wires of the bundle of N wires is active. Further, the present invention provides that the 1 of N encoding on the bundle of N wires cooperatively operate to reduce the power consumption in the integrated circuit according to the number of wires in the bundle of N wires evaluating per bit of encoded information.
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 present invention discloses an apparatus and method for adding two 1-of-4 inputs to produce a 1-of-4 sum, and also for performing carry propagate logic on the two inputs to produce a 1-of-3 Halt-Propagate-Generate (HPG) indicator. In an alternative embodiment, the HPG indicator is a 1-of-2 signal wherein the Halt and Propagate signals are combined.
REFERENCES:
patent: 4914614 (1990-04-01), Yamakawa
patent: 5208490 (1993-05-01), Yetter
patent: 5467298 (1995-11-01), Yoshida
patent: 5499203 (1996-03-01), Grundland
patent: 6003059 (1999-12-01), Bechade
Blomgren James S.
Petro Anthony M.
Booth Matthew J.
Booth & Wright, L.L.P.
Intrinsity, Inc.
Ngo Chuong Dinh
LandOfFree
Method and apparatus for an N-nary Sum/HPG gate 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 Sum/HPG gate, 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 Sum/HPG gate will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2546181