Design of Digital Systems II Combinational Logic Design Principles Moslem Amiri, Vaclav Prenosil Embedded Systems Laboratory Faculty of Informatics, Masaryk University Brno, Czech Republic amiriOmail.muni.cz prenosilOfi.muni.cz October, 2012 Introduction • Combinational logic circuit • A circuit whose outputs depend only on its current inputs • May contain an arbitrary number of logic gates and inverters but no feedback loops • A feedback loop is a signal path that allows output of a gate to propagate back to input of that same gate • Such a loop creates sequential circuit behavior • Combinational circuit analysis • We start with a logic diagram and proceed to a formal description of function performed by that circuit, such as a truth table or a logic expression • Combinational circuit synthesis • Reverse of analysis • Starting with a formal description and proceeding to a logic diagram Moslem Amiri, Václav Přenosi Design of Digital Systems II October, 2012 2/69 Switching Algebra • Boolean algebra • A two-valued algebraic system • Is used to formulate propositions that are true or false, combine them to make new propositions, and determine truth or falsehood of the new propositions • Switching algebra • Adaptation of Boolean algebra to analyze and describe behavior of circuits • A physical condition—voltage HIGH or LOW, capacitor charged or discharged, and so on—is represented by a variable X that can have one of two possible values, 0 or 1 Moslem Amiri, Václav Přenosi Design of Digital Systems II October, 2012 3/69 Switching Algebra: Axioms • Axioms or postulates • A minimal set of basic definitions that we assume to be true, from which all other information about system can be derived • The first two axioms of switching algebra embody digital abstraction {Al) X = 0 ifX^l {AV) X = l ifX^O • The only difference between Al and AV is interchange of 0 and 1 • This is a characteristic of all axioms of switching algebra • This is basis of duality principle • If X denotes an inverter's input signal, X' denotes its output value {A2) If X = 0, then X' = 1 {A2') If X = 1, then X' = 0 • AND and OR operations (AND has precedence) (-43) 0-0 = 0 (-43') 1 + 1 = 1 (-44) 1-1 = 1 (-44') 0 + 0 = 0 (-45) 0-1 = 1-0 = 0 (-45') 1 + 0 = 0 + 1 = 1 • The five pairs of axioms, -41--45 and AV-Ab', completely define switching algebra • All other facts about system can be proved using these axioms as a staring point 4/69 Switching Algebra: Single-Variable Theorems • Switching-algebra theorems o True statements that allow us to manipulate algebraic expressions to allow simpler analysis or more efficient synthesis of corresponding circuits Table 1: Switching-algebra theorems with one variable. (Tl) x + o = x (Tl') X • 1 = X (Identities) (T2) X+ 1 = 1 (T2-) X •0 = 0 (Null elements) (T3) x + x = x (T3-) X • x = X (Idempotency) (T4) (xy=x (Involution) (T5) X + X'= 1 (T50 X ■X'= = 0 (Complements) • Perfect induction • A technique to prove theorems in switching algebra • Since a variable can take on only 0 and 1, prove a theorem involving a single variable X by proving that it is true for both X — 0 and X — 1 • E.g., to prove Tl [X — 0] —> 0 + 0 = 0 —> true, according to axiom AA' [X — 1] —> 1 + 0 = 1 —> true, according to axiom A5' Moslem Amiri, Václav Přenosi Design of Digital Systems II October, 2012 5/69 Switching Algebra: Two- and Three-Variable Theorems Table 2: Switching-algebra theorems with two or three variables. (T6) X + Y = Y + X (T7) (X + Y) + Z = X + (Y + Z) (T8) X-Y + X- Z = X-(Y + Z) (T9) X + X - Y = X (T10) X-Y + X-Y' = X (Tll) X-Y + X'-Z + Y-Z = X- Y+X'-Z (T6') X ■ Y = Y ■ X (Commutativity) (TV) (X • Y) • Z = X • (Y • Z) (Associativity) (T8') (X + Y) - (X + Z) = X + Y - Z (Distributivity) (T9') X • (X + Y)=X (Covering) (TIC) (X + Y) • (X + Y')=X (Combining) (Consensus) (Tlľ) (X + Y) ■ (X' + Z) • (Y + Z) = (X + Y) • (X'+ Z) • Theorems in Tab. 2 are proved by perfect induction, by evaluating theorem statements for all possible combinations of X and Y (and Z) • Proof ofT9:X + X- y = X- l + X- y = X-(l + y)=X-l = X • In Til, if Y • Z = 1, either X • Y or X' • Z must also be 1 • Thus, Y ■ Z term is redundant • Consensus theorem is used to eliminate certain timing hazards • It is possible to replace each variable in Tab. 2 with a logic expression 6/69 Switching Algebra: n-Variable Theorems Table 3: Switching-algebra theorems with n variables. (T12) X + X + •• • + X = X (Generalized idempotency) (T12') XX- - ■X = X (T13) (X, ■ x2■ - •X„)' = X1' + X2'+- + Xn' (DeMorgan's theorems) (T13') (X, + X2 + ■ •• +X„)' = X]' • x2' ■ ••• • x„ (T14) [F(X„X2„ ...,Xn,+,.)]' = F(X1',X2',...,Xn',.,+) (Generalized DeMorgan's theorem) (T15) F(X„X2,.. ,.,Xn) = X, ■ F(1X2,...,X„) + X,' ■ F(0,X2,...,Xn) (Shannon's expansion theorems) (T15') F(X„X2,.. ..,X„)= rX, + F(0,X2, ...,Xn)] ■ [X,'+ F(1,X2,...,X„)] • Theorems in Tab. 3 are proved using finite induction Q Basis step: prove theorem is true for n — 2 © Induction step: if theorem is true for n — i, it is also true for n — i + 1 • Example: T12 Q For n — 2, T12 — T3, therefore true Q If it is true for a logical sum of / X's, it is also true for a sum of / + 1 X's X's /' X's if T12 is true for n=i 7/69 Switching Algebra: n-Variable Theorems Figure 1: Equivalent circuits according to DeMorgan's theorem T13: (a) AND-NOT; (b) NOT-OR; (c) logic symbol for a NAND gate; (d) equivalent symbol for a NAND gate. Figure 2: Equivalent circuits according to DeMorgan's theorem T13': (a) OR-NOT; (b) NOT-AND; (c) logic symbol for a NOR gate; (d) equivalent symbol for a NOR gate. 8/69 • Principle of duality • Any theorem or identity in switching algebra remains true if 0 and 1 are swapped and • and + are swapped throughout • This is true because duals of all axioms are true, so duals of all switching-algebra theorems can be proved using duals of axioms • Dual of a logic expression FD(X1,X2,..., Xn, +, •/ ) F{X1,X2,.. • Generalized DeMorgan's theorem [F(X1,X2,...,Xn,+,-)] F(X[,X^,.. FD(X{,X>,. •, x'n, +, •) Moslem Amiri, Václav Přenosil Design of Digital Systems II October, 2012 9/69 Switching Algebra: Duality LOW LOW LOW HIGH HIGH LOW HIGH HIGH LOW LOW LOW HIGH 0 0 0 1 1 0 1 1 1 1 1 0 0 1 0 0 Figure 3: A "type-1" logic gate: (a) electrical function table; (b) logic function table and symbol with positive logic; (c) logic function table and symbol with negative logic. (a) type 2 (b) (c) type 2 X Y Z LOW LOW LOW LOW HIGH HIGH HIGH LOW HIGH HIGH HIGH HIGH X Y Z 0 0 0 1 1 0 1 1 0 1 1 1 x Y Z 1 1 1 0 1 0 0 1 0 0 0 0 Figure 4: A "type-2" logic gate: (a) electrical function table; (b) logic function table and symbol with positive logic; (c) logic function table and symbol with negative logic. Moslem Amiri, Václav Přenosi Design of Digital Systems II 10 / 69 Switching Algebra: Duality Figure 5: Circuit for a logic function using inverters and type-1 and type-2 gates under a positive-logic convention. Figure 6: Negative-logic interpretation of the previous circuit. 11 / 69 Switching Algebra: Duality • Figs. 5 and 6 • Fig. 5 shows a circuit corresponding to expression F(X\,X2, ■ ■ ■ ,Xn) following positive-logic convention • Circuit of Fig. 6 is that of Fig. 5 without change, but logic convention is changed from positive to negative • For every possible combination of input voltages (HIGH and LOW), the circuit still produces the same output voltage • But from point of view of switching algebra, output value—0 or 1—is opposite of what it was under positive-logic convention • Likewise, each input value is opposite of what it was • Therefore, for each possible input combination to circuit in Fig. 5, output is opposite of that produced by opposite input combination applied to circuit in Fig. 6 F(X1,X2,...,Xn) = [FD(X{,X2;,...,X>)Y By complementing both sides, we get generalized DeMorgan's theorem [F(X1,X2,...,Xn)Y = FD(X{, X'„) Moslem Amiri, Václav Přenosil Design of Digital Systems II 12 / 69 Standard Representations of Logic Functions • The most basic representation of a logic function is truth table • It lists output of circuit for every possible input combination Table 4: General truth table Table 5: Truth table for a particular structure for a 3-variable logic 3-variable logic function, function, F(X, Y, Z). F(X, Y, Z). Row X Y z F Row X Y z F 0 0 0 0 F(0,0,0) 0 0 0 0 1 1 0 0 1 F(0,0,1) 1 0 0 1 0 2 0 1 0 F(0,1,0) 2 0 1 0 0 3 0 1 1 F(0,1,1) 3 0 1 1 1 4 1 0 0 F(1,0,0) 4 1 0 0 1 5 1 0 1 F(1,0,1) 5 1 0 1 0 6 1 1 0 F(1,1,0) 6 1 1 0 1 7 1 1 1 F(l,l,l) 7 1 1 1 1 Moslem Amiri, Václav Přenosil Design of Digital Systems II 13 / 69 Standard Representations of Logic Functions • Literal • A variable or complement of a variable • Examples: X, Y, X', V » Product term • A single literal or a logical product of two or more literals • Examples: Z', W ■ X ■ Y\ X ■ V ■ Z, W ■ V ■ Z • Sum-of-products expression • A logical sum of product terms • Example: Z' + W ■ X ■ Y + X ■ V ■ Z + W ■ V ■ Z • Sum term • A single literal or a logical sum of two or more literals • Examples: Z', W + X + Y, X + V + Z, W + Y'+ Z • Product-of-sums expression • A logical product of sum terms • Example: Z' ■ (W + X + Y) ■ (X + Y' + Z) ■ (W + Y' + Z) Moslem Amiri, Václav Přenosil Design of Digital Systems II 14 / 69 Standard Representations of Logic Functions • Normal term • A product or sum term in which no variable appears more than once • A nonnormal term can always be simplified to a constant or a normal term • Examples of nonnormal terms: W-X-X-Y', W+W + X' +Y, X -X' -Y » Examples of normal terms: W ■ X ■ Y', W + X'+ Y 9 n-variable minterm • A normal product term with n literals • There are 2" such product terms • Examples of 4-variable minterms: W ■ X' ■ V ■ Z', W XY' • Z, W X' Y Z' • n-variable maxterm • A normal sum term with n literals • There are 2" such sum terms • Examples of 4-variable maxterms: W' + X'+Y' + Z', W + X' +Y' + Z, W + X' + Y + Z' 15 / 69 Standard Representations of Logic Functions • Correspondence between truth table and minterms and maxterms • A minterm is defined as a product term that is 1 in exactly one row of truth table • A maxterm is defined as a sum term that is 0 in exactly one row of truth table Table 6: Minterms and maxterms for a 3-variable logic function, F(X, Y,Z). Row X Y z F Minterm Maxterm 0 0 0 0 F(0,0,0) X'-Y'Z' X +Y + Z 1 0 0 1 F(0,0,1) X'Y'Z X +Y + Z' 2 0 1 0 F(0,1,0) X'Y Z' X +Y'+Z 3 0 1 1 F(0,1,1) X' ■ Y ■ Z X +Y'+Z' 4 1 0 0 F(1,0,0) X■Y'Z' X'+Y + Z 5 1 0 1 F(1,0,1) X ■ Y'Z X'+Y + Z' 6 1 1 0 F(1,1,0) X ■ Y Z' X'+Y'+Z 7 1 1 1 F(1,U) X Y Z X'+Y'+Z' Moslem Amiri, Václav Přenosil Design of Digital Systems II 16 / 69 Standard Representations of Logic Functions • Minterm i • The minterm corresponding to row / of truth table • A variable is complemented if corresponding bit in binary is 0 • Example: row 5 —> binary: 101 —> minterm 5: X ■ Y' ■ Z • Maxterm i • The maxterm corresponding to row / of truth table • A variable is complemented if corresponding bit in binary is 1 • Example: row 5 —> binary: 101 —> maxterm 5: X' + Y + Z' • Canonical sum of a logic function • A sum of minterms corresponding to truth-table rows (input combinations) for which the function produces a 1 output • Canonical product of a logic function • A product of maxterms corresponding to input combinations for which the function produces a 0 output Moslem Amiri, Václav Přenosi Design of Digital Systems II 17 / 69 Standard Representations of Logic Functions • In Tab. 5 • Canonical sum F= ]T (0,3,4,6,7) x,y,z = X' Y' Z' + X' Y Z + XY' Z' + X Y ■ Z' + XY • Z Notation ^2X Y z(0, 3,4, 6, 7) is a minterm list or on-set • Canonical product f — Y[ (i, 2,5) = (x + y + z'). (x + v + z) ■ (x' + y + z') Notation Y\x Y z(l, 2, 5) is a maxterm list or off-set row X Y z F 0 0 0 0 1 1 0 0 1 0 2 0 1 0 0 3 0 1 1 1 4 1 0 0 1 5 1 0 1 0 6 1 1 0 1 7 1 1 1 1 18 / 69 Standard Representations of Logic Functions • Conversion between a minterm list and a maxterm list • For a function of n variables, possible minterm and maxterm numbers are in the set {0,1,... ,2" - 1} • To switch between list types, take the set complement • Example ]T (0,1,2,3)= [] (4,5,6,7) A,B,C A,B,C ]r(i)=n(°<2<3) x,y x,y (0,1,2,3,5,7,11,13)= [] (4,6,8,9,10,12,14,15) w,x,y,z w,x,y,z • Each of these representations specifies exactly the same information Q A truth table © An algebraic sum of minterms, the canonical sum A minterm list using Yl notation O An algebraic product of maxterms, the canonical product O A maxterm list using Yl notation Moslem Amiri, Václav Přenosi Design of Digital Systems II 19 / 69 Combinational-Circuit Analysis • We analyze a combinational logic circuit by obtaining a formal description of its logic function • Operations possible after obtaining a formal description • Determining behavior of logic circuit for various input combinations • Manipulating an algebraic description to suggest different circuit structures • Transforming an algebraic description into a standard form corresponding to an available circuit structure • E.g., a sum-of-products expression corresponds directly to circuit structure used in PLAs, and a truth table corresponds to lookup memory used in most FPGAs • Using an algebraic description of circuit's functional behavior in analysis of a larger system that includes the circuit Moslem Amiri, Václav Přenosi Design of Digital Systems II 20 / 69 Combinational-Circuit Analysis • The most basic functional description is truth table • Obtain truth table of an n-input circuit by working the way through all 2" input combinations • For each input combination, determine all of gate outputs produced by that input, propagating information from circuit inputs to outputs • Truth table is written by transcribing output sequence of final gate 00001111 00110011 01010101 -1 00001111 T-- |^>o 11001100 1__> 11001111 4> 01010101 11110000 00110011 10101010 Figure 7: Gate outputs created by all input combinations. Moslem Amiri, Václav Přenosi Design of Digital Systems II 21 / 69 Combinational-Circuit Analysis Table 7: Truth table for the logic circuit of Fig. 7. Row X Y z F 0 0 0 0 0 1 0 0 1 1 2 0 1 0 1 3 0 1 1 0 4 1 0 0 0 5 1 0 1 1 6 1 1 0 0 7 1 1 1 1 • The number of input combinations of a logic circuit grows exponentially with the number of inputs • Instead of exhaustive approach, we normally use an algebraic approach • Complexity of algebraic approach is linearly proportional to size of circuit Moslem Amiri, Václav Přenosi Design of Digital Systems II 22 / 69 Combinational-Circuit Analysis • Algebraic approach • Build up a parenthesized logic expression corresponding to logic operators and structure of circuit • Start at circuit inputs and propagate expressions through gates toward output • Simplify expressions while going, or defer all algebraic manipulations until an output expression is obtained F = ((X + Y')-Z) +(X'-Y- Z') Figure 8: Logic expressions for signal lines. Moslem Amiri, Václav Přenosi Design of Digital Systems II 23 / 69 Combinational-Circuit Analysis • In Fig. 8, a sum of products is obtained by "multiplying out" output function F = ((X + Y') ■ Z) + (X' • Y ■ Z') = X • Z +Y' ■ Z + X' Y ■ Z' This new expression corresponds to a different circuit for the same logic function, as shown in Fig. 9 x- z Y'- Z -^ F = X- Z + Y'-Z+X' Y- Z' X' ■ Y ■ Z' Figure 9: Two-level AND-OR circuit. Moslem Amiri, Vaclav Přenosil Design of Digital Systems II 24 / 69 • Similarly, a product of sums is obtained by "adding out" output function of Fig. 8 F = ((X+Y')-Z) + (X' -Y-Z') = (X+Y' + X') ■ (X + Y' + Y) ■ (X + Y' + Z') ■ (Z + X') ■ (Z + Y) ■ (Z + Z') = 1 ■ 1 ■ (X + Y' + Z') ■ (X' + Z) ■ (Y + Z) ■ 1 = (X + Y' + Z') ■ (X' + Z) ■ (Y + Z) x X + Y'+Z Y Z X'+ Z o F = (X + Y' + Z') ■ (X' + Z) ■ (Y + Z) Figure 10: Two-level OR-AND circuit. Moslem Amiri, Václav Přenosil Design of Digital Systems II 25 / 69 Combinational-Circuit Analysis ((w-xr-Y)' r3> (W + X + Y')' [((W ■ X')' ■ Y)' + (W + X + Y')' + (W+ Z)']' Figure 11: Algebraic analysis of a logic circuit with NAND and NOR gates. F = [((1/1/ - X')' ■ Y)' + (W' + X + Y')' + (W + Z)']' = {{w' + xy + Y'y -{w-x' -Y)' -{W ■ zy = ((1/1/ ■ X')' ■ Y) • (W' + X + Y') ■ (W + Z) = ((l/l/' + X)• y) • (1/1/' + X + y') • (1/1/ + z) Moslem Amiri, Václav Přenosil Design of Digital Systems II 26 / 69 Combinational-Circuit Analysis • DeMorgan's theorem can be applied graphically to simplify algebraic analysis • We can cancel out some of inversions • In Fig. 12, this manipulation leads us to a simplified output expression directly F = ((W' + X) ■ Y) ■ (W + X+ Y') ■ {W + Z) (1) X)-Y)' -o= (W + X + Y')' I ~\ (W + Z)' ■) =((W'+X)-Y)-(W'+X + Y-) Figure 12: Algebraic analysis of the circuit in Fig. 11 after substituting some NAND and NOR symbols. Moslem Amiri, Václav Přenosil Design of Digital Systems I October, 2012 27 / 69 Combinational-Circuit Analysis • When we simplify a logic expression, we get an expression corresponding to a different physical circuit • E.g., simplified expression (1) corresponds to circuit of Fig. 13 z Figure 13: A different circuit for same logic function. • We could also multiply out and add out expression (1) to obtain sum-of-products and product-of-sums expressions corresponding to two more physically different circuits for same logic function 28 / 69 Combinational-Circuit Analysis • Logic expressions are not always used to convey information about physical structure of a circuit • An expression might describe more than one circuit structure • The only sure way to determine a circuit's structure is via its drawing • But, for certain classes of circuits, structural information could be described without reference to drawing • E.g., "a two-level NAND-NAND circuit for W ■ X ■ Y + Y ■ Z" Figure 14: Three circuits for G(W,X, Y, Z) = W ■ X ■ Y + Y ■ Z. (a) two-level AND-OR; (b) two-level NAND-NAND; (c) with 2-input gates only. 29 / 69 Com.-Circuit Synthesis: Circuit Descriptions and Designs • Sometimes, a logic circuit description is a list of input combinations, verbal equivalent of a truth table or or Yl notation • Example (prime-number detector): "Given a 4-bit input combination N = N3N2N1N0, produce a 1 output for N = 1, 2,3,5, 7,11,13 and 0 otherwise" • A logic function described in this way can be designed directly from canonical sum or product expression F= ]T (1,2,3,5,7,11,13) /V3,/V2,«!,«(, = A/3 • A/j • A/( • A/0 + A/3 • A/j • A/i • A/q + A/3 • A/j • A/i • A/0 + A/3 • A/2 • A/i • A/0 + A/3 • A/2 • A/i • A/0 + A/3 • A/2 • A/i • A/0 + A/3 • A/2 • A/{ • A/o Moslem Amiri, Václav Přenosil Design of Digital Systems II 30 / 69 Com.-Circuit Synthesis: Circuit Descriptions and Designs 4> N,' N p o o o N3' ■ N2' ■ Ni' ■ Nq N3' • N2' • N1 • N0' N3' • N2' • N1 • N0 N3' ■ N2 ■ Ni' ■ Nq N3' • N2 • N1 • N0 N3 • N2' • N1 • N0 N3 • N2 • N^ • Nq Figure 15: Canonical-sum design for 4-bit prime-number detector. Design of Digital Systems II October, 2012 Moslem Amiri, Václav Přenosi Com.-Circuit Synthesis: Circuit Descriptions and Designs • Often, we describe a logic function using English-language connectives "and," "or," and " not" • Example (alarm circuit): "ALARM output is 1 if PANIC input is 1, or if ENABLE input is 1, EXITING input is 0, and house is not secure; house is secure if WINDOW, DOOR, and GARAGE inputs are all 1" • Such a description can be translated directly into algebraic expressions ALARM = PANIC + ENABLE ■ EXITING' ■ SECURE' SECURE = WINDOW ■ DOOR ■ GARAGE ALARM = PANIC + ENABLE ■ EXITING' ■ (WINDOW ■ DOOR ■ GARAGE)' ENABLE PANIC ALARM EXITING WINDOW DOOR GARAGE D SECURE r>cJ Figure 16: Alarm circuit derived from logic expression. Moslem Amiri, Václav Přenosi Design of Digital Systems II October, 2012 32 / 69 Com.-Circuit Synthesis: Circuit Descriptions and Designs • Having an expression for a logic function, we can do some other operations • We can manipulate it to get different circuits • E.g., ALARM expression can be multiplied out to get sum-of-products circuit • We can construct the truth table for the expression and use any of synthesis methods that apply to truth tables • E.g., canonical sum or product method and minimization methods PANIC ■ ENABLE■ EXITING ■ WINDOW ■ DOOR ■ GARAGE■ — ALARM = PANIC ENABLE • EXITING' ■ WINDOW ENABLE • EXITING' ■ DOOR' ENABLE • EXITING' ■ GARAGE' Figure 17: Sum-of-products version of alarm circuit. Moslem Amiri, Václav Přenosi Design of Digital Systems II 33 / 69 Combinational-Circuit Synthesis: Circuit Manipulations • We can translate any logic expression into an equivalent sum-of-products expression by multiplying it out o Such an expression may be realized directly with AND and OR gates • By substituting gates: two-level AND-OR —> two-level NAND-NAND ib) <>- <>- =o Figure 18: Alternative sum-of-products realizations: (a) AND-OR; (b) AND-OR with extra inverter pairs; (c) NAND-NAND. Moslem Amiri, Václav Přenosil Design of Digital Systems II October, 2012 34 / 69 Combinational-Circuit Synthesis: Circuit Manipulations ib) -1>— t (c) w- Figure 19: Another two-level sum-of-products circuit: (a) AND-OR; (b) AND-OR with extra inverter pairs; (c) NAND-NAND. Moslem Amiri, Václav Přenosil Design of Digital Systems II 35 / 69 Combinational-Circuit Synthesis: Circuit Manipulations • We can translate any logic expression into an equivalent product-of-sums expression by adding it out • Such an expression has both OR-AND and NOR-NOR circuit realizations =E> 3D- (b) <>- -4>- Figure 20: Realizations of a product-of-sums expression: (a) OR-AND; (b) OR-AND with extra inverter pairs; (c) NOR-NOR. 36 / 69 Combinational-Circuit Synthesis: Circuit Manipulations (a) (b) -o Figure 21: Logic-symbol manipulations: (a) original circuit; (b) transformation with a nonstandard gate; (c) inverter used to eliminate nonstandard gate; (d) preferred inverter placement; one level of gate delay is eliminated, and bottom gate becomes a NOR instead of AND. Moslem Amiri, Václav Přenosi Design of Digital Systems II 37 / 69 Combinational-Circuit Synthesis: Minimization • Conmbinational-circuit-minimization methods have as their starting point a truth table or, equivalently, a minterm list or maxterm list • Given a logic function that is not expressed in this form, we must convert it to an appropriate form before using these methods • Minimization methods reduce cost of a two-level AND-OR, OR-AND, NAND-NAND, or NOR-NOR circuit in three ways 0 By minimizing number of first-level gates Q By minimizing number of inputs on each first-level gate © By minimizing number of inputs on second-level gate • This is a side effect of the first reduction • Minimization methods do not consider cost of input inverters • They assume both true and complemented versions of all input variables are available • Not always the case in gate-level or ASIC design • But, appropriate for PLD-based design where both true and complemented versions of all input variables are available for free Moslem Amiri, Václav Přenosi Design of Digital Systems II 38 / 69 Combinational-Circuit Synthesis: Minimization • Most minimization methods are based on combining theorems, T10 and Jiff given product term • Y + given product term • Y' — given product term (given sum term + Y) ■ (given sum term + Y') — given sum term • Applying this method repeatedly to combine minterms 1, 3, 5, and 7 of prime-number detector shown in Fig. 15 F= (1,3,5,7,2,11,13) = A/3 ■ A/2 ■ N[- N0 + A/3 ■ A/2 ■ Wi ■ W0 + A/3 ■ N2 ■ N[ ■ N0 + A/3 ■ N2 ■ Nx ■ N0 + ■ ■ ■ = (W3 ■ W2 ■ N[ ■ N0 + W3 ■ W2 ■ Wi ■ W0) + (W3 ■ W2 ■ W{ ■ W0 + W3 ■ W2 ■ Wj ■ W0) + ■ ■ ■ = W3 ■ W2 ■ W0 + W3 ■ W2 ■ W0 + ■ ■ ■ = W3 ■ Wo + ■ ■ ■ Moslem Amiri, Václav Přenosil Design of Digital Systems II 39 / 69 Combinational-Circuit Synthesis: Minimization N3 N3' N2N2'N, N,'N0N0' I I I I I I I I N3'-N0 o o N3'-N2'-N1 -N0' Ng-Ng'-N, -N0 N3 -n2 ' N(' ■ Nrj Figure 22: Simplified sum-of-products realization for 4-bit prime-number detector. • Working more on preceding expression, we could save a couple more first-level gate inputs Moslem Amiri, Václav Přenosil Design of Digital Systems I October, 2012 Combinational-Circuit Synthesis: Karnaugh Maps • Karnaugh map • A graphical representation of a logic function's truth table • Map for an n-input logic function is an array with 2" cells, one for each possible input combination or minterm • Number inside each cell is corresponding minterm number in truth table o Truth-table inputs are labeled alphabetically from left to right (e.g., X, Y,Z) • E.g., cell 13 in 4-variable map corresponds to truth table row in which WXYZ = 1101 y\ o_1_ 0 X y ,_ z\ 00 01 11 0 10 w wx Yz\ 00 01 11 10 12 (a) (b) Y (c) X Figure 23: Karnaugh maps: (a) 2-variable; (b) 3-variable; (c) 4-variable. Moslem Amiri, Václav Přenosil Design of Digital Systems II October, 2012 Combinational-Circuit Synthesis: Karnaugh Maps • To represent a logic function on a Karnaugh map, we copy Is and Os from truth table or equivalent to the corresponding cells of map w X y\ o 0 (a) 0 0 2 0 1 0 3 1 z\ 00 01 11 10 0 0 1 2 0 6 1 4 1 1 1 0 3 1 7 1 5 0 (b) yz\ 00 01 11 10 00 01 11 10 0 4 12 8 0 0 0 0 1 5 13 9 1 1 1 0 3 7 15 11 1 1 0 1 2 6 14 10 1 0 0 0 (c) Figure 24: Karnaugh maps for logic functions: (a) F — Ex y(3); (b) F = Ex,v,z(0, 3,4, 6, 7); (c) F = J2w,x,y,z(^ 2, 3, 5, 7,11,13). Moslem Amiri, Václav Přenosil Design of Digital Systems II 42 / 69 Com.-Circuit Synthesis: Minimizing Sums of Products • Particular order of row and column numbers in a Karnaugh map makes each cell correspond to an input combination that differs from each of its immediately adjacent neighbors in only one variable • Corresponding cells on left/right or top/bottom borders also differ in one variable and hence neighbors; e.g., cells 12 and 14 in 4-variable map • Each input combination with a "1" in truth table corresponds to a minterm in logic function's canonical sum • Pairs of adjacent "1" cells in map have minterms that differ in only one variable • Thus, minterm pairs can be combined into a single product term term • Y + term • Y' — term • Thus, we can use a Karnaugh map to simplify canonical sum of a logic function Moslem Amiri, Václav Přenosi Design of Digital Systems II 43 / 69 Com.-Circuit Synthesis: Minimizing Sums of Products (a) z\ 00 01 11 10 (b) Y'-Z Figure 25: F — ^2X Y z(l, 2, 5, 7): (a) truth table; (b) Karnaugh map; (c) combining adjacent 1-cells. • In Fig. 25(b) For cells 5 and 7: F=-+XY'Z + XYZ = • • • + (X ■ Z) ■ Y' + (X ■ Z) ■ Y — ■ ■ ■ + X ■ Z For cells 1 and 5: F = X' ■ Y' ■ Z + X ■ Y' ■ Z + • • • ^ X' ■ {Y' ■ Z) + X ■ {Y' ■ Z) +■ ■■ = V ■ z + • • • Moslem Amiri, Václav Přenosil Design of Digital Systems II 44 / 69 Com.-Circuit Synthesis: Minimizing Sums of Products • We can simplify a logic function by first combining pairs of adjacent 1-cells (minterms) wherever possible and then selecting a set of product terms that covers all of 1-cells and summing them • Fig. 25(c) shows the result for our example logic function • Corresponding AND-OR circuit is shown in Fig. 26 x x-z Y i_r X' ■ Y ■ z' z Figure 26: Minimized AND-OR circuit. Moslem Amiri, Václav Přenosil Design of Digital Systems II 45 / 69 Com.-Circuit Synthesis: Minimizing Sums of Products o In many logic functions, cell-combining procedure can be extended to combine more than two 1-cells into a single product term • Number of cells combined is always a power of 2 • Example X,Y,Z — X' ■ Y' ■ Z' + X' ■ Y' ■ Z + X ■ Y' ■ Z' + X ■ Y' ■ Z + X ■ Y ■ Z' = [(X' • Y') ■ Z' + (X' • Y') ■ Z] + [(X • Y') ■ Z' + (X • Y') ■ Z] + X • Y ■ Z' = X' ■ Y' + X • Y' + X • Y ■ Z' = [X' • (Y') + X • (Y')] + X Y ■ Z' — Y' + X ■ Y ■ Z' 2' 1-cells may be combined to form a product term containing n — i literals (n — number of variables in function) A set of 2' 1-cells are combined if there are / variables that take on all 2' possible combinations within that set, while remaining n — i variables have the same value throughout that set • Corresponding product term has n — i literals, where a variable is complemented if it is 0 in all of 1-cells, and uncomplemented if it is 1 Moslem Amiri, Vaclav Přenosi Design of Digital Systems II 46 / 69 Com.-Circuit Synthesis: Minimizing Sums of Products • Graphically, we circle rectangular sets of 2' Is, stretching definition of rectangular to account for wraparound at edges of map • For each variable, if a circle covers only areas of map where it is 0, the variable is complemented in product term • If a circle covers only areas of map where the variable is 1, the variable is uncomplemented in product term • If a circle covers areas of map where the variable is 0 as well as areas where it is 1, the variable does not appear in product term • Finally, a sum-of-products expression for a function must contain product terms that cover all of Is and none of 0s on map • By circling largest possible set of Is, a less expensive realization of logic function is found Moslem Amiri, Václav Přenosi Design of Digital Systems II 47 / 69 Com.-Circuit Synthesis: Minimizing Sums of Products (a) Figure 27: F — ^2X Y z(0,1, 4, 5, 6): (a) initial Karnaugh map; (b) Karnaugh map with circled product terms; (c) AND/OR circuit. Moslem Amiri, Václav Přenosi Design of Digital Systems II 48 / 69 Com.-Circuit Synthesis: Minimizing Sums of Products (a) \3 N2 00 01 I- 11 -1 10 00 0 4 12 8 01 1 5 1 13 1 9 11 3 1 7 1 15 10 2 1 6 14 10 N2 F = £N3,N2,N1 ,N0(1,2,3,5,7,11,13) (b) N,N0\ 3 IN2 I- 00 01 11 10 N3'-N0 N, 1 (1 1 i PI 1 (1 1 V-1 . N2-Ni'-No . N2' ■ N, ■ N0 N3'-N2'-N1 _, F = N3'-N0 + N3'- N2'-Ni + N2'-Ni -N0 + N2- Nj'-Nr, I_I N, 4>^ N3'-N2'-N1 -j ^ n3--n0 b-o N2'-N1 - No N2-N1'-N0 Figure 28: Prime-number detector: (a) initial Karnaugh map; (b) circled product terms; (c) minimized circuit. Moslem Amiri, Václav Přenosil Design of Digital Systems II October, 2012 49 / 69 Com.-Circuit Synthesis: Minimizing Sums of Products • Minimal sum of a logic function F{X\,..., Xn) Q Has the fewest possible product terms @ Within constraint 1, has the fewest possible literals • A logic function P{X\,... ,Xn) implies a logic function F{X\,... ,Xn) if for every input combination such that P = 1, then F = 1 too • " P implies F" = "F includes P" = "F covers P" = P F • Prime implicant of a logic function F{X\,... ,Xn) • A normal product term P(X\,..., Xn) that implies F, such that if any variable is removed from P, resulting product term does not imply F • In Karnaugh map, a prime implicant of F is a circled set of 1-cells, such that if we make it larger (twice as many cells), it covers one or more Os • Prime-implicant theorem o A minimal sum is a sum of prime implicants Moslem Amiri, Václav Přenosi Design of Digital Systems II 50 / 69 Com.-Circuit Synthesis: Minimizing Sums of Products (a) w wx Yz\ 00 01 11 10 0 4 12 1 8 1 5 1 13 1 9 3 7 1 15 1 11 2 6 14 1 10 (b) x-z wx w Yz\ 00 01 11 10 00 T 01 11 Y 10 1 1 1 1 ■ w-x X F = £WXYZ(5,7,12,13,14,15) X-Z + W-X Figure 29: F — x Y ^ 12,13,14,15): (a) Karnaugh map; (b) prime implicants. • Complete sum • Sum of all prime implicants of a logic function • Is not always minimal • E.g., logic function shown in Fig. 30 has five prime implicants, but minimal sum includes only three of them 51 / 69 Com.-Circuit Synthesis: Minimizing Sums of Products F = EW,X,Y,zO. 3,4,5,9,11,12,13,14,15) F = X ■ Y' + X'-Z + W'X Figure 30: F = YZw,x,Y,z(l> 3> 4> 5> 9> 1:L> 12>13'14' 15): (a) Karnaugh map; (b) prime implicants and distinguished 1-cells. • Distinguished 1-cell of a logic function • An input combination that is covered by only one prime implicant • Essential prime implicant of a logic function • A prime implicant that covers one or more distinguished 1-cells 52 / 69 Com.-Circuit Synthesis: Minimizing Sums of Products • First step in prime-implicant selection process • Identify distinguished 1-cells and corresponding essential prime implicants, and include them in minimal sum • In Fig. 30, three distinguished 1-cells are shaded, and corresponding essential prime implicants are circled with heavier lines • All of 1-cells are covered by essential prime implicants, so we need go no further • In Fig. 31, all of prime implicants are essential, and so all are included in minimal sum 53 / 69 Com.-Circuit Synthesis: Minimizing Sums of Products (a) WX Yz\ 00 01 11 W 10 1 12 X F = Ew x Y z(2,3,4,5,6,7,11,13,15) (b) WX YZ\ W T 1 1 s 1 1 1) i 1 W Y ■ W'-X ■ X-Z Y- Z W Y Y- Z Figure 31: F — £ffX Y z(2, 3, 4, 5, 6, 7,11,13,15): (a) Karnaugh map; (b) prime implicants and distinguished 1-cells. Moslem Amiri, Václav Přenosi Design of Digital Systems II 54 / 69 Com.-Circuit Synthesis: Minimizing Sums of Products w (a) wx Yz\ 00 01 11 10 00 w (b) wx YZ\ 00 01 11 10 00 (c) i 1 i 1 (i i) . i wx Yz\ 00 01 11 10 (1 ) X F = £w,x,Y,z(0.1,2,3,4,5,7,14,15) W-Y' + WX' + WXY + WZ Figure 32: F = E w,x,y,z(°> !> 2> 3>4' 5> 7'14' 15): (a) Karnaugh map; (b) prime implicants and distinguished 1-cells; (c) reduced map after removal of essential prime implicants and covered 1-cells. • In Fig. 32, by removing essential prime implicants and the 1-cells they cover, we obtain a reduced map with only a single 1-cell and two prime implicants that cover it • We use W ■ Z product term because it has fewer inputs and therefore lower cost Moslem Amiri, Václav Přenosi Design of Digital Systems II 55 / 69 Com.-Circuit Synthesis: Minimizing Sums of Products • Eclipse • Given two prime implicants P and Q in a reduced map, P is said to eclipse Q (P D Q) if P covers at least all 1-cells covered by Q • If P eclipses Q, then Q can be ignored when finding a minimal sum • In Fig. 33(c), X ■ Y ■ Z eclipses the other two prime implicants • X ■ Y ■ Z is a secondary essential prime implicant that must be included in minimal sum (a) wx Yz\ 00 01 00 11 10 (b) WX Yz\ 00 01 00 jT III (1 wx Yz\ 00 01 jT N X-YZ W ■ X ■ Y F = £w,x,Y,z(2,6,7,9,13,15) W ■ Y' ■ Z + W ■ Y ■ Z' + X ■ Y ■ Z Figure 33: F — zZw x y z(2, 6, 7, 9,13,15): (a) Karnaugh map; (b) prime implicants and distinguished 1-cells; (c) reduced map after removal of essential prime implicants and covered 1-cells. 56 / 69 Com.-Circuit Synthesis: Minimizing Sums of Products w (a) WX Yz\ 00 01 11 10 00 13 w (b) WX Yz\ 00 01 11 10 00 (11 1) rn (1 I0 iJ) WX ,-, Yz\ 00 01 11 10 (c) 00 r 01 1 (i Y 11 1 i) 10 —\ V.W-Y-Z W-X-Z W-X-Z + W-Y-Z + X'-Y'-Z \ 00 01 I- 11 -1 10 00 01 (1 1) Tl 11 (1 1 10 \ \ W-X'-Z ■X-Y-Z X-Y- Z + W-X' -Z+ W-Y'- Z Figure 34: F = x y z(1> 5, 7, 9,11,15): (a) Karnaugh map; (b) prime implicants (no essential); (c) a minimal sum; (d) another minimal sum. Design of Digital Systems II October, 2012 Moslem Amiri, Václav Přenosi Com.-Circuit Synthesis: Minimizing Product of Sums Using principle of duality, we can minimize product-of-sums expressions by looking at Os on a Karnaugh map • Each 0 on map corresponds to a maxterm in canonical product of logic function • To find minimal product, we write sum terms corresponding to circled sets of Os • In Fig. 35 F = (X+Y' + Z)-(X' + Z')-(Y + Z') (a) X Y z\ 00 01 11 10 (b) Figure 35: F — Y[x y z(l> 2, 5, 7): (a) truth table; (b) Karnaugh map; (c) combining adjacent 0-cells. Moslem Amiri, Václav Přenosi Design of Digital Systems II 58 / 69 Com.-Circuit Synthesis: Minimizing Product of Sums • Indirect method to find minimal product • For circled sets of Os in Karnaugh map, write product terms • Equate F' to minimal sum • Use DeMorgan's theorem to find F • E.g., for Fig. 35(c), product terms of circled Os are: X' ■ Y ■ Z', X ■ Z, V ■ Z F' — X' ■ Y ■ Z' + X ■ Z + Y' ■ Z [F'Y — [X' ■ Y ■ Z' + X ■ Z + Y' ■ Z]' F = (X + Y' + Z) ■ (X' + Z') ■ (Y + Z') 9 PLD minimization • PLDs have an AND-OR array corresponding to sum-of-products form • Most PLDs, also have an inverter/buffer at output of AND-OR array, which can be programmed to invert or not • Thus, PLD can utilize the equivalent of minimal sum by using AND-OR array to realize complement of desired function and then programming inverter/buffer to invert • Most logic-minimization programs for PLDs find both minimal sum and minimal product and select the one that requires fewer terms 59 / 69 Timing Hazards • Predicting steady-state behavior of combinational logic circuits • Predicting a circuit's output as a function of its inputs under assumption that inputs have been stable for a long time, relative to delays in circuit's electronics » Circuit delay is ignored • But actual delay from an input change to corresponding output change in a real circuit is nonzero • Transient behavior of a combinational logic circuit • Considers circuit delays • May differ from what is predicted by a steady-state analysis • A circuit's output may produce a short pulse, called a glitch, at a time when steady-state analysis predicts that output should not change • A hazard exists when a circuit has possibility of producing such a glitch • A logic designer must eliminate hazards Moslem Amiri, Václav Přenosi Design of Digital Systems II 60 / 69 Timing Hazards: Static Hazards • Static-l hazard • A pair of input combinations that O Differ in only one input variable © Both give a 1 output such that it is possible for a momentary 0 output to occur during a transition in the differing input variable Figure 36: Circuit with a static-l hazard: (a) logic diagram; (b) timing diagram (X — 1, Y — 1, Z : 1 —>• 0, propagation delay through each gate or inverter is one unit time). (a) Moslem Amiri, Václav Přenosil Design of Digital Systems II 61 / 69 Timing Hazards: Static Hazards • Static-0 hazard c A pair of input combinations that O Differ in only one input variable Q Both give a 0 output such that it is possible for a momentary 1 output to occur during a transition in the differing input variable Figure 37: Circuit with static-0 hazards: (a) logic diagram; (b) timing diagram. Moslem Amiri, Vaclav Prenosil Design of Digital Systems II 62 / 69 Timing Hazards: Static Hazards • A Karnaugh map can be used to detect static hazards in a two-level sum-of-products or product-of-sums circuit • A properly designed two-level sum-of-products (AND-OR) circuit has no static-0 hazards • A static-0 hazard would exist only if both a variable and its complement were connected to the same AND gate, which would be silly • But the circuit may have static-1 hazards (a) XY z\ 00 01 11 10 0 (1 1) 1 f (1 1) Y-Z (b) X- Z' z\ 00 01 11 Y-Z 10 X-Z' z X-Y X-Z' + Y-Z X-Z' + Y- Z + X- Y Figure 38: Karnaugh map for the circuit of Fig. 36: (a) as originally designed; (b) with static-1 hazard eliminated. Moslem Amiri, Václav Přenosi Design of Digital Systems II 63 / 69 Timing Hazards: Static Hazards In Fig. 38 There is no single product term that covers both input combinations X,Y,Z= 111 and X,Y,Z= 110 • Possible for output to glitch momentarily to 0 if AND gate output that covers one of combinations goes to 0 before AND gate output covering the other input combination goes to 1 To eliminate hazard, include an extra product term (AND gate) to cover hazardous input pair a The extra product term to be added is consensus of the two original terms Figure 39: Circuit of Fig. 36 with static-1 hazard eliminated. Moslem Amiri, Václav Přenosil Design of Digital Systems II 64 / 69 Timing Hazards: Static Hazards X ■ Y' ■ Z (a) W X YZ \ 00 '01 11 10 wz 00 (b) W ■ X ■ Y' W Y X-Y'-Z' + W'-Z + W-Y W wx Yz\ 00 01 11 10 'it uJ '1s -1 (1 i i 1) (t- F = X-Y'-Z' + W'-Z + W-Y + W'-X-Y' + Y-Z + W-X- Z' Figure 40: Karnaugh map for another sum-of-products circuit: (a) as originally designed; (b) with extra product terms to cover static-1 hazards. Moslem Amiri, Vaclav Přenosi Design of Digital Systems II 65 / 69 Timing Hazards: Static Hazards • A properly designed two-level product-of-sums (OR-AND) circuit has no static-1 hazards • But, it may have static-0 hazards • These hazards can be detected and eliminated by studying adjacent Os in Karnaugh map F = (X' + Z) ■ (V + Z) F = (X' + Z) ■ (V + Z) ■ (X' + Y') Figure 41: Karnaugh map for a product-of-sums circuit: (a) as originally designed; (b) with extra sum term to cover the static-0 hazard. Moslem Amiri, Václav Přenosi Design of Digital Systems II 66 / 69 Timing Hazards: Dynamic Hazards • Dynamic hazard • Possibility of an output changing more than once as the result of a single input transition • Multiple output transitions can occur if there are multiple paths with different delays from the changing input to the changing output w o 0 0 X Y 0 t> t> 0 > 0 F 0 Z Figure 42: Circuit with a dynamic hazard. Moslem Amiri, Václav Přenosi Design of Digital Systems II 67 / 69 Timing Hazards: Dynamic Hazards • In Fig. 42 • Three different paths with different delays from input X to output F • If all of gates except the two marked "slow" and "slower" are very fast, the transitions shown in black occur first, and output goes to 0 • Then, output of "slow" OR gate changes, creating transitions shown in nonitalic color, and output goes to 1 o Finally, output of "slower" OR gate changes, creating transitions shown in italic color, and output goes to 0 • Dynamic hazards do not occur in a properly designed two-level AND-OR or OR-AND circuit • In such a circuit, no variable and its complement are connected to the same first-level gate Moslem Amiri, Václav Přenosi Design of Digital Systems II 68 / 69 References ^ John F. Wakerly, Digital Design: Principles and Practices (4th Edition), Prentice Hall, 2005. 69 / 69