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?"
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."
The whole concept of AND/OR/NAND is a Boolean construct. The gates define the 16 functions that can be expressed by two boolean variables. Ternary or quarternary logic would more basic functions, and different ones, but it would be easy to implement boolean logic as well (like your quarternary example).
Try reading this for a quick primer.
It wont happen all at once, its a different paradigm and a definate learning curve, like the difference between imperative, functional and object oriented programming. But it has definate advantages, beyond the Moores law tripe.
I don't need no instructions to know how to rock!!!!
For reference, Slashdot has done two other stories on ternary computing here and here.
Er. That's q for quantum, not q for quaternary.
I hope that was a joke :-P
> The Star Trek chronicles prove we will be using a quaternary system. How many gigaquads of hard drive storage do we need, anyway?
A "quad" does not refer to "quaternary," but is just a unit of storage space. It it not known how many bytes are in a quad.
It is common knowledge among trekkies that the term was invented specifically to avoid describing the data capacity of Star Trek's computers in 20th century terms. It was feared by technical consultant Mike Okuda that any such attempt would look foolish in just a few years, given the current rate of progress in that field.
The unofficial
No.
Qubits are bit which can be zero, one, or zero AND one both at the same point in time (although, in order to be measured they must collapse down and become either zero or one).
Here's a link to what you're talking about:
Third Base
It's a good read, stuff I didn't know until I read your post and looked it up =)
~Berj
To distinguish between more logic levels, you'd have to increase the voltage level, and power is proportional to the square of voltage.
I have studied little multi-value logic. In m-valued logic: AND is minimum. OR is maximum. XOR is complement modulo m A friend of mine that was doing testing of multi-value circuits (purely theoretical work, of course) said that some phenomena are seen "more clearly" when the base is bigger than 2. HTH.
Theres one small problem with this is that anyone who knows basic physics and logic design circuits that operate on voltage base would be impossible as you can not creat instantainious changes in voltage as it violates basic physical laws of capacitance (as the capacitance across 2 devices is = to 1/2 the capacitance multiplyed by the voltage squared and the only way for there to be an instantaious change across the 2 would be for there to be and infinite power supply). The only way in order to create a system with more then 2 stable states would be to use a different method for measurement such as measureing changes by useing lightbeams.
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.
However, look at it this way. The voltage differentials were able to drop from 2.5 volts to 0.75 volts (actually, even less than that inside modern microprocessors) because circuits got that much better at overcoming noise and detecting precise voltages. If you can detect a differential of 0.5 volts that you can go ternary without bothering about noise.
Besides, you're wrong. People have built digital systems with non-binary number systems. There are flash memory chips that use a 4-level voltage scheme to increase data capacity.
A deep unwavering belief is a sure sign you're missing something...
IIRC from MAT/CSE460, trinary (-1,0,1) is great for multiplication and division but sucks at addition and subtraction. With the opposite being true for binary (special cases like powers of 2 excepted).
I also thought the great advantage for transistors was speed (and power savings as a previous poster noted). You can drive one into cutoff or saturation very fast.
The phrase is "hear, hear". Saying it wrong makes you look like a dumbass. Dumbass.
Picture a system with:
1/3 power = 0
2/3 power = alpha
3/3 power = 1
Now consider the case of recursion where each iteration must be deffered until the one above returns - by using uncertain values instead you may be able to perform a range of forward-possibilty operations upon the as yet indeterminant numbers.
When the higher order recursion results eventually (lets assume) returns a value that determines the alpha value all that is required is to create a specific instance of the generalised results.
I like the concept - and it seems it could easily be integrated on the same die as a standard ternary chip.
Q.
Insert Signature Here
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
Most logic circuits, from an analog perspective, are amplifiers. Rather than operating in the linear region, however, these amplifiers, are overdriven to force the output to rail at one extreme or the other , producing a high or low voltage level (0 or 1). CMOS works particularly well iunder these conditions because, in steady state, only a small leaskage current flows through the circuit when it's railed. As the author indicates, you can design logic by comparing a voltage to a fixed threshold, such as in ECL, CML, SCFL, etc., but these circuits are based on differential amplifiers, which typically burn significant current at all times. Not to mention that it's difficult to imagine a circuit which can generate more than to voltage values that does not use significant current at all times. Therefore, it seems the price of non-binary logic in most cases is increased power, which is not a trade-off anyone's willing to make (Flash RAM is an exception because of it's unique nature).
Vote for Pedro
Umm... But if you want to store numbers 0..1000, you need 32 states (2+10+10+10) for decimal systen, 20 states (10*2) for binary, and 21 for ternary (7*3).
...
So I say that that reasoning does not prove that base 3 is 'more efficient'.
Btw what does 'more efficient' mean in this context: less power usage? lower cost? more girls?
--- Hindsight is 20/20, but walking backwards is not the answer.
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