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.
...prove we will be using a quaternary system. How many gigaquads of hard drive storage do we need, anyway?
Aren't quantum computers built around quaternary logic using qubits instead of bits?
Never eat more than you can lift -- Miss Piggy
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."
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
For reference, Slashdot has done two other stories on ternary computing here and here.
It's been a long time since I read an article about that, but AFAIK ternary system is most efficient in storing information (basically if you want to store numbers 0..700, you need 28 states (8+10+10) for decimal system, 20 states (10*2) for binary and 18 for ternary (6*3). This has something to do with 3 being closest to the value of e (2.718...) but I dont remember what exactly. Any /.-ers to fill in?
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.
Increasing the number of states requires you to increase the overall voltage required of the device to acount for noise in the system. So in return for more states you are running at a higher voltage and thus at a higher power consumption level. You still have the same problem.
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,
you can get either heads, tails, abdomen or heart!
New year Resolution: Don't change sig this year
Do you think three-valued logic is a good idea?
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. --
#define FALSE 0
#define TRUE 1
#define MAYBE 2
Hate me!
Yields an analog computer. Which is really a digital computer if you count individual electrons...
Now I am confused.
My rights don't need management.
will someone please think of the dialogs we will have to implement for this extended logic.
There will be no more
Yes No Cancel
Now it will be
Yes No Maybe Cancel
Yes No Maybe Dont_Know Cancel
Yes No Yes(but I mean no) No (but I mean yes) Maybe Cancel......
Do not try to read the dupe, thats impossible. Instead, only try to realize the truth
What truth?
There is no dupe
To distinguish between more logic levels, you'd have to increase the voltage level, and power is proportional to the square of voltage.
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.
Now, for a binary number system, digit 0 is [0, 2.5) volts, and digit 1 is (2.5, 5] volts. Clearly, the noise margin of the binary number system is much better than the noise margin of the base-3 number system.
Now consider the voltages of modern digital circuits. Consider a voltage range of [0, 1.5] volts. In a base-3 number systm, digit 0 would be [0, 0.5) volt. Digit 1 would be (0.5, 1.0) volt, and digit 2 would be (1.0, 1.5] volts.
For a binary number system, digit 0 is [0, 0.75) volt, and digit 1 is (0.75, 1.0] volt. Again, the noise margin of the binary number system is much better than the noise margin of the base-3 number system.
In fact, the noise margin of the binary number system is consistently 50% better than the noise margin of the base-3 number system. The noise margin of the binary number system is always better than the noise margin of the base-n number system, where n > 2. For this reason, engineers have not built and will not build digital systems with any non-binary number system.
The nice thing about binary systems are that they are either on or off. As gates and tracks get smaller, interference effects etc. become the limiting factor.
As we add more states, intermediate voltages, to the system, the difference between states becomes smaller, ie. the difference between states 2 and 3 in a ternary system is less than states 1 and 2 in a binary system.
Hence a binary system can be made smaller and denser than a ternary system and still work.
We may gain in logic density but lose out in physical density.
>Non base two computing is nothing new. But it is an
>idea that, for various reasons, never really caught on.
The various reasons not being so various; A binary system can be constructed in a much more stable fashion than can a trinary or quatrinary system. Everyone knows that 1 is not always exactly 5v (or 3v). Having several values confuses the picture even more
"but we have progressed enough that trinary systems are much more stable now!"
No matter what level of stability someone can get out of a trinaty or quatrinary system, a binary system will always be able to be more stable.
'ON', 'OFF' will *always* be superior to 'ON', 'KINDA ON', 'KINDA OFF', 'OFF'
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)
Well, if the word "bit" is a contraction of "binary digit", then I'm all for a move to "ternary digits". We need a lot more of those in this field.
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.
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.
- you have four grandparents, 2^2
Only if I dig them up.
http://jesus.everdense.com/
Date: Wed, 26 Dec 2001 10:38:34 -06000 387abs.htm
From: Jeff Epler
To: steve@trinary.cc
Subject: Trinary adder efficiency
Do you know of any more efficient trinary adder designs? I've found an
online abstract of a paper that may have some, but I don't have access
to the paper itself:
http://www.computer.org/proceedings/ats/7129/7129
Also, do you know if a "balanced trinary" adder (-1, 0, 1 trit values)
is any simpler than your trinary (0, 1, 2) adder?
I also performed a simplistic comparison of the proposed full adder on
your website against a binary full adder at
http://www.play-hookey.com/digital/adder.html
I compared number of gates and number of gate delays for a 64 bit binary
adder and a 40 trit (slightly smaller range than 64 bits) trinary adder
designed from each full adder. These aren't open-and-shut cases, since
they don't answer questions such as the relative size and speed of
trinary gates to binary gates in a particular process, but I think they
may raise some interesting questions about circuit design than the
proposed "minimize m*n for given m^n" measure.
In your adder, I count 17 gates + 3 muxes at 15 gates each for 47 gates
per trit, or 1880 gates for a 40-trit adder. I count 5 gates per bit,
or 320 gates for a 64-bit adder in the binary case. Thus, at least
in adders for numbers in this range seem to be significantly larger
for trinary. (won't this advantage always exist as a constant factor?)
In your adder, I count 7 gate delays for the MUX operation, giving a
count of 14 gate delays for the "result" path and 11 gate delays for the
"carry" path. In the binary full adder, I count 2 and 3 delays for
the paths. This gives 443 gate delays for the trinary adder, and 191
gate delays for the binary adder. (again, won't this advantage exist for
numbers of any magnitude with the same constant factor?)
By either of these measures, it's hard to see trinary logic as a "win".
I haven't investigated more complex adder designs (carry-lookahead adder
and its trinary counterpart, if any) or more complex ALU operations
(multiplication/division, floating point) to see if the advantage binary
shows here exists in other operations as well.
If the real "win" of trinary is in external pin-count, then another good
option would seem to be to use trinary (or even 4-state) logic for
I/O, and convert to binary before entering the main logic of the chip.
4-state logic would have easy binary conversion, and if trinary inputs
were chosen, encodings such as 6t->9b, 7t->11b, 9t->14b, 12t->19b (#
trits -> # bits) could be chosen. (You need 3**n to be just larger than
2**m, where you can also build efficient converters for that width
number)
One last thought -- when we convert all our old COBOL programs from
binary computers to trinary ones, we'll have to face the horrible
encoding "TCD", where each decimal digit will require three trits.
Thus, numbers up to one million would require 18 trits, compared to 24
bits. Using the 'm*n' measure, the bits solution wins (24*8 = 48
18*3 = 54)
Thanks for taking the time to read this far -- if you've addressed these
points on your website, I hope you'll let me know where (I read much of
it, but not the whole thing by any means).. thanks for the interesting
website, and I hope you're not drowning in messages after the recent
magazine article and publicity on a certain geek website...
Jeff
Hate stupid software on freshmeat? Laugh at
The quaternary system would be perfectly suited for women:
0 = No
1 = Yes
2 = No (But I mean yes)
3 = Yes (But I mean no)
Another poster provided trinary computing tutorial. On one of the pages for the introduction, the author writes:
As if we didn't lack sufficient sexual jokes regarding current computer technology. Now we have to introduce "trits" into the fray. Now we're going to have to explaing to our mothers that they're using 32 trit computers. Or stop people from laughing when we mention we like lots of trits.
I propose we quickly abandon this system in favor of quarternery logic. The possibilities for abuse of a trinary logic system (and its trits) are simply too many.
Join Tor today!
We have 10 fingers, 10 toes, etc. We can handle base-10 math easily, but not base-2 math.
Maybe you only use your 10 fingers to count to 10, but any self-respecting geek will use those 10 fingers to count, in binary, up to 1023 by using both states of their fingers to represent a one or zero (up or down). A base-1 system on your fingers is just a waste of states. With some practice you can even handle the unusual states like 21 and 27 easily (I use my thumb as 2^0).
Things you think are in the Constitution, but are not.
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.
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.
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
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
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.
Yeah, but decimal 132 or 891 tends to offend people, depending on how you define your states.
:P
Hint:
132 = 00100 00100
891 = 11011 11011
Besides, nearly half the states are uncomfortable for most people.
True geeks rely on their HP calc for math; manual calculation is for nerds.
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.
forget probability ... ... quantum physics is wrong :-)
... many systems simply exist beyond the limited scope of binary logic and are almost incomprehendable in such frameworks.
... can you comprehend this in a 2-state logic ?
... so simple, that we are not able to comprehend it fully :-)
you are right
reality is not binary.
much confusion comes when separating right/wrong,
truth/false
there are no absolute truths !
acording to quantum theory YOU change the state of an electron simply by looking at it
if we cannot decribe even simple quantum phenomena using 2-logic how could we ever dream of decribing more complicated things ?
nature is simple
(Exponential Growth = Unbreakable) => Tripe
I hate to add fuel to this sort of fire, but is Moore's "Law" a law, or an "observation"? They are not equivalent.
"...historical trend that hasn't been broken in thousands of years." - What codswallop. In a theoretically infinite universe this may be the case, but real life is never that simple. Exponential growth of velocity - diminishing returns as you approach the speed of light. Exponential population growth - always a ceiling....
I could go on and on - but I won't.
Q.
Insert Signature Here
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.
Bender: what a strange dream...I thought I saw a '2'.
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
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.
Unary logic. Also solves the pesky problems of users making mistakes.
--
Is that all there is to relationships -sex and robotics?