Issue 298: EQ Answers

Problem 1: What do we call a network of gates that has no feedback of any kind? What is its key characteristic?

Answer 1: A network of gates that has no feedback is called “combinatorial logic”, or sometimes “combinational logic”. Its defining characteristic is that the output of the network is strictly a function of the current input values; the past history of the inputs has no effect. The branch of mathematics associated with this is called “combinatorics”, and we say that the output is the result of logical combinations of the input values.

Problem 2: What do we call a network of gates that has negative feedback? Give an example.

Answer 2: If a network of gates has “negative” feedback, it means that an output is fed back to an input in such a way that it always causes that output to change state again. When this occurs, the output never achieves a stable state. We call this an “oscillator.”

The simplest example is the “ring oscillator,” which simply comprises an odd number of inverters, each with its output connected to the input of the next. When any output changes state, the change propagates all the way around through the chain and forces it back to the opposite state.

Note that a single inverter fed back to itself will not usually oscillate. Because the propagation delay is comparable to the transition time, the output will usually just settle at an intermediate analog value, rather than any valid digital value.

Problem 3: What do we call a network of gates that has positive feedback? Give an example of the simplest possible such network (there are several).

Answer 3: A network of gates with positive feedback becomes an asynchronous state machine (ASM). The network’s output becomes a function of both its current input values and the past history of the input values — in other words, the network can be said to have a “memory” of its past.

The simplest possible examples include a single AND gate or a single OR gate. An AND gate with one input tied to its output has two output states, 0 and 1. If the other input has at any time in the past been driven to 0, then the output will be 0; otherwise it will be 1.

Similarly, the output of an OR gate with one input tied to its output will be 1 if the other input has ever been driven to 1.

The simplest ASM that is of practical use in most applications is the set-reset latch, which requires two gates that each have an input from the output of the other. They can comprise one AND gate and one OR gate, or a pair of NAND gates or a pair of NOR gates. This type of ASM can be used to store one bit of information, and is a type of flip-flop. Another (very old) term is “bistable multivibrator.”

Problem: Why are NAND gates and NOR gates considered to be “universal” gates? Why is this important?

Answer 4: It can be shown that any logical function can be created from a network of only NAND gates, or of only NOR gates. This includes ASMs such as the two-NAND or two-NOR flip-flop described above.

This is important because many of the basic technologies for creating digital gates tend to require that each gate be implicitly inverting. In other words, a 1 on an input can only force a 0 at the output, and vice-versa.

Examples include RTL (resistor-transistor logic), which is based on NOR gates, and DTL (diode-transistor logic) or TTL (transistor-transistor logic), which are based on NAND gates.

This is particularly true of CMOS, the most popular implementation technology in current use. Any network of N-channel pull-down transistors and P-channel pull-up transistors can only invert an input signal. The big advantage of CMOS is that NAND and NOR gates can be combined with equal ease.

Contributor: David Tweed