Close

Tritwise Operations... And Eating Crow

A project log for Ternary Computing Menagerie

A place for documenting the many algorithms, data types, logic diagrams, etc. that would be necessary for the design of a ternary processor.

Mechanical AdvantageMechanical Advantage 05/02/2019 at 07:360 Comments

I've been working on the subject of ternary logic and ternary processing for years on and off, but I haven't been doing so in such a methodical way as I am now. By approaching this in a more methodical and comprehensive way, I have discovered a rather a big error in my logic.

Until now, I've been assuming that with careful design, a balanced ternary system could be made that would still be code-compatible with a conventional computer. Of course I knew that the internals of the compiler would have to have some significant work done to both interpret new syntax and to target a new (and highly unusual) architecture. Nonetheless, I was sure that existing code could somehow be shoe-horned in to the new system. This looked hopeful right up until I started trying to incorporate bitwise operators into the running thought-experiment I've been writing up in these posts. I didn't notice the problem when going over the NOT operator earlier and I started to get a hint of it when trying to get bool's and kleene's to play nice together. I finally realized the scope of the problem when I got into bitwise AND, OR, and XOR.

Each operator is useful for a variety of different purposes because of how they manipulate the bit pattern of their operands. But in a ternary system, the operands themselves are ternary, so even if you kept the operators identical, they will come up with unexpected answers every time. Basically, anything that is expecting to work at the bit-level will be broken. Anything that expects to work at the register/word level or that has to do with control flow, can be made to work.

So, going back to the beginning with bit-level subjects:

1) bools should still exist. To follow logical expectations in a balanced ternary environment, their FALSE representation should be a -, not a 0. I still favor strict value-checking so that bools can only hold a - or a +, nothing else.

2) Bitwise NOT and tritwise NEG (negation) become the same operation. NEG switches -'s into +'s and vice versa but leaves 0's alone. Since bool's now use - for their FALSE condition and + for their TRUE condition, there would be no difference between NEG and NOT when using them on bools or kleenes. However, NOT would produce unexpected results if applied as a bitwise operator to other types of data, just like bitwise AND, OR, and XOR would.

3) The other bitwise operators such as AND, OR, XOR, and the various shifts, would have utterly different effects than they would in a binary system. The solution is not to try to force them into the system. The solution is to find equivalent tritwise operators that produce the results that programmers want out of the conventional bitwise operators.

4) This doesn't effect logical operations or arithmetic operations. Those are just fine as previously described.

I don't have a comprehensive list of which ternary operations would produce each of the results people are currently using bitwise operators for (except NEG of course). There are 19,683 different possible tritwise operators (not counting shifts), so that would be a job about 1,200 times more complex than coming up with everything in the "Hackers Delight" book from scratch and then writing a book about it.

Instead I'll write up the few I know of right now, and then as I find them or learn of them, I will do a separate post on any new "tritwise operator candidates". I say "candidates" because choosing which operators to implement in a real processor will be an important point. Digit-level operations generally take place directly inside the ALU, which means that independent circuitry has to exist in the ALU for every digit-level operator the processor is capable of executing. To avoid unnecessary complexity in the ALU it will be necessary to carefully choose which operations to include. Of course, any tritwise operations that are also necessary for arithmetic will be there anyways, so you get those "for free". The exception is the shift operations. Those are often done in a separate piece of hardware from the ALU. I'll look into shift operations in a separate post.

One other important factor to note is that not all of the two-input gates are symmetrical and could produce different results if the input and the mask are switched. In the below examples I am assuming that the mask is always input 'a' and the data being masked is always input 'b'. If both arrangements are useful it could be arranged to get an extra tritwise operator without any additional hardware in the ALU. It also means that if you were applying an asymmetric operator to two variables (instead of masking) then a <operation> b would produce different results than b <operation> a.

Free tritwise operators used in basic arithmetic. They may have other uses I haven't thought of yet:

Negation gate (5)

A Single-input gate, negations performs an inversion on a single trit by switching -'s and +'s. Also used in performing subtraction. However, it may not be needed as inversion can also be performed by the XNOR gate below by masking with all -'s.

Sum gate (BP7):

Performs single-trit addition by returning the sum of two trits. Also used in multi-trit addition, subtraction, and probably multiplication.
1) Mask with a - to decrement the input trit.
2) Mask with a 0 to pass the input trit through unchanged.
3) Mask with a + to increment the input trit.
Can be used to selectively increment, decrement, or pass through any trit.

Consensus gate (CDR):

Calculates the carry-out of an addition or subtraction. Returns - if both inputs are -, returns + if both inputs are +, otherwise returns 0.
1) Mask with a - to pass through only -'s. Anything else becomes a 0.
2) Mask with a 0 to set the trit to 0.
3) Mask with a + to pass through only +'s. Anything else becomes a 0.
Can be used to selectively detect -'s or +'s, or to neutralize any trit.

XNOR gate (5DP):

Performs single-trit multiplication. Almost certainly going to be needed for multi-trit multiplication.

1) Mask with a - to invert the input trit.
2) Mask with a 0 to set the trit to 0.
3) Mask with a + to pass the input trit through unchanged.
Can be used to selectively invert, neutralize, or pass through any trit.

So far I've identified four other operators that have a clear use and could be candidates for inclusion in a processor. Below are the names, truth tables, and how they can be used. They may have other uses I haven't thought of.

Min Gate (0CP):

Passes through the lessor of each input trit. Equivalent to an AND gate.
1) Mask with a - to set a trit to -.
2) Mask with a 0 to clamp +'s down to 0's.
3) Mask with a + to pass an input trit through unchanged.
Can be used to selectively clamp down, pass through, or set any trit to -.

Max Gate (PRZ):

Passes through the greater of each input trit. Equivalent to an OR gate.
1) Mask with a - to pass an input trit through unchanged.
2) Mask with a 0 to clamp -'s up to 0's.
3) Mask with a + to set a trit to +.
Can be used to selectively clamp up, pass through, or set any trit to +.

0PZ gate:

Several of these gates are probably going to be used in the status register for detecting the most significant non-zero trit.

1) Mask with a - to set a trit to -.
2) Mask with a 0 to pass an input trit through unchanged.
3) Mask with a + to set a trit to +.
Can be used to selectively set any trit to -, or +, or pass them through unchanged.

Equality gate (26K):

Mask with a desired pattern of trits. Every trit that matches the pattern will be set to +. Any trit that doesn't match will be set to -.

Much more research will need to be done to see what logic and math tricks can be performed with these gates and which other gates would be of equal or greater value in the ALU.

Discussions