Method and apparatus for an N-NARY HPG gate

The present invention discloses an apparatus and method for performing carry propagate logic on two 1-of-4 two-bit addends to produce a 1-of-3 carry propagate indicator. The preferred embodiment of the present invention will set an H indicator for a given dit n if the sum of A.sub.n and B.sub.n is less than or equal to two, will set a P indicator if the sum is three, and will set a G indicator if the sum is greater than three.

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-lookahead circuitry
 using 1-of-N logic.
 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.sub.0 and A.sub.1. The second
 operand, B, is a two-bit value comprising bits B.sub.0 and B.sub.1.
 TABLE 2
 A = B = A + B =
 Decimal Decimal Dec.
 A.sub.1 A.sub.0 B.sub.1 B.sub.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.sub.0 and A.sub.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 performing
 carry propagate logic on two 1 -of-N addends to produce a 1 -of-N carry
 propagate indicator. The invention comprises an HPG circuit that receives
 two addends and performs logic to determine whether a (P)ropagate, (H)alt,
 or (G)enerate signal should be set. In the preferred embodiment, the two
 addends and the sum comprise two-bit 1 -of-4 logic signals, and the HPG
 signal comprises a 1 -of-3 logic signal. The preferred embodiment of the
 present invention will set an H indicator for a given dit n if the sum of
 A.sub.n and B.sub.n is less than or equal to two, will set a P indicator
 if the sum is three, and will set a G indicator if the sum is greater than
 three.

