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?

[stratjakt]

The whole concept of AND/OR/NAND is a Boolean construct. The gates define the 16 functions that can be expressed by two boolean variables. Ternary or quarternary logic would more basic functions, and different ones, but it would be easy to implement boolean logic as well (like your quarternary example).

Try reading this for a quick primer.

It wont happen all at once, its a different paradigm and a definate learning curve, like the difference between imperative, functional and object oriented programming. But it has definate advantages, beyond the Moores law tripe.

Re:Truth Tables * n?

[Maimun]

I have studied little multi-value logic. In m-valued logic: AND is minimum. OR is maximum. XOR is complement modulo m A friend of mine that was doing testing of multi-value circuits (purely theoretical work, of course) said that some phenomena are seen "more clearly" when the base is bigger than 2. HTH.

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?

[b!arg]

Perhaps they would be Abort, Retry, Fail?

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

The Star Trek chronicles...

[Anonymous Coward]

...prove we will be using a quaternary system. How many gigaquads of hard drive storage do we need, anyway?

Trinary Computing

[Liselle]

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.

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

Re:Trinary Computing

[isomeme]

The most effective base being e is not coincidental. Consider that the number of digits required to represent a number is proportional to the log to the base in use of that number. Since e is the base of the natural logarithms, with the property that the slope of the curve e^x equals e^x for all x, the product of a base and the logarithm of any number to that base will always reach a minimum for base = e.

Re:Trinary Computing

[Snorpus]

Here's why (I think) the minimum of m*n is considered optimal:

Each additional "base" value takes more complex circuitry (base 2 being the simplest).

But for small values of the base, we need more "bits" to represent a given value. A single hex value can represent the same number as four binary values.

Those of us old enough to remember using octal notation probably remember wishing that getting to 7 as a largest value was getting close, but not quite, to 9.

Binary (base 2) was adopted in the early days of computers because (1) electronically it was very easy to design circuits that either were saturated (max current) or cut-off (zero current), and (2) Boolean algebra had been around for 200 or so years, making the transition straightforward (although not easy).

It's been a long time since I took a semiconductor course, but I would think that a tri-state logic circuit (using -1.5V, 0V, and +1.5V, for example) should be fairly straightforward today.

Yes, truth-tables and such would become much more complicated, and de-Morgan's theorem would be relegated to the scrap heap, but it would seem to be a way to continue to increase processing power once Moore's Law begins to poop out as feature sizes become sub-atomic.

Moore's Law itself could continue, just taking advantage of better technology to move to quad-bit, penta-bit, and so forth, computing.

In deference to those who might be easily offended, I have abstained from using the obvious acronym for a 3-state digit.

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.

Ternary

[Anonymous Coward]

For reference, Slashdot has done two other stories on ternary computing here and here.

Re:Ternary

[borgboy]

So, /. has done 3 stories on ternary logic?

Ternary system is the way to go

[a_ghostwheel]

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?

Re:Ternary system is the way to go

[Andorion]

Here's a link to what you're talking about:

Third Base

It's a good read, stuff I didn't know until I read your post and looked it up =)

~Berj

Re:Ternary system is the way to go

[Mechanik]

Here's a link to what you're talking about:

Third Base

There is just something funny about the concept of Slashdotters needing to follow a hyperlink in order to get to third base...


Mechanik

Its not a smart move at all

[Grieveq]

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.

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.

So, if you flip a coin

[civilengineer]

you can get either heads, tails, abdomen or heart!

Re:Qubits

[Anonymous Coward]

No.

Qubits are bit which can be zero, one, or zero AND one both at the same point in time (although, in order to be measured they must collapse down and become either zero or one).

Survey ...

[BabyDave]

Do you think three-valued logic is a good idea?

1. Yes
2. No
3. Maybe

Ternary programming would rock!

[Dark Lord Seth]

#define FALSE 0
#define TRUE 1
#define MAYBE 2

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

