PC [Guide] An Idea On How To Make A Combinational Logic Circuit With The Least Logic Gates

putianyi888

Terrarian
The idea came from this thread. The full adder by @ekinator surprised me quite a bit because I had always thought that the complexity of a single logic gate is too small to express the logic in a full adder. Then I began to think of the complexity of a single logic gate. I came up with some methods with which I made a key part of a binary-to-BCD decoder much smaller than that within this thread.
upload_2019-2-9_21-36-55.png

You don't need to know the wiring because I will show the logical expression later.

NOTATIONS
'&' denotes the operator AND. '~' denotes the operator NOT.
Note that the Terrarian XOR gate does not perform the XOR operation in reality. Because terrarian XOR doesn't satisfy the associative law, I would consider it as a function ^() rather than an operator.
But Terraria does have a real XOR operation which is to simply connect two or more inputs to one lamp. According to how it seems like in game, we simply denote a XOR b by ab. This free operation significantly raises the complexity of logic gates.

THE TRUTH TABLE
Definitions
Any combinational logic is associated with a unique truth table. The size of a truth table is (n+1)x2^n where n denotes the number of inputs. The first step is to reduce the size of the truth table.
Let F denote the combinational logic with inputs a_1,...,a_n.
Define size(F) as the 1's in the (n+1)-th column of the truth table of F.
In terraria, F is basically the same as ~F, so we can assume that size(F) is at most 2^(n-1).
Let M be a matrix whose rows are all possible inputs (a_1,...,a_n) with F=1. For example, if F=^(a,b,c), then F=1 if and only if (a,b,c)=(1,0,0), (0,1,0) or (0,0,1). Thus M should be:
upload_2019-2-9_22-7-56.png

It's clear that switching rows of M doesn't matter. Switching rows doesn't make any sense as well.
From now on, we regard M as the truth table of F. The approach is to transform M to some specific truth tables which can be achieved by a single logic gate.

Truth Tables of Single Logic Gates
There are two distinct combinational logic gates in Terraria: the AND gate and the XOR gate.

A single AND gate has a logical expression of s_1&s_2&...&s_r where s_i's denote strings of {~,a_1,...,a_n}. The number of &'s is one less than that of lamps on the gate. For example, consider F with three inputs a,b and c, then a&b&c, a&~b&~c, a&b, ab&c and abc can all be achieved with a single AND gate:
upload_2019-2-9_22-27-15.png
upload_2019-2-9_22-27-52.png
upload_2019-2-9_22-28-10.png
upload_2019-2-9_22-28-39.png
upload_2019-2-9_22-28-59.png

The truth tables of these logics are:
upload_2019-2-9_22-31-3.png
upload_2019-2-9_22-31-38.png
upload_2019-2-9_22-32-27.png
upload_2019-2-9_22-33-3.png
upload_2019-2-9_22-33-27.png


A single XOR gate has a logical expression of ^(s_1,s_2,...,s_r) where s_i's are the same as above. XOR gates only make sense with more than 2 inputs. The examples here are ^(a,b,c) and ^(ab,b,c):
upload_2019-2-9_22-40-18.png
upload_2019-2-9_22-41-15.png


As there are many candidates of those strings, a single logic gate can play quite a few logics. The problem is, given the truth table of ^(ab,b,c), how can we find the logical expression?

TRANSFORMATION OF TRUTH TABLES
I have talked about switching of rows, which is a useless way to transform M. There are ways to change M as well. Similarly, we can switch columns with there titles as well. For example, we switch column b and column c of M of ab&c:
before:
upload_2019-2-9_22-51-21.png
after:
upload_2019-2-9_22-52-13.png


This still doesn't make much sense. Now we add column b to column a. The addition is actually XOR operation: 0+0=1+1=0, 0+1=1+0=1. Also we have to add the column titles. When two column titles add, simply put the letters together and cancel letters which appear twice.
before:
upload_2019-2-9_22-52-13.png
after:
upload_2019-2-9_22-56-26.png


This truth table is the same as the truth table of a&b (see above), so we conclude that the original truth table is associated with expression ab&c.

There is another transformation that I didn't use in the example. We can switch 1's and 0's of a column and add '~' to the column title. The addtion also follows the string addition rule.

Given any truth table, we implement three operations: switching columns, adding a column to another and, switching 1's and 0's of a column. The truth table may become our known truth table and we obtain a simplified logic.

As I have promised, I'm going to put the logical expression of the part of binary to BCD decoder. It has 4 inputs denoted by a,b,c,d and 4 outputs denoted by A,B,C,D, all from higher digit to lower digit. The truth tables of A,B,C and D are shown below:
upload_2019-2-9_23-8-55.png
upload_2019-2-9_23-9-38.png
upload_2019-2-9_23-10-13.png
upload_2019-2-9_23-11-26.png


The truth table of B can be transformed to below, which tells that B=ab&~c&~ad.
upload_2019-2-9_23-13-14.png


The truth table of C can be transformed to below, which tells that C=^(a,b,cd,bd).
upload_2019-2-9_23-14-18.png


The truth table of D can be transformed to below, which tells that D=^(a,b,bc,bcd).
upload_2019-2-9_23-15-29.png


The truth table of A cannot be transformed to a good enough table, so we have to take "undefined" inputs into consideration. The inputs can only be 0 to 9, so given 10 to 15, the output can be arbitrary. So we add another 6 rows marked with 'x' to note that these rows can be freely deleted.
upload_2019-2-9_23-19-47.png

Add column b to column a, then the column ab has 7 1's. If it had 8 1's, we could have A=ab. The exception is 0100, so we can add a gate to exclude the exception: A=ab(~a&b&~c&~d).
 
So we can compact calculators and ALU’s now?
This method doesn't seem to work on complex logic, or logic with many inputs, because the complexity of outputs is much larger than the complexity of logic gates when n becomes large, not to mention that sequential logic works better than combinational logic in complicated cases.
It works fine on simple logics, such as binary to BCD, 7 segment display, etc.
 
I have successfully simplified the last logic:
upload_2019-2-10_13-4-45.png

Take the first 6 rows and we get A=^(bc,~ad,cd). Wiring:
upload_2019-2-10_13-6-13.png

An 8 bit binary to BCD converter:
upload_2019-2-10_13-6-49.png

Not sure if a unit can fit into 4 tiles width. It takes 5 tiles here. Also it's possible to reduce the height by 1.
 
Last edited:
Back
Top Bottom