Tern - Ternary Logic Circuits

Sometimes you just have to do things the hard way. Or at least I do. I was thinking over different ways to arrange the 5 gate(simple inverter) and P gate(buffer) to possibly arrive at the XOR and XNOR gates. Then is struck me. Why the heck am I building buffers?!?! You stick a 0 in, you get a 0. Duh.

I just built a Max gate using nothing but two diodes. I guess I'll have to test the 8 two-input gates I already built and re-do the schematics replacing all the P gates with diodes. That sure does make things easier in the long run.

I guess I was just so busy patting myself on the back that I totally bypassed the obvious ;)

After having built my first 8 two-input logic gates, I needed to figure out what to name them. The first four, Min, Max, Antimin, and Antimax came from Dr. Jones' work here. The next four were nameless, but very similar to the first four. I realized I didn't really have a full grasp of the relationship between binary and ternary and needed to learn a bit more about "-arity" as an abstract. This took me into symbolic logic.

In symbolic logic a binary system has 16 different "connectives". These are what we know as the logic gates. Mathematicians call them connectives because they connect statements. For example: Joe ate apples AND oranges. The logic gate is the connective. In a ternary system, nobody could ever hope to name all 19,683 connectives, but each of the binary connectives does have an analog in the set of ternary gates; a ternary gate "most like" the binary connective. This was mildly interesting and since looking over the subject had revealed the very useful datum that I had a functionally complete set of gates, I decided to look deeper and find the ternary gate that corresponded to each of the 16 binary connectives.

For two inputs, P and Q, these are the 16 connectives.

In a ternary system the first 6, Tautology - Negation Q, are trivial and consist of connections to signal reference voltages, the buffer(P), and the simple inverter(5). The next 8 are combinations of the buffer and simple inverter. The final two, Exclusive Disjunction and Biconditional are a bit more complicated and I have not built them yet.

With the possible exception of XOR and XNOR, I can build all of the ternary equivalents to the binary system with nothing but combinations of the buffer and the simple inverter. I already know that The Min gate, Max gate, and the monadics "Is False", "Is Unknown", and "Is True" form a functionally complete set, but Min and Max are combinations of the buffer and the simple inverter. So really, just those five monadic gates are a functionally complete set. I'm highly suspicious that I'll be able to make the ternary equivalents of XOR and XNOR with just the 5 and P as well.

The interesting thing about the first four two-input gates I devised (Min, Max, Antimin, and Antimax), was that they were just combinations of monadic gates 5 and P. Specifically, two 5's (Antimin), two P's (Max), two 5's passed through a 5(Min), and two P's passed through a 5(Antimax). This is important later.

Because I already had this set up on the breadboard I tried mixing the first set of 5's and P's to see what truth tables I would get out of them. I found four more interesting gates and eventually learned that the 5-P gate is called Implication, P-5 is called Converse Implication, 5-P followed by an inverter (another 5) is called Nonimplication, and a P-5 followed by a 5 is called a Converse Nonimplication. Here are the truth tables.

Implication

Converse Implication

Nonimplication

Converse Nonimplication

And the schematic is here.

As a byproduct of trying to figure out what these gates should be called, I learned some pretty fundamental things about what I am trying to do with ternary logic that I was unaware of. I took a deep dive into symbolic logic to figure it out, but that's another post for another time.

It seems that the project has just achieved functional completeness! In doing a little algebra study, I ran across a proof showing that the Min gate, Max gate, and monadic gates 2 (Is False), 6(Is Unknown), and K(Is True), form a functionally complete set. To put it simply, any of the 19,683 two-input gates can be formed from combinations of these five gates. Since I've already built each of them in the real world I can now rest easy knowing that, if the mood struck me, I could build any ternary circuit imaginable using only what I have already demonstrated to work {high-five!}.

If anyone is interested, the ternary (actually, any-valued) equivalent to Boolean logic is Kleene logic. There are other competing logic systems (who would have guessed!) but I'm following the naming conventions of Kleene logic because it seems the most sensible to me. Sure that's arbitrary. Sue me.

The first four two-input gates are done! They take a bit of explaining but are roughly equivalent to AND, OR, NAND, and NOR. The reason I say they are only approximations of those familiar binary gates is because the words AND and OR (and the phrases NOT AND and NOT OR by extension) are meant to be descriptive of the binary truth tables for those gates. Unfortunately they fall short of describing ternary gates. Allow me to demonstrate with the binary truth table for an AND gate.

The output is high when A AND B are both high. The name of the gate describes how it behaves. Ternary gates are significantly more complex, and those binary names break down because they do not adequately describe the function of the gates or the name could be used to describe many different gates with similar truth tables. Here is the ternary truth table for the gate most closely approximating AND.

