Generalising Logic Gates

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. 0-input nodes are the “input” for the whole system. 1-input nodes are always NOT gates, they output 0 if they are input 1 and vice versa. 2-input 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 $(m, n)$ gate as a function ${0, 1}^{m} \to {0, 1}^{n}$ . In this case a NOT gate is a $(1, 1)$ gate; both AND and OR gates are $(2, 1)$ gates. Consider all of the possible $(m, n)$ gates: there are $2^{m}$ possible inputs, and each one of them has one of $2^{n}$ possible outputs. This means there are $(2^{n})^{2^{m}} = 2^{n \times 2^{m}}$ possible $(m, n)$ gates. Keeping track of the number of gates is important so we will thoroughly convince ourselves of this.

For $m = 0, n = 1$ there are $2^{1 \times 2^{0}} = 2$ 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 $n$ to vary, we have $2^{n}$ possible $(0, n)$ gates. This makes sense, as a $(0, n)$ gate just consists of a node which always outputs the same string of $n$ bits. $(m, n)$ gates can then be considered as a lookup table with $2^{m}$ locations, each containing $n$ bits of information. In general there are $n \times 2^{m}$ bits of information required to specify an $(m, n)$ gate.

Example 1

Now let’s consider all possible $(2, 1)$ gates. There are $2^{1 \times 2^{2}} = 16$ of them:

$0_{10} = 0000_{2}$

	0	1
0	0	0
1	0	0

$1_{10} = 0001_{2}$

	0	1
0	1	0
1	0	0

$2_{10} = 0010_{2}$

	0	1
0	0	1
1	0	0

$3_{10} = 0011_{2}$

	0	1
0	1	1
1	0	0

$4_{10} = 0100_{2}$

	0	1
0	0	0
1	1	0

$5_{10} = 0101_{2}$

	0	1
0	1	0
1	1	0

$6_{10} = 0110_{2}$

	0	1
0	0	1
1	1	0

$7_{10} = 0111_{2}$

	0	1
0	1	1
1	1	0

$8_{10} = 1000_{2}$

	0	1
0	0	0
1	0	1

$9_{10} = 1001_{2}$

	0	1
0	1	0
1	0	1

$10_{10} = 1010_{2}$

	0	1
0	0	1
1	0	1

$11_{10} = 1011_{2}$

	0	1
0	1	1
1	0	1

$12_{10} = 1100_{2}$

	0	1
0	0	0
1	1	1

$13_{10} = 1101_{2}$

	0	1
0	1	0
1	1	1

$14_{10} = 1110_{2}$

	0	1
0	0	1
1	1	1

$15_{10} = 1111_{2}$

	0	1
0	1	1
1	1	1

So what are the numbers above each gate?

Consider the input ${0, 1}^{m}$ as a set of numbers $a_{0}, . . ., a_{m - 1}$ . We can define the input $A$ uniquely using $A = \sum_{i = 0}^{m - 1} a_{i} 2^{i}$ . In binary this is just the concatenation $a_{m - 1} | | . . . | | a_{0}$ . This means there are $2^{m}$ possible inputs. We will index these with $k \in 0, . . ., 2^{m} - 1$ .

We then take $b_{j}$ as the $j$ th output when the input $A$ is fed into the gate. We define $B$ similarly to $A$ above as $B = \sum_{j = 0}^{n - 1} b_{j} 2^{j}$ . We then let $B_{k}$ be the output number corresponding to the input $A_{k}$ .

Each $B$ has $n$ digits, so we can define $C = \sum_{k = 0}^{2^{m} - 1} B_{k} 2^{A_{k} \times n}$ . This is equivalent to concatenating $B_{n - 1} | | . . . | | B_{0}$ in binary, which also makes clear that $C$ has $n \times 2^{m}$ digits so the maximum value of $C$ is $2^{n \times 2^{m}} - 1$ .

Each $C$ thus uniquely defines an $(n, m)$ gate, therefore the three values $(m, n; C)$ with $C \in 0, . . ., 2^{n \times 2^{m}} - 1$ define a function ${0, 1}^{m} \to {0, 1}^{n}$ . This is a slight generalisation of the notion of a boolean function, as boolean functions are generally defined as functions ${0, 1}^{n} \to {0, 1}$ . 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 $B$ , the gate $15 - B$ is the result of applying a NOT function to the output.

We also have some input-asymmetric gates. 2, 4, 11, and 13 are all of the form ( $a_{0}$ [GATE] NOT $a_{1})$ 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 $(0, 1)$ or $(1, 1)$ 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 $(2, 2)$ gates for which $b_{0} = b_{1}$ for all inputs. There are 16 of them, each corresponding to a $(2, 1)$ gate.

Another is separability. We will define an $(m, n)$ gate as separable if we can split the $m$ inputs into two or more subsets, each of which can only affect a subset of the $n$ outputs. A case of this would be the $(2, 2)$ gate where $b_{0}$ = $a_{0}$ , and $b_{1}$ = $a_{1}$ . Another example would be the $(2, 2)$ gate where $b_{0}$ = NOT $a_{1}$ , and $b_{1}$ = $a_{0}$ .

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 half-adder is a $(2, 2)$ 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 $C$ can be easily read off as 10 01 01 00. $10010100_{2} = 148_{10}$ therefore the half-adder is identified as $(2, 2; 148)$ .

A full-adder is a $(3, 2)$ gate:

	0	1
0	0, 0	0, 1
1	0, 1	1, 0

	0	1
0	0, 1	1, 0
1	1, 0	1, 1

The binary number $C$ is here read off as 11 10 10 01 10 01 01 00. $1110100110010100_{2} = 59796_{10}$ . So the full adder can be expressed as $(3, 2; 59796)$ . $C$ 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 half-adder from just two “standard” $(2, 1)$ logic gates, an AND and an XOR. A full-adder requires 5 “standard” $(2, 1)$ logic gates. It may be possible to build a full-adder with even fewer $(2, 1)$ 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 lower-bound 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 $g$ $(2, 1)$ gates.

The space complexity of a gate is $l o g_{2} (m) + l o g_{2} (n) + n \times 2^{m}$ . This grows as $Θ (n \times 2^{m})$ .

When specifying a gate network, we need to specify the gates, which grows linearly in $g$ : $Θ (g)$ . 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 $g + m$ , and the number of edges is $2 g$ . The space complexity of this thus grows as the space complexity of a sparse directed graph, which is $Θ (| V | + | E |)$ . Here this ends up being $Θ (g + m)$ .

Binary Addition

But this is not always the case: consider a gate which adds together two $d$ -digit binary numbers. This will be a $(2 d, d + 1)$ gate. But to construct this from 1 half-adder and $d - 1$ full-adders requires only $g = 2 + 5 \times (d - 1) = 5 d - 3$ separate standard logic gates. Our value of $g$ here does not satisfy $Θ (g + m) = Θ (n \times 2^{m})$ , as $Θ (d) \neq Θ (d \times 2^{2 d})$ . 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.