Fast Ternary Addition

Abstract

Unsigned and 3's-complement ternary arithmetic uses the values 0, 1, and 2 for each digit, while in balanced ternary uses –1, 0 and +1. Balanced ternary is equivalent to biased unsigned ternary, with a bias of half the range. The implementations of ternary arithmetic are presented here, follow the conventional sequence used in presenting binary arithmetic, working up from a half adder to a full adder, and from there to an ALU and carry-lookahead logic. Carry-lookahead logic for balanced ternary is significantly more complex than for unsigned ternary; as with other number bases, an unsigned ternary adder also computes a three's complement sum.

1. Ternary Number Representations
2. Increment, Decrement and the Half Adder
   1. Unsigned and 3's-Complement Half Adder
   2. Balanced Half Adder
3. Addition and the Full Adder
   1. Unsigned and 3's Complement Full Adder
   2. Balanced Full Adder
4. Comparison
   1. Comparison with Zero
   2. Comparing Two Numbers
5. Carry Lookahead
   1. Increment
   2. Add
6. Conclusion

1. Ternary Number Representations

In Kleene logic, we speak of logical variables having the values true and false and unknown [Fitting, 1994]. When encoding numbers using ternary logic, we ignore the conventional meanings of these three symbols and simply assign numeric values that conform to the ordering implicit in Kleene logic. Given our interest in supporting numbers in base-3, there are two useful encodings:

ternary encoding of base-3 digits

truth value	unsigned	balanced
false	0	–
unknown	1	0
true	2	+

The first encoding given above is used in representing unsigned base-3 numbers. This encoding corresponds closely to the familiar encoding used for decimal and binary numbers, with digit values ranging from zero to one less than the radix. Counting proceeds naturally in unsigned ternary: 0, 1, 2, 10, 11, 12, 20, 21, 22 and so on, corresponding to the decimal numbers from zero to 8.

In contrast, balanced ternary numbers use the digit values –1, 0 and +1, represented more compactly as -, 0 and + when writing out numbers. In this system, counting proceeds as follows: 0, +, +-, +0, ++, +--, +-0, +-+, +0-, etc, corresponding to the decimal numbers from zero to 8. The number +-0 has +1 in the 9's place, –1 in the 3's place and 0 in the 1's place, so the value is 9–3 or 6. This may seem unnatural at first, but it allows convenient representation of signed numbers. The following table shows all 3-trit (3 ternary digit) numbers in balanced, unsigned and 3's-complement form:

All 3-trit numbers

Bal	-13	-12	-11	-10	-9	-8	-7	-6	-5	-4	-3	-2	-1	0	1	2	3	4	5	6	7	8	9	10	11	12	13
	---	--0	--+	-0-	-00	-0+	-+-	-+0	-++	0--	0-0	0-+	00-	000	00+	0+-	0+0	0++	+--	+-0	+-+	+0-	+00	+0+	++-	++0	+++
Hept	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F	G	H	K	M	N	P	R	T	V	X	Z
Uns	000	001	002	010	011	012	020	021	022	100	101	102	110	111	112	120	121	122	200	201	202	210	211	212	220	221	222
	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26
3's	0	1	2	3	4	5	6	7	8	9	10	11	12	13	-13	-12	-11	-10	-9	-8	-7	-6	-5	-4	-3	-2	-1

In the above table, the row marked Hept gives the heptavintimal encoding of the trit pattern. As with hexadecimal, we always use heptavintimal to represent the trit pattern itself without regard to its intended interpretation as a signed or unsigned number. Thus, heptavintimal A represents both the unsigned value 10 and the balanced value –3.

The final row gives the 3's-complement interpretation. Just as 2's-complement uses the samed representation for positive numbers as is used in unsigned binary, the positive 3's-complement numbers use the same representation as unsigned ternary. Both the balanced and 3's-complement systems use the same range of values.

Note that balanced ternary is a biased number system. That is, to convert an unsigned or 3's complement number to its balanced equivalent using modular addition, and to convert a balanced number to its 3's complement equivalent, we subtract the bias. For 3-trit ternary, the bias we use is 13. In general, for an n-trit number, the bias is (2ⁿ – 1)/2.

The fact that balanced numbers are equivalently interpreted as biased numbers means that we can use a balanced adder to compute unsigned sums, and we can use an unsigned adder to compute balanced sums. In each case, following the addition, we simply add or subtract the bias, as required, where the bias is always the maximum balanced value. Using the subscripts bal and uns to indicate balanced and unsigned operators, the following relationships hold:

