## Truth Tables and Karnaugh Maps

A truth table for a logic function is a list of input combina­tions and their corresponding output values. Truth tables are suitable to present functions with small numbers of inputs (for instance, single cells of iterative circuits). Truth tables can be easily specified in hardware description languages such as VHSIC hardware description language (VHDL).

Table 1 shows the truth table of a full adder. A full adder is a logic circuit with two data inputs A and B, a carry-in input Cin, and two outputs Sum and carry-out Cout.

Karnaugh maps are two-dimensional visual representa­tions of truth tables. In a Karnaugh map, input variables are partitioned into vertical and horizontal variables, and all value combinations of input variables are expressed in Gray codes. The Gray code expressions allow the geometrically ad­jacent cells to become cpmbinable using the law AB + AB = A. For instance, cells abcd and abcd are combined as a prod­uct acd. For functions with large numbers of inputs, the corre­sponding truth tables or Karnaugh maps are too large.

Table 1. Truth Table of Full Adder

 A B Cin Sum Cout 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 1 0 1 1 1 0 0 1 1 1 1 1 1

Cube Representation. An array of cubes is a list of cubes, which is usually interpreted as a sum of products of literals, where a cube corresponds to a product of literals. A (binary) lit­eral is a variable or a negated variable. In binary logic, symbol 0 corresponds to a negated variable, symbol 1 to a positive (af­firmative, nonnegated) variable, symbol X to the absence of a variable in the product, and symbol e to a contradiction. A cube is a sequence of symbols 0, 1, X, and e, corresponding to their respective ordered variables. For instance, assuming the order of variables: x1, x2, x3, x4, the cube 01X1 corresponds to the prod­uct of literals x1x2x4, and the cube 0eX0 is an intermediate data generated to show contradiction or a nonexisting result cube of some cube operation. A minterm (a cell of a Karnaugh map and a row of a truth table) is thus a sequence of symbols 1 and 0. Arrays of cubes can also correspond to exclusive sums of prod­ucts, products of sums, or others. For instance, the array of cubes {01X1, 11XX} describes the sum-of-products expression x1x2x4 + x1x2 called also the cover of the function with product implicants (usually, with prime implicants). Depending on the context, the same array of cubes can also describe the exclu – sive-sum-of-products expression x1x2x4 ® x1x2, or a product-of – sums expression (x1 + x2 + x4) • (x1 + x2). The correct meaning of the array is taken care of by applying respective cube calculus operators to it.

An algebra of cube calculus has been created with cubes and arrays of cubes and operations on them. The most impor­tant operators (operations) are negation of a single cube or nondisjoint sharp, disjoint sharp, consensus, crosslink, inter­section, and supercube of two cubes. The cube operators most often used in EDA programs are presented briefly below. The nondisjoint sharp, A#B, creates a set of the largest cubes in function A • B. Disjoint sharp,^.#dB, creates a set of disjoint cubes covering function A • B. Sharp operations perform graphical subtraction and can be used in algorithms to re­move part of the function that has been already taken care of. Consensus of cubes A and B is the largest cube that in­cludes part of cube A and part of cube B. Supercube of cubes A and B is the smallest cube that includes entirely both cubes A and B. Consensus and supercube are used to create new product groups. Intersection of cubes A and B is the largest common subcube of cubes A and B. It is perhaps the most commonly used cube calculus operation, used in all practically known algorithms. These operations are used mostly in the inclusive (AND-OR) logic. Crosslink is the chain of cubes be­tween two cubes. The chain of cubes covers the same min – terms as the two cubes, and does not cover the minterms not covered by the two cubes. Since A ® A = 0, an even number of coverings is treated as no covering, and an odd number of coverings is treated as a single covering. It is used mostly in the exclusive (AND-EXOR) logic, for instance, in exclusive – sum-of-products minimization (21). Positive cofactor fa is function f with variable a substituted to 1. Negative cofactor fa is function f with variable a substituted to 0.

