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?"

Comments

Truth Tables * n?

[RobertB-DC]

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?

Re:Truth Tables * n?

[26199]

You're a relic, I'm afraid ;-)

Binary operations can be carried out by considering whatever values you have to be binary numbers, and working from there. Binary operations would probably have to be implemented like that somewhere, because they're quite useful...

Implementing binary operations using any base which isn't a power of two would, I suspect, be extremely painful...

But arithmetic and other operations wouldn't have to be based around binary logic; it seems like the circuits might get horribly difficult to reason about, but with decent computerised tools that's hardly a problem...

Re:Truth Tables * n?

[Saeger]

But it has definate advantages, beyond the Moores law tripe.

Tripe? Where do you get that from? Moore's observation about the exponential growth of transistor count is just a specific case of the more general Law of Accelerating Returns.

Exponential growth isn't tripe-- it's historical trend that hasn't been broken in thousands of years.

--

Re:Truth Tables * n?

[mindriot]

I think the whole point is not about changing the boolean logic, but merely changing the representation of numbers, such as considering a number as octal and thinking of the values 0..7 as different voltages. Building an adder of course requires new logic circuits, but no one will take away boolean logic from you.

Besides, there exist many non-binary logic ideas with AND/OR etc. operations (such as the ternary Lukasiewicz logic), even continuous logic (see, for instance, the lecture slides here -- German unfortunately), but they are /not/ Boolean as they can not satisfy the Boolean axioms.

So, for you writing software, nothing changes really... but internally, numbers would be represented differently. (Of course, when switching a whole CPU to n-valued calculation, you still need a way to do simple Boolean calculations since that is needed for conditionals.)

Sounds like a good idea.

[digital bath]

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?

My mind is too used to binary :) But I'd be willing to learn..

Sounds like a good idea.

Re:Sounds like a good idea.

[Sparr0]

How about + voltage, no voltage, - voltage? Thats the most basic way to implement ternary logic into electrical circuits.

Power

[overshoot]

The big limit on device complexity and speed now isn't transistor count, it's power. CMOS and related gates have relatively low power because when they're conducting they don't have (much) voltage across them and when they have voltage across them they're not conducting (much).

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.

Binary logic

[OneIsNotPrime]

Actually yes, Boolean functions such as AND, OR, etc., typically accept binary input, but logic tables can be created for functions with ternary (or quarternary, etc.) input.

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.

Re:Binary logic

[The_Laughing_God]

While higher-base number systems might have "special case" uses someday, it's important to understand that they are mere steps on the continuum to analog. This trivial seeming fact has some surprising consequences.

Binary, being the lowest base that can represent any integer mathematics, is not a point on the continuum, it is a defining terminus of the continuum, and has many special properties. Termini (endpoints) often do, especially in one-ended ranges (e.g. base two is the lowest number of sates, but in theory analog has an infinite number of states, and any real-world instantiation of an analog computer can only be an approximation.) One example of an open-ended range where the sole endpoint has unique properties is the prime numbers (which, properly, must be positive integers): the lowest prime, 2, has so many unusual properties that it is often excluded or dealt with as a special case. it is believed (but not quite proven) that there is no highest prime

This may sound trivial or like mealy-mouthed gibberish, so here's an example:
In every multi-state binary-like computer, division is computationally 'harder' than multiplication except base two!

Any algorithm for general division (by an arbitary divisor) involve more multiplications (and then subtractions, according to the results of implicit trial and error subtraction [branchpoints]) than a corresponding extended ('long form') multiplication. The reason this does not occur in base two is that multiplications by the two binary digits 1 and zero is so trivial that it does not need to actually be performed - a compare and branch suffices, which corresponds to the compare and branch preceding the additions of a binary multiplication.

This is pretty special. While multiplication and division are inverse function, full generalized division is always 'harder' than generalized multiplication. This is quite unlike, say, subtraction, where a 'subtraction circuit' can be constructed to perform subtraction exactly as easily and in roughly the same number of, say, transistors as an adder.

Binary math has many special properties in group and number theory. We'd lose those in higher base math, and we wouldn't gain new properties to make up for that loss. Two, the low bound, is special.

Just base 3 or 4? How about base pi, e, i, 1,...

[dwheeler]

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 :-).

Balanced Ternary, and Ternary circuits

[Sparr0]

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.

Re:Trinary Computing

[DataPath]

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).

Aymara

[fven]

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.

Important detail about truth tables

[Sparr0]

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.

Fuzzy Logic

[Corpus_Callosum]

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?