• a +_bal b   =   a +_uns b –_uns bias
• a +_uns b   =   a +_bal b +_bal bias

Note that negation of balanced ternary numbers is trivial. All the trits that are zero remain unchanged in the negated value, while all instances of +1 are replaced with –1, and visa versa. In the context of the ternary logic operations, this means that the arithmetic negation operation applied to a ternary number is done by applying the logical negation operator to each trit of the number. Alternatively, we can describe this transformation as the ternary 2's complement because we have subtracted the unsigned representation of each digit from 2. Similarly, the negation of a 3's complement number is done by taking the ternary 2's complement or logical not of each trit and then adding one.

2. Increment, Decrement and the Half Adder

2.1 Unsigned and 3's-Complement Half Adder

2.2 Balanced Half Adder

Comparison with the truth tables for the binary operators in ternary logic shows that the sum function given above is identical to the modulo-3 sum function, and the carry function is identical to the consensus function. Therefore, the implementation of a balanced ternary half adder is straightforward.

A balanced ternary half adder

si = ( ai + ci ) ci+1 = ( ai ⊠ ci )

The above schematic diagram looks remarkably like the schematic diagram for a conventional binary half adder, with sum and consensus gates where the binary version had exclusive or and and gates. This half adder works for both unsigned and balanced ternary numbers, since the order of values is the same in both systems. There is one important difference between this half adder and its close binary cousin. This half adder will either increment or decrement, depending on whether c₀ is +1 or –1, while the binary equivalent can only incrment.

If we had to draw a conclusion at this point, it would be that balanced ternary is a distinctly superior notation, when compared with unsigned and 3's-complement ternary. In fact, this is based on the delusional idea that the diadic ternary addition operator is a simple primitive. It is not, and if we reduce these to canonical sum of products form, the unsigned (or 3's-complement) increment circuits are slightly simpler than the balanced ternary form, although the latter offers additional functionality, since it can also be used to decrement.

Numerous other authors have designed ternary half adders. [Dhande, Jaiswal and Dudam, 2007; Đorđević 1967] both give unsigned ternary half-adders implemented using min, max and decoding gates. [Gorde 2010] gives a balanced ternary half adder implemented using a multiplexer tree, reducing the design to the VLSI chip layout level.

3. Addition and the Full Adder

In the above, we have followed the elementary school rules for addition, writing the carry out of each column of the problem above the next column, just as in the example at the start of Section 2 on incrementing and decrementing. In elementary school, the carry in to the least significant position usually went unmentioned because it was implicitly zero. We will use the following notation for addition, a natural extension of the notation used for incrementing:

General notation used for addition

C = c4 c3 c2 c1 0 A = a3 a2 a1 a0 + B = b3 b2 b1 b0 S = s3 s2 s1 s0

Again, c₀ is the carry in to the least significant digit of the sum, usually set to zero. The logic required to perform the operations at each step is referred to as a full adder; this takes as inputs c_i, the carry in to step i, plus a_i and b_i, the two addend digits for that step. The outputs are the same as for the increment problem, s_i, the sum digit from step i, and c_i+1, the carry in to the next step. The above notation applies for any radix.

3.1 Unsigned and 3's-Complement Full Adder

Note that the carry in and out from each stage is two-valued, giving us two possible encodings if we wish to express this using ternary logic. As was the case with half adders, we can encode the carry values 0 and 1 as unsigned ternary numeric values, represented by – and 0, or we can encode them as the ternary truth values false and true represented as – and +. Again, it turns out that these alternatives lead to optimal sum-of-products realizations that are identical in complexity. Here is the result for the latter encoding:

Truth tables for an unsigned full adder, using uniform encoding

inputs    outputs  ai bi ci ci+1 si – – – – – – – 0 – – + – 0 – 0 – – 0 – 0 0 – 0 + – + – + – – + – + 0 – + + + – 0 – – – 0 0 – 0 0 – + – + 0 0 – – + 0 0 0 0 0 + + – 0 + – + – 0 + 0 0 + + + 0 + – – – + + – 0 + – + + – + 0 – + – + 0 0 + 0 + + 0 + + – + 0 + + 0 + + + + +

inputs    output  ai bi ci ci+1 0 0 + + 0 + + + 0 + + + + + + + + + +

inputs    output  ai bi ci si – – + 0 – 0 + + – + – + 0 – + + 0 0 – + 0 + + 0 + – – + + 0 + 0 + + + + – 0 0 0 – 0 + + 0

