Slashdot Mirror
Ternary Computing Revisited
Black Acid writes: "American Scientist's Third Base was a nice introduction to the advantages base 3 but didn't really explain ternary computing. Since 1995, Steve Grubb has maintained trinary.cc which covers many aspects of computing with base 3. Not only are the basic unary and binary gates enumerated, which I independently verified as being basic building blocks, but real-world circuits are described also. Half and full adders, multiplexers and demultiplexers, counters, shift registers, and even the legendary flip-flap-flop are all covered with ternary algebra equations and schematics. Steve Grubb touches on problems of of interfacing to binary computers elegantly, although no schematics are given. Perhaps most impressive are the Transistor Models - schematics of the basic gates which can be built from cheap parts available at your local electronic component store."
does ternary processing mean you will be using on, off, and some third state of electricity? "dim"?
--
fight global cooling
If a Bit is short for Binary Digit...
Does that mean that a Ternary digit is a 'Tart'? Do 8 Tarts make a 'Tight'?
We could be having MegaTights of Ram, and GigaTights (or even TeraTights) of disk!
Tony
However, in stodgy old binary, the levels are typically something like 0 Volts (i.e. "off") and 5 Volts (or 3.5 Volts). A "typical" ternary system would add a negative voltage, like -5V (or -3.5V), since that's easier to detect reliably than an intermediate positive voltage value.
So to answer your question, yes a "third state of electricity" is used, one which was previously being ignored in binary circuits. Instead of on, off, and dim, think of positive, off, and negative.
This is all nice, but if we have to go to all the effort to reinvent the wheel , why not go all the way, I mean if we have to come up with all new components and software why no go the Analog route ?
Digital computing gained popularity for many reasons, cost effective to build, easy to program, with the state of current electronics this is no longer neccesarly the case but we there ,
Analog copmuting has many advantages over digital computing, especially in the AI arena, Since there can never be a digital concept of infinity
Rockets in the beggining were put into orbit using ANALOG computers, there is a reason, accuracy to the nth factor.
I played around with analog computing in the 70-early 80's cool stuff if more would have been available, fact wsas everyone was happy with their 8 bit pc.
Trinary computing sounds a little like taking something that was settled on in the first place and resettling again
I mean come on isnt the goal of computing to have a supercomputer take control of our national defense grid when it becomes sentient ?
Sig went tro...aahemmm.....fishing........
One of the engineering problems w.r.t. trenary computing is how to have a crypto algoritm for trenary computing, since all of the modern crypto schemes assume binary computing.
One of the nice things about the Rijndael crypto algorithm is that, becuase of its "wide trail strategy" design, it is easy to adopt to different environments, including trenary computing.
I am sure that a variant of Rijndael which does everyting in "trits" instead of "bits" would have the same security features as the current Rijndael algorithm. The only thing that would have to be re-invented is the sbox. The rest (changing the galois field to a 3-base instead of a 2-base galois field, and chainging the MDS matrix used) could be simply adopted.
- Sam
The secret to enjoying Slashdot is to realize that it should not be taken too seriously.
Easy answer: Signal to Noise ratio renders ternary logic useless. Either it comes at a slower speed than binary logic or at higher power consumption.
In addition - the site design doesnt make it look very credible..
Maybe this "doesn't effect your day to day job", but it is an interesting computer science article. Apparently you want a site that's "software news for developers, stuff that matters only to a very narrow audience".
If you'd get your head out of your ass, you'd realize that most of technology comes from building on the past; that's why it doesn't usually make the news. Technology has always been marked by gradual refinements, occasionally interrupted by large leaps.
"Dude, check this out. So I'm reading this news site for nerds, right, and I see this article on computers that work on some "base 3" kinda deal. So I'm like Damn! Those PCs can get to third base! I wonder if I can learn some tips from em?"
"So I call one up and we agree to meet out at Woody's on 4th. And this PC never shows up. So I just keep drinking, waiting for it. I musta had too many because all I know is that I woke up in this apartment on 84th with these three midgets screaming at me in portugeuse."
"Damn unreliable computers."
------
Let me give you the lowdown
Err how would that be broken exactly by a move to base3. Guess what you can represent base 2 directly in base 3. In the same way as working in base 10 doesn't break on a base 2 machine. The definition of & etc are within the specification of the language, to take advantage of the base 3 processor you'd need base 3 operators and base 3 syntax for those operators (if x, else y, else). It would not break anything that currently exists.
I'd ask for a refund on that college education if I were you.
An Eye for an Eye will make the whole world blind - Gandhi
Naturally, such systems get enhanced so they can send more data at the cost of a little harmonic purity. For expample, they could get 50% more data through by using pairs of trits to send 3 binary bits. The 9th state would be used to prevent leaving the line at one voltage level too long. The real encodings are better behaved in the analog domain, and therefore more complex, but lookup tables for the trit to binary conversions take very little silicon.
For those who haven't memorized powers of three, if trinary logic, memory or signalling works better in some situation, 1 trit holds 1 bit, 2 trits hold 3 bits, 12 trits hold 19 bits, 31 trits hold 49 bits, etc...
Going the reverse is also very simple. If you have an algorithm that works better in trinary, store 1 trit in 2 bits, 3 trits in 5 bits, 5 trits in 8 bits, etc... You don't need special hardware.
Electrically, implementation is inevitably binary, at its core... electrical comparisons of boundary conditions. "Trinary" is just a minimal case of "analog", with all of the same disadvantages.
You want the same noise margins? You'll have to double your voltage. That means you're cutting your speed in half. So overall you're taking a loss because at half speed you could have gotten two whole bits for your money instead of one lousey trit.
Not to mention the fact that you're using more power, switching between these trinary states due to the longer transition and detection times. Oh boy! Hotter chips! Bleah!
Looking at the schematics I see that it is based on a analog design style. The transistors are bipolar and there are plenty of resistors used for biasing. All in all, it looks more like an amplifier than a digital gate.
A previous poster commented on returning to analog computing. While there are several major problems with analog computing, I want to just mention a few.
High Implementation Cost
Currently, resistors are considered a somewhat "expensive" item in VLSI designs, since they use a lot of area and lead to static power dissipation. Using bipolars instead od MOSFETS is probably a mistake from a fabrication standpoint, but I don't see why the schematic couldn't be modified to take this into account.
In other words, any design using these gates would be big and power hungry. This isn't to say that a base-3 system is infeasible, only that this implementation doen't map very well to existing technology.
I think a MOSFET only implementaion would be required before we can take base-3 really seriously. Maybe something using depletion mode MOSFETS would work better.
No Component Architecture
Analog components are difficult to interconnect. Without going into too much detail, they don't just snap togeater like legos; rather, each brick must be modified slightly depending on what it connects to.
The schematics shown also exibit this problem; the author freely admits it. While I feel that this problem could be partially solved by automated tools, it is still a big hassle. Not just because I'm lazy either. Many tools operate using O(n ln n) or even O(n^2) algorithms. Increasing the time constant or adding unnecessary coupling means that the tools won't finish their production times for very long periods of time. A Xilinx FPGA synthesis run, which is comparativly simple, can allready take several hours to complere. This hurts the design cycle time, since even small changes can require a full recompile totaling hours. No telling how long it would take to make a full microprocessor - many days I am sure.
A true digital design, by contrast, does not exibit this problem. Again, I don't feel that this problem is insurmountable. The problem here is all those resistors whose values must be changed. Remove them and remove the problem as well.
Problem with interconnect
One more problem is that in most modern designs the design area is dominated by interconnect. Active areas (made of real transisotrs) are connected by routing channels, and the channels are getting to be quite large. Ternary logic doesn't exactly help with this, since we now have three power rails. This is at worst a second order problem though, since it doesn't really increate the interconnection between any two components, just the interconnection between all the components.
Underdeveloped logic family
While on the topic of power rails, I can't help but wonder about the clock. It seems underutilized. What should a negative (-1) pulse on the clock do? Or the control lines on a flip flop. Take a D-type flip flow for example. if load=1 loads a new value, and load=0 hold the old value, what does load=-1 do? load an inverted value perhaps? Until clocking a flip flop behavior is defined, I don't see any complete designs coming out. These ideas probably just need some more "brain time".
Error Correction and Asthetics
Lastly, let me say what I do like. The fundamental advantage of digital gates are that signals can be regenerated. In a five volt system, if you have a 4.89 volt signal, it is probably supposed to be a 5.00, so the gate boost it up and passes it on. This means that error do not propogate. This is the essence of Digital design.
The ternary design style we see is not incompatable with this notion. In binary, The decision is made around the transisors meta-stability point, typically 2.5V. This means that the fundemental decision is to determine if a signal is [ s>2.5V ] | [ 0V ] | [s
Sure this sort of thing is "interesting", but what is the actual benefit of writing applications in HLL that are then compiled down to this instruction set or that ?
You are rather arrogant, aren't you? I care about this kind of stuff because I don't write applications. I build hardware. You don't seem me bitching about MAME running on the XBox. I could use your same "who cares" argument by saying "No kidding, its a PC. Let's stop wasting our time with that. Its 'interesting' but nothing new."
So I am sorry if it bothers you that Slashdot appeals to a broader audience than code monkies (which apparently you are and the other 99% of the people that read slashdot are not).
This isn't "Stuff that matters" its "irrelevant stuff to pass sometime"
God, a statement like that just makes me boil.
This is yet another example of the desire for "new or different" over getting hands dirty and improving what is there
You don't even know what a trinary system is, do you? Its exactly dealing with improving what is there already. By having 3 different states, we could significantly increase the rate with we transmit serial data. (Which is idea that just popped into my head.) Its a lot faster to detect two distinct voltages than two that are very close.
Ah, no one cares about you anyway. Go back under your rock.
To quote the core argument of the article:
Evidently we need to optimize some joint measure of a number's width (how many digits it has) and its depth (how many different symbols can occupy each digit position). An obvious strategy is to minimize the product of these two quantities. In other words, if r is the radix and w is the width in digits, we want to minimize rw while holding r^w constant.
This may be an "obvious" strategy, but is it a useful one? A modern computer typically contains hundreds of millions of digits in base two. According to this theory, the cost of a computer (ie, the value we are trying to minimize) is equal to the radix times the width. If this is true, we can reverse the radix and the width to get a system that has precisely the same cost: thus, a machine that stores one hundred million digits in base two costs the same as a machine that stores two digits in base one hundred million, because two times one hundred million equals one hundred million times two.
In practice, building an electronic computers capable of distinguishing between one hundred million distinct voltage levels is a practical impossibility. Early attempts to build machines that had just ten distinct voltage levels were abandoned, not because of any theoretical arguments about data density, but because these devices turned out to be extremely difficult to manufacture and notoriously unreliable in operation. A computer with one hundred million distinct voltage levels, if it could be built at all, would certianly cost several million dollars to construct, and it would probably require a special power supply and several pounds of electromagnetic sheilding. It would certianly not "cost the same" as a typical desktop computer.
Even if we were to ignore the absurdity of the basic premise of the theory, and take for granted that the trinary computer is better than binary in some abstract way, there is still no compelling reason to switch. We have already invested billions of dollars into binary technology, and the benifits of that investment are undeniable. If you think companies like Sun and Apple has a hard time selling theoretically superior hardware in a market dominated by cheap PC clones, imagine how much harder it would be to introduce a computer that is so fundamentally incompatable that it does not even work with binary data. The dominance of the Windows platform proves that people don't want theoretical perfection: they want something that gets the job done, they want it to be cheap, and they want it now.
Consider again the task of representing all numbers from 0 through decimal 999,999. In base 10 this obviously requires a width of six digits, so that rw=60. Binary does better: 20 binary digits suffice to cover the same range of numbers, for rw=40. But ternary is better still: The ternary representation has a width of 13 digits, so that rw=39. (If base e were a practical choice, the width would be 14 digits, yielding rw=38.056.) so the theoretical approximate is less than 2% efficiency increase. But what they don't say is that it takes 2 operantions to distinguish a ternary system: v < 1 ? 0 : v < 2 ? 1 : 2 as oppose to binary: v < 1 ? 0 : 1 In the real world you can't do "equal to" because there is the potential for infinite precision -- you can always measure more closely. And you can't measure on/off, because then your circuit is dead and no further calculations can be done. You can't use positive/negative, because you want three. So you need something that can detect voltage levels. The problem is, that if such a device can be created that distinguish 3 different voltage levels, and do so more efficiently than using to binary operations (see above ternary notation :) -- it could also be used to perform 2 binary operations which doubles the efficiency of the binary system
rw = 40 / 2 = 20
almost twice as efficient as the ternary circuit.
A friend of mine who's into digital pro audio looked into building logarithmic audio gear, but the recording industry went to 24-bit linear instead, which provides more headroom.
One big disadvantage of trinary is the number of transistors involved. I don't know if the author's schematics were minimal or not, but his inverter required 2 transistors and 5 resistors. A standard CMOS inverter requires 2 transistors and *zero* resistors. On top of that, the transistors were BJT (Bipolar Junction Transistors), not CMOS which are what current most common.
The other functions will take a lot more real estate if realized in trinary too. The Full Adder he had listed has 20 gates of varying complexity, that would take at least 2 transistors per gate, probably resistors as well considering his schematics. A binary/CMOS implementation can be done in about 30 transistors.
One of the professors in our department has been doing some heavy research into computations using more than one base. The idea goes like this:
- 6 = 2^1 * 3^1
- 18 = 2^1 * 3^2
- 231.67 ~= 2^3 * 3^3.0637
Keep in mind that there are many possibilities for your mapping (he's developed optimizations for finding good mappings)Obviously this isn't a universal solution, but think about DSP hardware, where multiplications are expensive and needed all the time. Not to mention exponentiation for cryptography. Also, this brief explanation doesn't do justice to the full potential/applications of DBNS. A lot of work has gone into it.
If you want to find out more about DBNS, there is a primer at www.rcim.ca/Research/Video_Rate/DBNS/, miscellaneous papers at people.atips.ca/~eskritt and a collection of a few published papers at www.atips.ca/research. Also, some older presentations are archived at wooster.hut.fi/geta/courses/graham/Applications/.
Disclaimer: I'm the web guy for our research group at the U of Calgary. The guy who came up with DBNS is a professor here (Dr. V. Dimitrov).
Actually, I used base3.org and changed to trinary.cc when the cc domain opened up. Before base3.org, it was available from my personal homepage at gate.net.
-Steve grubb
The last time ternary logic came up, I was disappointed to see no proposed schematics. Now there are schematics, but I'm still disappointed. One thing is that they designed with bipolar transistors rather than CMOS -- you cannot put more than a few thousand bipolar transistors on one chip without serious heatsinking... Beyond that, these designs lack quite a lot in speed, power consumption, and reliability as compared to even the 7400-series of TTL bipolar logic chips of the late 60's. And the first one I looked at doesn't even work.
Their ternary inverter is simply a two-transistor inverting _analog_ amplifier running on +/-3V supplies. If the input is -, Q2 turns on, bringing the base of Q1 low, turning Q1 off, so R2 pulls the output (which isn't explicitly shown) to the + rail. If the input is +, Q2 is off, and apparently this circuit depends on leakage to then bias Q1 on. This brings the output almost to the - rail. So it would work as a binary inverter. It's not nearly as good as a
TI 7404 (see page 2). The major difference is that R2 was replaced by a transistor, which turns on for high. This speeds up the low-to-high transition, since you get the full output current of the transistor until the output node is charged up. It also saves power, because one
output transistor is always off and the other always on, so when not switching only leakage currents flow at the output. (This two transistor output is called a "totem pole", and CMOS similarly depends on transistor pairs, one always off so little current flows.) Two more intermediate transistors are added, to control the top transistor on the totem pole and to reduce the resistor count. (On-chip, resistors are not cheaper than transistors.) But if you used it as a binary circuit, trinary.cc's inverter is basically the stripped-down ancestor of the 7404 circuit.
As a trinary circuit, it also has to take a 0V input and output 0V. This inverter does not do this reliably. It probably could be made to work by adjusting the resistor values until 0.0V in gave 0.0V out, but warm or cool the transistors a few degrees, and the amplifier bias will shift so that the output swings to the + or - rail. When you are trying to put the mid-level through it, you are running it like an analog amplifier, and analog amplifiers are unstable without negative feedback.
Nor would adding a few transistors and a negative feedback loop to stabilize it make it work well enough. A trinary inverter should take an input that is not right at any logic level, decide which level is closest, and output the corresponding nomimal voltage. For highs and lows (2 and 0), it does that, since it pins the output to the opposite rail. But even if you can be sure that 0.0V in = 0.0V out, with a circuit that is basically an analog amp, -0.1V in will give more than +0.1V out. So a chain of gates would allow the logic levels to get worse at each gate, until the mid-level became misinterpreted as + or -. To restore the mid-level would take a much more complicated circuit. I lay no claims to being a good designer at the transistor level, but I can't see any possibilities that are not nearly twice as complex as the corresponding binary circuits.
Any trinary machine can mimic a binary machine simply by getting rid of one of its states. So if we switch to ternary, the first ports of crypto libraries will just be binary libraries running on ternary machines.
Second, separate theory from implementation, please. Very few areas of information theory and cryptography are dependent on base-2. That'd be counter to the entire point of math, which is to think abstractly enough that the principles apply to any base. Your statement is sort of like saying "moving from base 10 to base 16 is hard, since we learn arithmetic in base 10 and we'd have to relearn all our arithmetic". It's just not the case. A + B = B + A, no matter what base you use. And likewise, the integer factorization problem and the discrete logarithm problem are damn hard no matter what base you use.
Implementations are highly dependent on binary systems, yeah--but that's only because we only have binary computers right now. As soon as someone comes up with a ternary computer, rest assured, Blowfish and 3DES and RSA and El Gamal and AES and all sorts of crypto goodness will be running on it in no time flat.
Think about this one for a moment. Computers are Turing machines. We write in Turing-complete languages.
But there's nothing in the definition of a Turing machine which requires that it be binary, trinary, or base radical two. The Turing machine doesn't care.