[maraist]

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.

No, they'd just trade the engineering problem of packing more bits into once space with finding ways of unambiguously interpreting a value.

See the whole power of binary (pardon the pun) has always been it's wonderful noise-suppression ability. Imagine a copper wire running 2 miles with either a 5V or a 0V signal on it. You can apply a simple analog device (say a BJT transistor amplifier) that utilizes an exponential function switching at some precisely known voltage (we'll call it 2.5Volts). Voltages before and beneath this voltage are amplified to either zero or 5V exponentially, such that only voltages within a small delta of the threshold voltage have any ambiguity.

Thus you can determine the likelyhood of noise on a line, then put digital amplifiers every so often such that no amount of noise will be sufficient to raise or lower the voltage to the ambiguous region.

The same is true even on micro-scopic wires; Fanning transistor outputs out to too many transistor inputs introduces noise on the wire. CPU's not surprisingly utilize "buffers" which are trivial 2 transistor logic gates which pass the output to the input. This cleans the signal just as the higher-powered digital amplifiers do.

While I'm not sure which particular technologies are being considered in this trinary/quatrinary logic system, if it is nothing more than a sub-division of voltages, then it's doomed to failure for general processing, and possibly even simple memory storage. First of all, you introduce another whole region of voltage ambiguity. The only way to maintain your safety zone is to up the voltage or provide more amplification stages to garuntee a cleaner signal. But the trend has been to decrease, not increase voltages (lower power consumption, smaller devices, whatever), and adding additional logical devices merely to interpret a signal means that your bit-density is going to suffer.. Exactly impeeding it's whole point.

Likewise for denser bit-storage, since the probability of bit-error necessarily increases (all else being equal), then you're not as likely to achieve as small or as dense a physical digit. So unless you can at least achieve less than 1.5x logical-digit spacial expansion (due to error-compensating material), you haven't gained anything by going to a trinary system.

Lastly, the concept of >2 digit computing already has a particular niche where it's trade-offs are acceptible.. Think of 56k modems which encorporate dozens of thousands of "values" for a single digit. They utilize a full 256 voltages for each anticipated time-slice. Of course the analog modem can't anticipate the exact sampling point where the analog phone line gets digitized (happening to transition at that point can be bad), and there is usually a tremendous amount of line noise. But what modems wind up having to do is group several time-slices together and produce a macro-digit with a but-load of error-correcting pad-values. And that's not even enough; the entire packet is still likely to have misrepresented digits, so CRCing and thereby retransmission is often necessary.

All this effort is worth it because we physically realize extra bandwidth.. But such a "probabalistic" solution (prone to bit-error) is unacceptable at the lowest level of computation. You can't get any less error prone than binary (given the above discussion), and mathmeticians have shown that base-e (2.717) is the optimal number to balance complexity of the number of combinations with the number of digits in a given number. (analogously demonstrated by considering an automated phone system where you have to wait to hear 10 possible choices per menu (the base-10), and you have to go through k menu levels to achieve what you want. The metric is the average wait-time using different bases, and mathmatically the shortest wait time was the

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.

Noise Margin

[reporter]

When the voltage for digital circuits back in 1970 ranged from 0 volt to 5 volts, there was talk about using, say, a base-3 number system. Imagine how this system might be implemented. Digit 0 would be [0, 1.67) volts. Digit 1 would be (1.67, 3.33) volts. Digit 2 would be (3.33, 5.0] volts.

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.

Re:Noise Margin

[be-fan]

However, look at it this way. The voltage differentials were able to drop from 2.5 volts to 0.75 volts (actually, even less than that inside modern microprocessors) because circuits got that much better at overcoming noise and detecting precise voltages. If you can detect a differential of 0.5 volts that you can go ternary without bothering about noise.

Besides, you're wrong. People have built digital systems with non-binary number systems. There are flash memory chips that use a 4-level voltage scheme to increase data capacity.

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

Here, here!