The above exercise allows us to measure the complexity of the unsigned adder. It has 6 minterms in the carry function and 12 minterms in the sum. The optimized sum and carry truth tables do share at most one minterm, given a logic implementation that allows the output of the ++• term to be interpreted as a + in one function and as a 0 in the other.

3.2 Balanced Full Adder

The truth tables for modulo-3 sum and accept anything operators differ from each other only in the positions that are don't-care positions above. Therefore, either function could be used to combine c_a and c_b. Here, we used accept anything because it is the simpler of the two functions.

Optimization

A systematic exercise in deriving an optimal sum-of-products implementation for the full adder begins with a truth table. The truth table for a 3-input ternary function has 27 entries:

Truth table and optimization results for a balanced ternary full adder

inputs    outputs  ai bi ci ci+1 si – – – – 0 – – 0 – + – – + 0 – – 0 – – + – 0 0 0 – – 0 + 0 0 – + – 0 – – + 0 0 0 – + + 0 + 0 – – – + 0 – 0 0 – 0 – + 0 0 0 0 – 0 – 0 0 0 0 0 0 0 + 0 + 0 + – 0 0 0 + 0 0 + 0 + + + – + – – 0 – + – 0 0 0 + – + 0 + + 0 – 0 0 + 0 0 0 + + 0 + + – + + – 0 + + + 0 + – + + + + 0

inputs    output  ai bi ci ci+1 0 + + + + 0 + + + + 0 + + + + + 0 0 0 0 0 0 0 0 0 + 0 + 0 + 0

inputs    output  ai bi ci si – – – 0 – – 0 + – 0 – + – 0 + 0 – + 0 0 – + + + 0 – – + 0 – + 0 0 0 0 0 0 0 + + 0 + – 0 0 + 0 + + – 0 0 + – + + + 0 – 0 + 0 0 + + + – + + + + 0

The results of the optimization exercises shown to the right of the truth table above are presented in a compact tabular form instead of the algebraic form. Aside from that notational change, the work was carried out following the same methodology as was described in Section 4 of Standard Ternary Logic. Note that the carry out function minimized quite nicely, while the sum function resisted minimization. This is also the case with binary adders.

In somewhat intuitive English, the optimal sum of products for the carry out can be summarized as follows: If at least 2 of the three inputs are +1 and none are –1, then the carry out will be +1. If at least two of the three inputs are zero, then the carry out will be zero. Otherwise, if exactly one input that is +1, then the carry output will be zero. If none of the above are satisfied, the carry out will be –1.

We will not draw a circuit diagram for the above functions for two reasons: First, it is complex, and second, while interesting, we are not interested in this full adder design. High performance computer systems generally need carry-lookahead adders, not the ripple-carry design we have have focused on here.

The complexity of a one trit balanced adder can now be given: It takes 10 minterms to compute the carry out of each place and 18 minterms to compute the sum at each place. As with the balanced adder, the two optimized truth tables have at most one shared minterm. In summary, moving from an unsigned or 3's complement adder to a balanced adder requires 4 extra minterms per trit to compute the carry and 6 extra minterms per trit to compute the sum. This amounts to about a 50% increase in complexity. If the complexity of addition is our only consideration, and if we stick with ripple-carry logic, balanced ternary is not the best choice for building a ternary ALU.

4 Comparison

4.1 Comparison with Zero

It is worth noting that the 3's complement comparison function x described above can be implemented with threshold logic. If we encode our logic values as 0, 1 and 2, then c_{1 - 0} = a₀/2 + a₁ using the thresholds t_– = 0.25 and t₊ = 1.75 to assign logic values to the result.

For balanced ternary, the general rule above can be restates as follows: The sign is determined by the sign of the most-significant non-0 trit. The encoding of the sign is trivial because our digit values and our logic values are encoded identically. The following truth table and logic diagram describe the resulting function x for balanced ternary:

Comparison function x for balanced ternary

c1 - 0   a0  –   0   +  a1 – – – – 0 – 0 + + + + +

c1 - 0   meaning  – < 0 = + >

This encoding is more obvious, largely because of the natural relationship between our logic notation and balanced ternary. Again, it is worth noting that this function can be computed using threshold logic, and in fact, other than the value of one threshold, the function is actually the same as the function developed above for 3's complement comparison with zero. If we encode our logic values as 0, 1 and 2, then c_{1 - 0} = a₀/2 + a₁ using the thresholds t_– = 1.25 and t₊ = 1.75 to assign logic values to the result.

