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.
Didn't the Soviets already do this? I don't remember it catching on very splendidly, though I guess than can be chalked up to the limitations of the times.
Auto-reply to ACs: "Truly, you have a dizzying intellect."
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
For reference, Slashdot has done two other stories on ternary computing here and here.
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?
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,
Do you think three-valued logic is a good idea?
#define FALSE 0
#define TRUE 1
#define MAYBE 2
Hate me!
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.
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)
Well, if the word "bit" is a contraction of "binary digit", then I'm all for a move to "ternary digits". We need a lot more of those in this field.
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 quaternary system would be perfectly suited for women:
0 = No
1 = Yes
2 = No (But I mean yes)
3 = Yes (But I mean no)
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.
Base 3 or higher are a lose for implementing logic. Base 4 is useful in some kinds of memory, and this has been done by Intel since around 1980-81. Intel used a quaternary ROM (two bits per cell) for the microcode store of the 43203 Interface Processor, and (IIRC) for the 8087. More recently this technique has been used in flash memory.
Hence, making such transistors would allow chip makers to make huge strides in speed without having to handle the engineering problem of packing in more transistors.
No, they'd just trade the engineering problem of packing more bits into once space with finding ways of unambiguously interpreting a value.
See the whole power of binary (pardon the pun) has always been it's wonderful noise-suppression ability. Imagine a copper wire running 2 miles with either a 5V or a 0V signal on it. You can apply a simple analog device (say a BJT transistor amplifier) that utilizes an exponential function switching at some precisely known voltage (we'll call it 2.5Volts). Voltages before and beneath this voltage are amplified to either zero or 5V exponentially, such that only voltages within a small delta of the threshold voltage have any ambiguity.
Thus you can determine the likelyhood of noise on a line, then put digital amplifiers every so often such that no amount of noise will be sufficient to raise or lower the voltage to the ambiguous region.
The same is true even on micro-scopic wires; Fanning transistor outputs out to too many transistor inputs introduces noise on the wire. CPU's not surprisingly utilize "buffers" which are trivial 2 transistor logic gates which pass the output to the input. This cleans the signal just as the higher-powered digital amplifiers do.
While I'm not sure which particular technologies are being considered in this trinary/quatrinary logic system, if it is nothing more than a sub-division of voltages, then it's doomed to failure for general processing, and possibly even simple memory storage. First of all, you introduce another whole region of voltage ambiguity. The only way to maintain your safety zone is to up the voltage or provide more amplification stages to garuntee a cleaner signal. But the trend has been to decrease, not increase voltages (lower power consumption, smaller devices, whatever), and adding additional logical devices merely to interpret a signal means that your bit-density is going to suffer.. Exactly impeeding it's whole point.
Likewise for denser bit-storage, since the probability of bit-error necessarily increases (all else being equal), then you're not as likely to achieve as small or as dense a physical digit. So unless you can at least achieve less than 1.5x logical-digit spacial expansion (due to error-compensating material), you haven't gained anything by going to a trinary system.
Lastly, the concept of >2 digit computing already has a particular niche where it's trade-offs are acceptible.. Think of 56k modems which encorporate dozens of thousands of "values" for a single digit. They utilize a full 256 voltages for each anticipated time-slice. Of course the analog modem can't anticipate the exact sampling point where the analog phone line gets digitized (happening to transition at that point can be bad), and there is usually a tremendous amount of line noise. But what modems wind up having to do is group several time-slices together and produce a macro-digit with a but-load of error-correcting pad-values. And that's not even enough; the entire packet is still likely to have misrepresented digits, so CRCing and thereby retransmission is often necessary.
All this effort is worth it because we physically realize extra bandwidth.. But such a "probabalistic" solution (prone to bit-error) is unacceptable at the lowest level of computation. You can't get any less error prone than binary (given the above discussion), and mathmeticians have shown that base-e (2.717) is the optimal number to balance complexity of the number of combinations with the number of digits in a given number. (analogously demonstrated by considering an automated phone system where you have to wait to hear 10 possible choices per menu (the base-10), and you have to go through k menu levels to achieve what you want. The metric is the average wait-time using different bases, and mathmatically the shortest wait time was the
-Michael
(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
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.
Say you wanted to add an 8 bit field - bits 0-7, to another, bits 8-15, and store the result in a 9 bit field, 16-24.
Search as follows (CC Field is Carry):-
Whew. You have added the LSBs of the fields together, in 6 operations. There are 8 more to go. However, you have done it for the entire array which might be thousands of records.So there is a fixed processing time for parallel operations on all the data.
We still had to use two input lines to represent the Ternary value, but, remember, no address lines needed.
Content Addressable memory chips are also used for lookaside Cache memory in CPUs today.
Cheers, Andy!
Andy Rabagliati