[jemenake]

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.

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.

Perfect for women

[marvin2k]

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)

Re:It's commonly assumed that people are base-10..

[Mr. Sketch]

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

Base 3 or 4 logic is NOT smaller than base 2.

[Eric Smith]

A move to multi-valued logic provides more computational capability without the standard increase in die size or transistor count.

No, it doesn't. Let's see you design a 16-quat full adder that takes fewer transistors or less die area than an 32-bit full adder.

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.

I like the indeterminant ternary logic concept

[quinkin]

I have always felt (but my models have failed miserably so far) that combining binary with uncertainty to create an indeterminant ternary logic would be extremely useful for many rule-of-thumb applications (ie. pattern matching, fuzzy logic).

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.

Re:I like the indeterminant ternary logic concept

[dasmegabyte]

The problem with this is that fuzzy logic is no more ternary than it is in binary. Fuzzy logic is about effectively weighing options. With ternary logic, you've only increased your options by 50%. Fuzzy logic is generally probabalistic...which means it's nicest when utilized with sufficiently large integers or, more importantly, huge floating point numbers. Like a nice 64 bit quad.

Consider a typical "fuzzy" logic problem of when to stop a car. You want to weigh variables like the speed of a car, the amount of force to apply, distance to the stopping point and other options like the existance of pedestrians (generally, if there's people within 20 feet of your stopping point, like say at a bus stop near a stop sign, you'll want to slow down quicker at first but roll longer, to decrease the effect of a fluke accident).

Lots of variables. Lots of choice. Lots of probability to weigh. Having an extra option out of 3 does not help you. Having 64 bits to work with does.

I have a hard time coming up with problems in my line of software dev in which ternary or quaternary logic is any more useful than nested binary logic or some fun probability and calculus. Mostly because it's rare that I care about anything other than STOP or GO, ON or OFF. About the only time I do care is when I'm dealing with a database (YES, NO or NULL [no data])...all the rest of the time, alternative options are best handled with an enumerated type or a nice exception.

Anyway, it's all well and good to talk about ternary computing being 'faster' with less overhead, but it's never really going to take off. It will take at least an extra year to train engineers to use the new logic effectively and for them to learn the tricks...and in that year, binary computing will have doubled. And when you live in a world where most software isn't optimized anyway...waiting for a slightly faster logic system that 9/10 of programmers will merely treat as binary because it's easier to understand in more comfortable is a waste of everyone's resources.

Even the terminology is bad. True, false, alpha. Ugh. If P is sort of true, then kind of do q.

logic circuits don't like trinery and beyond

[geekee]

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

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.

Ah, some pedantic semantic conflict

[quinkin]

(Moores Law = A Law) => Tripe

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

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.

Associative processing

[andyr]

When I was at Brunel University on a post-grad course, we built chips for Associative Processing (pdf)> or Google HTML that inherently used Ternary logic. The main chip that we built was an Associative memory chip, that stored binary data, but was addressed by searching for data. There were no address lines. It was a wide field - 40 bits,(this was late 70's) and you presented a search term as Ternary data on the input lines. Each bit was 1,0,X - where X meant "don't care". You could add one field column to another, without any of the data exiting the chip.

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

Bits: C 1 1 1 1 1 1 1
Bits: C 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0
Find: X X X X X X X X X X X X X X X X X X # All rows
Writ: 0 0 X X X X X X X X X X X X X X X X # Clear output
Find: X X X X X X X X X 0 X X X X X X X 1 # 0+1=1
Writ: 0 1 X X X X X X X X X X X X X X X X # write 1
Find: X X X X X X X X X 1 X X X X X X X 0 # 1+0=1
Writ: 0 1 X X X X X X X X X X X X X X X X # write 1
Find: X X X X X X X X X 1 X X X X X X X 1 # 1+1=0 carry 1
Writ: 1 0 X X X X X X X X X X X X X X X X # write 0 carry 1

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!

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?