It is worth noting that, with the exception of the balanced values –...– – – and 0...000, which correspond to the 3's complement values 0...000 and 1...111, the balanced comparator given above will always report as negative every value that the 3's complement comparator reports as positive and visa versa. Thus, given one of these comparators plus special logic to recognize the zero for the other number system, the output of the other comparator can be synthesized.

In summary, it seems fair to conclude that 3's-complement-ternary comparison with zero is no more than twice as complex as balanced-ternary comparison with zero, and if threshold logic is allowed, they may be identical in complexity. In general, threshold logic requires tighter control of switching thresholds than conventional logic and smaller noise margins. Therefore, complexity conclusions based on threshold logic should be viewed with suspicion.

4.2 Comparing Two Numbers

A quick comparison of the truth table above with the truth tables for the ternary diadic operators reveals that function y is simply the accept anything operator with one input inverted. If there is an efficient implementation of this operator, we can use it directly, as suggested in the logic diagram above. If not, the minimal sum of products for this function has 6 minterms:

Sum-of-products for unsigned and balanced comparison function y

inputs    outputs  a0 b0 c0 – – 0 – 0 – – + – 0 – + 0 0 0 0 + – + – + + 0 + + + 0

inputs    outputs  a0 b0 c0 0 – + 0 0 0 + – + + 0 + + 0 – 0

The above in graphical and algebraic form

ci  =  ( ( ai =   0 ) ∧ ( bi = –1 ) ∧ +1 ) ∨ ( ( ai =   0 ) ∧ ( bi =   0 ) ∧   0 ) ∨ ( ( ai = +1 ) ∧ ( bi = –1 ) ∧ +1 ) ∨ ( ( ai = +1 ) ∧ ( bi =   0 ) ∧ +1 ) ∨ ( ( ai = +1 ) ∧   0 ) ∨ ( ( bi = +1 ) ∧   0 )

It is worth noting that the above function can be computed using threshold logic. If we encode our logic values as 0, 1 and 2, then c₀ = a₀ – b₀ using the thresholds t_– = –0.5 and t₊ = +0.5 to assign logic values to the result.

For 3's-complement comparison, the model we used above does not appear to be workable. Instead, it seems that we have two choices:

• We can subtract and then examine the sign of the result. This requires us to develop the full mechanism of a fast adder, which we augment by comparing the result to zero. The latter is a natural augmentation since we are likely to want something like condition codes computed from the output of the ALU.

• We can compare each of the operands with zero and also do an unsigned comparison of the two operands. If both operands have the same sign, the unsigned comparison will give the correct result. If the signs of the operands differ, the signs alone are sufficient to tell us which operand is greater.

5 Carry Lookahead

Charles Babbage wrote at length about this issue in [Babbage, 1864]. He referred to the ripple-carry adder as performing successive carriage, and he recognized that successive carriage created a major performance bottleneck in any mechanical computer. He termed his eventual solution to this an anticipating carriage mechanism. Although his mechanical solutions do not resemble those of modern digital logic, his idea of carry anticipation remains in modern carry-lookahead logic. Gerald Rosenberger of IBM filed for a patent on a modern binary carry-lookahead adder in 1957, see [Rosenberger, 1960].

5.1 Increment

A second handle on the behavior of the propagate signal comes from comparing the original half adder given in Section 2.1 with the carry-lookahead version given here. One consensus consensus gate has been eliminated from the new version. This must be moved into internal nodes of the carry-lookahead tree marked x. These two lines of reasoning lead us to the following design for the nodes of a balanced carry-lookahead tree:

A balanced carry-lookahead tree internal node x

c1 = ( p0 ⊠ c0 ) p1-0 = ( p0 ⊠ p1 )

A balanced carry-lookahead tree root node y

c4 = ( p3-0 ⊠ c0 )

All of the internal nodes in the tree are identical. The labeling in the above figures is specific to the upper right internal node that communicates with the least significant two half adders in the tree and to the root of a 4-trit tree, but the logic does not change for different sized trees. In practice, shallower trees and therefore faster increment circuits will be built by replacing the binary tree given above with a ternary or quaternary tree, limited only by the fan-in of the consensus gates. Here is the internal node design appropriate for a ternary tree:

A ternary carry-lookahead tree internal node

