advertisement

EECS 150 - Components and Design Techniques for Digital Systems Lec 06 – Minimizing Boolean Logic 9/16-04 David Culler Electrical Engineering and Computer Sciences University of California, Berkeley http://www.eecs.berkeley.edu/~culler http://www-inst.eecs.berkeley.edu/~cs150 9/16/04 UCB EECS150 D. Culler Fa04 1 Review • Combinational logic • Truth Tables vs Boolean Expressions vs Gates • Minimal Operators – And / Or / Not, NAND, NOR • New Friends – XOR, EQ, Full Adder • Boolean Algebra – +, *, ~, assoc, comm, distr., …. • Manipulating Expressions and Circuits – – – – Proofs: Term rewriting & Exhaustive Enumeration Simplifications De Morgan’s Law Duality • Canonical and minimal forms – Sum of products – Product of sums 9/16/04 UCB EECS150 D. Culler Fa04 2 Review: Relationship Among Representations * Theorem: Any Boolean function that can be expressed as a truth table can be written as an expression in Boolean Algebra using AND, OR, NOT. unique ? not unique Boolean Expression [convenient for manipulation] Truth Table ? gate representation (schematic) not unique [close to implementaton] How do we convert from one to the other? Optimizations? 9/16/04 UCB EECS150 D. Culler Fa04 3 Review: Canonical Forms • Standard form for a Boolean expression - unique algebraic expression directly from a true table (TT) description. • Two Types: * * Sum of Products (SOP) Product of Sums (POS) • Sum of Products (disjunctive normal form, minterm expansion). Example: minterms a’b’c’ a’b’c a’bc’ a’bc ab’c’ ab’c abc’ abc 9/16/04 abc 000 001 010 011 100 101 110 111 f f’ 01 01 01 10 10 10 10 10 One product (and) term for each 1 in f: f = a’bc + ab’c’ + ab’c +abc’ +abc f’ = a’b’c’ + a’b’c + a’bc’ UCB EECS150 D. Culler Fa04 4 Review: Sum of Products (cont.) Canonical Forms are usually not minimal: Our Example: f = a’bc + ab’c’ + ab’c + abc’ +abc (xy’ + xy = x) = a’bc + ab’ + ab = a’bc + a (x’y + x = y + x) = a + bc f’ = a’b’c’ + a’b’c + a’bc’ = a’b’ + a’bc’ = a’ ( b’ + bc’ ) = a’ ( b’ + c’ ) = a’b’ + a’c’ 9/16/04 UCB EECS150 D. Culler Fa04 5 Review: Canonical Forms • Product of Sums (conjunctive normal form, maxterm expansion). Example: maxterms a+b+c a+b+c’ a+b’+c a+b’+c’ a’+b+c a’+b+c’ a’+b’+c a’+b’+c’ abc 000 001 010 011 100 101 110 111 f f’ 01 01 01 10 10 10 10 10 One sum (or) term for each 0 in f: f = (a+b+c)(a+b+c’)(a+b’+c) f’ = (a+b’+c’)(a’+b+c)(a’+b+c’) (a’+b’+c)(a+b+c’) Mapping from SOP to POS (or POS to SOP): Derive truth table then proceed. 9/16/04 UCB EECS150 D. Culler Fa04 6 Incompletely specified functions • Example: binary coded decimal increment by 1 – BCD digits encode decimal digits 0 – 9 in bit patterns 0000 – 1001 A 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 B 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 9/16/04 C 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 D 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 W 0 0 0 0 0 0 0 1 1 0 X X X X X X X 0 0 0 1 1 1 1 0 0 0 X X X X X X Y 0 1 1 0 0 1 1 0 0 0 X X X X X X Z 1 0 1 0 1 0 1 0 1 0 X X X X X X off-set of W on-set of W don't care (DC) set of W these inputs patterns should never be encountered in practice – "don't care" about associated output values, can be exploited in minimization UCB EECS150 D. Culler Fa04 7 Outline • Review • De Morgan’s to transform SofP into simple 2-level forms • Uniting Law to reduce SofP • N-cube perspective • Announcements • Karnaugh Maps • Examples • Reduction Algorithm 9/16/04 UCB EECS150 D. Culler Fa04 8 Putting DeMorgan’s to work DeMorgan’s Law: (a + b)’ = a’ b’ a + b = (a’ b’)’ (a b)’ = a’ + b’ (a b) = (a’ + b’)’ = = = = push bubbles or introduce in pairs or remove pairs. 9/16/04 UCB EECS150 D. Culler Fa04 9 Transformation to Simple Gates Sum of Products Involution: x = (x’)’ = De Morgans 9/16/04 UCB EECS150 D. Culler Fa04 10 Implementations of Two-level Logic • Sum-of-products – AND gates to form product terms (minterms) – OR gate to form sum • Product-of-sums – OR gates to form sum terms (maxterms) – AND gates to form product 9/16/04 UCB EECS150 D. Culler Fa04 11 Two-level Logic using NAND Gates • Replace minterm AND gates with NAND gates • Place compensating inversion at inputs of OR gate 9/16/04 UCB EECS150 D. Culler Fa04 12 Two-level Logic using NAND Gates (cont’d) • OR gate with inverted inputs is a NAND gate – de Morgan's: A' + B' = (A • B)' • Two-level NAND-NAND network – Inverted inputs are not counted – In a typical circuit, inversion is done once and signal distributed 9/16/04 UCB EECS150 D. Culler Fa04 13 Two-level Logic using NOR Gates • Replace maxterm OR gates with NOR gates • Place compensating inversion at inputs of AND gate 9/16/04 UCB EECS150 D. Culler Fa04 14 Two-level Logic using NOR Gates (cont’d) • AND gate with inverted inputs is a NOR gate – de Morgan's: A' • B' = (A + B)' • Two-level NOR-NOR network – Inverted inputs are not counted – In a typical circuit, inversion is done once and signal distributed 9/16/04 UCB EECS150 D. Culler Fa04 15 The Uniting Theorem • Key tool to simplification: A (B' + B) = A • Essence of simplification of two-level logic – Find two element subsets of the ON-set where only one variable changes its value – this single varying variable can be eliminated and a single product term used to represent both elements F = A'B'+AB' = (A'+A)B' = B' A B F 0 0 1 0 1 0 1 0 1 1 1 0 9/16/04 B has the same value in both on-set rows – B remains A has a different value in the two rows – A is eliminated UCB EECS150 D. Culler Fa04 16 Boolean cubes • Visual technique for identifying when the uniting theorem can be applied • n input variables = n-dimensional "cube“ • Neighbors “address” differs by one bit flip 11 01 0 1-cube 1 Y X 00 Y 000 101 Z 0111 1111 4-cube Y X 0000 9/16/04 10 X 111 3-cube 2-cube Z W X UCB EECS150 D. Culler Fa04 1000 17 Mapping truth tables onto Boolean cubes • Uniting theorem combines two "faces" of a cube into a larger "face" • Example: A B F 0 0 1 0 1 0 1 0 1 1 1 0 F 11 01 two faces of size 0 (nodes) combine into a face of size 1(line) B 00 A 10 A varies within face, B does not this face represents the literal B' ON-set = solid nodes OFF-set = empty nodes DC-set = 'd nodes 9/16/04 UCB EECS150 D. Culler Fa04 18 Three variable example • Binary full-adder carry-out logic A 0 0 0 0 1 1 1 1 B 0 0 1 1 0 0 1 1 Cin 0 1 0 1 0 1 0 1 Cout 0 0 0 1 0 1 1 1 (A'+A)BCin 111 B 000 AB(Cin'+Cin) 101 C A A(B+B')Cin the on-set is completely covered by the combination (OR) of the subcubes of lower dimensionality - note that “111” is covered three times Cout = BCin+AB+ACin 9/16/04 UCB EECS150 D. Culler Fa04 19 Higher dimensional cubes • Sub-cubes of higher dimension than 2 F(A,B,C) = m(4,5,6,7) 011 111 110 010 B 000 9/16/04 C 001 A 101 100 on-set forms a square i.e., a cube of dimension 2 represents an expression in one variable i.e., 3 dimensions – 2 dimensions A is asserted (true) and unchanged B and C vary This subcube represents the literal A UCB EECS150 D. Culler Fa04 20 m-dimensional cubes in a ndimensional Boolean space • In a 3-cube (three variables): – – – – 0-cube, i.e., a single node, yields a term in 3 literals 1-cube, i.e., a line of two nodes, yields a term in 2 literals 2-cube, i.e., a plane of four nodes, yields a term in 1 literal 3-cube, i.e., a cube of eight nodes, yields a constant term "1" • In general, – m-subcube within an n-cube (m < n) yields a term with n – m literals 9/16/04 UCB EECS150 D. Culler Fa04 21 Announcements • Homework 2 due Friday • Reading: 2.5-2.8 (rest of ch 2) • Homework 3 posted 9/16/04 UCB EECS150 D. Culler Fa04 22 Karnaugh maps • Flat map of Boolean cube – Wrap–around at edges – Hard to draw and visualize for more than 4 dimensions – Virtually impossible for more than 6 dimensions • Alternative to truth-tables to help visualize adjacencies – Guide to applying the uniting theorem – On-set elements with only one variable changing value are adjacent unlike the situation in a linear truth-table B A 0 1 9/16/04 0 0 1 1 0 1 2 3 1 0 A B F 0 0 1 0 1 0 1 0 1 1 1 0 UCB EECS150 D. Culler Fa04 23 Karnaugh maps (cont’d) • Numbering scheme based on Gray–code – e.g., 00, 01, 11, 10 – 2n values of n bits where each differs from next by one bit flip » Hamiltonian circuit through n-cube – Only a single bit changes in code for adjacent map cells C AB 0 C 1 00 11 01 A 0 2 6 4 1 3 7 5 10 A B A C 9/16/04 0 2 6 4 1 3 7 5 B C 0 4 12 8 1 5 13 9 3 7 15 11 2 6 14 10 B UCB EECS150 D. Culler Fa04 D 13 = 1101= ABC’D 24 Adjacencies in Karnaugh maps • Wrap from first to last column • Wrap top row to bottom row 011 A 000 010 110 100 C 001 011 111 101 B 9/16/04 111 110 010 B C 000 UCB EECS150 D. Culler Fa04 001 A 101 100 25 Karnaugh map examples • F= A • Cout = B 1 1 0 0 B’ • f(A,B,C) = m(0,4,6,7) A 0 0 1 0 Cin 0 1 1 1 B A C 1 0 0 1 0 0 1 1 B 9/16/04 AB + ACin + BCin AC + B’C’ + AB’ UCB EECS150 D. Culler Fa04 obtain the complement of the function by covering 0s with subcubes 26 More Karnaugh map examples A C 0 0 1 1 0 0 1 1 G(A,B,C) = A B A C 1 0 0 1 0 0 1 1 F(A,B,C) = m(0,4,5,7) = AC + B’C’ B A C 0 1 1 0 1 1 0 0 F' simply replace 1's with 0's and vice versa F'(A,B,C) = m(1,2,3,6) = BC’ + A’C B 9/16/04 UCB EECS150 D. Culler Fa04 27 K-map: 4-variable interactive quiz • F(A,B,C,D) = m(0,2,3,5,6,7,8,10,11,14,15) F= A C 1 0 0 1 0 1 0 0 1 1 1 1 1 1 1 1 0111 D C 0000 D A B 1111 1000 B find the smallest number of the largest possible subcubes to cover the ON-set (fewer terms with fewer inputs per term) 9/16/04 UCB EECS150 D. Culler Fa04 28 Karnaugh map: 4-variable example • F(A,B,C,D) = m(0,2,3,5,6,7,8,10,11,14,15) F= C + A’BD + B’D’ A C 1 0 0 1 0 1 0 0 1 1 1 1 1 1 1 1 0111 D C 0000 D A B 1111 1000 B find the smallest number of the largest possible subcubes to cover the ON-set (fewer terms with fewer inputs per term) 9/16/04 UCB EECS150 D. Culler Fa04 29 Karnaugh maps: don’t cares • f(A,B,C,D) = m(1,3,5,7,9) + d(6,12,13) – without don't cares » f= A’D + B’C’D A C 0 0 X 0 1 1 X 1 1 1 0 0 0 X 0 0 D B 9/16/04 UCB EECS150 D. Culler Fa04 30 Karnaugh maps: don’t cares (cont’d) • f(A,B,C,D) = m(1,3,5,7,9) + d(6,12,13) – f = A'D + B'C'D – f= without don't cares with don't cares A'D + C'D A C 0 0 X 0 1 1 X 1 1 1 0 0 0 X 0 0 B 9/16/04 D by using don't care as a "1" a 2-cube can be formed rather than a 1-cube to cover this node don't cares can be treated as 1s or 0s depending on which is more advantageous UCB EECS150 D. Culler Fa04 31 Design example: two-bit comparator A B 0 0 N1 A B N2 C D LT EQ GT AB<CD AB=CD AB>CD block diagram and truth table 0 1 1 0 1 1 C 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 D 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 LT 0 1 1 1 0 0 1 1 0 0 0 1 0 0 0 0 EQ 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 GT 0 0 0 0 1 0 0 0 1 1 0 0 1 1 1 0 we'll need a 4-variable Karnaugh map for each of the 3 output functions 9/16/04 UCB EECS150 D. Culler Fa04 32 Design example: two-bit comparator (cont’d) A C A 0 0 0 0 1 0 0 0 1 1 0 1 1 1 0 0 D C 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 D C A 0 1 1 1 0 0 1 1 0 0 0 0 0 0 1 0 B B B K-map for LT K-map for EQ K-map for GT LT = A' B' D + A' C + B' C D EQ = A'B'C'D' + A'BC'D + ABCD + AB'CD’ GT = B C' D' + A C' + A B D' D = (A xnor C) • (B xnor D) Canonical PofS vs minimal? LT and GT are similar (flip A/C and B/D) 9/16/04 UCB EECS150 D. Culler Fa04 33 Design example: two-bit comparator (cont’d) A B C D two alternative implementations of EQ with and without XOR EQ EQ 9/16/04 XNOR is implemented with at least 3 simple gates UCB EECS150 D. Culler Fa04 34 Design example: 2x2-bit multiplier A1 A2 B1 B2 P1 P2 P4 P8 block diagram and truth table A2 A1 B2 0 0 0 0 1 1 0 1 0 0 1 1 1 0 0 0 1 1 1 1 0 0 1 1 B1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 P8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 P4 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 P2 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 P1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 4-variable K-map for each of the 4 output functions 9/16/04 UCB EECS150 D. Culler Fa04 35 Design example: 2x2-bit multiplier (cont’d) A2 B2 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 K-map for P8 K-map for P4 P4 = A2B2B1' + A2A1'B2 B1 P8 = A2A1B2B1 B2 A2 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 A1 A1 A2 B2 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 A1 9/16/04 B1 K-map for P2 K-map for P1 P1 = A1B1 B1 P2 = A2'A1B2 + A1B2B1' + A2B2'B1 + A2A1'B1 UCB EECS150 D. Culler Fa04 B2 A2 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 B1 A1 36 Design example: BCD increment by 1 I1 I2 I4 I8 O1 O2 O4 O8 block diagram and truth table I8 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 I4 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 I2 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 I1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 O8 0 0 0 0 0 0 0 1 1 0 X X X X X X O4 0 0 0 1 1 1 1 0 0 0 X X X X X X O2 0 1 1 0 0 1 1 0 0 0 X X X X X X O1 1 0 1 0 1 0 1 0 1 0 X X X X X X 4-variable K-map for each of the 4 output functions 9/16/04 UCB EECS150 D. Culler Fa04 37 Design example: BCD increment by 1 (cont’d) I8 I2 0 0 X 1 0 0 X 0 0 1 X X 0 0 X X O8 I1 I2 0 0 X 0 1 1 X 0 0 0 X X 1 1 X X O8 = I4 I2 I1 + I8 I1' O4 = I4 I2' + I4 I1' + I4’ I2 I1I2 O2 = I8’ I2’ I1 + I2 I1' I4 I8 O4 0 1 X 0 0 1 X 0 1 0 X X 0 1 X X O2 O1 I1 I2 I8 1 1 X 1 0 0 X 0 0 0 X X 1 1 X X I4 UCB EECS150 D. Culler Fa04 I1 I4 O1 = I1' I4 9/16/04 I8 38 I1 Definition of terms for two-level simplification • Implicant – Single element of ON-set or DC-set or any group of these elements that can be combined to form a subcube • Prime implicant – Implicant that can't be combined with another to form a larger subcube • Essential prime implicant – Prime implicant is essential if it alone covers an element of ON-set – Will participate in ALL possible covers of the ON-set – DC-set used to form prime implicants but not to make implicant essential • Objective: – Grow implicant into prime implicants (minimize literals per term) – Cover the ON-set with as few prime implicants as possible (minimize number of product terms) 9/16/04 UCB EECS150 D. Culler Fa04 39 Examples to illustrate terms A C 0 X 1 0 1 1 1 0 1 0 1 1 0 0 1 1 B 6 prime implicants: A'B'D, BC', AC, A'C'D, AB, B'CD D essential minimum cover: AC + BC' + A'B'D A 5 prime implicants: BD, ABC', ACD, A'BC, A'C'D essential C minimum cover: 4 essential implicants 9/16/04 UCB EECS150 D. Culler Fa04 0 0 1 0 1 1 1 0 0 1 1 1 0 1 0 0 D B 40 Algorithm for two-level simplification • Algorithm: minimum sum-of-products expression from a Karnaugh map – Step 1: choose an element of the ON-set – Step 2: find "maximal" groupings of 1s and Xs adjacent to that element » consider top/bottom row, left/right column, and corner adjacencies » this forms prime implicants (number of elements always a power of 2) – Repeat Steps 1 and 2 to find all prime implicants – Step 3: revisit the 1s in the K-map » if covered by single prime implicant, it is essential, and participates in final cover » 1s covered by essential prime implicant do not need to be revisited – Step 4: if there remain 1s not covered by essential prime implicants » select the smallest number of prime implicants that cover the remaining 1s 9/16/04 UCB EECS150 D. Culler Fa04 41 Algorithm for two-level simplification (example) A A C X 1 0 1 0 1 1 1 0 X X 0 0 1 0 1 D C X 1 0 1 0 1 1 1 0 X X 0 0 1 0 1 1 0 1 0 1 1 1 0 X X 0 0 1 0 1 D 3 primes around AB'C'D' C X 1 0 1 0 1 1 1 0 X X 0 0 1 0 1 2 essential primes UCB EECS150 D. Culler Fa04 1 0 1 0 1 1 1 0 X X 0 0 1 0 1 D 2 primes around ABC'D A D B X B A X 9/16/04 C 2 primes around A'BC'D' A B D B B C A C X 1 0 1 0 1 1 1 0 X X 0 0 1 0 1 D B minimum cover (3 primes) 42 Summary • Boolean Algebra provides framework for logic simplification • De Morgans transforms between gate types • Uniting to reduce minterms • Karnaugh maps provide visual notion of simplifications • Algorithm for producing reduced form. • Question: are there programmable logic families that are simpler than FPGAs for the canonical forms? 9/16/04 UCB EECS150 D. Culler Fa04 43