Digital Logic Design

Computers, and other digital systems, are designed using elementary electronic circuits called gates . In this article, Inverters, Or gates, and And gate s are introduced by logical statements justifying the term "logic design." Then, the design procedure is illustrated, and integrated circuits are discussed.

Gates

Gates are used to regulate electronic flow and to construct devices to process data, as well as to build memory devices. There are three fundamental gates—"And," "Or," and "Not"—as well as some "hybrid" gates such as "Nand" (Not-And) and "Nor" (Not-Or).

Not

Consider the logical statement: "The porch light is on (Z 1) when I am not home (A 0)." Z is the output; A is the input (I am home). A corresponding binary function, of one variable , which is also binary, is called "Complement" or "Not." "Not" is represented by "Z ~A" and its behavior is:

The electronic implementation of Not is the inverter, a one-transistor current amplifier with one input and one output. A high (binary-1) input voltage, typically about 5 Volts, forces current into the amplifier's input. So, the amplifier draws current from its output, pulling its output voltage low (binary-0), typically, close to 0 Volts. A 1 or high input gives a 0 output (the complement of the input). Since a low input voltage provides no current to the amplifier's input, the amplifier draws no current from its output, causing a high voltage there. A low or 0 input gives a 1 output. The output is the opposite or complement (Not) of the input.

Or

Consider the logical statement: "I wear a jacket (Z 1) if it is cold (A 1) or if it rains (B 1) or …" A corresponding binary function, of two or more binary variables, is called "Or." The behavior of "Or" is tabulated for two and three variables:

One or the other or both (or "all" three) of the inputs "on" cause the output to be true. A Nor gate is like an inverter, but with N input terminals instead of one. A high input voltage on any of the inputs causes a low output voltage and a low voltage on all inputs causes a high output voltage. Since "Nor" is the complement of "Or," "Or" is implemented in electronics by a "Nor-Not" tandem. "Not-Nor" or "OR." But, "Nor" has another application.

Consider a pair of two-input "Nor" gates, and let the output of each gate be one of the other gate's inputs. Label the unused inputs as S and R, and assume both these inputs are low. A positive pulse on S causes the corresponding "Nor" gate's output to go low. Since both inputs to the other gate are low, its output is high. The pair of gates remains in this state even after the pulse on S returns to 0. A positive pulse on R causes the output of R's "Nor" gate to go low. Since both inputs to S's gate are low, its output is high. The pair of gates now remains in this opposite state even after the pulse on R returns to 0. This pair of cross-connected "Nor" gates is called a "Set-Reset Flip-Flop" and it is the basic binary storage element used throughout digital design. The memory element is a 1 if S (Set) is 1, 0 if S is 0, or, what is the same, R (Reset) is 1.

And

Consider the logical statement: "I wear a hat (Z = 1) when it is cold (A = 1) and when it is raining (B = 1) and …" A corresponding binary function of two or more binary variables is called "And." The behavior of "And" is tabulated for two and three variables:

All inputs must be on for the output to be on.

Like a "Nor" gate, a "Nand gate" also has N input terminals and one output terminal. But, "Nand" is more complicated than "Nor," because a low output voltage is caused by a high voltage on all the inputs, and the output voltage is high if any of the input voltages is low. "And" is implemented in electronics by a "Nand-Not" tandem. Again, "Not-Nand," or "Not-Not-And," hence, "And."

Design Example

Consider a binary circuit, with output X and three inputs. D and E are separate streams of binary data, and C is a control signal so that X D when C 0 and X E when C 1. That is, the output is equal to D when C is 0, and equals E when C is 1. C controls the output. This Binary Multiplexor's behavior is tabulated:

Compare the output to D's value when C is 0; compare the output to E's value when C is 1. In the first four rows of the table, X D because C 0. In the last four rows, X E because C 1. The device is called a multiplexor because it switches ("multiplexes") between the data streams D and E under the control of C. It is a "binary multiplexor" because it switches between or "multiplexes" among two devices, D and E. It takes turns servicing them under the control of C. Consider two approaches for implementing this function.

Canonic And-Or Implementation.

Any binary function can be implemented in three layers of logic: (1) a layer of inverters that provides the complement of each input if it is needed; (2) a layer with K different N-input "And" gates where the circuit has N inputs and the circuit's output function has K one-points (one outputs); and (3) one K-input Or gate. Since the multiplexor's output function, X, has four one-points, the canonic "And-Or" implementation has four "And" gates, each with three inputs. The different "And" gates' inputs are appropriately inverted so each gate identifies a different one-point (one in the output). For example, an "And" gate whose inputs are ~C, D, and ~E has a 1-output when CDE 010. A four-input "Or" gate, with an input from each "And" gate, provides the circuit's output. This would be (~C,D,~E) (or) (~C,D,E) (or) (C,~D,E) (or) (C,D,E) for the four one-points (one outputs) given.

Based on the Logical Description.

We can design the multiplexor in an ad-hoc manner from its logical description. If the inputs to a two-input "And" gate are ~C and D, this gate's output equals D when C equals 0, and is 0 when C equals 1. If the inputs to another two-input "And" gate are C and E, this gate's output equals E when C equals 1, and equal 0 when C equals 0. The "Or" of these two "And" gates gives X. That is, the output is D (equal to D) when C is off (~C or C 0), the output equals E when C is on.

Obviously this second implementation, with only two two-input "And"-gates and one two-input "Or"-gate, is less expensive than the first. This is one of the issues in design. Cost, a complex issue, is illustrated next.

Integrated Circuits

Integration is the manufacture of more than one gate, an entire binary circuit, or even a whole system, on the same silicon chip. Transistorized gates and flip-flops were made in the 1950s from discrete resistors and transistors. Then, they were integrated onto a single chip, called a "small-scale" integrated circuit (IC). Often, a chip's complexity is limited by the package's pin-outs. The "7400 series" of integrated circuits, introduced in the late 1960s, is still used today. If a part is popular, its per-chip overhead is small. Then, its price covers only the cost of materials and manufacturing— about $3 (in quantity). Allowing pins for common battery and ground, a 14-pin package has the following limits:

As chip manufacturers placed more logic circuits on a single chip of silicon, integration proceeded through three subsequent scales of fabrication. Simple binary functions are fabricated on a single chip with up to 100 transistors on a chip, in what has come to be called "Medium Scale Integration." For example, the Quad Set-Reset Flip-Flop is a useful digital integrated circuit (IC). But, when fitting four SR-FFs within the pin constraints of a 14-pin DIP (Dual In-Line Package), each SR-FF gets only three pins (14 2 (for battery and ground) 12; 12 / 4 (Quad) FF's 3 pins per SR flip-flop, 2 inputs, 1 output) and only one of each flip-flop's outputs is connected to a pin (the S or the R but not both).

More complicated digital circuits, such as binary counters and shift registers, are fabricated with many hundreds of transistors on a chip in "Large Scale Integration." Finally, modern digital circuits—like 16-and 32-bit CPUs and memory chips with vast amounts of binary storage—are fabricated with thousands of transistors on a chip in "Very Large Scale Integration" (VLSI).

see also Boolean Algebra; Integrated Circuits; Transistors.

Richard A. Thompson

Bibliography

Booth, Taylor L. Digital Networks and Computer Systems. New York: Wiley, 1971.

Hill, Fredrick J., and G. R. Peterson. Introduction to Switching Theory and Logical Design. New York: Wiley, 1974.