c1 = ( p0 ⊠ c0 ) c2 = ( p0 ⊠ p1 ⊠ c0 ) p2-0 = ( p0 ⊠ p1 ⊠ p2 )

Unsigned Increment

In the abstract, an unsigned carry-lookahead ternary adder stage can be described by the following truth table:

Table for an unsigned carry-lookahead incrementer

inputs    outputs  ai ci pi si 0 F F 0 0 T F 1 1 F F 1 1 T F 2 2 F T 2 2 T T 0

In the above, we have used a mixed notation, using numeric values for the data in and out of each stage of the incrementer, while using Boolean values for carry in to the stage and propagate out from the stage. This mixed notation leads immediately to the conclusion that the carry lookahead logic is identical to that used in a binary increment circuit. In fact, this is true for the unsigned increment function in any number base. Encoding this table using ternary logic, we get the following:

Table for an unsigned carry-lookahead incrementer

inputs    outputs  ai ci pi si - - - - - 0 - + - 0 0 - - 0 0 0 0 + - + + - + + + 0 + + + -

inputs    outputs  ai ci pi   + +

inputs    outputs  ai ci si - + 0 0 + + + - + 0 0

We can now give give diagrams and formulas for these, in optimal sum-of-products form:

An unsigned carry-lookahead half adder

si  =  ( ( ai = –1 ) ∧ ( ci = +1 ) ∧   0 ) ∨ ( ( ai =   0 ) ∧ ( ci = +1 ) ∧ +1 ) ∨ ( ( ai = +1 ) ∧ ( ci = –1 ) ∧ +1 ) ∨ ( ( ai =   0 ) ∧   0 ) pi = ( ai = +1 )

The logic for the carry lookahead tree supporting this half adder is nothing new. In the schematic diagrams below, all of the ternary notation that is used is there merely to indicate that the devices used should be ternary compatible. Aside from this, the gates used are simple and gates.

An unsigned carry-lookahead tree internal node x

c1 = ( p0 ∧ c0 ) p1-0 = ( p0 ∧ p1 )

An unsigned carry-lookahead tree root node y

c4 = ( p3-0 ∧ c0 )

5.2 Add

The tree structure shown in the following figure illustrates the classical construciton of a carry-lookahead adder, built along the lines suggested by Rosenberger, 1960.

Tree structure of a carry-lookahead adder

The above figure shows a binary tree, but Rosenberger used a ternary tree, and quatrinary trees have been commonly used with binary adders since the introduction of the 74182 chip in the early 1970s. The leaves of the carry-lookahead tree for a binary adder are modified full adders that produce two auxiliary signals instead of the carry out signal used for ripple-carry adders. The first of these, p, indicates whether that stage of the adder will propagate a carry from its input to its output. This corresponds exactly to the propagate signal used above for a carry-lookahead incrementer. The second, g, indicates whether that stage of the adder will generate a carry independent of the carry in to that stage.

Unsigned Addition

The situation is relatively simple for unsigned addition. Here is the table for unsigned add, using the standard Boolean encoding of propagate, generate and carry used with binary addition:

Table for an unsigned carry-lookahead adder

inputs    outputs  ai bi ci pi gi si 0 0 F F F 0 0 0 T F F 1 0 1 F F F 1 0 1 T F F 2 0 2 F T F 2 0 2 T T F 0 1 0 F F F 1 1 0 T F F 2 1 1 F T F 2 1 1 T T F 0 1 2 F T 0 1 2 T T 1 2 0 F T F 2 2 0 T T F 0 2 1 F T 0 2 1 T T 1 2 2 F T 1 2 2 T T 2

In the above table, note that, when the adder stage generates a carry locally, we don't particularly care about the propagate output. This leads us to a new insight: The propagate and generate signals naturally combine into a single ternary signal that we will call pg:

Propagate and generate combined

pi   gi   pgi  F F – T F 0 T +

Combining the propagate and generate signals gives us the following simplified tree structure for the lookahead carry logic connecting the stages of an adder:

Modified tree carry-lookahead tree structure

Recoding the table for the adder into a truth table involves two changes. First, we combine the propagate and generate signals, and second, we recode the unsigned 0, 1 and 2 into the balanced notation used for ternary logic throughout this discussion. This allows us to derive an optimal sum-of-products:

Truth tables for an unsigned carry-lookahead adder

