Introduction to Combinational Logic Circuits

Building Blocks of Digital Circuits

657

Overview of Combinational Logic Circuit

Combinational logic circuits use networks of logic gates to produce outputs that change in strict relation to input changes; that is, an output can only change state immediately after an input changes state. In a combinational circuit, some input signal changes propagate through the logic gates and interconnections and produce output signal changes, while some input changes may have no effect on outputs; furthermore, the same input patterns will always produce the same outputs. In contrast, outputs from a sequential circuit, or a circuit that contains memory devices, can change irrespective of input signal changes, and the same input patterns applied at different times can produce different outputs (memory containing circuits are covered in a later module). All combinational circuits can be expressed in two forms: an OR’ing of AND’ed terms, or an AND’ing of OR’ed terms. Since these general forms, called Sum of Products (or SOP) and Product of Sums (or POS), can be used to express any combinational logic requirement, we will examine them in some detail.

Define Combinational Circuit Behavior

Any given pattern of inputs to a combinational circuit will always produce the same outputs, regardless of when the inputs are applied. The behavior of combinational logic circuits is most typically identified and specified by a logic equation or by a truth table. Either of these methods provides a clear, concise, and unambiguous definition of how input signals are combined to drive outputs signals.

Logic equations arise naturally when a given worded problem is stated in a more rigorous engineering formalism. For example, the worded problem statement; the latch should be released when the EAST and WEST buttons are pressed simultaneously, or when the NORTH button is pressed provided the WEST button is not pressed at the same time, or whenever the SOUTH button is pressed all by itself. This could be cast in a logic equation as:

L=(EW)+(NW)+(SEWN)L = (E \cdot W) + (N \cdot \overline W) + (S \cdot \overline E \cdot \overline W \cdot \overline N)

A logic equation states behavioral requirements in a concise, unambiguous fashion. Often, for simple equations (as with the example), a structural circuit can be constructed directly from the equation.

Truth tables are perhaps the most rigorous expression of a combinational logic system, because they define output behavior under all possible combinations of inputs. A truth table for N variables contains 2N2^N rows, with each row showing a unique pattern of inputs. The rows are typically arranged so that each successive N-bit row is the next binary number in sequence from the preceding row. A circuit schematic can readily be defined from either a logic equation or from a truth table.

Combinational Logic Circuit Schematic

Figure 1.F=A⋅B+C⋅B can be interpreted in two ways.
Figure 1.F=A⋅B+C⋅B can be interpreted in two ways.

A circuit schematic for any logic equation can be easily created by substituting logic gate symbols for logical operators, and by showing inputs as signal wires arriving at the logic gates. Perhaps the only step requiring some thought is in deciding which logic operation (and therefore, which logic gate) drives the output signal, and which logic operations drive internal circuit nodes.

Any confusion can be avoided if parentheses are used liberally in logic equations to show operator precedence, or if rules of precedence are established. For example, a schematic for the logic equation F=AB+CBF= A \cdot B + C \cdot B might use an OR gate to drive the output signal F, and two AND gates to drive the OR gate inputs, or it might use a three-input AND gate to drive F, with AND inputs coming from the A and B signals directly and a B+CB+C OR gate. If no parentheses are used, then NAND/AND has the highest precedence, followed by XOR, then NOR/OR, and finally INV. In general, it is easiest to sketch circuits from logic equations if the output gate is drawn first.

Inversions in logic equations show when an input signal must be inverted prior to driving a logic gate and also when an output from a logic gate must be inverted. These inversions can map directly to inverters in schematics. For example, in the schematic for the equation F=AB+BCF = \overline{A \cdot B} + B \cdot \overline C below, an inverter is placed on the C input prior to a 2-input NAND gate and on the output of the ABA \cdot B gate as required by the equation. It is a common practice to “absorb” an inverter that follows a logic gate into the gate itself, by placing an inverting “bubble” on the gate output (if one did not exist), or removing an output bubble if one was already present. In fact, using an input or output bubble instead of an inverter often results in a more minimal CMOS circuit. For example, an inverter following an AND gate represents 8 transistors, while a NAND gate performing the same logic uses only 4 transistors. It is also common to absorb an input inverter into a subsequent logic gate, particularly if the inverted signal only drives one single logic input. The schematic in Fig. 1 above shows an example of absorbing inverters into gate symbols. The meaning of the one-bubble AND gate symbol for BCB \cdot C is clear: drive the gate output to a ‘1’ if B is a ‘1’ and C is a ‘0’.

Figure 2. Schematic with inversion shown as inverters or bubbles at input or output of a gate.
Figure 2. Schematic with inversion shown as inverters or bubbles at input or output of a gate.

Two “back-to-back” signal inversions cancel each other. That is, if a signal is inverted, and immediately inverted again before it is used anywhere else, then the circuit would perform identically if both inversions were simply removed.

This observation can be used to simplify circuits, or to make them more efficient. As an example, consider the circuits below in Fig. 3, both of which perform identical logic functions.The circuit on the right has been simplified by removing the two inverters on signal C, and made more efficient by adding inversions on internal nodes so that NAND gates (at four transistors each) could be used instead of AND/OR gates (at six transistors each).

Figure 3. Back to back signal inversions can make circuit more efficient.
Figure 3. Back to back signal inversions can make circuit more efficient.

Reading logic equations from schematics is also straightforward. The logic gate that drives the output signal defines the “major” logic operation, and it can be used to determine how other terms must be grouped in the equation. An inverter, or an output bubble on a logic gate, requires that the inverted signal or function output be shown in the output of the “downstream” gate (see Fig. 4 below). A bubble on the input of a logic gate can be thought of as an inverter on the signal leading to the gate.

Figure 4. Read logic equations from schematics.
Figure 4. Read logic equations from schematics.

Important Ideas

  • A circuit schematic for any logic equation can be easily created by substituting logic gate symbols for logical operators, and by showing inputs as signal wires arriving at the logic gates.
  • Reading logic equations from schematics is straightforward. The logic gate that drives the output signal defines the “major” logic operation, and it can be used to determine how other terms must be grouped in the equation.
  • Two “back-to-back” signal inversions cancel each other. That is, if a signal is inverted, and immediately inverted again before it is used anywhere else, then the circuit would perform identically if both inversions were simply removed.
  • When these circuits are used in schematic drawings, the well-known symbols shown below are used rather than the FET circuit diagrams (it would simply be too tedious to draw the FET circuits). A straight edge on the input side of a symbol and smoothly curved output side means AND, while a curved edge on the input side and pointed output side means OR.