DETAILED DESCRIPTION OF THE INVENTION
 The present invention relates to a Halt-Propagate-Generate (HPG) gate using
 N-NARY logic. This disclosure describes numerous specific details that
 include specific formats, structures, circuits, and logic functions in
 order to provide a thorough understanding of the present invention. One
 skilled in the art will appreciate that one may practice the present
 invention without these specific details. Additionally, this disclosure
 does not describe in detail some well-known structures such as N-FETs,
 P-FETs, nor does it describe N-NARY logic in detail, in order not to
 obscure the present invention.
 A truth table demonstrating the add operation using 1 -of-4 encoding is set
 forth in Table 3. Each of the inputs A and B in Table 3 is a two-bit input
 that can represent one of four values, 0 through 3 inclusive, depending on
 which of the four wires for each signal is set high. Table 3 discards any
 potential input value that includes more than one wire asserted for each 1
 -of-4 signal, such as 1111 and 0101. Such values are undefined for the
 evaluate stage of 1 -of-4 logic gates. The four wires for the two-bit sum
 of the 1-of-4 addition operation in Table 3 are labeled S.sub.3, S.sub.2,
 S.sub.1, and S.sub.0.
 TABLE 3
 A B
 Output
 Dec. Dec.
 Decimal
 A.sub.3 A.sub.2 A.sub.1 A.sub.0 Value B.sub.3 B.sub.2 B.sub.1
 B.sub.0 Value S.sub.3 S.sub.2 S.sub.1 S.sub.0 Value
 0 0 0 1 0 0 0 0 1 0 0 0 0
 1 0
 0 0 0 1 0 0 0 1 0 1 0 0 1
 0 1
 0 0 0 1 0 0 1 0 0 2 0 1 0
 0 2
 0 0 0 1 0 1 0 0 0 3 1 0 0
 0 3
 0 0 1 0 1 0 0 0 1 0 0 0 1
 0 1
 0 0 1 0 1 0 0 1 0 1 0 1 0
 0 2
 0 0 1 0 1 0 1 0 0 2 1 0 0
 0 3
 0 0 1 0 1 1 0 0 0 3 0 0 0
 1 0*
 0 1 0 0 2 0 0 0 1 0 0 1 0
 0 2
 0 1 0 0 2 0 0 1 0 1 1 0 0
 0 3
 0 1 0 0 2 0 1 0 0 2 0 0 0
 1 0*
 0 1 0 0 2 1 0 0 0 3 0 0 1
 0 1*
 1 0 0 0 3 0 0 0 1 0 1 0 0
 0 3
 1 0 0 0 3 0 0 1 0 1 0 0 0
 1 0*
 1 0 0 0 3 0 1 0 0 2 0 0 1
 0 1*
 1 0 0 0 3 1 0 0 0 3 0 1 0
 0 2*
 In Table 3, output values with asterisks indicate that a carry is
 conceptually generated into a higher-order bit representing a decimal
 value of 4.
 N-NARY Logic Circuits
 A background discussion of N-NARY circuits is in order before discussing
 the HPG gate of the present invention. N-NARY logic may be used to create
 circuits to perform a desired function. The present invention utilizes
 N-NARY logic. FIG. 1 illustrates a 1-of-N logic gate 60 that uses two sets
 of 1-of-N signals for the inputs and produces one 1 -of-N signal for the
 output. In gate 60, the A and B inputs comprise four wires each, with each
 set of wires representing 2 bits (one dit) of data. A is a one-dit input,
 B is a one-dit input, and O is a one-dit output. In other words, the
 N-NARY gate 60 depicted in FIG. 1 comprises 4 input bits (2 dits) and 2
 output bits (one dit).
 Referring to FIG. 1, each N-NARY dit logic circuit 60 comprises a logic
 tree circuit 61, a precharge circuit 31, and an evaluate circuit 36. The
 logic tree circuit 61 performs a logic function on the two 1 -of-4 input
 signals that could comprise a variety of functions, for example, the
 Boolean logic functions AND/NAND and OR/NOR, or the more complex
 carry-lookahead function of the present invention. The logic gates of the
 N-NARY family are clocked pre-charge (CP) gates. FIG. 2 illustrates that
 each input into the logic tree circuit 61 is coupled to at least one
 single N-channel field effect transistor (NFET) A.sub.0 -A.sub.3, B.sub.0
 -B.sub.3. Referring back to FIG. 1, the logic tree circuit 61 therefore
 comprises one or more N-channel FETS. Coupled to the wires of the 1 -of-4
 output signal are the output buffers 34 that aid in driving additional
 circuits that couple to the output signal. The preferred embodiment of the
 present invention uses a circuit with an inverting function as the output
 buffer 34.
 Referring again to FIG. 1, a precharge circuit 31 couples to the logic tree
 circuit 61 and precharges the dynamic logic of the logic tree circuit 61.
 The precharge circuit 31 comprises one or more FETs with the preferred
 embodiment of the circuit comprising P-channel FETs (PFETs). Each
 evaluation path of the logic tree circuit 61 has its own precharge PFET,
 shown as 500 in FIG. 2. The PFETs 500 of the precharge circuit 31 quickly
 and fully precharge all of the dynamic logic in the logic tree circuit 61
 during the precharge phase of the clock cycle.
 FIG. 2 is a diagram of an N-NARY adder gate. FIG. 2 illustrates that the
 precharge PFET 500 for an evaluation node E of an N-NARY circuit is
 connected to positive high voltage, Vcc, and is used to create conductive
 paths between the evaluation node E and Vcc. Each precharge PFET 500 is
 coupled to an input, the pre-charge signal. When the pre-charge signal for
 any evaluate node has a low voltage, then there is a conductive path
 between Vcc and the evaluation node E. Coupled to the precharge circuit 31
 is the clock signal CK. A low clock signal on CK will cause the FETs in
 the logic tree circuit 32 to charge when using P-channel FETs in the
 precharge circuit 31.
 An evaluate circuit 36 couples to the logic tree circuit 61 and controls
 the evaluation of the logic tree circuit 61. The evaluate circuit 36
 comprises one or more FETs connected to the CK signal, with the preferred
 embodiment of the evaluate circuit comprising a single N-channel FET. The
 single N-FET acts as an evaluation transistor that is used to control when
 the gate is sensitive to inputs, helps avoid races between other devices,
 and prevents excessive power consumption. During the precharge phase, the
 evaluate circuit 36 receives a low value so that no path to Vss may exist
 through the NFET(s) of the logic tree circuit 61. During the evaluate
 phase, the evaluate circuit 36 receives a high signal so that a path to
 Vss through the NFET(s) of the logic tree circuit 61 may exist. Coupled to
 the evaluate circuit 36 is the clock signal CK. A high clock signal on CK
 will cause the FETs in the logic tree circuit 61 to evaluate when using
 N-channel FETs in the evaluate circuit 36. In other words, when the clock
 signal is high, the evaluate circuit 36 evaluates the logic tree circuit
 61.
 An evaluate node, E, which comprises the four wires E.sub.0, E.sub.1,
 E.sub.2, and E.sub.3, is the signal pathway between the logic tree circuit
 61 and an output buffer 34, and constitutes an evaluation path of the
 logic tree circuit 61. As stated earlier, each evaluation node wire
 E.sub.0, E.sub.1, E.sub.2, and E.sub.3 has its own precharge PFET. The
 signal on a particular wire, E.sub.0, E.sub.1, E.sub.2, E.sub.3 of the
 evaluate node E is high, only when there is no connection to Vss through
 the logic tree circuit 61 NFET(s) associated with that particular wire. If
 the pre-charge signal is low at time 0, and there is no path to ground
 through the NFET(s) associated with an evaluate node E, of the logic tree
 circuit 61, then the evaluate node wire E gets pulled to a high voltage.
 This is called the precharge phase of the gate and we may also say that
 the gate is in precharge mode. If the precharge signal switches to a high
 voltage at a later time, the evaluate node E will be floating but the
 charge left on it will leave the voltage high. This is called the evaluate
 phase of the gate, and we may also say that the gate is in evaluate mode.
 If input signals generate a high voltage for any NFET(s) in the logic tree
 circuit 61 such that a path from the evaluate node E to ground (Vss)
 exists, then the charge on the evaluate node E will drain to ground, and
 the evaluate voltage will drop to Vss. If no such path exists, then the
 evaluate node E will remain at Vcc. When any gate, therefore, switches
 from precharge mode to evaluate mode, the evaluate node voltage is high,
 and it either stays high or goes low. Once the evaluate node voltage goes
 low during the evaluate phase, it cannot be driven high again until the
 next precharge phase.
 Each evaluate node wire E.sub.0, E.sub.1, E.sub.2, and E.sub.3 couples to
 an output buffer 34. Two embodiments of the output driver circuit 600
 comprising output buffer 34 are illustrated in FIGS. 3 and 4. FIG. 3
 illustrates a half keeper output driver circuit 602 that comprises an
 inverter 620 and a PFET device 640. FIG. 4 illustrates a full keeper
 output driver circuit 601 that comprises an inverter 610 coupled to a PFET
 device 630 and an NFET device 650. Full keeper output driver circuits 601
 are only necessary for gates that can be in neither evaluate nor precharge
 mode for lengthy periods. The flow through the output driver circuit 600
 is from evaluate node E to the output signal path O. The inverter 610, 620
 of the output driver circuit 600 is necessary because the evaluate nodes
 of CP gates of the N-NARY logic family precharge to a high value and
 evaluate to a low value. The output driver circuit 34, holds the value
 during an evaluate phase if the evaluate node E has not discharged. If the
 evaluate node E has discharged, then there is a path to ground holding its
 value low. The output of each evaluate node E will switch from low to high
 once, at most, during an evaluate phase. The output of each evaluate node
 E, once coupled to an output driver circuit 600 of output buffer 34, is
 therefore suitable for feeding a subsequent CP gate.
 A shorthand notation for circuit diagrams can be adopted to avoid needless
 repetition of elements common to all N-NARY circuits. FIG. 2 illustrates
 these common elements. One common element is the pre-charge P-FET 500.
 Precharge P-FETs 500 are required for each evaluate node E in every 1
 -of-N gate since a single precharge PFET 500 would short each evaluate
 node E relative to the other evaluate nodes. Since all N-NARY gates
 require a pre-charge P-FET 500 for each evaluate node E, the pre-charge
 P-FETs 500 may be implied and need not be shown. The same is true for the
 N-FET associated with each input wire of the A and B inputs. Similarly,
 each evaluate node E must have its own output buffer 34, which may be
 implied. The N-FET associated with the evaluate node 36 may also be
 implied. Since these features are common to all N-NARY circuits, we may
 use the shorthand shown in FIG. 5 to represent the N-NARY circuits.
 Accordingly, FIG. 5 illustrates a shorthand notation of the adder gate
 depicted in FIG. 2. This shorthand notation is used in FIGS. 5, 7, and 7A.
 In each figure, the elements discussed herein should be implied
 accordingly.
 A further simplification to the representation of the FIG. 2 adder is shown
 in FIG. 6, where the inputs and outputs are shown as single signals that
 each can represent one of four signals and each impliedly comprises four
 wires. The number "4" shown within the add gate of FIG. 6, adjacent to the
 connections, indicates that each signal can represent one of four values.
 The number above the gate indicates the number of transistors in the
 evaluate stack, and the number below the FIG. 6 gate represents the
 maximum number of transistors in series between the evaluate node and
 virtual ground. In FIG. 6, the elements discussed herein should be implied
 accordingly.
 Carry Propagate Logic
 The asterisks of Table 3 illustrates that additional logic is required in
 order to determine whether the sum of two one-dit addends is too large to
 represent in two bits of information. In such cases, a carry out condition
 is present. What is required is a gate that can utilize carry-propagate
 techniques to account for carry conditions. This is accomplished through
 the use of carry propagate logic, as described below.
 Carry propagate logic takes carry conditions into account. For any two
 binary numbers A and B, the sum, S.sub.n, and the carry, C.sub.n, for a
 given bit position, n, are:
