Truth Tables and Karnaugh Maps
A truth table for a logic function is a list of input combinations 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 carryin input Cin, and two outputs Sum and carryout Cout.
Karnaugh maps are twodimensional visual representations 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 adjacent cells to become cpmbinable using the law AB + AB = A. For instance, cells abcd and abcd are combined as a product acd. For functions with large numbers of inputs, the corresponding truth tables or Karnaugh maps are too large.
Table 1. Truth Table of Full Adder

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) literal is a variable or a negated variable. In binary logic, symbol 0 corresponds to a negated variable, symbol 1 to a positive (affirmative, 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 product 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 products, products of sums, or others. For instance, the array of cubes {01X1, 11XX} describes the sumofproducts 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 – sivesumofproducts expression x1x2x4 ® x1x2, or a productof – 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 important operators (operations) are negation of a single cube or nondisjoint sharp, disjoint sharp, consensus, crosslink, intersection, 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 remove part of the function that has been already taken care of. Consensus of cubes A and B is the largest cube that includes 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 (ANDOR) logic. Crosslink is the chain of cubes between 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 (ANDEXOR) logic, for instance, in exclusive – sumofproducts 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 calculus extends these representations and operations to multivalued variables. In multivalued logic, each variable can have several values from a set of values. For a nvalued variable, all its literals are represented by nelement 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 4valued logic, the literal X0,1,2 is represented as a binary string 1110, which means the following assignment of values: X0 = 1, X1 = 1, X2 = 1, Xs = 0. It means, the literal X{01’21 is a 4valuedinput binaryoutput function defined 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 4valued model used in programmable logic array (PLA) minimization, a 4valued set variable corresponds 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 compositions of cube arrays (each array specifies a two level logic block). Factored form is thus represented as a multiDAG (directed 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 primary 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 multilevel circuit, or are the inputs to other blocks of this circuit. Initial twolevel cube calculus description is factorized to such multilevel 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, factored forms, expressions, or netlists. The diagram is obtained by recursive application of Shannon expansion to the function, 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 similar reduction transformations in those diagrams which are more general than BDDs. Decision diagrams with such reductions 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 expansion 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 expansions of Boolean functions are thus included in KDD. Other known decision diagrams include zerosuppressed binary decision diagrams (ZSBDDs) and moment diagrams. They are used primarily in verification or technology mapping. Multivalued 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 diagrams and noncanonical diagrams. Canonical diagrams are used for function representation and tautology checking. ZSBDDs and KDDs are examples of canonical representations. An example of noncanonical decision diagrams is a free pseudoKronecker 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 pseudoKronecker decision diagrams are used in synthesis 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.
Leave a Reply