Building Blocks: Logic Gates

Building Blocks: Logic Gates

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:

  • AND
  • OR
  • NOT
  • NAND
  • NOR
  • XOR
  • XNOR

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.

AND gate

All of the possible AND gates are known.

opposing inputs, single output
adjacent input, single output
adjacent input, two outputs
Opposing inputs, two outputs.

XOR gate

The situation for XOR gates is similar.  Missing is opposing input with two outputs.

opposing inputs, single output
Adjacent input, single output. The double-output version is constructed similarly to the double-output AND gate.

OR gate

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.

opposing inputs, single output
Adjacent inputs, first version. A second output can easily be connected.
Adjacent inputs, version two, which is 3 cells narrower. The transformation to double-output is as simple as connecting the second wire.

AND-NOT gate

The AND-NOT gate is asymmetrical, so there’s five possible configurations  So far, two have been found:

  1. Adjacent inputs, single output, with input A across from the output.
  2. Opposing inputs, single output.
  3. Adjacent inputs, single output, with input B across from the output.
  4. Adjacent inputs, two outputs

Missing is the following:

  1. Opposing inputs, two outputs
adjacent inputs, single output, with input A across from the output
Adjacent input, double output. This is one of the largest gates.
adjacent input, single output, with input B across from the output. The more compact output means that it can’t be turned into a double-output gate.
opposing inputs, single output

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.


4 thoughts on “Building Blocks: Logic Gates

  1. “We must individually, and explicitly, construct each distinct gate configuration. For symmetrical gates, there are 4 configurations, and for asymmetrical gates, there are 5.”
    What exactly? I count 2 for symmetric gates and 3 for asymmetric gates.
    Symmetric:
    1. Opposing inputs, output to one of the other sides (can be mirrored or turned 180° to output to the other side).
    2. Inputs at neighboring sides, output at one other side. (Inputs are the same, so outputting to the other free side is just swapping the inputs. You can rotate it 90°, 180° and 270° for different sides and also mirror it instead of swapping the inputs to get the other output direction.)
    Asymmetric:
    1. Opposing inputs, output to one of the other sides (can be mirrored to output to the other side and mirrored on the other axis or turned 180° to swap inputs).
    2. Inputs next to each other, output to one of the other sides, transformations almost like for the symmetric variation, except…
    3. Choosing the other possible output direction is another variation.
    What are the other two for symmetric and the other two for asymmetric?

      1. “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.
        Adjacent inputs, single output, with input B across from the output
        […]”
        But what exactly is the difference between the two? Can’t you just flip it, turn it 90° and then call input A input B and input B gets called input A. Then you have the other one. Since it’s a symmetrical gate, it works the same.

Leave a Reply

Your email address will not be published. Required fields are marked *

www.000webhost.com