EQU S.sub.n =A.sub.n.sym.B.sub.n.sym.C.sub.n-1, where C.sub.n-1 is the carry in
 from the previous bit, n-1. (1)
EQU C.sub.n =A.sub.n B.sub.n.vertline.A.sub.n C.sub.n-1.vertline.B.sub.n
 C.sub.n-1, where C.sub.n is the carry out from bit n. (2)
 The truth tables for Equation 1 and Equation 2 are set forth in Table 4.
 TABLE 4
 A.sub.n B.sub.n A.sub.n C.sub.n-1 B.sub.n C.sub.n-1
 A.sub.n .sym. B.sub.n S.sub.n = (4) .sym. C.sub.n =
 A.sub.n B.sub.n C.sub.n-1 (1) (2) (3) (4)
 C.sub.n-1 (1).vertline.(2).vertline.(3)
 0 0 0 0 0 0 0 0 0
 0 0 1 0 0 0 0 1 0
 0 1 0 0 0 0 1 1 0
 0 1 1 0 0 1 1 0 1
 1 0 0 0 0 0 1 1 0
 1 0 1 0 1 0 1 0 1
 1 1 0 1 0 0 0 0 1
 1 1 1 1 1 1 0 1 1
 In formulating carry propagate logic, one must recognize that the critical
 path in any adder is along the carry chain. The most significant bit of
 the sum depends not only on the two most significant addend bits, but also
 the addend bits of every other bit position via the carry chain. Simply
 allowing carries to ripple from the least significant end would result in
 a compact but very slow adder, since the worst-case carry propagation
 delay would be approximately as many gate delays as the bit width of the
 adder.
 Fast carry-propagate techniques can dramatically decrease the carry
 propagation delay, and therefore decrease the overall delay of the adder.
 Adders employing such techniques are sometimes referred to as
 carry-lookahead adders, or CLAs. Conventional carry propagate adder
 structures speed up the carry chain by computing the individual carry
 propagate (P) and carry generate (G) signals for each bit position.
 For any two binary numbers A and B, the P and G signals for a given bit
 position, n, are:
