Generalising Logic Gates
post by Jemist · 20210717T17:25:08.428Z · LW · GW · 2 commentsContents
Example 1 Example 2 Constructing Gates from Simpler Gates Binary Addition None 2 comments
Logic circuits traditionally consist of a directed, acyclic graph. Each node can take a value of 0 or 1. The nodes can have 0, 1, or 2 inputs. 0input nodes are the "input" for the whole system. 1input nodes are always NOT gates, they output 0 if they are input 1 and vice versa. 2input nodes are either AND or OR gates, which work like you would expect. Some of the nodes are designated output nodes.
Let's generalise. We can define an gate as a function . In this case a NOT gate is a gate; both AND and OR gates are gates. Consider all of the possible gates: there are possible inputs, and each one of them has one of possible outputs. This means there are possible gates. Keeping track of the number of gates is important so we will thoroughly convince ourselves of this.
For there are possible gates. These correspond to gates with no inputs and one output, so the two gates are a node which always outputs 0 and a node which always outputs 1. If we allow to vary, we have possible gates. This makes sense, as a gate just consists of a node which always outputs the same string of bits. gates can then be considered as a lookup table with locations, each containing bits of information. In general there are bits of information required to specify an gate.
Example 1
Now let's consider all possible gates. There are of them:



 



 



 




So what are the numbers above each gate?
Consider the input as a set of numbers . We can define the input uniquely using . In binary this is just the concatenation . This means there are possible inputs. We will index these with .
We then take as the th output when the input is fed into the gate. We define similarly to above as . We then let be the output number corresponding to the input .
Each has digits, so we can define . This is equivalent to concatenating in binary, which also makes clear that has digits so the maximum value of is .
Each thus uniquely defines an gate, therefore the three values with define a function . This is a slight generalisation of the notion of a boolean function, as boolean functions are generally defined as functions . We will call C the identifier of the gate.
Let's look at the above table more closely. We see some familiar gates: 1 is NOR, 6 is XOR, 7 is NAND, 8 is AND, 9 is XNOR, and 15 is OR. In fact for any gate , the gate is the result of applying a NOT function to the output.
We also have some inputasymmetric gates. 2, 4, 11, and 13 are all of the form ( [GATE] NOT where [GATE] is an AND, OR, NAND or NOR gate.
The remaining gates are also of note. 1 and 15 are both constant. 3, 5, 10, and 12 all only depend on one of the inputs. These gates could be constructed from a circuit containing a single or gate. These illustrate a way in which gates can be trivial: they can be independent of one or more of the inputs.
There are other ways gates can be trivial: but these rely on having multiple output nodes. The first is duplicate output nodes, imagine the set of gates for which for all inputs. There are 16 of them, each corresponding to a gate.
Another is separability. We will define an gate as separable if we can split the inputs into two or more subsets, each of which can only affect a subset of the outputs. A case of this would be the gate where = , and = . Another example would be the gate where = NOT , and = .
Gates can also be equivalent to each other with regards to permuting the inputs. We see this with the pairs 2 and 4; and 11 and 13 above.
Example 2
A halfadder is a gate. We can work through and find its identifier: First we need a table of inputs and outputs. We will take the carry term first and the sum second.
0  1  
0  0, 0  0, 1 
1  0, 1  1, 0 
The binary representation of can be easily read off as 10 01 01 00. therefore the halfadder is identified as .
A fulladder is a gate:
0  1  


The binary number is here read off as 11 10 10 01 10 01 01 00. . So the full adder can be expressed as . gets big fast as gates gain inputs.
Constructing Gates from Simpler Gates
We might want to construct larger gates from simpler ones. This is how computers are built, and in fact we can build a halfadder from just two "standard" logic gates, an AND and an XOR. A fulladder requires 5 "standard" logic gates. It may be possible to build a fulladder with even fewer logic gates if we are allowed to use all 15, but I have not checked and I do not know a good way to check yet.
We can use some tools from information theory to lowerbound how many smaller gates we ought to need in general to construct a bigger one. We will consider the space complexity as the amount of information required to specify a gate of a certain size, and compare this to the space complexity of a network of gates.
The space complexity of a gate is . This grows as .
When specifying a gate network, we need to specify the gates, which grows linearly in : . We must also consider the information required to specify the connectivity of the network. This is an acyclic directed graph. The number of vertices is , and the number of edges is . The space complexity of this thus grows as the space complexity of a sparse directed graph, which is . Here this ends up being .
Binary Addition
But this is not always the case: consider a gate which adds together two digit binary numbers. This will be a gate. But to construct this from 1 halfadder and fulladders requires only separate standard logic gates. Our value of here does not satisfy , as . Something is clearly up here. Addition appears to be some sort of special process which is unusually simple.
In this framework, this appears to us as addition being much easier than expected to construct as a network. Being easier than expected to construct as a network also makes it faster to compute, since the number of gates corresponds the number of operations needed to evaluate the process.
2 comments
Comments sorted by top scores.
comment by Viliam · 20210718T23:25:49.124Z · LW(p) · GW(p)
I am curious how to construct the cheapest addition for d digits.
Intuitively, "cheapest" refers to using as few gates as possible, exploting some mathematical properties of binary addition, and perhaps reusing some intermediate results. Though I am not sure how exactly to compare "costs" of gates of different dimensions. (This probably requires some insight into how the hardware of actual computers is built. The mathematical "cost" of gates should approximate the actual costs of producing and operating the hardware. I mean, the ultimate benefit of this exercise would be to design an actual computer that is cheaper or faster or more energy efficient.)
Then the same question for multiplication. Then, for building the entire computer.
Replies from: JBlack↑ comment by JBlack · 20210720T06:19:55.578Z · LW(p) · GW(p)
Even very simply stated problems in boolean circuit optimization turn out to be deeply connected with extremely hard mathematical and computational problems, and in some cases even provably undecidable problems.
I don't hold out very much hope of ever being able to find and prove solutions to most of these questions, even assuming superintelligence.
On the other hand, there are no doubt lots of practical improvements, even very substantial ones, to be made.