Trinary Computer Systems

Copyright (C) 2003-2005 Jeff Connelly

"I am shocked, shocked to discover that a fundamental computer architecture explored in the 1950's, rejected as unworkable, and forgotten is in fact unworkable." -- leighklotz

1. Base 3

Base 3 is any weighted numbering system which uses three digits. I'll spare you an introduction to positional numbering systems which has been countlessly reiterated when introducing base 2.

Base 3 is traditionally known as ternary. I prefer trinary to ternary or tertiary. My dictionary defines ternary as "Composed of three or arranged in threes, having the base three." while trinary is defined as "Consisting of three parts of proceeding by threes; ternary.", and tertiary as "Third in place, order, degree, or rank". Seems as if they're nearly synonyms, although tertiary would be more appropriate if base 2 was called secondary. Perhaps my preference stems from avid use of Perl, and Larry Wall using trinary over ternary in Apocalypse 3. In fact, IIRC an old version of perlop had a quote about ternary being old-fashioned, but don't quote me on that.

1.1. Compared to Analog

Analog computers use a large range of voltages to represent data. Their advantage is that only one wire is used to store any number. Opamps can perform integration, differentiation, root extraction, multiplication/division, logarithms, anti-logs, and more. However, analog computers are prevented from becoming mainstream because of their inherent inaccuracy. Resistance, which occurs in all conductors except superconductors, degradates the signal. It cannot be amplified without knowing how much loss actually occured, and that varies with ambient temperature. Of course, this problem doesn't exist with analog devices such as speakers because they operate on Alternating Current, where the frequency determines the signal rather than the amplitude. But I disgress. Analog has it's uses, but not in precise arithmetic which modern computers require.

1.2. Compared to Base 10 and 2

Digital computers are defined as using distinct voltages. The first digital computers used ten voltages, meaning they where base 10 - or decimal. Atanasoff came up with the idea of using two voltage levels. According to Debate Stirs Over Origin of Computers:

Atanasoff was thinking about computers. There were already mechanical and analog computers. But Atanasoff thought there might be better methods of computing. He drove from dry Iowa to a bar over the Illinois line, drank three Scotch and waters, and had a Eureka! moment.

"That's when he figured out he could do everything in base 2," Gustafson says. Base 2 is digital. It's 1s and 0s. Previous computers worked in base 10. "He jotted on a cocktail napkin all the basic principles of modern computing."

(The quote is slightly inaccurate. Base 2 is indeed digital, but so is base 10.)

"A common man marvels at uncommon things; a wise man marvels at the commonplace."

-Confucious

1.3. Compared to Base e

According to Third Base, e is the most optimal base when efficiency is measured as rw where r=radix and w=width. 3 is the closest integer to e, closer than 2. See the article for more information, including how the author used base 3 to organize his file folders more efficiently.

1.4. Base 9 and 27

Just as in binary computing where one octal digit is 3 bits and one hexadecimal digit is 4 bits, trinary computing has conventional bases of it's own.

If a^n = b, then one base b digit holds n base-a digits. Since 3^2 = 9, three ninary digits (base 9) represent 2 trits. Groups of 2 trits can be converted directly to a ninary digit and vice versa:

Base
 3 9
00 0
01 1
02 2
10 3
11 4
12 5
20 6
21 7 
22 8

For example, using the table above, we can find out that 20213 = 679. Base 9 uses digits [0..8].

3^3 = 27, so in base 27 (needs a name), three trits = one base-27 digit. Base 27 uses [0..9] plus [A..S] excluding I and O for obvious reasons.

 3 000 001 002 010 011 012 020 021 022 100 101 102 110
27  0   1   2   3   4   5   6   7   8   9   A   B   C 

 3 111 112 120 121 122 200 201 202 210 211 212 220 221 222
27  D   E   F   G   H   J   K   L   M   N   P   Q   R   S

One base-27 digit is equivalant to exactly 1.5 = 3/2 = log27(9) base-9 digits.

Any power higher than base 27 is impractical, but base 27 is highly practical and useful for compact trit representation.

1.5. Trits, Tribbles, and Trytes

Trits are base 3 digits.

The TriINTERCAL manual:

5.4 DATA TYPES

The two TriINTERCAL data types are 10-trit unsigned integers and
20-trit unsigned integers.  All INTERCAL syntax for distinguishing
data types is ported to these new types in the obvious way.  Small
words may contain numbers from #0 to #59048, large words may contain
numbers from #0$#0 to #59048$#59048.  Errors are signaled for constants
greater than #59048 and for attempts to WRITE IN numbers too large
for a given variable or array element to hold.

The 10- and 20-trit numbers are remarkably close to their 16- and 32-bit counterparts. 16 bits store as much as 16*(log(2)/log(3)) =~ 10.0949 trits, and 32 bits store as much as 32*(log(2)/log(3)) =~ 20.1898 trits. 64 bits are about 40.3795 trits. On the surface, it looks as if the TriINTERCAL programmers picked 10 and 20 because they're multiples of ten, but upon deeper inspection this is obviously not the case. On a related note, 2^8=256, which is quite near 3^5=243.

Base 2 word sizes are almost aways powers of 2. Following this trend, we'll choose powers of base 3 word sizes if possible.

Suggested trit groupings:
Trits (base 3) Digits (base 9) Digits (base 27) Max (decimal, 3^trits) Name Description
1 1/3 1/27 2 trit Well established.
2 1 3/2 9 nit One base-9 digit.
3 2/3 1 27 tribble Half of a tryte, one base-27 digit.
6 2 729 tryte Analogous to a byte.
9 3 19,683 tryte and 1/2 9 = 3^2
24 282,429,536,481 ? Good word size perhaps.
27 7,625,597,484,987 ? Seems like a good word size.

