#balanced ternary

Okay.

First, in case anyone reading this is unaware of what a logic gate, truth table, or the balanced ternary number system is, you'll want to read these three Wikipedia articles to get some background knowledge:

https://en.wikipedia.org/wiki/Truth_table

https://en.wikipedia.org/wiki/Logic_gate

https://en.wikipedia.org/wiki/Balanced_ternary

Second, if you're unaware of how water and lava behave in Minecraft, you'll want to read this article from the Minecraft wiki.

Thirdly, you'll want to read these excerpts (↓) from my notes (my apologies for their quality), where I list my personal conventions and definitions for what is to come.

Got that all?

What we want to do now is try to construct some of the aforementioned logic gates with Minecraft's fluid model. Water will be used to represent 1, lava will represent T (-1), and air (neither water nor lava) will represent 0.

Believe it or not, this isn't too difficult. Most of the logic gates I describe above are rather simple to implement -- so long as we ignore the timing constraints imparted by water and lava flowing at different rates, which for the sake of brevity (brevity, lol) we will.

Two of the most fundamental of these logic gates, at least for our purposes, are MAND and OR. They are implemented like this (↓)

If you're having trouble grasping how these work, and have access to a copy of the game, I encourage you to play around with it yourself! After a while, the principles start to become pretty intuitive.

We can use these "fundamental" gates to construct the rest. ISN, ISP, NISN, and NISP can be made by simply hard-wiring one or the other of the inputs of a MAND gate to 1/water or T/lava. (Not that you'd always want to implement ISP in particular that way--it's actually the third fundamental logic gate and can be implemented via a different principle, but I digress)

From there we can construct NEG, as NEG a is equal to (NISN a) OR (NISP a); from NEG we can construct AND, because a AND b = a MAND (NEG b); and so on and so forth. (Exercise for the reader to derive the rest :P)

This brings us back to the shift register, which is primarily constructed of these (↓) little circuits who operate analogously to normally-closed relays.

Let the green input be a, the white input be b, and the output be q. When a is nonnegative (0 or 1), b will "pass through", so to speak, and q = b. When a is negative (T), q will always be 0.

Put more simply, q = b OR (ISN a) OR (NISN a). Run the numbers and you'll see how it works!

From there, it's pretty trivial to line a few of these up, tie their outputs together, and get a demultiplexer -- a circuit that takes in some number of inputs (here three) and "selects" one of them to output. Let's look at our demultiplexer now:

Let s1, s2 and s3 be the blue "selector" inputs; p1, p2, and p3 be the white "selectee" inputs; b1, b2 and b3 be the intermediate "blocking" signals (the green inputs from earlier); q1, q2 and q3 be the outputs from our relays; and q (no number) be the overall output.

The yellow and light blue circuitry are our relays, the black concrete is the aforementioned output tying-together (q = q1 OR q2 Or q3), and the blue and red circuitry is... complicated.

Its job, though, is simple: translate a positive "selecting" signal on one of its three inputs (s1, s2 and s3) into two negative "blocking" signals to be sent to the relays (b1, b2, b3).

This is implemented as follows:

b1 = (NISP (s1 OR s2 OR s3)) OR s1 b2 = (NISP (s1 OR s2 OR s3)) OR s2 b3 = (NISP (s1 OR s2 OR s3)) OR s3

In other words, b1 is negative iff s2 or s3 is positive, b2 is negative iff s1 or s3 is positive, and b3 is negative iff s1 or s2 is positive.

Let's work through an example. Say c1 is 1, c2 is 0 and c3 is T, and we set s3 to 1--"selecting" c3.

Since s1 and s2 are 0, and s3 is 1, s1 OR s2 OR s3 = 1 and NISP (s1 OR s2 OR s3) = T

It follows then that b1 = T OR s1 = T OR 0 = T, b2 = T OR s2 = T OR 0 = T, and b3 = T OR s3 = T OR 1 = 0.

