Slashdot Mirror
Ternary Computing
eviltwinimposter writes: "This month's American Scientist has an article about base-3 or ternary number systems, and their possible advantages for computing and other applications. Base-3 hardware could be smaller because of decreased number of components and use ternary logic to return less than, greater than, or equal, rather than just the binary true or false, although as the article says, '...you're not going to find a ternary minitower in stock at CompUSA.' Ternary also comes the closest of any integer base to e, the ideal base in terms of efficiency, and has some interesting properties such as unbounded square-free sequences. Also in other formats."
Ternary numbers are an interesting sidetrack and some similar techniques are used in fast chip-based systems to speed up adding (each bit also caries it's own overflow and sign bits, turning the classic serial add-with-carry into a more parallel operation).
It must be remembered that, for floating point numbers, base 2 is *the* most efficient representation, as argued in the classic paper "What Every computer Scientist Should Know About Floating Point Arithmetic" by David Goldberg. The deep understanding behind IEEE754 is a masterpiece of numerical engineering that is often overlooked, IMO.
As far as I know radio astronomers user 3-level data recording for their VLBI (Very Long Baseline Interferometry) data. One of the equipment was from JPL at Caltech lab. Their problem is to detect a weak signal in presence of strong noise. In this case, it doesn't make sense to do 8-bit digitization. Instead people do 1-bit, 2-bit digitization and average out many sample of data. They found that the recording efficiency was highest when they used 3-level digitization.
I myself worked on VLBI in the same lab but our machines were using 1-bit digitization (BTW, we used regular video cassette and somewhat modified VCR to record 7 GBytes on single 2-hour tape).
> comes the closest of any integer base to e, the ideal base in terms of efficiency
What does this mean? I'm pretty decent with numbers, but I've never heard e being referred to as the most efficient base. Anybody know any more about this? Math article somewhere?
Think about applying it to D/A and A/D conversion for AC signals. It could simplify a flash converter,a nd conversion to convention twos-complement signed integers can be performed by a hard-wired lookup table.
-jcr
The only title of honor that a tyrant can grant is "Enemy of the State."
One of the advantages of digital over analog is that between the 1 and the 0 you have a ton of space that you can consider an error so if your signal is distorted (long wires), you still know what's going on- and you know when you have an error in transmission. In fact, when you read a binary signal, you can have true, false, and no output. With 3 possible inputs, the neutral zones between accepted values would become smaller and would significantly increase chances of error. In fact, the higher the base you take, the less margin of error.
I agree that a practical ternary computer is unlikely. Rather, the value of the theory might lie in helping us to realize the shortcomings of the binary approach, and the way our familiarity with it molds our thinking. How many of us would have come up with the ternary solution to the coin balance problem?
Please donate your spare CPU cycles to help fight cancer and other diseases
Electron, proton, neutron
Up, down, top,
bottom, strange, charmed
blue, red, green
Yikes!
A really cool number system that is rarely mentioned is factorial base notation. What makes factorial base interesting is that all rational number are represented by finite factorial base numbers, and transcendental numbers like e and pi are represented by infinite but nonrandom factorial numbers. So, somehow factorial notation "captures" and "tames" the complexity of the real number continuum in a way that decimal notation can't.
--- even the safest course is fraught with peril
The entire theory "ternary is most efficient" hinges on the idea that the 'best' base is the one that minimizes digits per number * possible digits.
In other words, base 1000 has 1000 different possible digits, but will require very few digits to represent numbers compared to (say) base 2.
According to the article, the 'most efficient' base according to this property is base e (2.7182818...), which they round to 3. My retort is: who cares? Why on earth would you judge a base system by digits per number * possible digits?
Digits per number is important, obviously -- base 16 requires far fewer digits than base 2 to represent most numbers. However, the complexity of building hardware which can efficiently represent 16 different digits is overwhelming, which is why no computer (to my knowledge) has ever used higher than base 10. Even the early ternary computers used a pair of bits rather than genuine trits, because they didn't have hardware capable of representing three states.
I'd argue that minimizing the number of possible digits far, far outweighs the number of bits per number, as evidenced by the fact we all seem pretty darned happy with binary. Storage is cheap, meaning bits per number just isn't a significant measure anymore, whereas designing and building every part of the computer to use ternary rather than binary is an expensive proposition.
In short: the measure they used to prove ternary 'best' was pulled from their nether regions, not based on anything in real life. As such, the basic premise of the article is flawed.
ZFS: because love is never having to say fsck
I am shocked, shocked to discover that a fundamental computer architecture explored in the 1950's, rejected as unworkable, and forgotten is in fact unworkable.
The feeling that this induces has no word in English, but in Japanese it's called yappari.
Ternary number systems are specifically interesting in the case of "balanced ternary", in which numbers are represented using a {-1,0,1} base set (as opposed to {0,1,2}). The resulting system is symmetric, has a unique zero, and most importantly (for those of us who worry about this kind of thing) rounding a balanced ternary number is equivalent to truncating its last bit. Truncation of the ultimate bit is obviously more efficient then doing the standard compare routine.
The major part of creating efficient communications protocols is determining the probability of a bit error.
You have made some very good points, and the bit error problem is one of the big ones. When you go to ternary logic levels, you reduce the noise margin, so you have to slow down the clock and/or spread out the logic (more space) which offsets the gains you might get from ternary logic.
I once saw a point-to-point ternary logic data bus design that looked very clever on paper. It allowed simultaneous transfer of data in two directions on the same wires. Both ends of the bus were allowed to drive 0 or 1, and both ends watched the ternary logic level on the bus. If the middle state, "M", was observed, then the other end must be driving the opposite logic level.
This looks like a big win since the same wires can carry twice as much traffic than a normal binary bus, but the reality of noise margin made the bus impractical. The noise from the dynamic voltage swing between 0 and 1 made it difficult to reliably discriminate the smaller 0/M or M/1 voltages at high clock rates. The clock rate had to be slowed to less than half the speed of a binary bus which made the ternary bus lose its apparent advantage.
I won't even get into the headaches that ternary logic design would cause. It makes my binary brain hurt.
As long as we're turning the world on its ear, lets go all the way, and use triacs. We implement it (the tri-state gate, that is) like an inverter, more-or-less. These have two (non-linear ) on states plus off, and are just right for implementing an inverter. They'd probably be great for trinary logic, too.
I just dug out my old physical electronis book (Micro Electronics, by Jacob Millman, First edition), and can't find them in there, so here's a slightly less academic reference.
There might be some problems with trying to get the clock speed high enough to compete with the Intel/AMD marketing, though; it says that they can be triggered into conduction by high dV/dt.
See what I've been reading.
It may be difficult using conventional transitors, but an interesting approach might be a spin-valve transistor.
Simply put it's a transistor that has different transport properties for either spin up or spin down electrons. The Giant Magneto Resistive (GMR) head in your fancy new 100GB hard disk is a fine example of spin effects being used in every day life. A similar device could be used for doing base 3 arithmatic.
A while back I did some simulations (admittedly simple and first order) of seperating different spins without using ferromagnetic materials. Which are used in GMR devices and are basically nasty things to use in device fabrication that should be avoided if at all possible. I found that you can get pretty good separation from the geometry of the device and an applied external magnetic field. This was all done with device sizes and parameters that were reasonable (a few microns in size, not huge magnetic fields, etc) for real life.
Imagine a transistor with a single source and two drains one for spin up and one for spin down.
Not to say it would be easy, just that it's possible given a little ingenuity to make a transitor that has 3 states.
C is defined for a binary machine, like most programming languages (if they are defined properly at all). That's why it's hard to believe that we're going to see non-binary computing anytime soon. It would be very inefficient to reuse old software, making the theoretical effiency gain rather worthless. (Hmm, but this didn't prevent Intel/HP/et al. from developing the IA-64 architecture, may be they start trinary computing next?).
By the way, Ada does have support for trit operations (in some bizarre way), but this was merely an accident.
You really couldn't be more wrong! Ternary logic is at the basis of some of the hottest research in asynchronous logic design right now.
For instance, if you had a group of transistors that computed multiplication and stored the output in a register you might see the value of that register change several times until the computation was completed. Right now, the only way that you know a computation is complete is that logic is designed to complete an action in X cycles; as long as you feed in the data and wait X cycles you will get the proper result. Clock cycles can be waisted here, because a simple multiplication might be completed in a single clock while harder multiplications might take the full amount of time the logic area is spec'ed for.
Using async logic, this can be done much more effciently. The multiplication happens just as soon as input data is given and the next stage of the logic knows when the operation is complete because its wires has three states: 0, 1, and not-yet-done. As soon as all the wires are 0 or 1, the computation is finished (consequently, this is how input works to). There are no "wasted" clock cycles, stuff moves through the logic as quickly as it is completed.
Of course, there has been some debate whether three states are needed on each wire, or an just additional acknowledgement wire is needed (say 8 wires + 1 for an 8-bit computation block). But, believe it or not there are already patents for both methods!
I guess, by having true ternary logic on each wire, you could have logic that will grab a result just as soon as X% of the wires report they are done with the computation to get "good enough" answer if the logic is iteratively improving a problem.
-AP