Digital Circuits

The CPU is implemented as a complex set of digital circuits. Digits circuits are built out of logic gates (which, in turn, are built using transistors). In a digit circuit design, we show how logic signals (on/off values) flow from inputs, through logic gates, to outputs. A logic signal is high (on) if there is current flowing through it, and low (off) if there is not (or a very small amount of current).

The basic types of logic gates are:

• NOT: Single input, single output gate which inverts its input. If the input is high, the output is low, and vice versa.

  

  The C/C++ operator for NOT is ~ (this is bitwise NOT, which is different from logical NOT, !).

• AND: Two input, single output gate: the output is high if and only if both inputs are high, otherwise it is low.

  

  The C/C++ operator for AND is & (this is bitwise AND, which is different from &&, logical AND).

• OR: Two input, single output gate: the output is high if either or both of its inputs is high, otherwise (if both inputs are low) it is low.

  

  The C/C++ operator for OR is | (this is bitwise OR, again, different from logical OR, ||).

• XOR: Two input, single output gate: the output is high if either of its inputs is high but not both, otherwise (if both inputs are high, or both are low), the output is low. Effectively, the output is high if the inputs are different (one high and one low), and low if they are the same.

  

  The C/C++ operator for XOR is ^ (this is bitwise XOR; there is no logical XOR operator in C/C++). Note that C/C++ does not have an exponentiation operator.

• NAND: An AND gate with a NOT attached to the output. That is, the output is low if both inputs are high, and high otherwise.

  

  There is no C/C++ operator for NAND, although you can combine & with ~ to achieve the same effect.

• NOR: An OR gate with a NOT attached to the output. The output is high if both inputs are low, and low otherwise.

  

  There is no C/C++ operator for NOR, although you can combine | with ~ to achieve the same effect.

• XNOR: An XOR gate with a NOT attached to the output. The output is high if both inputs are the same (both low, or both high), and low otherwise.

  

  There is no C/C++ operator for XNOR, although you can combine ^ with ~ to achieve the same effect.

The first three are probably at least a bit familiar to you. There are a few things to note:

• AND and OR can be extended to more than two inputs: an n-input AND gate is high if all of its n inputs are high, and low otherwise. Likewise, an n-input OR gate is high if at least one of its n inputs is high, and low if all its inputs are low.

  This diagram illustrates how to built a 3-input AND gate:

  

  Question: If XOR gates are arranged in the same configuration, what does the resulting 3-input, 1-output circuit do?

• NAND and NOR gates have the property of universality: all of the other gates can be built from just NAND, or just NOR. In fact, its common for circuits to be built using just NAND gates, to simplify manufacturing.

  For example, here is a circuit that is equivalent to A OR B implemented using only NAND gates (you should verify that the circuit produces the correct output for all four combinations of inputs A and B):

  

  You can find a full reference of how to translate all the other types of logic gates into both NAND and NOR gates on Wikipedia. Assignment 1 will ask you to translate a circuit using NOT, AND, and OR into one that only uses NAND gates.

Table form of circuits

The behavior of any (stateless) m-input, n-output circuit can also be illustrated using a table showing how each combination of inputs maps to a particular set of outputs. Because each input can be either low (0) or high (1), the table will have 2^m rows and m + n columns. For example, the 3-input AND shown above

can be defined via the following table:

Inputs			Output
A	B	C	Q
0	0	0	0
1	0	0	0
0	1	0	0
1	1	0	0
0	0	1	0
1	0	1	0
0	1	1	0
1	1	1	1

I.e., the output is high (1) only when all three inputs are high (1).

Circuits in hardware

If you were to try and implement a logic circuit in actual electronic hardware, you’d come up against several issues that were not mentioned above:

1. Electricity does not just flow from point A to point B (as a logic diagram would suggest), but rather only flows if a closed circuit is present. In order for a circuit to work in the real world, there must be a return connection from the final output of the circuit, back to the source which is powering the inputs. In a real circuit, these connections would of course be present, but in a logic diagram, we omit them, because they do not affect the logic of the circuit, what it actually computes.

   Further complicating real-world circuit layouts is the fact that many logic gates requires a supply connection: an input that is always high, supplying power to the device.

2. If you try to buy an OR gate (for example), you’ll discover that you usually can’t buy just one; gates are usually only available on ICs, which will bundle several of the same type of gate together. For example, you can purchase an IC (integrated circuit) with four, or eight, or more NAND gates on a single chip. This makes sense, because in a real circuit design, you would rarely need just one gate. (The chip will have a single supply input, shared by all its gates.)

3. Ideally, we describe logic circuits as if the signals instantaneously switched from low to high, and vice versa, but in real-world systems this is impossible. The rise time of a circuit is the amount of time it takes for a line to go from low to high. During this transition period, the amount of current flowing through the connection is somewhere in between 0 and 1, which may cause the circuit output to be unpredictable for a brief period.

   In order to work around this period of unpredictability, most digital circuits are synchronous: they use a clock to control when computation is performed. A clock is a 0-input, 1-output logic device which outputs a signal which alternates low, high, low, high, … at a regular clock rate. Typically, when the clock signal goes from low to high (the “rising edge” of the clock signal), the rest of the circuit will perform its computation, but the output of the computation will not be read until the rising edge of the next clock cycle. Thus, the output has 1 entire clock cycle to stabilize on the correct value.

   In fact, even when the signal is high it will still not be at a constant level; it is simply higher than some threshold value which marks the dividing line between “low” and “high”.

4. Electrically, a single output cannot be connected to an unlimited number of other devices; there is a limit to the “fan-out” of an output.

5. Logic gates can be implemented electronically in many different ways, leading to different logic families, each with its own electrical characteristics. E.g., the voltage levels for “low” vs. “high” may be very different for different families. Note also that in most families the “low” level is not 0V, but some voltage level less than the “high” level. E.g., the transistor-transistor-logic (TTL) family uses a low voltage level between 0 and 0.8V (with respect to ground), and a high 2 and 5V. An input signal between 0.8 and 2V is in the “unpredictable” range and may be seen as high, or low, or even fluctuating between the two.

Logic circuit problems

Here are some circuits you can try to build, to test your understanding of logic circuits:

• Using any gates you like, build a 4-input, 1-output circuit where the output is high if and only if exactly one of the inputs is high.

• Using any gates you like, build a 4-input, 1-output circuit where the output is high if and only if exactly two of the inputs are high (but it could be any two).

• Using only NAND, build a comparator circuit, a 2-input, 1-output circuit where the output is high if

  • Both inputs are low
  • The first input is low and the second is high
  • Both inputs are high

  This is equivalent to checking whether the first input is “less than or equal to” the second, where low is “less than” high.

Note that there are many different possible solutions to these problems. A more advanced course in digital circuits would teach methods for optimizing the design of a circuit, so as to minimize the number of gates used.