Representations of Logic Operations

Signals in digital circuits are driven to Vdd or GND, so they transport one binary digit (or bit) of information. It is common practice to represent the state of a binary signal using a ‘1’ for Vdd and a ‘0’ for GND. Two state (or “binary”) signals are used because they are very immune to noise, and because they efficiently drive transistor-based logic circuits (i.e., they fully turn ON or OFF the FETs used in logic circuits).

Logic circuits receives some number of binary input signals, combine them through various logic operations (like AND, OR, and NOT), and produce a binary output signals. A truth table is the primary tool for specifying the behavior of a logic circuit. A truth table shows all possible combinations of input signals, and what the output should be for each combination. Based on a truth table, straight-forward procedures can be used to find a logic circuit to implement the specified behavior.

Truth tables for common logic relationships are shown below. Note: the “exclusive or” (or “xor”) relationship, expressed in two variables as “A and not B, or B and not A”, is commonly regarded as one of the primary logic relationships even though it is a compound circuit constructed from other logic functions (ANDs, OR, and NOT). Xor circuits are frequently invoked in discussions about arithmetic and encryption circuits, and they will be presented in more detail later.

AND, OR, and NOT (or inversion) are the three primary logic relationships that can be used to express any logical relationship between any number of variables. Think of that for a moment – any logic system, from a simple toy to the most powerful computer ever built can be represented in terms of AND, OR, and NOT relationships.

SOP and POS circuits

A “product term” is defined as an AND relationship between any number of signals, and a “sum term” is defined as an OR relationship between any number of signals. Any logic system can be implemented in two different forms: using product terms (AND gates) to decode inputs, and then combining those terms with an OR gate – this is the “Sum of Products” (SOP) form; or using sum terms (OR gates) to decode the inputs, and then combining those terms with an AND gate – this is the “Product of Sums (POS) form. The SOP and POS forms use different logic gates, but they are equivalent – that is, they produce the same output signal for the same patterns of inputs. Often, the two forms require the same number of logic gates, but sometimes, one of the two forms is more efficient than the other.

A “canonical” SOP logic circuit (i.e., an un-minimized circuit that contains all possible logic terms) is easily derived from a truth table: include one n-input AND gate for each output row that contains a ‘1’ (where n is the number of inputs shown in the truth table), and attach ‘1’ inputs directly to the AND gate and attach ‘0’ inputs through an inverter; and attach all AND outputs to an m-input OR gate (where m is the number of ‘1’ output rows).

A canonical POS logic function is easily derived as well, by swapping ANDs, ORs and signal inversions: include one n-input OR gate for each output row that contains a ‘0’, and attach ‘0’ inputs directly to the OR gate and ‘1’ inputs through an inverter, and attach all OR outputs to an m-input AND gate (where m is the number of ‘1’ output rows).

Logic Functions

In a system with N input signals, there are 2^2^N possible logic functions. So, a two-input logic system has 16 possible logic functions, a three input logic system has 256 possible logic functions, a four input logic system has 65K possible functions, etc. The extended truth table below shows the 16 possible logic functions of two variables. Many of them have common names (AND, OR, NAND, etc.), and in fact only four possible functions (F2, F4, F11, and F13) are not associated with common relationships.

A truth table can always be used to represent a logic system, but a truth table is not always convenient to use for specification or documentation purposes. Various other methods have been invented to specify logic relationships, and most of them involve an output assignment operator and logic operators for common functions like AND, OR, and NOT. The table below shows the logic operators used in several different disciplines. Here, we will use the operators and notations associated with logic equations, Verilog, and schematics.

Based on these logic operators, behavioral logic functions can be written as logic equations and as Verilog descriptions, and/or translated to structural schematic pictures. Several single-gate representations and two slightly more complex examples are shown below.

:

Minterms and Maxterms

Any product term than contains all the input signals is called a “minterm”, and any sum term that contains all the input signals in called a “maxterm”. Minterms and maxterms are identified by their row numbers in the truth table, as so for any given system, the numbers range from [0 – 2N], where N is the number of input signals. The binary row numbers for minterms can be converted to an AND’ed term involving all input signals by mapping a ‘1’ input to a non-inverted input signal, and a ‘0’ input to an inverted singal; the binary row numbers for maxterms can be converted to an OR’ed term involving all input signals by mapping a ‘1’ input to an inverted signal, and a ‘0’ input to a non-inverted. From this, “minterm coding” means mapping a ‘0’ input to an inverted signal and a ‘1’ input to a non-inverted signal in an AND’ed term, and “maxterm coding” means mapping a ‘0’ input to a non-inverted and a ‘1’ input to an inverted signal in an OR’ed term.

It is common practice, particularly when dealing with computer-based representation, to describe a logic circuit by the minterms or maxterms that are present in the system. A “minterm equation” describes an SOP circuit, and so borrows the summation symbol to denote the summing (OR’ing) of terms; a maxterm equation describes a POS circuit, and so borrows the product symbol to denote finding a product. The following example shows the relationships between all the forms of logic system representations that we will use.