There has been much discussion about trinary digit groupings on Slashdot | Ternary Computing Revisited, but I believe these make the most sense. At least, one user agreed. A document on trinary computing says a tryte is 6 trits (e.g. two tribbles), although 6 is not an integer power of 3. The argument is that a nibble is 1/2 byte, so a tribble should be 1/3 tryte. This document uses 6-trit trytes, e.g. 2 tribbles, 1 tribble = 1/2 tryte.

1.6. Encodings

As discussed in section 3, trinary digits can be defined as as {0,1,2} (unbalanced) or {-1,0,1}. Of these, {-1,0,1} can be defined as {F,?,T} where ? is unknown (simultaneously T and F)--this is is known as "Unknown-State Logic" and is covered elsewhere. However, Boolean algebra can be mapped in other ways: {T,F,T}, where -1 and 1 are both true, only 0 is false. This more closely represents conventional logic, but is less useful. "Trinary Coded Binary" can refer to either.

For textual output, Unicode is used. Blocks are often partially encoded because Unicode is aligned on hexadecimal boundaries, but if more characters can be used, the number of trits can be extended. See RFC 4042 for UTF-9 and UTF-18.
# Trits Range Character Range
6 0 - 243
U+0000 - U+00F3
All of ASCII
Most Latin-1 Supplement
7 0 - 2,187
U+0000 - U+088B
Latin Extended-A, Latin-Extended B, IPA Extensions, Spacing Modifier Letters, Combining Diacritical Marks, Greek and Coptic, Cyrillic, Cyrillic Supplement, Armenian, Hebrew, Arabic, Syriac, Thaana
8 0 - 6,561
U+0000 - U+19A1
Devanagari, Bengali, Gurmukhi, Gujarati, Oriya, Tamil, Telugu, Kannada, Malayalam, Sinhala, Thai, Lao, Tibetan, Myanmar, Georgian, Hangul Jamo, Ethipoic, Cherokee, Unified canadian Aboriginal Syllabic, Ogham, Runic, Tagalog, Hanunoo, Buhid, Tagbanwa, Khmer, Mongolian, Limbu, Tai Le
9 0 - 19,683
U+0000 - U+4CE3
a lot, but only part of CJK, no Yi, surrogates, or private use.
18 0 - 387,420,489
U+0000_0000 + U+1717_9149
All, Unicode 4 only goes up to U+10_0000
27 0 - 7,625,597,484,987
up to U+6EF_7907_7FBB
Should be enough for anybody...

2. Basic Trinary Algebra

Boolean (binary) Algebra was invented in 1854 by George Boole (1815-1864). It's well known, whole books have been written on it, and algorithms have been developed. This section attempts to help the world fully understand Trinary Algebra, so it can be used more extensivily.

2.1. Unary Functions

Binary has 2^2=4 possible unary functions, while trinary has 3^3=27. They can be divided into several subgroups.

2.1.1. Constant Functions

The output is always the same. You can't derive input from output, not even partially. Uninteresting, never used in practice. If you want a specific trit value, no input is needed - the wire is connected directly to a neutral, positive, or negative rail.

000 clear to 0
111 clear to 1
222 clear to 2

2.1.2. One-to-one Functions

Each input maps to exactly one output. They all have 0, 1, and 2 in their output, meaning that the original input can be derived from the output, by taking the inverse of the output.

