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?"
It's been a long time since I read an article about that, but AFAIK ternary system is most efficient in storing information (basically if you want to store numbers 0..700, you need 28 states (8+10+10) for decimal system, 20 states (10*2) for binary and 18 for ternary (6*3). This has something to do with 3 being closest to the value of e (2.718...) but I dont remember what exactly. Any /.-ers to fill in?
Increasing the number of states requires you to increase the overall voltage required of the device to acount for noise in the system. So in return for more states you are running at a higher voltage and thus at a higher power consumption level. You still have the same problem.
God, I'm assuming you get more ass than J-Lo's jumpsuits.
Yields an analog computer. Which is really a digital computer if you count individual electrons...
Now I am confused.
My rights don't need management.
There is no such word as "definate"!!! You did it more than once, and it's so fucking irritating! What the fuck is wrong with you people? Why do so many of you assholes make that same damned mistake?
Obviously, you aren't a total fucking moron and you can spell most words (even uncommon ones). So, why the fuck can't you spell this one? Just think about it... definite, as in defined, as in not infinite. Clearly, you are just using the word, with no comprehension of how the word came to be or its relationship to other words (do you even know what it means?), otherwise the spelling would be glaringly-fucking-obvious.
You fucking idiot!!!
Now, for a binary number system, digit 0 is [0, 2.5) volts, and digit 1 is (2.5, 5] volts. Clearly, the noise margin of the binary number system is much better than the noise margin of the base-3 number system.
Now consider the voltages of modern digital circuits. Consider a voltage range of [0, 1.5] volts. In a base-3 number systm, digit 0 would be [0, 0.5) volt. Digit 1 would be (0.5, 1.0) volt, and digit 2 would be (1.0, 1.5] volts.
For a binary number system, digit 0 is [0, 0.75) volt, and digit 1 is (0.75, 1.0] volt. Again, the noise margin of the binary number system is much better than the noise margin of the base-3 number system.
In fact, the noise margin of the binary number system is consistently 50% better than the noise margin of the base-3 number system. The noise margin of the binary number system is always better than the noise margin of the base-n number system, where n > 2. For this reason, engineers have not built and will not build digital systems with any non-binary number system.
The nice thing about binary systems are that they are either on or off. As gates and tracks get smaller, interference effects etc. become the limiting factor.
As we add more states, intermediate voltages, to the system, the difference between states becomes smaller, ie. the difference between states 2 and 3 in a ternary system is less than states 1 and 2 in a binary system.
Hence a binary system can be made smaller and denser than a ternary system and still work.
We may gain in logic density but lose out in physical density.
>Non base two computing is nothing new. But it is an
>idea that, for various reasons, never really caught on.
The various reasons not being so various; A binary system can be constructed in a much more stable fashion than can a trinary or quatrinary system. Everyone knows that 1 is not always exactly 5v (or 3v). Having several values confuses the picture even more
"but we have progressed enough that trinary systems are much more stable now!"
No matter what level of stability someone can get out of a trinaty or quatrinary system, a binary system will always be able to be more stable.
'ON', 'OFF' will *always* be superior to 'ON', 'KINDA ON', 'KINDA OFF', 'OFF'
Date: Wed, 26 Dec 2001 10:38:34 -06000 387abs.htm
From: Jeff Epler
To: steve@trinary.cc
Subject: Trinary adder efficiency
Do you know of any more efficient trinary adder designs? I've found an
online abstract of a paper that may have some, but I don't have access
to the paper itself:
http://www.computer.org/proceedings/ats/7129/7129
Also, do you know if a "balanced trinary" adder (-1, 0, 1 trit values)
is any simpler than your trinary (0, 1, 2) adder?
I also performed a simplistic comparison of the proposed full adder on
your website against a binary full adder at
http://www.play-hookey.com/digital/adder.html
I compared number of gates and number of gate delays for a 64 bit binary
adder and a 40 trit (slightly smaller range than 64 bits) trinary adder
designed from each full adder. These aren't open-and-shut cases, since
they don't answer questions such as the relative size and speed of
trinary gates to binary gates in a particular process, but I think they
may raise some interesting questions about circuit design than the
proposed "minimize m*n for given m^n" measure.
In your adder, I count 17 gates + 3 muxes at 15 gates each for 47 gates
per trit, or 1880 gates for a 40-trit adder. I count 5 gates per bit,
or 320 gates for a 64-bit adder in the binary case. Thus, at least
in adders for numbers in this range seem to be significantly larger
for trinary. (won't this advantage always exist as a constant factor?)
In your adder, I count 7 gate delays for the MUX operation, giving a
count of 14 gate delays for the "result" path and 11 gate delays for the
"carry" path. In the binary full adder, I count 2 and 3 delays for
the paths. This gives 443 gate delays for the trinary adder, and 191
gate delays for the binary adder. (again, won't this advantage exist for
numbers of any magnitude with the same constant factor?)
By either of these measures, it's hard to see trinary logic as a "win".
I haven't investigated more complex adder designs (carry-lookahead adder
and its trinary counterpart, if any) or more complex ALU operations
(multiplication/division, floating point) to see if the advantage binary
shows here exists in other operations as well.
If the real "win" of trinary is in external pin-count, then another good
option would seem to be to use trinary (or even 4-state) logic for
I/O, and convert to binary before entering the main logic of the chip.
4-state logic would have easy binary conversion, and if trinary inputs
were chosen, encodings such as 6t->9b, 7t->11b, 9t->14b, 12t->19b (#
trits -> # bits) could be chosen. (You need 3**n to be just larger than
2**m, where you can also build efficient converters for that width
number)
One last thought -- when we convert all our old COBOL programs from
binary computers to trinary ones, we'll have to face the horrible
encoding "TCD", where each decimal digit will require three trits.
Thus, numbers up to one million would require 18 trits, compared to 24
bits. Using the 'm*n' measure, the bits solution wins (24*8 = 48
18*3 = 54)
Thanks for taking the time to read this far -- if you've addressed these
points on your website, I hope you'll let me know where (I read much of
it, but not the whole thing by any means).. thanks for the interesting
website, and I hope you're not drowning in messages after the recent
magazine article and publicity on a certain geek website...
Jeff
Hate stupid software on freshmeat? Laugh at
We have 10 fingers, 10 toes, etc. We can handle base-10 math easily, but not base-2 math.
Maybe you only use your 10 fingers to count to 10, but any self-respecting geek will use those 10 fingers to count, in binary, up to 1023 by using both states of their fingers to represent a one or zero (up or down). A base-1 system on your fingers is just a waste of states. With some practice you can even handle the unusual states like 21 and 27 easily (I use my thumb as 2^0).
Things you think are in the Constitution, but are not.
You have to worry a lot more about intermediate states.
Consider a ternary machine. There are three states-- represented, let's say, by 0V, 3V, and 6V (yes, I know, this probably wouldn't be the case-- work with me).
To go from the 6V state to the 0V state (or vice-versa), the signal will momentarily pass through the 3V state. While this may not seem like a big deal, you need to consider what it could mean when that intermediate state is active-- entire parts of a ternary CPU could be activated.
Mind you, if every subsystem is watching the clock like a hawk, it makes it a lot easier. But it's still another design consideration that makes ternary (and quaternary) computing a LOT more complex than binary computing.
Not only that, but binary logic has some convenient tie-ins with various branches of math, notably number theory. Mersenne primes would be a royal pain in the ass in ternary (though quaternary logic wouldn't be bad, I suppose). Similarly for the square-multiply exponentiation algorithm.
Not to say that non-binary computing doesn't have potential, but there are going to be a LOT more changes to consider than simply "how large a number will fit in a 32-trit register".
Food for thought.
Here's why (I think) the minimum of m*n is considered optimal:
Each additional "base" value takes more complex circuitry (base 2 being the simplest).
But for small values of the base, we need more "bits" to represent a given value. A single hex value can represent the same number as four binary values.
Those of us old enough to remember using octal notation probably remember wishing that getting to 7 as a largest value was getting close, but not quite, to 9.
Binary (base 2) was adopted in the early days of computers because (1) electronically it was very easy to design circuits that either were saturated (max current) or cut-off (zero current), and (2) Boolean algebra had been around for 200 or so years, making the transition straightforward (although not easy).
It's been a long time since I took a semiconductor course, but I would think that a tri-state logic circuit (using -1.5V, 0V, and +1.5V, for example) should be fairly straightforward today.
Yes, truth-tables and such would become much more complicated, and de-Morgan's theorem would be relegated to the scrap heap, but it would seem to be a way to continue to increase processing power once Moore's Law begins to poop out as feature sizes become sub-atomic.
Moore's Law itself could continue, just taking advantage of better technology to move to quad-bit, penta-bit, and so forth, computing.
In deference to those who might be easily offended, I have abstained from using the obvious acronym for a 3-state digit.
A move to multi-valued logic provides more computational capability without the standard increase in die size or transistor count.
yeah right.... lets just move to near infinite values to have near infinite computing from the same transistor count! Shannon and Nyquist be darned!!
forget probability ... ... quantum physics is wrong :-)
... many systems simply exist beyond the limited scope of binary logic and are almost incomprehendable in such frameworks.
... can you comprehend this in a 2-state logic ?
... so simple, that we are not able to comprehend it fully :-)
you are right
reality is not binary.
much confusion comes when separating right/wrong,
truth/false
there are no absolute truths !
acording to quantum theory YOU change the state of an electron simply by looking at it
if we cannot decribe even simple quantum phenomena using 2-logic how could we ever dream of decribing more complicated things ?
nature is simple
(Exponential Growth = Unbreakable) => Tripe
I hate to add fuel to this sort of fire, but is Moore's "Law" a law, or an "observation"? They are not equivalent.
"...historical trend that hasn't been broken in thousands of years." - What codswallop. In a theoretically infinite universe this may be the case, but real life is never that simple. Exponential growth of velocity - diminishing returns as you approach the speed of light. Exponential population growth - always a ceiling....
I could go on and on - but I won't.
Q.
Insert Signature Here