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.
Aren't quantum computers built around quaternary logic using qubits instead of bits?
Never eat more than you can lift -- Miss Piggy
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
I don't see why software would have to deal with
quarternary logic at all.
Currently the assembler- hardware logic is already an abstraction (microcode).
If only the main busses (address bus, data bus, and their modern counterparts) would simply use that, and elementary pieces like barrelshifters would
be quaternary, one could severely limit the number of lines (and thus transistors)
However it could be that because of tolerance problems quaternary logic elements have to be larger, and thus don't yield the big benefit one would expect.
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,
It has to do with the decision part of a logic gate. To take an OLD example, in 7400 logic, 3.8V and above is "1", .8 and below is "0", anything else is considered ambiguous.
All that would have to happen is for a middle range to be established: 2-3V is "2".
But why stop there? You could have a base10 system by making further divisions. It depends on your ability to differentiate between the various voltage levels.
You could even have a system wherein a multi-volt circuit checked to see what kind of input it was receiving, and adjusted its decision levels accordingly.
Back-wards compatible, in other words.
A tertiary system could get hooked up to a binary hard drive and still have the hard drive work. It would just work like a binary processor.
hook it up to a base7 operating system, and it adjusts on the fly.
The only downsides I can see would be that there would be no more bit-"ANDing" or "ORing", etc. It'd be straight math from here on out.
Also, if you were on a battery system, and your battery levels died slightly, it could mean catastrophe. RF interference could be an issue to.
Oh well, just my $(2e-2)
Then we will never have to check for "NULL" ever again. :)
... especially in the realtime world.
Also, I want to work on a computing system wherein *every* single data has its own timestamp.
I've been experimenting with 64-bit processors in this regard - using regular 32-bits for data, and the remaining 32-bits as a timestamp - and it has produced some interesting results. Treating *all* data as though it has a 'last modified' timestamp...
If computing systems can be designed to take Time into account with every single operation, it can make for some interesting changes in the programming paradigm
; -- the corruption of government starts with its secrets. a truly free people keep no secrets. --
Actually I would think -1 : less than 0 : equal to 1 : greater than Would make sorting interesting.
It's hard to break out of binary thought since the traditional AND/OR in computer science mimic the English language usage of these terms, but in reality one could create any logic table and assign it a name. The fact that AND/OR have clear English meanings confuses the issue when we try to apply them to ternary input; we might as well call the functions FuncA, FuncB, etc. and define the logic tables arbitrarily, then pick those which are commonly useful and give them more definitive names.
Note that the size of a logic table increases geometrically with the number of possible values of each input. 8 bits have 256 possible values, but a group of ternary transistors has 6561 possible values, and quarternary would have 65536. As you can see, this number explodes very quickly. 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.
---
WARNING:Slashdot karma not redeemable in the afterlife.
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)
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.
But I don't think this fact has any important practical consequences. If you store something on a CD, you would obviously be able to fit the same amount of data on the disk, regardless of what base you use. Of course, if you could use another technology (one dot on a CD being a value in a different base, not just on or off), then decimal would be much better than ternary. ;)
Of course, if you are talking about processing information (CPU vs. RAM), ternary system is a little bit better, but the advantage over binary is very small, IIRC - about 10% may be. Not worth the hassle, I would say, unless there are other advantages.
Future Wiki -- If you don't think about the future, you cannot have one.
The reason for doing work in trinary computing is that it is closest to the theoretically optimal computing base. The reasoning was something like this:
Representations of numbers in a particular base have two defining characteristics - the number of values that can occupy a digit (m), and the number of digits it takes to represent that value (n).
(Here's where the theory takes a leap, at least to me) The most efficient base (or simplest) base for performing computations is the one at which the m*n product is minimized. As an example, we'll take THE ANSWER, 42(base10).
THE ANSWER in base 16 has a result of 16*2=32
THE ANSWER in base 10 has a result of 10*2=20
THE ANSWER in base 8 has a result of 8*2=16
Here are the interesting cases, though:
THE ANSWER in base 2 has a result of 2*6=12
THE ANSWER in base 3 has a result of 3*3=9
THE ANSWER in base 4 has a result of 4*3=12
IIRC, according to the article I was reading, the most effective base is actually "e" (euler's constant).
Inconceivable!
The problem I see with this is:
Already our processors are dissipating a serious amount of heat. This heat is developed only during the switching time.
Picture a cpu clock:
_|-|_|-|_|-|_
Haha, something like that. Anyways, the heat is only developed during the vertical bars of that clock. (Because the vertical bars arent perfectly vertical in the real world and that P(heat)=VI. During the horizontal bars, only V or I are present, so no power, ie: no heat)
I dont exactly know how this ternary or quaternary computing works, but if its forcing the transistor to work in stages between full off and full on (1 and 0), you will be increasing the heat output by your cpu exponentially.
Correct me if im wrong on this, but maybe we'll really need those diamond semiconductors to make this feasable for high computing power applications.
It's easier to fight for one's principles than to live up to them.
e is an irrational number. How do you get e possible choices for a single digit?
Ternary computing could be quite useful for asynchronous logic. The three states would be 1/yes, 0/no, and n/(no answer yet).
Basically you want the truth table to be, in order of precedence:
0 AND * = 0
n AND 1 = n
n AND n = n
1 AND 1 = 1
(OR is the reverse, swap 0 and 1)
NOT 1 = 0, NOT 0 = 1, NOT n = n
Gates can be actually made to follow the right truth tables by diddling your substrate voltages in an otherwise fairly standard CMOS design; this has the effect of making your circuit twice as slow or quadrupling its power consumption though, which sucks. You also have to watch your noise thresholds here, transients can be nasty although they are unlikely to propagate far through a network of n's. This can be mostly fixed by further tinkering with thresholds, but then the leakage current becomes prohibitively high.
You can also just design extra logic with standard gates and watch your glitches very carefully.
There may be cleverer ways to do this, or the savings of asynch might be enough to make it useful anyway.
I hereby place the above post in the public domain.
Think about it: male/female, life/death, something/nothing; it goes back ages into daoist philosophy, and you all know the yin/yang, right? If there was no male/female, we'd all be at a bacterial level. Now look closer at the 1 and the 0. 1 = phallus, 0 = hole (vagina).
And when you get down to the quantum level (and correct me if I'm wrong (and I'm sure you will), because I'm no quantum physicist), you find that electrons sort of blink in and out of existence -- you can only measure them in terms of probability of them existing at a certain point in time. It seems like reality as we know it is based on a binary system.
Add to that how computers are affecting just about every way of life, even after being around a mere half century. There's some sort of big interconnectedness going on here, I think. Binary all the way.
c-hack.com |
The aymara people have used trivalent logic for thousands of years. It allows precise definition of "maybe" or "possibly"
There is a great writeup of these people and their logic at:
http://www.aymara.org/biblio/igr/igr3.html
The article mentions that it is very difficult to impossible to express the logic of one culture in the language of another. Thus to understand better the inferences in Aymara logic, we have to resort to mathematics, which is sufficiently general to be understandable and translatable.
It's closer to an observation than a Law, since scientific laws are usually mathematical descriptions of our worldly observations. e.g. I can observe that an apple falls "faster and faster", but Newton's Laws describe that motion more precisely (and Einsteins theories go a step further by attempting to explain, rather just describe what he observed).
Exponential growth of velocity - diminishing returns as you approach the speed of light.
The Speed of Light would *be* the Singularity in the case of the evolution of transportation (unless you count some future hyperspace possibility as the Singularity, but you're not really moving through space then, but slipping between it).
Exponential population growth - always a ceiling....
Yes, there's a ceiling on the number of physical human bodies that can occupy a sustainable planet Earth. But we'll be expanding outward into space, as well as inward into virtual space at an ever increasing rate.
I think you're maybe confused about the definition of the technological Singularity. It isn't a truly infinite blackhole-type singularity in the mathematical sense of the word, but rather an amount of change so vast that current human minds can't comprehend.
A quote from Kurzweil's Law of Accelerating Returns:
--
Power to the Peaceful
As I said in this post, it doesnt have to be like that. You're still thinking two dimensional.
eg
* red, green, blue
* apples, lemons and bananas.
All perfectly unique, all one move away, no intermediate transitions. The trick is finding an electrical equivalent.
Another analogy is to imagine points in space - eg trinary could be a set of points in two dimensional space, quaternary logic a set of points in three dimensional space etc.
One important thing to remember about truth tables is that the number of operands (the numbers you give to a function to get an output) for a given operator is NOT always the same as the base. For base two you have two operand operations, which we all know as AND OR XOR, but you also have operations that require only one operand, the common NOT (1->0, 0->1) and what I will call EQV (1->1, 0->0). There are also 9 more two operand truth tables that you see in varying degrees of extreme rarity, f/e the following arbitrary truth table that you will never see in practice:
A B out
0 0 1
0 1 1
1 0 0
1 1 1
Apply this to base 3 and you find that there are not just 3-operand operations but 1 and 2 as well. For one operand you can have a rotate-down(0>2,1>0,2>1), shift-down (0>0,1>0,2>1), rotate-up (note that in binary one-operand rotation happens to coincide with NOT), shift-up, and various arbitrary tables like the one above. For two operands you have NeitherBoth (00>0,01>2,02>1,10>2,11>1,12>0,20>1,21>0,22>2), and the arithmetic operators, plus a bunch of others with explanations i cant think of right now. For three operands there are thousands of possible truth tables, many with useful explanations, many many more arbitrary ones. Oh, and for both 2 and 3 operands you have multiple partial or complete counterparts to the traditional binary AND OR XOR that apply the same kinds of rules to the operands.
You're a relic, I'm afraid ;-) ... Binary operations can be carried out by considering whatever values you have to be binary numbers...
Heh.. I hate to break this to you, but your thinking is a bit behind the times as well...
Multivalued logic = Fuzzy logic
The most common AND and OR operations in Fuzzy Logic are min() and max() that together form the basis of a De-Morgan Algrebra (only the law of excluded middle [A AND NOT A = 0, A OR NOT A = 1] must be thrown out)
AND(A,B) = MIN(A,B)
OR(A,B) = MAX(A,B)
NOT(A) = 1-A
Generally, a trenary logic is composed of { 0, 0.5, 1 } where each value is the "degree" or "belief" in TRUE.
0 = FALSE
0.5 = UNKNOWN
1 = TRUE
Some of you may recognize this from SQL (yes, SQL does actually have a simple trenary fuzzy logic base).
The truth table ends up looking like this:
0 AND 0 = 0
0 AND 0.5 = 0
0.5 AND 0.5 = 0.5
0.5 AND 1 = 0.5
1 AND 1 = 1
0 OR 0 = 0
0 OR 0.5 = 0.5
0.5 OR 0.5 = 0.5
0.5 OR 1 = 1
1 OR 1 = 1
NOT 0 =1
NOT 0.5 = 0.5
NOT 1 = 0
If we move from trenary to any other precision, the rules stay the same and the table is easily derived ( min, max, 1- ). Generally, it is prefered to always have a 0.5 value, because UNKNOWN is actually a useful truth indicator. The next set after trenary that makes sense is not 4-value-logic (because it would exclude unknown), but instead 5. For instance:
0 = FALSE
1/4 = UNLIKELY
1/2 = UNKNOWN
3/4 = LIKELY
1 = TRUE
At this point, some truly interesting approximate reasoning is possible, although going to 15 values or (ideally) handling multivalue logic as analog until storage/retrieval would be much better. Approximate reasoning is one of the many things that fuzzy logic makes possible. Essentially it is the application of fuzzy logic to determining beliefs where certainty is not important (and in fact the lack of certainty is where the power of such a system comes from - being able to continue computing without full knowledge, only belief)...
The idea of signals that are analog flying around on a semiconductor, instead of digital, yet time discreet in the same way as digital signals is quite interesting and could probably be done quite easily. Anyone have any ideas on how a min(A,B), max(A,B) and (1-A) operation might look on silicon?
The reason that it can be true that 1+1 > 2 is that very peculiar nonzero value of the + operator
I've started a rule of thumb whenever I see a slashdot article on the upper limits of computing. This rule is activated even more rapidly if I see the phrase "Moore's Law". The game is I simply say to myself "How does this compare to the human brain?"
For example the poster for this article asked "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?"
So we're wondering about the upper limits of processing operations and the power expenditure. Is the sky the limit? Will we have to use something besides binary? I saw some posts saying ternary logic wasn't very practical because more interconnection requires even MORE power.
The human brain can peform on the order of perhaps trillions of operations per second.
The human brain can do this with about 20 watts of electrical power provided chemically.
NOT BAD!! So what logical circuitry does the brain use for this?
Electrically, brain cells are either firing or not firing. 1 or 0. That sounds kind of like binary. But we also know that they connect with and are connected to 1000s of other neurons, which have a summing effect on whether they fire or not. That sounds more like a very large-base number system. So the brain sort of combines a manageble width with a large depth.
Anyway I just wanted to chime in that when it comes to pondering alternate calculation methods like ternary math, we would do well to at least think about reverse engineering the human brain's logical circuitry. And when it comes to thinking about the upper limits of computing, we should remind ourselves that we are competing with (and losing to, for now) a glob of salty fat that still outperforms our sillicon processor equivilants by orders of magnitude with less energy. If the brain can do it, so can we.