Finally, since b1 and b2 are T, q1 and q2 are 0 (relay 1 and relay 2 "block" their inputs from flowing through) and since b3 is 0, q3 = p3 and thus q = q3 = p3 = T.

Got that? Great! Let's move on to the monster then.

A diagram may be in order.

Better?

The shift register (again not the correct term because this is a one-time use circuit, but I digress -- they're roughly analogous) is constructed mainly of demultiplexers (light blue boxes), as described before.

Each demuxer is selecting between the input directly above it, the input to its left, and the input to its right. (e.g. demuxer #4 is selecting between In3, In4 and In5).

The signals telling the demuxers which inputs to select (s1, s2 and s3 from earlier) are generated by the "split" box (in blue) from the "Selector" signal. If "Selector" is T, "Split" sends a positive signal to the s1 input of the demuxers; if it is 0, s2; if it is 1, s3.

This is implemented as follows:

s1 = NISN "Selector" s2 = NISN ("Sync" OR s1 OR s3) s3 = ISP "Selector"

The "Sync" signal line (in orange) and circuits (purple boxes) work to ensure the timing constraints and invariants we've so far elided are upheld. "Sync" is always either 0 (wait for sync) or T (resume), never 1.

The purple boxes work like the opposite of the relays we described earlier: they receive an input and only output it after they receive a "Sync" signal.

They are implemented as follows:

q = (a MAND "Sync") OR (a MAND (NISN "Sync"))

Likewise, the "Split" box waits for a "Sync" signal to determine if "Selector" is 0 -- if it "jumped the gun" it wouldn't be able to go back and correct its output, all fluid-based logic gates are necessarily one time use.

What does all of this nonsense accomplish?

When "Selector" is 0, the input is simply passed through; when "Selector" is T, the input is shifted left (Out1 = In2, Out2 = In3... Out6 = 0); when "Selector" is 1, the input is shifted right (Out1 = 0, Out2 = In1... Out6 = In5). This is equivalent to either multiplying or dividing the output by 3.

And that's that!

As even-numbered base natives (decimal, binary, hex, octal, etc.) we take for granted that determining the parity of a given integer (is it even or odd) is trivial. Just look at the last digit! parity(x) = parity(x % b), where x is some integer and b is the radix of your number system. (e.g. in decimal parity(107) = parity(107 % 10) = parity(7) = odd).

In binary this even easier, as the least-significant digit can only be either 0 or 1: even or odd.

Not so for odd-numbered bases! As a trivial counterexample, 1T0 (dec. 6) is even and has an even least significant digit (0, dec. 0); 1T (dec. 2) is even but has an odd lsd (T, dec. -1).

Fortunately, we have a slightly more roundabout way of determining parity. The parity of any given balanced ternary integer is equal to the parity of the sum of its digits, for example 1T10 [dec. 21] is odd and 1 + T + 1 + 0 = 1 [dec. 1 + -1 + 1 + 0 = 1], which is also odd.

This makes some intuitive sense if we consider five facts:

The parity of the sum of any two integers is even iff both are even or both are odd; the sum of any two integers is odd iff one is odd and the other is even.

The parity of the sum of a given set of integers is equal to the parity of the count of odd integers in that set. For example, Σ{1, 2, 3} is even because there an even number of odd numbers (specifically 2: 1 and 3), Σ{1, 2, 3, 3} is odd because there an odd number of odd numbers (specifically 3: 1, 3 and 3). Why does this work? Let's step through a bigger example: Σ{1, 2, 3, 7, 9, 2, 0, 5}. First, we'll group these numbers by their parity: (1 + 3 + 7 + 9 + 5) + (2 + 2 + 0) We know that the sum of the even numbers can only be even, so for the purpose of calculating parity we can simply ignore them. Only the sum of the odd numbers will have any bearing on the result. Second, we'll try to group the odd numbers into pairs: ((1 + 3) + (7 + 9)) + 5 Since we had an odd number of odd numbers, we are left with one unpaired number. Since the sum of odd + odd is even, these paired odds will all sum to even numbers: (4 + 16) + 5 The sum of these results can thus also only be even: 20 + 5 Odd + even = odd (20 + 5 = 25, which is odd) If there has been an even number of odd numbers, we wouldn't have had an unpaired odd number, and thus the result would have been even.

The product of any two integers is odd if both are odd, otherwise it's even. (e.g. 5 * 7 = 35, 6 * 7 = 42, 6 * 8 = 48)

Since 3 (our radix) is odd, 3 to any nonnegative power will also be odd -- exponentiation is of course merely successive multiplication. Thus, the parity of any given digit * radix-to-some-power product will be determined by the parity of that digit -- it doesn't matter what that power is. 1 * 3^0 is odd, 1 * 3^1 is odd, 1 * 3^2 is odd, 1 * 3^982908 is odd. Likewise, 0 * 3^0 is even, 0 * 3^1 is even, 0 * 3^2 is even, 0 * 3^982908 is even.

Any number can be written as a sum of products between digit values and increasing powers of the number system's radix. For example: 127 in decimal is equal to 1 * 10^2 + 2 * 10^1 + 7 * 10^0, and 11T0 in balanced ternary is equal to 1 * 3^3 + 1 * 3^2 + -1 * 3^1 + 0 * 3^0.

Let's apply this to our original example: parity(1T10) [dec. 21]. First, we re-write it as parity(1 * 3^3 + -1 * 3^2 + 1 * 3^1 + 0 * 3^0). Because 3 to any nonnegative power is odd, we can rewrite this as parity(1 * 3^0 + -1 * 3^0 + 1 * 3^0 + 0 * 3^0).

3^0 is 1, and 1 is the multiplicative identity, so we can re-write this further as parity(1 + -1 + 1 + 0). (Hey, that's the sum of the digits!)

Finally, we know from earlier that the parity of the sum of any set of integers is equal to the parity of the count of odd numbers in that set. Since there are three odd integers in this sum, and three is odd, we know that parity(1 + -1 + 1 + 0) is odd.

We can take advantage of this fact to build a (relatively) simple parity-determining circuit out of successive stages of half-adders. The first will compute 1 + -1 = 0 and 1 + 0 = 1, the second will compute 0 + 1 = 1.

But wait a minute: half-adders have carry-outs. They're not guaranteed to produce fewer digits of output than they get as input! Fortunately, we can take advantage of the fact that C_out and S will never be nonnegative and equal, and thus we can calculate their sum with an OR gate. Take 1101 [Dec. 37], then. 1 + 1 = 1T and 0 + 1 = 01, 1 OR T = 0 and 0 OR 1 = 1, 0 + 1 = 01, 0 OR 1 = 1. 1 is odd, hooray!

Here's another interesting observation: since the Sum output of a half adder is equal to (A XOR B) OR (A NAND B) and C_out is equal to (A AND B), what we're actually calculating here is ((A XOR B) OR (A NAND B)) OR (A AND B), aka (A XOR B) OR ((A NAND B) OR (A AND B)), aka (A XOR B) OR 0, aka A XOR B!

So it seems we don't actually have to bother taking the sums in the first place, any parity-preserving gate with two or more inputs will suffice. In other words, we can use any gate obeying this truth table:

| | T | 0 | 1 | |---|---|---|---| | T | 0 | a | 0 | | 0 | b | 0 | c | | 1 | 0 | d | 0 |

Where a, b, c, d ∈ {T, 1}.

XOR is one such gate, but it's not the easiest of them to construct. The pictured circuit is constructed with a (as-of-yet unnamed) gate following this truth table:

| | T | 0 | 1 | |---|---|---|---| | T | 0 | 1 | 0 | | 0 | T | 0 | T | | 1 | 0 | 1 | 0 |

And the final result is fed into an ABS gate, a single-input gate following this truth table: