Slashdot Mirror
Beyond Binary Computing?
daksis writes "Non base two computing is nothing new. But it is an idea that, for various reasons, never really caught on. Embedded.com is running an op/ed piece that asks if hardware and software engineers are ready to move to ternary or quaternary logic. A move to multi-valued logic provides more computational capability without the standard increase in die size or transistor count. Is the need to make do with the current fabrication technology enough to drive the move to multi-valued logic? Or will Moore's law continue without the need for doing more with less silica based real estate?"
I learned truth tables when I was a kid, and it was pretty simple:
a and b = ?
-----------
0 and 0 = 0
0 and 1 = 0
1 and 0 = 0
1 and 1 = 1
But how would you make an AND gate for a trinary system? Would it be like multiplication with signs?
a and b = ?
-----------
- and - = +
- and 0 = 0
- and + = -
0 and - = 0
0 and 0 = 0
0 and + = 0
+ and - = -
+ and 0 = 0
+ and + = +
And then quarternary... if it's just pairs of Boolean digits, no problem. It's just a four-input AND:
a and b = ?
-----------
0x and 0x = 0
0x and 1x = 0
1x and 0x = 0
x0 and x0 = 0
x0 and x1 = 0
x1 and x0 = 0
11 and 11 = 1
Or is the whole concept of an AND (OR, NAND, NOR, XOR) gate a relic of my Boolean thinking?
Stressed? Me? Of course not. Stress is what a rubber band feels before it breaks, silly.
Looks like systems working with more than ones and zeros would just need a way to encode these different values with different strengths of signals (as opposed to off=0, on=1). Something like no voltage=0, 1/3 voltage = 1, 2/3 voldage = 2 and 3/3 voldage=4. Seems like a very good way to wrap more information in the same signal/clock, but how would the logic work? How would and/or/xor work?
:) But I'd be willing to learn..
My mind is too used to binary
Sounds like a good idea.
find / -name "*.sig" | xargs rm
If you go to multilevel logic (not just on/off) then you're necessarily going to have intermediate states which both conduct and have voltage across them, with the resulting dramatic increase in power. This is an acceptable tradeoff for charge-storage devices like memories but a non-starter for logic.
Lacking <sarcasm> tags,
Base 2,3,4, and 10 are so easy. If you really want a challenge, build a computer using base pi, e, i, 1, or 0 :-).
- David A. Wheeler (see my Secure Programming HOWTO)
One of the best parts of Ternary (Trinary, base 3) is that you can use BALANCED Ternary, in which the digits are not 0, 1, and 2, but are -1, 0, and 1. This allows you to represent any integer without a sign bit. Letting N represent -1 digit you can represent -17 in balanced ternary as 101N (1*(3^0),0*(3^1),1*(3^2),N*(3^3)).
You can check out http://www.trinary.cc/Tutorial/Tutorial.htm for many examples of ternary circuits using ternary logic gates.
The reason for doing work in trinary computing is that it is closest to the theoretically optimal computing base. The reasoning was something like this:
Representations of numbers in a particular base have two defining characteristics - the number of values that can occupy a digit (m), and the number of digits it takes to represent that value (n).
(Here's where the theory takes a leap, at least to me) The most efficient base (or simplest) base for performing computations is the one at which the m*n product is minimized. As an example, we'll take THE ANSWER, 42(base10).
THE ANSWER in base 16 has a result of 16*2=32
THE ANSWER in base 10 has a result of 10*2=20
THE ANSWER in base 8 has a result of 8*2=16
Here are the interesting cases, though:
THE ANSWER in base 2 has a result of 2*6=12
THE ANSWER in base 3 has a result of 3*3=9
THE ANSWER in base 4 has a result of 4*3=12
IIRC, according to the article I was reading, the most effective base is actually "e" (euler's constant).
Inconceivable!
Binary, being the lowest base that can represent any integer mathematics, is not a point on the continuum, it is a defining terminus of the continuum, and has many special properties. Termini (endpoints) often do, especially in one-ended ranges (e.g. base two is the lowest number of sates, but in theory analog has an infinite number of states, and any real-world instantiation of an analog computer can only be an approximation.) One example of an open-ended range where the sole endpoint has unique properties is the prime numbers (which, properly, must be positive integers): the lowest prime, 2, has so many unusual properties that it is often excluded or dealt with as a special case. it is believed (but not quite proven) that there is no highest prime
This may sound trivial or like mealy-mouthed gibberish, so here's an example:
In every multi-state binary-like computer, division is computationally 'harder' than multiplication except base two!
Any algorithm for general division (by an arbitary divisor) involve more multiplications (and then subtractions, according to the results of implicit trial and error subtraction [branchpoints]) than a corresponding extended ('long form') multiplication. The reason this does not occur in base two is that multiplications by the two binary digits 1 and zero is so trivial that it does not need to actually be performed - a compare and branch suffices, which corresponds to the compare and branch preceding the additions of a binary multiplication.
This is pretty special. While multiplication and division are inverse function, full generalized division is always 'harder' than generalized multiplication. This is quite unlike, say, subtraction, where a 'subtraction circuit' can be constructed to perform subtraction exactly as easily and in roughly the same number of, say, transistors as an adder.
Binary math has many special properties in group and number theory. We'd lose those in higher base math, and we wouldn't gain new properties to make up for that loss. Two, the low bound, is special.