The second class of building blocks is where things get interesting: logic gates. In real-life digital design, the gates you would typically encounter are as follows:
With the exception of NOT (which has a single input), all of the gates listed above have two inputs and one output. Furthermore, they are symmetrical: swapping the order of inputs has no effect. Unfortunately, only a portion of these gates are available for use in our computer. The main issue we run into is that it is impossible for a gate to create electrons from nothing. This means that any gate with all zeroes input must give a zero output, immediately eliminating the possibility of NOT, NAND, NOR, and XNOR gates. To be more precise, those gates would require a clock as input to make sure that the outputs have the correct timing. For example, a NOT gate would be an XOR hooked up to a clock. At that point, however, we are no longer dealing with the basic building blocks.
There is some good news though. One gate left off the above list is the AND-NOT gate, which outputs true iff the first input is true and the second input is false. Unlike the gates above, this is an asymmetrical gate. Since it returns false when both inputs are false, we are able to build it as a core gate. This gate will help reduce our need for inverters.
Configuration is Key
There’s not much that isn’t important when designing logic gates. In order for a logic gate to be useful, it has to fit with the wires that we chose. Since we are arranging everything rectilinearly, each logic gate has four sides, two of which are input, and one or two of which are output. This gives rise to multiple distinct configurations of each gate. For an example, one version of a gate could take input from the left and right, while another version could take input from the left and top. These gates are distinct because there’s no sequence of rotations/reflections that transforms one to the other. We must individually, and explicitly, construct each distinct gate configuration. For symmetrical gates, there are 4 configurations, and for asymmetrical gates, there are 5.
Having a wide palette of gates is very important, since not having the right gate generally results in additional wiring or additional gates, which slows down the circuit, which means that other parts of the circuit (or computer) must be adjusted as to keep the timing in sync.
There is an important additional restriction on shape, which is that they fit into a square bounding box (of arbitrary size) with the input/output wires centered on each side. This helps the gate fit into the grid system and means they may be rotated/reflected and still fit properly without affecting timing.
Timing is Key
In order for a given logic gate to be compatible with our wiring system, they must follow an important timing principle:
The time between input and output is given by the Manhattan distance between input and output, not by the type of gate or what the input/output values are. If the logic gate were replaced by a straight or corner wire, the delay must be identical.
This rule is what ensures that the logic gates are compatible with each other, and that the next layer of abstraction (detailed in a later post) actually works. Several gates have been discovered that are completely unusable because of timing issues. In those cases, it is generally possible to correct the timing issue by simply bending some of the surrounding wires, but that generally adds to the size of the gate.
List of “Core” Logic Gates
Here is a (to-be-completed) comprehensive list of the known logic gates. Some of the animation needs to be updated to VarLife quality. The VarLife animations are also hyperlinked to an example implementation. In some images, a red bounding box (11×11, inclusive) is displayed, although that same bounding box can fit (centered) over any other gate here.
All of the possible AND gates are known.
The situation for XOR gates is similar. Missing is opposing input with two outputs.
The OR gate typically uses the B12/S1 cell type. It has, however, a second version of the adjacent-input configurations which is more compact. The larger version is often used, simply for consistency. It is likewise missing the opposing-inputs double-output version.
The AND-NOT gate is asymmetrical, so there’s five possible configurations So far, two have been found:
- Adjacent inputs, single output, with input A across from the output.
- Opposing inputs, single output.
- Adjacent inputs, single output, with input B across from the output.
- Adjacent inputs, two outputs
Missing is the following:
- Opposing inputs, two outputs
What about those missing gates?
As you may have noticed, a couple theoretical gate configurations are missing. This is generally due to a lack of effort: a serious need for many of the double-output gates hasn’t arisen yet, so not much time has been spent searching for them. On the other hand, I do not believe that the double-output gates will be simple. If you find a missing gate, or a more compact version of an existing gate, please contact us. If it is compatible with our project, I will add it to this list.