Okay, the formatting doesn't look so good, but the first row of "- 0 +" on top is the "B" input and the first column on the left is the "A" input. The 3x3 square in the bottom right is set of 9 possible results for the given A and B inputs. Example: If input A is 0 and input B is +, the result is 0 (far right column, second from the bottom).

As you can see, calling this gate AND is somewhat accurate because if both inputs are the same, the output will be the same as the two inputs. Unfortunately AND doesn't cover many of the other conditions. If A is a 0 and B is a +, the result is a 0. Obviously we need more accurate names, so here they are:

• AND becomes Min (minimum), the result is always the lower of the two inputs.
• OR becomes Max (maximum), the result is always the higher of the two inputs.
• NAND becomes Antimin, the result is the simple inversion of Min.
• NOR becomes Antimax, the result is the simple inversion of Max.

Remember that the simple inversion (Monadic gate 5) leaves 0's alone but swaps -'s and +'s.

If you look back at the binary truth table for AND, you will see that the more general name Min works just as well for the binary gate as it does for the ternary one. The same is true of the other three examples here.

The Antimin (NAND) is two monadic 5's (simple inverters) with their outputs tied together. Max (OR) is two monadic P's (buffers) with their outputs tied together. Min (AND) is just an Antimin who's output has been passed through a simple inverter and Antimax (NOR) is a Max gate passed along to a simple inverter.

Now is a good time to mention that even these conventions are not standardized. For example, one source on the internet who was investigating ternary universal gates used the term NAND to describe a different gate entirely. His quite reasonable logic was that the basic description of NAND was "True when inputs differ, else rotate to next value" and assigned that to a ternary truth table where all outputs were + except for when both inputs were + (output would be -) or when both inputs were - (output would be 0). His work is here and is quite interesting. My terminology continues to be based on this.

Enough wordage. The schematics and truth tables are here.

Now that I've met my first milestone; the documented implementation of all 27 monadic gates, it's time to move on. Obviously the next step are the familiar, and some not so familiar 2-input gates. This will not be a comprehensive listing since there are 19,683 two-input ternary gates compared to the measly 16 two-input binary gates.

However, in working them out on paper (really, with a pen and stuff) I have come to the realization that even my space-saving comparators are just too bulky for the task. For example, a 1-trit multiplication circuit would require 8 comparators, meaning 4 LM319's. That would take up an entire breadboard when you add in the power circuitry. Or how about the circuit to handle the carry trit in a ternary adder? Thats 13 LM319's... just for the carry trit. [Edit: These estimates were hopelessly naive. Since writing this log entry I have worked out much more efficient versions... at least on paper].

While I do still intend to build up implementations of the simpler 2-input gates like AND, OR, NAND, and NOR using LM319's, I am now officially looking for denser solutions. At this point I am looking for parts that will either replace or simulate my comparators. Some ideas I've had so far:

-Cypress PSoC's. They have configurable analog circuitry, part of which is a collection of comparators and Op Amps. Would have to buy Windows. ::Sigh::

-Power monitoring chips from Linear. They have a few chips that monitor different voltage inputs and you program them to activate and deactivate output pins based on the voltages they are monitoring. This could effectively simulate a collection of comparators. Unfortunately, they are surface mount and something like $20 per chip.

-Anadigm field programmable analog arrays. Probably the best possible solution from a technical viewpoint... but it's $200 for a dev board and I would have to buy a copy of Windows.

-Configurable or programmable comparator arrays. Does such a thing even exist?

-Just saying F$#&-it and using pins on a micro to simulate the behavior of ternary gates. Not elegant, and I'd probably get accused of cheating, but it may come down to that. I hate the idea that I would be just simulating a true ternary system... but what are you gonna do?

-Busting out Design Workshop 2000 and laying down the masks to send to a foundry. Oh yeah, and paying them a few mil in the process.

I'm officially asking for suggestions.

Monadic gates N-Z are now re-tested, verified, and the schematic is done up neatly in it's final form. The link is here.

Okay, debugging is under control now and I've re-verified gates A-M. The completed schematic is now up here. Gates N-Z should be done soon as well and I can move on to 2-input gates like AND, OR, NAND, NOR, etc.

::Sigh:: It's awesome when you waste every minute you have available for a project for almost a week trying to figure out why you keep destroying chips and then discover it's because your breadboard has shorts in it.

Okay, I've re-tested each gate from 0-9 and documented them properly. This "final" version includes a correction to one of the gates (I don't recall which) so it should definitely be used instead of earlier versions of the schematics. The remainder of the gates will be posted in the near future. Here's the link.