F#  Name    Diff:012 Inverse   Expression
012 buffer       '''  012      A    A
021 swap 1/2     '/\  021      ['A  A
102 swap 0/1     /\'  102      ]'A  A
120 rotate up    ///  201      ]A   A
201 rotate down  \\\  120      [A   A
210 swap 0/2     \'/  210      'A   A, or A'

The "Diff" column points to the trit's original position. ' means the trit stayed in the same place, / points left, \ right. The inverses of these functions are themselves except for the rotates. Some rules:

A = A
A = A
A = A
A = A
A = A

The last rule works because these are unique-loss-none/1-to-1 functions, which means they have inverses which are also functions.

A word about notation: [, and are both rotate down/left. The [ was chosen as an ASCIIized because:

012 A
120 Q

As you can see, the digits are shifted left, just as how [ closes left. Flip [ 90 degrees and it will be similar to . Rotate down=[, up=].

2.1.3. Many-to-One Functions

The most plentiful trinary unary functions have only two values of trits in their function table; one is repeated. These have the effect of replacing the trit with a specified value if it is another specified value, else defaulting to the third specified value. The shift functions are useful for coercing trits into bits, used with Trinary Coded Binary, but with the help of the swap, rotate, and invert operators can create any of the partial unique loss functions.

F#  ITE  Expression
001 210 \A     A            Shift Down
002 220 ]/'A   A
010 100 \]A    A
011 001 \/A    A
020 120 ]/['A  A
022 002 [\'A   A
100 010 \'A    A
101 101 [/['A  A
110 210 [/'A   A
112 221 /\A    A
121 121 ]\]A   A
122 012 /A     A            Shift Up
200 020 ]/A    A
202 102 [\]A   A
211 021 ]\'A   A
212 112 /['A   A
220 202 [\A    A
221 212 /'A    A
The first trit of the if-then-else field is the value to compare the input with; if the input is this value the second value of the ITE field is output, else the third value is. For example, function 1223 has an ITE of 0123, so the process goes like this: a) if input is 0, output is 1 b) else, output is 2. ITE reverse-lookup:
ITE F#  Expression
001 011 \/A    A
002 022 [\'A   A
010 100 \'A    A
012 122 /A     A
020 200 ]/A    A
021 211 ]\'A   A
101 101 [/['A  A
102 202 [\]A   A
110 010 \]A    A
112 212 /['A   A
120 020 ]/['A  A
121 121 ]\]A   A
201 110 [/'A   A
202 220 [\A    A
210 001 \A     A
212 221 /'A    A
220 002 ]/'A   A
221 112 /\A    A

Note than an ITE of xaa (last two trits equal) always gives the same output, meaning it's a constant (unique loss: complete) function. Some Algebraic laws:

A = A     '(\A) = /'A
A = A     '(/A) = \'A

2.1.4. Basic Unary Functions

In the last three sections, we proved that the follow unary functions are able to create any of the 27 unary functions:

001 \A  A     Shift Down (ITE=210)
122 /A  A     Shift Up   (ITE=012)
120 ]A  A     Rotate Up           ///  
201 [A  A     Rotate Down         \\\  
210 'A  A      Invert (swap 0/2)   \'/  

No other unary operators need be implemented.

This document uses both Symbol/Wingding fonts which show how the trinary operators are supposed to look, and ASCII approximations which work on all modern platforms. Neither is sufficient on a real trinary computer, as the ASCII characters may be used for other purposes. Unicode defines all the necessary unary operator characters:

]   U+2229  INTERSECTION        ∩
[   U+222A  UNION               ∪
/   U+2197  NORTH EAST ARROW    ↗
\   U+2198  SOUTH EAST ARROW    ↘
'   U+0305  COMBINING OVERLINE  ˝

However, Unicode will not be used in this document because my Windows box doesn't have the necessary fonts, and yours probably doesn't either.

Unary Quick Reference

2.2. Binary Functions

It's no problem to enumerate all the unary functions, because there's only 3^3 of them. Not the case with trinary binary functions. There are 9^3 = 3^3^3 = 19,683 possible trinary binary functions. We can't possibly list them all; most of them wouldn't even be useful or could be derived from more basic building block functions.

2.2.1. Commutativity

One interesting thing about trinary binary functions is you can tell if they are commutative (order of inputs doesn't matter, A ? B = B ? A) by their function table. Here's how it works: Take the function number bits, suppose its bits are abc,def,ghi. Write them in a 3x3 table, as rows:

a b c
d e f
g h i
Now take the columns: adg,beh,cfi. If adg,beh,cfi = abc,def,ghi, then the function is commutative. In order for this to occur:
b = d
c = g
f = h
(Note: the method of writing the function in rows then taking the columns works for binary also; if you use a 2x2 table. I suppose it'll work for higher bases also.) Another method of determining commutativity is by swapping the inputs, leaving the outputs attached, and checking if they're equal. In fact, the matrix method is a shortcut of the former.

If a function isn't commutative, it's probably not worth our time. So we can downsize all the possible functions to a mere 729 commutative functions, less than 4% of the possible functions. To do this, we remove the inputs which are the same as other inputs, but in a different order:

               
00 a                  New truth:
01 b                  00 a a
02 c                  01 b b
10 d same as 01       02 c c
11 e                  11 e d
12 f                  12 f e
20 g same as 02       22 i f
21 h same as 12   
22 i
abcdefghi
   b  cf

9 bits down to 6. 3^9=19683, 3^6=729. 729/19689=1/27=3.7037''% of all possible binary trinary functions. It should be obvious whether we are talking about a abcdefghi or abcefi truth table depending on it's length.

To convert a 6-trit truth table to 9-trit, simply follow this formula:

6-trit-truth = abcdef
9-trit-truth = abc,bde,cef
Example: 6-trit 000112 is 000,011,012

All commutative binary trinary function truth tables:

Total bi-tri: 19683
Commutative: 729 (3.7037037037037%)
000000000 000000001 000000002 000001010 000001011 000001012 000002020 000002021
000002022 000010000 000010001 000010002 000011010 000011011 000011012 000012020
000012021 000012022 000020000 000020001 000020002 000021010 000021011 000021012
000022020 000022021 000022022 001000100 001000101 001000102 001001110 001001111
001001112 001002120 001002121 001002122 001010100 001010101 001010102 001011110
001011111 001011112 001012120 001012121 001012122 001020100 001020101 001020102
001021110 001021111 001021112 001022120 001022121 001022122 002000200 002000201
002000202 002001210 002001211 002001212 002002220 002002221 002002222 002010200
002010201 002010202 002011210 002011211 002011212 002012220 002012221 002012222
002020200 002020201 002020202 002021210 002021211 002021212 002022220 002022221
002022222 010100000 010100001 010100002 010101010 010101011 010101012 010102020
010102021 010102022 010110000 010110001 010110002 010111010 010111011 010111012
010112020 010112021 010112022 010120000 010120001 010120002 010121010 010121011
010121012 010122020 010122021 010122022 011100100 011100101 011100102 011101110
011101111 011101112 011102120 011102121 011102122 011110100 011110101 011110102
011111110 011111111 011111112 011112120 011112121 011112122 011120100 011120101
011120102 011121110 011121111 011121112 011122120 011122121 011122122 012100200
012100201 012100202 012101210 012101211 012101212 012102220 012102221 012102222
012110200 012110201 012110202 012111210 012111211 012111212 012112220 012112221
012112222 012120200 012120201 012120202 012121210 012121211 012121212 012122220
012122221 012122222 020200000 020200001 020200002 020201010 020201011 020201012
020202020 020202021 020202022 020210000 020210001 020210002 020211010 020211011
020211012 020212020 020212021 020212022 020220000 020220001 020220002 020221010
020221011 020221012 020222020 020222021 020222022 021200100 021200101 021200102
021201110 021201111 021201112 021202120 021202121 021202122 021210100 021210101
021210102 021211110 021211111 021211112 021212120 021212121 021212122 021220100
021220101 021220102 021221110 021221111 021221112 021222120 021222121 021222122
022200200 022200201 022200202 022201210 022201211 022201212 022202220 022202221
022202222 022210200 022210201 022210202 022211210 022211211 022211212 022212220
022212221 022212222 022220200 022220201 022220202 022221210 022221211 022221212
022222220 022222221 022222222 100000000 100000001 100000002 100001010 100001011
100001012 100002020 100002021 100002022 100010000 100010001 100010002 100011010
100011011 100011012 100012020 100012021 100012022 100020000 100020001 100020002
100021010 100021011 100021012 100022020 100022021 100022022 101000100 101000101
101000102 101001110 101001111 101001112 101002120 101002121 101002122 101010100
101010101 101010102 101011110 101011111 101011112 101012120 101012121 101012122
101020100 101020101 101020102 101021110 101021111 101021112 101022120 101022121
101022122 102000200 102000201 102000202 102001210 102001211 102001212 102002220
102002221 102002222 102010200 102010201 102010202 102011210 102011211 102011212
102012220 102012221 102012222 102020200 102020201 102020202 102021210 102021211
102021212 102022220 102022221 102022222 110100000 110100001 110100002 110101010
110101011 110101012 110102020 110102021 110102022 110110000 110110001 110110002
110111010 110111011 110111012 110112020 110112021 110112022 110120000 110120001
110120002 110121010 110121011 110121012 110122020 110122021 110122022 111100100
111100101 111100102 111101110 111101111 111101112 111102120 111102121 111102122
111110100 111110101 111110102 111111110 111111111 111111112 111112120 111112121
111112122 111120100 111120101 111120102 111121110 111121111 111121112 111122120
111122121 111122122 112100200 112100201 112100202 112101210 112101211 112101212
112102220 112102221 112102222 112110200 112110201 112110202 112111210 112111211
112111212 112112220 112112221 112112222 112120200 112120201 112120202 112121210
112121211 112121212 112122220 112122221 112122222 120200000 120200001 120200002
120201010 120201011 120201012 120202020 120202021 120202022 120210000 120210001
120210002 120211010 120211011 120211012 120212020 120212021 120212022 120220000
120220001 120220002 120221010 120221011 120221012 120222020 120222021 120222022
121200100 121200101 121200102 121201110 121201111 121201112 121202120 121202121
121202122 121210100 121210101 121210102 121211110 121211111 121211112 121212120
121212121 121212122 121220100 121220101 121220102 121221110 121221111 121221112
121222120 121222121 121222122 122200200 122200201 122200202 122201210 122201211
122201212 122202220 122202221 122202222 122210200 122210201 122210202 122211210
122211211 122211212 122212220 122212221 122212222 122220200 122220201 122220202
122221210 122221211 122221212 122222220 122222221 122222222 200000000 200000001
200000002 200001010 200001011 200001012 200002020 200002021 200002022 200010000
200010001 200010002 200011010 200011011 200011012 200012020 200012021 200012022
200020000 200020001 200020002 200021010 200021011 200021012 200022020 200022021
200022022 201000100 201000101 201000102 201001110 201001111 201001112 201002120
201002121 201002122 201010100 201010101 201010102 201011110 201011111 201011112
201012120 201012121 201012122 201020100 201020101 201020102 201021110 201021111
201021112 201022120 201022121 201022122 202000200 202000201 202000202 202001210
202001211 202001212 202002220 202002221 202002222 202010200 202010201 202010202
202011210 202011211 202011212 202012220 202012221 202012222 202020200 202020201
202020202 202021210 202021211 202021212 202022220 202022221 202022222 210100000
210100001 210100002 210101010 210101011 210101012 210102020 210102021 210102022
210110000 210110001 210110002 210111010 210111011 210111012 210112020 210112021
210112022 210120000 210120001 210120002 210121010 210121011 210121012 210122020
210122021 210122022 211100100 211100101 211100102 211101110 211101111 211101112
211102120 211102121 211102122 211110100 211110101 211110102 211111110 211111111
211111112 211112120 211112121 211112122 211120100 211120101 211120102 211121110
211121111 211121112 211122120 211122121 211122122 212100200 212100201 212100202
212101210 212101211 212101212 212102220 212102221 212102222 212110200 212110201
212110202 212111210 212111211 212111212 212112220 212112221 212112222 212120200
212120201 212120202 212121210 212121211 212121212 212122220 212122221 212122222
220200000 220200001 220200002 220201010 220201011 220201012 220202020 220202021
220202022 220210000 220210001 220210002 220211010 220211011 220211012 220212020
220212021 220212022 220220000 220220001 220220002 220221010 220221011 220221012
220222020 220222021 220222022 221200100 221200101 221200102 221201110 221201111
221201112 221202120 221202121 221202122 221210100 221210101 221210102 221211110
221211111 221211112 221212120 221212121 221212122 221220100 221220101 221220102
221221110 221221111 221221112 221222120 221222121 221222122 222200200 222200201
222200202 222201210 222201211 222201212 222202220 222202221 222202222 222210200
222210201 222210202 222211210 222211211 222211212 222212220 222212221 222212222
222220200 222220201 222220202 222221210 222221211 222221212 222222220 222222221
222222222

Bold functions have a name, examined in section 2.A.

2.2.2. Preference Functions

Preference/choice functions where brought to my attention by the TriINTERCAL manual, specifically section 5.5.2.1:

5.5.2.1 UNARY LOGICAL OPERATORS

Let's start with AND and OR.  To begin with, these can be considered
"choice" or "preference" operators, as they always return one of their
operands.  AND can be described as wanting to return 0, but returning 1
if it is given no other choice, i.e., if both operands are 1.  Similarly,
OR wants to return 1 but returns 0 if that is its only choice.  From
this it is immediately apparent that each operator has an identity
element that "always loses", and a dominator element that "always wins".

AND and OR are commutative and associative, and each distributes
over the other.  They are also symmetric with each other, in the sense
that AND looks like OR and OR looks like AND when the roles of 0 and 1
are interchanged (De Morgan's Laws).  This symmetry property seems to be
a key element to the idea that these are logical, rather than arithmetic,
operators.  In a three-valued logic we would similarly expect a three-
way symmetry among the three values 0, 1 and 2 and the three operators
AND, OR and (of course) BUT.

The following tritwise operations have all the desired properties:
OR returns the greater of its two operands.  That is, it returns 2 if
it can get it, else it tries to return 1, and it returns 0 only if both
operands are 0.  AND wants to return 0, will return 2 if it can't get
0, and returns 1 only if forced.  BUT wants 1, will take 0, and tries
to avoid 2.  The equivalents to De Morgan's Laws apply to rotations
of the three elements, e.g., 0 -> 1, 1 -> 2, 2 -> 0.  Each operator
distributes over exactly one other operator, so the property
"X distributes over Y" is not transitive.  The question of which way
this distributivity ring goes around is left as an exercise for the
student.

In TriINTERCAL programs the '@' (whirlpool) symbol denotes the unary
tritwise BUT operation.  You can think of the whirlpool as drawing
values preferentially towards the central value 1.  Alternatively,
you can think of it as drawing your soul and your sanity inexorably
down...

On the other hand, maybe it's best you NOT think of it that way.

A few comments about how these operators can be used.  OR acts like
a tritwise maximum operation.  AND can be used with tritmasks.  0's
in a mask wipe out the corresponding elements in the other operand,
while 1's let the corresponding elements pass through unchanged.  2's
in a mask consolidate the values of nonzero elements, as both 1's and
2's in the other operand yield 2's in the output.  BUT can be used to
create "partial tritmasks".  0's in a mask let BUT eliminate 2's from
the other operand while leaving other values unchanged.  Of course,
the symmetry property guarantees that the operators don't really
behave differently from each other in any fundamental way; the apparent
differences come from the intuitive view that a 0 trit is "not set"
while a 1 or 2 trit is "set".

To summarize:

OR  prefers 2, 1, 0      - this is the max operator
AND prefers 0, 2, 1
BUT prefers 1, 0, 2

Knowing what an operator prefers, we can easily find it's truth table.

In       Preferences    (pref-nnn)
AB 012 021 102 201 120 210
00  0   0   0   0   0   0
01  0   0   1   0   1   1
02  0   0   0   2   2   2
10  0   0   1   0   1   1 
11  1   1   1   1   1   1
12  1   2   1   2   1   2
20  0   0   0   2   2   2
21  1   2   1   2   2   2
22  2   2   2   2   2   2

Notice how A ? A = A, where ? is a preference/choice function. The operator has no other choice but to return A. Also, since preference functions are commutative, 01 and 10, 02 and 20, 12 and 21, are equal, respectively. So the only outputs worth looking at are the bold ones. The bold outputs, 01, 02, and 12 form the zoztot number (zero one, zero two, one two). Zoztot's contain one of the middle pref, two of the first, and zero of the third. If a is the middle preference trit, then:

pref  zoztot
0ab = 00a
1ab = 1a1
2ab = a22

pref-012 is the minimum function while pref-210 is the maximum; this is quite obvious as they prefer the highest or lowest trit. By extrapolating, all of the preference functions can be found:

pref  truth:long  short    zoztot   name(s)
012  000,011,012  000112     001     pref-012        minimum
021  000,012,022  000122     002     pref-021  3and
102  010,111,012  010112     101     pref-102  3but
120  012,111,222  012112     121     pref-120
201  002,012,222  002122     022     pref-201
210  012,112,222  012122     122     pref-210  3or   max

Now to assign them symbols...

2.2.3. Tritmasks

Unary gates exist within binary gates, no matter the base. Binary trinary gates have unary trinary gates within them, just as Binary Boolean Gates are composed of unary boolean gates.

If we write a binary trinary function's truth table in three groups of three, each group will be a unary function. Group 0 is the unary function which operates on B if A is 0, group 1 is the unary function which operates on B if A is 1, etc.

 0   1   2
abc,def,ghi = unary operations on B if A=0,1,2

Knowing this, we can decompose unary functions to see how they operate when used as tritmasks.

truth:long  short    0    1     2       name(s) and symbol(s)
000,011,012 000112   0    \/B   B       |<  Minimum - prefer 012
002,012,222          ]/'B B     2       |prefer 201
012,111,222          B    1     2       |prefer 120
012,112,222 012122   B    /\B   2       |>  Maximum - prefer 210 ("trinary or")
012,102,220 012020   B    ]'B   [\B     |^  Exclusive Max
000,012,022 000122   0    B     ]\'B    |prefer 021 ("trinary and")
010,111,012 010112   \[B  1     B       |prefer 102 ("trinary but")

Minimum sets output to 0 if mask is, lets pass through if mask is 2, and if the mask is 1 then 0 and 1 pass through, but 2 is changed to a 1. Similarily, maximum lets the input pass through if the mask is 0, sets the output to 2 if the mask is, and lets 1,2 pass through but sets 0 to 1 if the mask is 1.

A trit exclusive max'd with 1, and then exclusive max'd with 1 again gives the original value, just as (XOR A,1) XOR 1 = A. This works because the unary function B is called when one of the inputs is 1. Since it is being called on it's own output, (XMAX A,1) XMAX 1 = B = B = B.

BUT, as explained in the TriINTERCAL manual, eliminates 2's while leaving other values unchanged, if the mask contains a 0. 010=\[B causes 2 to be mapped to a 0. 1's in the input always output 1's, while 2's output the other operand.

2.A. Named Functions

Most functions here where taken from Binary Operations on trinary.cc.



                  decomposition
truth:long short   0   1   2      name(s)
000011012 000112   0  A  B      | Minimum - prefer 012
012112222 012122   B  A  2      | Maximum - prefer 210 ("trinary or")
012102220 012020   B  B   B    |Exclusive Max
010121010         B B B   |   Mean
122012001         B  B   B      |   Magnitude

000012022 000122 prefer 021 ("trinary and")
010111012 010112 prefer 102 ("trinary but")
012111222 012112 prefer 120
002012222 002122 prefer 201

3. Advanced Functions

This section is about the applications of trinary algebra, to get back to familiar arithmetic.

3.1. Unbalanced Arithmetic

In unbalanced arithmetic, the digits {0,1,2} are used as themselves.

3.1.1. Negation: 3's Complement

In base 2, 1's complement is found by performing bitwise inversion. 2's complement is obtained by adding 1 to 1's complement. Trinary is similar. Tritwise inversion gives 2's complement, adding 1 gives 3's complement.

According to a base converter, 42 = 11203. Tritwise inversion of 000011203 = 222211023 = 651810 unsigned, which is the 2's complement. Add one to get unsigned 6519 = -42 signed, known as the 3's complement. Verify this works by performing -42 + 42, or 6519 + 42 = 6561 = 1_0000_00003, truncated equals 0.

3.1.2. Addition

First make a truth table:

A B C S
0 0 0 0
0 1 0 1
0 2 0 2
1 0 0 1
1 1 0 2
1 2 1 0
2 0 0 2
2 1 1 0
2 2 1 1
A,B = inputs
C,S = carry, sum
C = 000,001,011 = 0   \A   \/A
S = 012,120,201 = A   ]A   [A

3.1.3. Subtraction

Subtraction is simply negation via 3's complement followed by addition.

3.2. Balanced Arithmetic

"Ahhh, what an awful dream. Ones and zeroes everywhere...[shudder] and I thought I saw a two." -- Bender
"It was just a dream, Bender. There's no such thing as two". -- Fry
-- Futurama

What Fry says rings true in balanced trinary.

"There can only be one"

Positive and negative one, that is. Lack of being is zero. That is, balanced trinary uses digits {-1,0,+1}, rather than {0,1,2}. To map unbalanced trinary to balanced, subtract one. Because the prefix negative sign makes it longer than 0 or 1, it's often written above the numeral as a vinculum or overscore:

_
1 0 1

Unbalanced and balanced conversion chart:

Unbalanced  Balanced
    0          -1
    1           0
    2          +1

Since HTML doesn't have overstrike, we'll use 1 for -1 instead. Optimally, the Unicode character U+0305 COMBINING OVERLINE could be used.

Balanced Ternary Webpage

TriINTERCAL manual, section 5.4:

Note that though TriINTERCAL considers all numbers to be unsigned,
nothing prevents the programmer from implementing arithmetic operations
that treat their operands as signed.  Three's complement is one obvious
choice, but balanced ternary notation is also a possibility.  This
latter is a very pretty and symmetrical system in which all 2 trits
are treated as if they had the value -1.

Balanced ternary notation is an interesting idea. Example:

1110 = 0*(3^0) + 1*(3^1) + -1(3^2) + 1(3^3) 0 + 3 + -9 + 27 = 21

Almost as weird as using negative bases, but suprisingly elegant.

Knuth claims a balanced ternary system is best in:

D.E. Knuth, The Art of Computer Programming - Volume 2: Seminumerical Algorithms, pp. 190-192. Addison-Wesley, 2nd ed., 1980. ISBN 0-201-03822-6.

On sci.math, James Allwright announced a Balanced Ternary System arithmetic package. According to Allwright, the advantages of it is:

3.2.1. Negation: Inversion

Numbers are negated by swapping all 1's with 1 and vice versa. Truth table:

A -A
1 1
0 0
1 1

101 Balanced
210 Unbalanced

210 is also known as the invert operator. In balanced trinary notation, logical inversion = arithmetic negation, unlike in binary where x86 PCs have both NOT and NEG.

3.2.2. Addition

Truth table:

A B C S
1 1 1 1 (-1 + -1 = -2 = (-1*3^1+1=-3+1=-2))
1 0 0 1
1 1 0 0
0 1 0 1
0 0 0 0
0 1 0 1
1 1 0 0
1 0 0 1
1 1 1 1

C = 100,000,001 Balanced = 011,111,112 Unbalanced
S = 110,101,011 Balanced = 201,012,122 Unbalanced

C = \/A   1   /\A
S = [A    A   /A

3.2.3. Subtraction

Although subtraction can be derived from addition, addition can be derived from subtraction. The 1100 Univac takes advantage of this by what is called a subtractive adder. Here is a subtractor:

A B C D (C=borrow should be B but taken, D=difference)
1 1 0 0
1 0 0 1
1 1 1 1
0 1 0 1
0 0 0 0
0 1 0 1
1 1 1 1
1 0 0 1
1 1 0 0

C=001,000,100 Balanced = 110,111,211 Unbalanced
D=011,101,110 Balanced = 102,210,021 Unbalanced

C = [/'A    1    ]\'A
D = ]'A     A'   ['A

An additive subtractor can be made from the adder in 3.2.2 and a negation. A subtractive adder can be made by using the subtractor above with a negation.

3.3. Unknown-State Logic

Unknown-State Logic is boolean logic with the addition of the ? state. ? is unknown, which means T or F since those are the only values in boolean logic.

Unbal Bal USL
  0   -1  F
  1    0  ? = TF
  2    1  T

The addition of the ? state enables short-circuiting to be more used.

3.3.1. NOT: Inversion

Tritwise inversion performs the NOT operation.

A A'
T F
? ?
F T

NOT ? is the same as the combination of NOT T and NOT F. NOT T = F and NOT F = T, so T and F combine to give TF, or ?.

There are 27 possible unary functions, although NOT is the only useful one which follows the rule that ? = TF.

3.3.2. AND, XOR, OR, XNOR, NAND

Inputs 0001 0110 0111 1000 1001 1110
 A  B  and  xor   or  nor  xnor nand
 F  F   F    F    F    T    T    T
 F  ?   F    ?    ?    ?    ?    T
 F  T   F    T    T    F    F    T
 ?  F   F    ?    ?    ?    ?    T
 ?  ?   ?    ?    ?    ?    ?    ?
 ?  T   ?    ?    ?    ?    ?    ?
 T  F   F    T    T    F    F    T
 T  ?   ?    ?    ?    ?    ?    ?
 T  T   T    F    T    F    T    F


       US Logic     Unbalanced    Unary Gates
and = FFF,F??,F?T = 000,011,012 = 0   \/A   A
xor = F?T,???,T?F = 012,111,210 = A   1     A'
or  = F?T,???,T?T = 012,111,212 = A   1     /['A
nor = T?F,???,F?F = 210,111,010 = A'  1     \]A
xnor= T?F,???,F?T = 210,111,012 = A'  1     A
nand= TTT,T??,T?F = 222,211,210 = 2   ]\'A  A'

The table above was filled in by using the definition that ? = TF. For example, F and ? = (F and T)(F and F) = FF = F. Substitute ? for T and F in two expressions and combine them. Because ? is more of an extention to boolean algebra than a whole new system, binary functions are still represented by four bits.

4. Implementation

The toughest part of building a trinary computer system is the actual implementation. Note that this document uses {0,1,2} for trits when discussing theory, but when implementation is discussed {-1,0,+1} shall be used instead, corresponding to actual voltage levels. Keep in mind -1 maps to 0, 1 to 0, and +1 to 2. Simply using 0->0, 1->1, and 2->-1 will not work. Subtract or add one when converting from unbalanced to balanced to keep everything in balance.

4.1. Existing Computers

If we see how existing computers implemented trinary logic, much can be learned. Unfortunely, little technical detail can be found.

TERNAC
A software-emulated machine developed at State University of New York by Gideon Frieder in 1973. Mentioned in Third Base.

Trinary
Rumored to be used by the Tholians in Star Trek. Can anyone verify this?

Dytrax 1000
Imaginary computer in the science fiction The Fall of Binary Symbolism. This chapter has a mention of an imaginary trinary computer, the Dytrax 1000.

TRIPS Processor
COMP203 (1997 Mid-trimester Test) at Victoria University of Wellington mentions the imaginary TRIPS processor, which supports ternary arithmetic in 3's complement using 4-trit fixed-width operands.

Setun'
W. H. Ware, S. N. Alexander, N. M. Astrahan, H. H. Goode, M. Rubinoff, P. Armer, L. Bers, H.d. Huskey, "Soviet computer technology - 1959," Communications of the ACM, pp. 149-150, 1960.

SETUN was build with add and multiply instructions at Moscow State University in the 1950's. However, it's trit flip-flap-flops where not genuine, rather two bits wired to have three stable states.

4.2. Magnetism

Magnetism naturally has North, South, and unmagnetised states. Materials respond differently depending on if they're diamagnetic, paramagnetic, or ferromagnetic. Diamagnetism is a phenomena all materials inherently experience, but it's very weak. Diamagnetic materials repell both North and South magnetic flux. Ferromagnetism occurs when magnetic domains align, forming a temporary magnet. The magnetization is greater than the applied magnetic field. Paramagnetic materials have magnetization proportional to the strength of the magnetic field applied to it.

4.2.1. Electromechanical Relays

A relay's coil normally is wound around a ferromagnetic material which increases it's strength. The contacts themselves however are for the most part paramagnetic. This means the COM contact is attracted to the NO contact if there any magnetic flux radiating from the coil, no matter the direction.

A ------)|| |  /-----NC--- C
        )|| | /
        )|| | -------COM-- Q
GND-----)|| +---------NO-- B

Shown above is a standard relay. If A=0V=0, Q=C, while if |A|>0 then Q=B. |A|>0 means both 1 (+5V) and 2 (-5V) cause Q=B. Therefore, the truth table looks like this:

A Q
0 C
1 B
2 B

Possible functions where C != B:
011 022 100 122

The relay's inability to distinguish between positive and negative voltages, in this case, is an advantage as it allows the shift up (122) function to be implemented.

To tell negative and positive voltages apart, we can have two relays with diodes to separate the signals:

        -----------------)|| NO---- D
        v      y-trit 2  )|| COM-----+
       ---          GND--)||         |
        |                            |
   A ---+                            +----- Q           
        |                            |
        v           GND--)||         |
       ---     x-trit 1  )|| COM-----+
        -----------------)|| NO---- C
 
 Dual Diode/Dual Relay -- 2D2R Config

A Q
0 B
1 C
2 D

With dual relays, functions in the form x1y can be implemented because an input of zero results in an output of zero:

010 \]A
012 A
011 \/A  -- used within minimum binary function
110 [/'A
112 /\A  -- used within maximum binary function
210 A'   -- inverter
211 ]\'A
212 /['A

The 2D2R configuration has been successfully constructed physically by myself. I created a tritwise inverter, it worked great. However, the relays required large voltages and where generally unpleasant to deal with.

2D2Q, that is Dual Diode/Dual Transistor, is a similar configuration but the relays are replaced with transistors. It has not yet been tested.

4.2.2. Bipolar Relays

In what I call a bipolar relay, the paramagnetic COM contact is replaced by a ferromagnetic temporary magnet.

A ------)||    |------Neutral
        )|| |    -----South
        )|| |  |
        )|| |   ------COM-- Q
GND-----)||  ---------North

The COM contact is normally connected to Neutral, but a positive voltage causes it to be connected to North, while negative connects it to South. In this way, the 0, 1, and 2 trits can be detected and substituted with arbitrary values. All 27 unary functions can be created using a single bipolar relay.

A Q
0 Neutral
1 North
2 South

Bipolar relays can also be used as 1-trit demultiplexers. The input is still the coil, but the trit on COM redirects to South/Neutral/North depending on the coil. In this way, several unary gates can be created having an input we'll call A, and demultiplexed by an input called B -- thus creating a binary trinary logic gate.

4.3. Rapid Single Flux Quantum

RSFQ Logic came up in a thread on Slashdot. Liquor made a post which I'll quote in full:

Unfortunately,( RSFQ (Rapid Single Flux Quantum) [rochester.edu] circuitry is beyond the scope of SPICE simulations, but this appears to me to be a natural fit to the trinary logic paradigm.

Some circuits have already been physically built and tested - and at least one person feels that they lend themselves to tristate logic gates [sunysb.edu].

The basic principles are already in the category of proven technology - ever heard of a SQUID sensor?

Josephson junctions work equally well for either positive or negative currents - and so do magnetic flux quanta. (But this circuitry has to be the ultimate in low-power computing - you can't get much lower discrete amounts of energy than a single quantum of magnetic flux.)

4.4. Rectifiers

Rectifier diodes are primarily used to make 1-to-2, unique loss partial functions, because information is lost.

4.4.1. Half-Wave

Blocking negative:

A ----->|----- Q
 A  Q
-1  0
 0  0
+1  1
Balanced 001 = unbalanced 112
Q = /\A
Q = A

Blocking positive:

A -----|<----- Q
 A   Q
-1  -1
 0   0
+1   0
Balanced -1,0,0=011 unbalanced
Q = \/A
Q = A

4.4.2. Full-Wave Bridge

     +------- +
    / \
   ^   ^
  /     \
 +-~   ~-\
 \       /
  \     /
   ^   ^
    \ /
     +------- -

A full-wave bridge rectifier has four diodes, all cathode-up, here denoted by a ^. FWBR's are often used in power supplies to flip the negative half of the waveform; AC is given on ~, and positive voltage is on +, negative on -. With trinary computers, a FWBR makes a binary trinary gate because there is two inputs.

    Balanced (voltages)Unbalanced
+ = 001,001,111        112,112,222 unbalanced    (FWBR+, commutative)
- = 111,100,100        000,211,211 unbalanced    (FWBR-)

+ = /\A   /\A   1      /\A   /\A    2
- = 1     ]\'A  ]\'A   0     ]\'A   ]\'A

The unary /\A gates are nothing new, but ]\'A is. Combining them gives /\]\'A = ]\'A, nothing is gained. \/]\'A = 1, which is not useful either.

A. References

The Comprehensive List of What Other People Think about Trinary supercedes this section.

Trinary.cc
Great site on trinary logic and implementation by Steve Grubb. I learned about most of the gates from here. The tutorials explain how to use trinary logic to create useful circuits, and schematics of how to build trinary gates are included. Slashdot | Ternary Computing Revisited, submitted by yours truly, links to this article.

American Scientist: Computing Science: Third Base by Brian Hayes
A short article with some nice theory and math behind the ternary number system itself. Slashdot | Ternary Computing, links to this article.

TriINTERCAL Manual
Trinary dialect of the INTERCAL programming language. Although TriINTERCAL itself is obviously a joke, the logic behind it is not. Or is it?
Tri-Stable RSFQ Elements
About Josephson junctions, which are inheirantly ternary in nature.

Team-R2D2
(At end of page) Fabricated a 64-tert SRAM and 4-tert adder -- "the very first full-ternary circuit ever fabricated".