inputs    outputs  ai bi ci pgi si – – – – – – – 0 – – + – 0 – 0 – – 0 – 0 0 – 0 + – + – + – 0 + – + 0 – + + 0 – 0 – – – 0 0 – 0 0 – + – + 0 0 – 0 + 0 0 0 0 0 + 0 – 0 + – + – 0 + 0 0 + + + 0 + – – 0 + + – 0 + – + 0 – + 0 – + – + 0 0 + 0 + + 0 + + – + 0 + + 0 + + + + +

inputs    outputs  ai bi ci pgi   0 0 0 + 0 + 0 0 + + + 0 + + + +

inputs    outputs  ai bi ci si – – + 0 – 0 + + – + – + 0 – + + 0 0 – + 0 + + 0 + – – + + 0 + 0 + + + + – 0 0 0 – 0 + + 0

The question of what to do with the don't-care conditions in the above tables will crop up later in this discussion. As we will see, there is some benefit to making c_i = 0 equivalent to c_i = –1 This leads to the following optimized results, expressed as a circuit diagram and formulas:

An unsigned carry-lookahead full adder

si  =  ( ( ai = –1 ) ∧ ( bi = –1 ) ∧ ( ci = +1 ) ∧   0 ) ∨ ( ( ai = –1 ) ∧ ( bi =   0 ) ∧ ( ci = +1 ) ∧ +1 ) ∨ ( ( ai = –1 ) ∧ ( bi = +1 ) ∧ ( ci ≠ +1 ) ∧ +1 ) ∨ ( ( ai =   0 ) ∧ ( bi = –1 ) ∧ ( ci = +1 ) ∧ +1 ) ∨ ( ( ai =   0 ) ∧ ( bi =   0 ) ∧ ( ci ≠ +1 ) ∧ +1 ) ∨ ( ( ai =   0 ) ∧ ( bi = +1 ) ∧ ( ci = +1 ) ∧   0 ) ∨ ( ( ai = +1 ) ∧ ( bi = –1 ) ∧ ( ci ≠ +1 ) ∧ +1 ) ∨ ( ( ai = +1 ) ∧ ( bi =   0 ) ∧ ( ci = +1 ) ∧   0 ) ∨ ( ( ai = +1 ) ∧ ( bi = +1 ) ∧ ( ci = +1 ) ∧ +1 ) ∨ ( ( ai = –1 ) ∧ ( bi =   0 ) ∧   0 ) ∨ ( ( ai =   0 ) ∧ ( bi = –1 ) ∧   0 ) ∨ ( ( ai = +1 ) ∧ ( bi = +1 ) ∧   0 ) pgi  =  ( ( ai =   0 ) ∧ ( bi =   0 ) ∧ 0 ) ∨ ( ( ai = +1 ) ∧ 0 ) ∨ (     ( bi = +1 ) ∧ 0 ) ∨ ( ( ai =   0 ) ∧ ( bi = +1 ) ∧ +1 ) ∨ ( ( ai = +1 ) ∧ ( bi =   0 ) ∧ +1 ) ∨ ( ( ai = +1 ) ∧ ( bi = +1 ) ∧ +1 )

Note that the above equations and logic diagram have not been fully reduced in order to emphasize their relationship to the truth tables from which they were derived. Indicating a constant input of +1 to an min gate, for example, does not actually imply the need for an input to that gate. Given that all other inputs to the min gates in sum-of-products logic are Boolean valued, all such min gates are actually simple Boolean and gates.

In the case of min gates with one input set to the constant 0, where all other inputs are Boolean, we do not need to use ternary logic gates at all. Instead, we can use Boolean logic, with the output clamped into the range -1 to 0 instead of the usual -1 to +1. Thus, all of the min gates in the sum of products are no more complex than conventional Boolean and gates.

Combining propagate and generate signals moving up the tree, half of the logic for the internal nodes (x) in our carry-lookahead tree, can be remarkably simple when propagate and generate are combined as a single ternary function. The truth table is presented below, along with the result of an optimal sum-of-products minimization exercise:

Combining propagate-generate

inputs    outputs  pg1 pg0 pg1-0 – – – – 0 – – + – 0 – – 0 0 0 0 + + + – + + 0 + + + +

inputs    outputs  pg1 pg0 pg1-0 0 0 0 0 + + + +

It is highly probable that a simple logic gate can be built that directly implements the above truth table. One avenue to this, for example, would be to compute the analog sum 3pg₁ + lpg₀ and then compare this with appropriate thresholds to determine the result. Of course, if sufficiently precise control of thresholds is difficult, then conventional logic optimization methods can be applied. If that is not possible, then we can always fall back on the following:

An unsigned carry-lookahead tree root node y

pg1-0 = (( pg0 =   0 ) ∧ ( pg1 =   0 ) ∧   0 )* ∨ (( pg0 = +1 ) ∧ ( pg1 =   0 ) ∧ +1 ) ∨ ( ( pg1 = +1 ) ∧ +1 )

As with a conventional carry-lookahead Boolean adder, the carry in to the most significant subtree of each vertex will be the same as the carry in to the least significant subtree when the least significant subtree propagates, and it will be true if the least significant subtree generates. If we encode carry as +1 and no carry as either -1 or 0, as already mentioned, the root node (y) of our carry lookahead tree becomes identical to half of an internal node (x), although it can be simplified if the carry in signal never has the value 0. In that case, the gate marked with an asterisk above can be omitted. The full internal node is constructed from two of these:

An unsigned carry-lookahead tree internal node (x)

Note that the computation of the carry out of the internal node can also be simplified. The simplified version of the carry lookahead tree's root node (y) discussed above omits a term. In constructing each internal node, the carry in to the most significant subtree of that node can be computed from the carry in to the node using the simplified form, as indicated by the asterisk here.

Balanced Addition

For adding balanced ternary numbers, an adder stage will propagate a positive carry in if one or both of the addend inputs to that stage are positive (and none are negative), and it will propagate a negative carry if one or both addends are negative (and none are positive). Thus, at stage i, we can compute the propagate output using an accept anything operator:

• p_i ≟ ( a_i ⊞ b_i)

This looks promising, but all is not well. Given no carry in to a stage, that stage will generate a carry out of +1 if the two addends are both +1, and a carry out of –1 if both addends are –1. Thus, we could use a consensus operator to compute the generate output from stage i of the adder:

• g_i ≟ ( a_i ⊠ b_i)

Unfortunately, the above paragraph contained the caveat "given no carry in to a stage." In a binary adder, the two addend digits input to a stage of the adder could force a carry out independent of the carry in to that stage. With a balanced ternary adder, the carry in to a stage of the adder can prevent that stage from generating a carry out. Solving this problem requires a more complex encoding than the 3 or 4-valued propagate-generate signals that work for binary and unsigned ternary arithmetic.

There is a high-level discussion of carry-lookahead in binary-coded ternary computers in [Parhami and McKeown, 2013]. They conclude that two copies of a conventional unsigned carry lookahead tree will suffice to build a balanced ternary carry lookahead tree. Here, we note that this bound conforms to the basic insight that balanced ternary is essentially a biased number system, and therefore biased addition can be done by adding the two operands and then adding a bias to the result. Here, we focus on a different approach. Can we directly build a carry lookahead circuit for balanced ternary?

Looking at the recoding we used for the propagate and generate signals for the unsigned ternary adder, we can quickly conclude that each stage of the balanced ternary adder will have the following propagate-generate outputs:

Balanced adder propagate and generate

ai   bi   pgi  – – M– – 0 P– – + N 0 – P– 0 0 N 0 + P+ + – N + 0 P+ + + M+

pgi  associated meaning M– may generate negative carry P– propagate negative carry N neither propagate nor generate P+ propagate positive carry M+ may generate positive carry

There is no condition of the inputs that guarantees that a stage in the adder will generate a carry, only that it may generate. For example, if both inputs to a stage are +1, the stage will only generate a carry if the carry in to that stage is not –1. Our challenge with these new signals is to work out how they propagate up the carry lookahead tree, and how carry signals are generated in this tree.

Note that the work we have already done on a ripple-carry balanced adder is still applicable for computing s_i as a function of a_i, b_i and c_i, so aside from questions of the encoding of pg_i, our primary job at this point is to work out the details of the internal nodes of the lookahead tree

At each internal node, two propagate-generate signals encoded as above arrive, one from the left (more significant) subtree, one from the right (less significant) subtree. If the left subtree says M+ and the right subtree says N, then the output from the internal node must indicate that there will, most certainly, be a carry out. Thus, we must add two more values to our encoding:

7-valued propagate-generate

pgi  associated meaning G– will generate negative carry M– may generate negative carry P– propagate negative carry N neither propagate nor generate P+ propagate positive carry M+ may generate positive carry G+ will generate positive carry

We can now fully define the internal node of the carry anticipation tree in terms of these values with a 7 by 7 table describing how each node computes the propagate-generate signal sent on up the tree and a 7 by 3 table describing how each node computes the carry in to its left subtree from the carry in to the node itself:

Functional description of a carry anticipation tree node

pgout   pgright  G– M– P– N  P+ M+ G+  pgleft  G– G– G– G– G– G– G– G– M– G– G– G– G– M– P– N  P– G– M– P– N  N  N  N  N  N  N  N  N  N  N  N  P+ N  N  N  N  P+ M+ G+ M+ N  P+ M+ G+ G+ G+ G+ G+ G+ G+ G+ G+ G+ G+ G+

cout   pgright  G– M– P– N  P+ M+ G+  cin  – – – – 0 0 0 + 0 – – 0 0 0 + + + – 0 0 0 + + +

Two cells the left table above have been shaded. These mark cases where the two subtrees may generate carries of opposite polarity depending on the carry in to that subtree. At first blush, it might look like this is a worst case that prevents carry lookahead, but in fact, there are only two possibilities:

• The carry signal in to the right subtree permits it to generate a carry. In this case, the carry out of the right subtree prevents the left subtree from generating a carry.
• The carry in to the right subtree prevents it from generating a carry. In this case, the left subtree will generate a carry of the exact same sign as the carry in to the right subtree.

In sum, the net result is that two subtrees that each conditionally generate a carry of opposing sign work together to create a tree that effectively propagates from carry in to carry out, even though that carry is actually adsorbed and another carry of the same sign is regenerated.

It is worth nothing that the diagonal structure of both tables above strongly suggests that these two functions can be computed with threshold logic threshold logic, although threshold logic with 3 or 4 ternary inputs would require setting very finely tuned thresholds. In general, finely tuned thresholds are not good candidates for mass production.

To reduce the above to practical form, we must find an encoding of the seven-valued propagate-generate signal that leads to convenient implementation of the necessary logic. Two ternary signals can encode 9 values, and there are a huge number of ways our 7 values can be mapped onto the 9. Symmetry arguments allow us to eliminate many of them, but the number remains daunting. The following coding is arbitrary and seems reasonable:

Ternary encoding for propagate and generate

p   g   pg  – – G– – 0 M– – + P– 0 – 0 0 N 0 + + – P+ + 0 M+ + + G+

The labels p and g are used here without the specific meanings propagate and generate, but rather, these names are retained arbitrarily because, taken together, they communicate what in a binary carry-lookahead adder were the propagate and generate signals.

Using the above encoding, we can finish the truth tables for each stage of the adder.

Balanced adder propagate and generate

ai   bi   pgi   pi   gi  – – M– – 0 – 0 P– – + – + N 0 0 0 – P– – + 0 0 N 0 0 0 + P+ + – + – N 0 0 + 0 P+ + – + + M+ + 0

ai   bi   pi  0 0 0 0 + + + 0 + + + + + 0 + 0

ai   bi   gi  – 0 + 0 – + 0 0 0 + + 0 – 0 – 0

The optimizations shown above require a total of 12 distinct minterms. Note that the work we have already done on a ripple-carry balanced adder shows that it takes 12 minterms to compute s_i as a function of a_i, b_i and c_i. Thus, we can conclude that it takes 24 minterms for each trit of a balanced carry lookahead adder, plus the logic of the carry lookahead tree itself. This compares with 18 minterms per trit of an unsigned or 3's complement carry lookahead adder.

Using the above encoding, we can write out the truth table for carry in to the left subtree as a function of PG out of the right subtree and the carry in to the entire tree:

Truth table and optimization for balanced carry lookahead

inputs    output  c0 p0 g0 c1 – – – – – – 0 – – – + – – 0 – – 0 0 0 – 0 + – + – 0 – + 0 0 – + + + 0 – – – 0 – 0 – 0 – + 0 0 0 – 0 0 0 0 0 0 + 0 + – 0 0 + 0 + 0 + + + + – – – + – 0 0 + – + 0 + 0 – + 0 0 0 + 0 + + + – + + + 0 + + + + +

inputs    output  c0 p0 g0 c1 0 + 0 + + + + + 0 0 0 + 0 + + 0 + + + 0 0 + 0

Where the optimized carry out computation for an unsigned ternary carry-lookahead tree node had just 2 minterms, the move to balanced ternary seems to have raised the cost to 7 minterms. It may be the case that a different encoding would permit better optimization, but it does not look promising.

The exercise of developing the full tree node is daunting. This involves a function of 4 ternary variables, where the full truth table has 81 rows.

6. Conclusion