Cube calculus is used mostly for optimization of designs with two or three levels of logic gates. It is also used in test generation and functional verifications. Multivalued cube cal­culus extends these representations and operations to multi­valued variables. In multivalued logic, each variable can have several values from a set of values. For a n-valued variable, all its literals are represented by n-element binary vectors where value 0 in the position corresponds to the lack of this value in the literal, and value 1 to the presence of this value. For instance, in 4-valued logic, the literal X0,1,2 is represented as a binary string 1110, which means the following assign­ment of values: X0 = 1, X1 = 1, X2 = 1, Xs = 0. It means, the literal X{01’21 is a 4-valued-input binary-output function de­fined as follows: X{0’1,21 = 1 when X = 1, or X = 2, or X = 3, X10’1’21 = 0 when X = 4. Such literals are realized in binary circuits by input decoders, literal generators circuits, or small PLAs. Thus, multivalued logic is used in logic design as an intermediate notation to design multilevel binary networks. For instance, in 4-valued model used in programmable logic array (PLA) minimization, a 4-valued set variable corre­sponds to a pair of binary variables. PLA with decoders allow to decrease the total circuit area in comparison with standard PLAs. This is also the reason of using multivalued logic in other types of circuits. Well known tools like MIS and SIS from the University of California at Berkeley (UC Berkeley) (23) use cube calculus format of input/output data.

A variant of cube calculus representation are the factored forms (for instance, used in MIS), which are multilevel compo­sitions of cube arrays (each array specifies a two level logic block). Factored form is thus represented as a multi-DAG (di­rected acyclic graph with multiedges). It has blocks as its nodes and logic signals between them as multiedges. Each component block specifies its cube array and additionally its input and output signals. Input signals of the block are pri­mary inputs of the multilevel circuit, or are the outputs from other blocks of this circuit. Output signals of the block are primary outputs of the multi-level circuit, or are the inputs to other blocks of this circuit. Initial two-level cube calculus description is factorized to such multi-level circuit described as a factored form. Also, a multilevel circuit can be flattened back to a two level cube representation.

Binary Decision Diagrams.

Decision diagrams represent a function by a directed acyclic graph (DAG). In the case of the most often used binary decision diagrams (BDDs), the nodes of the graph correspond to Shannon expansions (realized by multiplexer gates), controlled by the variable a associated with this node: F = a • Fa + a • Fa. Shared BDDs are those in which equivalent nodes of several output functions are shared. Equivalent nodes g and h are those whose cofactor functions are mutually equal: ga = ha and ga = ha. Ordered BDDs are those in which the order of nodes in every branch from the root is the same. A diagram can be obtained from arbitrary function specifications, such as arrays of cubes, fac­tored forms, expressions, or netlists. The diagram is obtained by recursive application of Shannon expansion to the func­tion, next its two cofactors, four cofactors of its two cofactors, and so on, and by combination of any isomorphic (logically equivalent) nodes. The function corresponds to the root of the diagram. There are two terminal nodes of a binary decision diagram, 0 and 1, corresponding to Boolean false and true. If two successor nodes of a node Sj point to the same node, then node Sj can be removed from the DAG. There are other simi­lar reduction transformations in those diagrams which are more general than BDDs. Decision diagrams with such reduc­tions are called reduced ordered decision diagrams.

In addition, negated (inverted) edges are introduced in BDDs. Such edges describe negation of its argument function. In Kronecker decision diagrams (KDDs) three types of expan­sion nodes exist: Shannon nodes (realizing function f = a • fa + a • fa), positive Davio nodes [realizing function f = a • (fa ® fa) ® fa], and negative Davio nodes [realizing function f = a • (fa ® fa) ® fa]. All of the three possible canonical expan­sions of Boolean functions are thus included in KDD. Other known decision diagrams include zero-suppressed binary de­cision diagrams (ZSBDDs) and moment diagrams. They are used primarily in verification or technology mapping. Multi­valued decision diagrams have more than two terminal nodes and multivalued branchings with more than two successors of a node. These diagrams allow one to describe and verify some circuits (such as large multipliers) that are too large to be described by standard BDDs. Some diagrams may also be better for logic synthesis to certain technologies.

There are two types of decision diagrams: canonical dia­grams and noncanonical diagrams. Canonical diagrams are used for function representation and tautology checking. ZSBDDs and KDDs are examples of canonical representa­tions. An example of noncanonical decision diagrams is a free pseudo-Kronecker decision diagram. In this type of diagram, any types of Shannon and Davio expansions can be mixed in levels and all orders of variables are allowed in branches. Free pseudo-Kronecker decision diagrams are used in synthe­sis and technology mapping (21,22). Decision diagrams can be also adapted to represent state machines. By describing a state machine as a relation, the (logic) characteristic function of the machine can be described by a decision diagram.