EQU P.sub.n =A.sub.n.sym.B.sub.n (3)
EQU G.sub.n =A.sub.n B.sub.n (4)
 P and G may also be generated for 1 -of-4 numbers. G indicates that the
 given dit position, n, generates a carry that will have to be accounted
 for in the higher dits of the sum. G will be set when the sum of two
 1-of-4 numbers is greater than 3. P indicates that any carry generated in
 lower dits will propagate across the given dit position, n, to affect the
 higher dits of the sum. P will be set when the sum of two 1-of-4 numbers
 is exactly three. If neither G nor P is true for a given dit position,
 then a carry halt signal (H) is implied. An H signal indicates that any
 carry generated in lower dits will not propagate across the given bit
 position, n. H will be set if the sum of two 1-of-4 numbers is less than
 three. Restated, if the sum of two operand dits in a given dit position is
 greater than 3, G is true. If the sum is exactly 3, P is true. Otherwise,
 H is true.
 FIG. 7 illustrates an N-NARY HPG gate 700 that utilizes carry propagate
 logic to generate an H, P, or G indication for two 1-of-4 addends. A
 similar function may be performed with one 1-of-3 addend and one 1-of-5
 addend. An illustration of such a gate 701 is shown in FIG. 7A.
 The output of the HPG gate 700 conforms to Table 5. The output of the FIG.
 7 gate is a 1-of-3 N-NARY signal, such that one, and only one, of the H,
 P, or G wires is set high during a given evaluate cycle. The H, P, and G
 outputs represent the three wires for a 1-of-3 output.
 TABLE 5
 A Dec. B Dec.
 A.sub.3 A.sub.2 A.sub.1 A.sub.0 Value B.sub.3 B.sub.2 B.sub.1
 B.sub.0 Value P.sub.n G.sub.n H.sub.n
 0 0 0 1 0 0 0 0 1 0 0 0 1
 0 0 0 1 0 0 0 1 0 1 0 0 1
 0 0 0 1 0 0 1 0 0 2 0 0 1
 0 0 0 1 0 1 0 0 0 3 1 0 0
 0 0 1 0 1 0 0 0 1 0 0 0 1
 0 0 1 0 1 0 0 1 0 1 0 0 1
 0 0 1 0 1 0 1 0 0 2 1 0 0
 0 0 1 0 1 1 0 0 0 3 0 1 0
 0 1 0 0 2 0 0 0 1 0 0 0 1
 0 1 0 0 2 0 0 1 0 1 1 0 0
 0 1 0 0 2 0 1 0 0 2 0 1 0
 0 1 0 0 2 1 0 0 0 3 0 1 0
 1 0 0 0 3 0 0 0 1 0 1 0 0
 1 0 0 0 3 0 0 1 0 1 0 1 0
 1 0 0 0 3 0 1 0 0 2 0 1 0
 1 0 0 0 3 1 0 0 0 3 0 1 0
 FIG. 7 illustrates the HALT output is set high when the sum of two 1-of-4
 addends equals 0, 1, or 2. The PROP output is pulled high if the sum of
 the addends is 3. Finally, the GEN output is pulled high when the sum of
 the two addends equals 4, 5, or 6.
 In sum, the preferred embodiment of the present invention utilizes 1-of-N
 logic to implement a method and apparatus that perform carry propagate
 logic on two 1-of-N addends to produce a 1-of-3 HPG indicator that pulls
 the HALT wire high if the sum of the two addends is less than three, pulls
 the PROP wire high if the sum of the two addends is equal to three, and
 pulls the GEN wire high if the sum of the two addends is greater than
 three.
 Other embodiments of the invention will be apparent to those skilled in the
 art after considering this specification or practicing the disclosed
 invention. The specification and examples above are exemplary only, with
 the true scope of the invention being indicated by the following claims.