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
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.
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.
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
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.
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.
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.
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... |
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.
Binary has 2^2=4 possible unary functions, while trinary has 3^3=27. They can be divided into several subgroups.
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
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=].
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 äAThe 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
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.
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.
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 iNow 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.
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...
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.
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
This section is about the applications of trinary algebra, to get back to familiar arithmetic.
In unbalanced arithmetic, the digits {0,1,2} are used as themselves.
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.
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
Subtraction is simply negation via 3's complement followed by addition.
"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.
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 = 21Almost 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:
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.
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
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.
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.
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.
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.
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.
If we see how existing computers implemented trinary logic, much can be learned. Unfortunely, little technical detail can be found.
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.
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.
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.
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.
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.)
Rectifier diodes are primarily used to make 1-to-2, unique loss partial functions, because information is lost.
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
+------- +
/ \
^ ^
/ \
+-~ ~-\
\ /
\ /
^ ^
\ /
+------- -
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.
The Comprehensive List of What Other People Think about Trinary supercedes this section.