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
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.
"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
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
This works for base-2 just as well, as you see the operations are exactly the same.
Please consider making an automatic monthly recurring donation to the EFF
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.
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.