VLSI & Adv Digital Dsgn
VLSI & Adv Digital Dsgn ECE 3060
Popular in Course
verified elite notetaker
Popular in ELECTRICAL AND COMPUTER ENGINEERING
This 0 page Class Notes was uploaded by Cassidy Effertz on Monday November 2, 2015. The Class Notes belongs to ECE 3060 at Georgia Institute of Technology - Main Campus taught by Vincent Mooney in Fall. Since its upload, it has received 15 views. For similar materials see /class/233852/ece-3060-georgia-institute-of-technology-main-campus in ELECTRICAL AND COMPUTER ENGINEERING at Georgia Institute of Technology - Main Campus.
Reviews for VLSI & Adv Digital Dsgn
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 11/02/15
ECE 3060 VLSI and Advanced Digital Design Lecture 10 TWO Level Logic Minimization Motivation We will study modern techniques for manipulating and minimizing boolean functions lssue Tractibility of minimization problem for large number of variables Exact methods Heuristic methods Issue Representation of boolean expressions in a form conducive to boolean operations Implicant tables Binary decision diagrams Issue Manipulation of realistic multilevel networks 0 Graph representations multilevel minimization Technology mapping E CE 3060 Lecture 10 2 Definitions Binary space B 0 1 Operations OR AND NOT Single output fB a B Incompleter specified single output function fiB 01 Multiple output fB a Bm Incompleter specified multiple output function fiB 01m E CE 3060 Lecture 10 3 Cube Representation B can be represented by a binary ncube ie an n dimensional binary hypercube Cl a ab ab 6 le C abc Z abc b As usual literals may be replaced with binary values Le 6150 E 010 Adjacent minterms vertices differ in only one vari able similar to Kmap E CE 3060 Lecture 10 4 Definitions Boolean variable a e B Boolean literal a or 21 Product or cube product of literals lmplicant product term implying a value of a function usually TRUE 0 binary hypercube in the boolean space Minterm product using all input variables implying a value of a function usually TRUE vertex in the boolean space E CE 3060 Lecture 10 5 Tabular Representations Truth table 0 list of all minterms of a function Implicant table or cover 0 list of all implicants of a function sufficient to define the function Comment Implicant tables are smaller in size Example Cover x ab ac y abbcac 11 01 11 11 11 E CE 3060 Lecture 10 6 Cube Representation F 555Zz cal cabcab5 F 2113Bcacab ECE 3060 Lecture 10 7 Prime Definitions Prime implicant implicant not contained by any other implicant Prime cover 0 cover of prime implicants Essential Prime Implicant EPI there is at least one minterm covered by EPI and not covered by any other prime implicant E CE 3060 Lecture 10 8 Two level logic optimization Assumptions 0 primary goal is to reduce the number of implicants all implicants have the same cost secondary goal is to reduce the number of literals Minimum cover 0 0 cover of the function with the minimum number of implicants global optimum 001 E CE 3060 Lecture 10 9 Minimal or Irredundant Cover Cover of the function that is not a proper superset of another cover 0 no implicant can be dropped 0 local optimum 001 E CE 3060 Lecture 10 10 Minimal Cover with respect to singleimplicant containment no implicant is contained by any other implicant weak local optimum E CE 3060 Lecture 1 0 1 I Logic Minimization Exact methods compute minimum cover 0 often intractable for large functions 0 based on QuineMcCluskey method Heuristic methods 0 Compute minimal cover possibly minimum There are a large variety of methods and programs 0 academic MINI PRESTO ESPRESSO UCBerkeley industry Synopsys Cadence Mentor Graphics Zuken E CE 3060 Lecture 10 12 Exact Logic Minimization Quine s theorem 0 There is a minimum cover that is prime 0 Consequently the search for minimum cover can be restricted to prime implicants QuineMcCuskey method 1 compute prime implicants 2 determine minimum cover Via branching Petrick s method 1 compute prime implicants 2 determine minimum cover Via covering clause E CE 3060 Lecture 10 13 Computing Prime Implicants The Hamming weight of a minterm is the number of ones in that minterm Start with list of minterms sorted by Hamming weight 1 Combine all possible implicants minterms using Qty or 0L Note that this algebraic reduction speci es two implicants with Hamming weights that differ by one 2 Group resulting implicants by Hamming weight 3 Repeat 1 and 2 on the resulting implicants until no further factoring is possible ie all implicants are prime Example f gzz z555dazcaabadabcaabcd abcd 61556 abcc l abcc l E CE 3060 Lecture 10 14 Prime Implicant Table Rows minterms Columns prime implicants Exponential size for a function fB a B o 2 minterms up to 3nn prime implicants E CE 3060 Lecture 1 0 15 Example 0 Function f 1135 1130 all 90 abc ab Primes Label 06 B Y 5 PIs W T T T Implicant Table Primes Minterms 0L 3 y 6 Ell 5 1 O 0 5136 1 1 O O aim O 1 1 0 abc 0 0 1 1 abg O O O 1 Choose cover by selecting a set of implicants which cover all minterms ECE 3060 Lecture 1 0 1 6 Cube Representation 71111 111 001 001 110 110 000 000 a prime implicants E b minimum cover E CE 3060 Lecture 10 1 7 Petrick s Method Determine minimum cover via covering clause 1 Write covering clauses in p05 form 2 Multiply out p05 form into 50p form and simpify 3 Select cube of minimum size Covering clause describes necessary and sufficient conditions to cover function Note multiplying out clauses is exponential Example 0 pos clauses ococ 3B yy 88 Each term covers a minterm sop clauses 0438 ow Covers x 3 8 or ocy 8 E CE 3060 Lecture 10 18 Exact Twolevel Logic Minimization Matrix representation Covering problem Reduction strategies Branch and bound covering algorithm E CE 3060 Lecture 10 19 Matrix representation View implicant table of some function f as Boolean matrix A 0 av 1 gt the ith minterm is covered by thejth prime implicant The Boolean selection vector x selects which prime implicants will be in the cover To cover find an x which satisfies 3212 l v z39 Ax y ie select enough columns to cover all rows To find a minimum cover minimize cardinality of x ie the number of nonzero entries of x E CE 3060 Lecture 10 20 Example The magnitude of yl indicates the number of prime implicants which cover the ith minterm 1000 1100 0110 0011 0001 H O H H II gt gt gt l gt E CE 3060 Lecture 10 21 Branch and Bound Algorithm Exact algorithm but not polynomial time First step Remove Essential Prime lmplicants EPls which are columns incident to one or more rows with a single 1 in them Modify A by removing the column and incident rows Example rows 1 and 5 from previous matrix J J l CD CD A becomes 1 1 l a g k w P P CD CD l l CD CD E CE 3060 Lecture 10 22 Reduction Strategies Column implicant dominance a column 1 dominates columnj iff for all rows k akl 2 akj 100 011 010 100 o In this example which columns dominate any dominated column 139 may be removed because the implicant corresponding to column 139 is not prime E CE 3060 Lecture 10 23 Reduction Strategies Row minterm dominance a row k dominates row 1 iff for all columns 1 akl 2 100 001 010 110 0 Which rows dominate a row k which dominates another row I may be removed because whichever implicant is eventually chosen to cover I will also cover k E CE 3060 Lecture 10 24 Branching Algorithm Remove essential primes from consideration Perform a depthfirst search of remaining covers Bounding algorithm used to prune search tree E CE 3060 Lecture 10 25 Branch and Bound Algorithm EXACTCOVERA x b b is current best estimate gt Reduce matrix A and update corresponding x Calculate currenlieslimale for this branch we don t cover this gt if currenliestimate gt b return b if A has no rows return x Select a branching column c xc l this changes element 0 in x gt A A after deleting column 0 and rows incident to c Sc EXACTCOVERA x b ifc ltb b 57 xc O A A after deleting column 0 Sc EXACTCOVERA x b ifcltb b 5c return b E CE 3060 Lecture 10 26 Example 11000 x1 1 01100 x2 1 ConsiderA00110xx3b1 00011 x4 1 10001 x5 1 There are no essential primes and no row or column dominance Denote the implicants P and the minterms as I Choose P1 ie c 1 E CE 3060 Lecture 1 0 2 7 11000 1 P1 N 0110 x2 NOW1 00110x x3 00011 x4 10001 x5 Columns 2 and 5 are dominated after removing col umns 2 and 5 row 3 is dominating so I3 and 14 cover ing 112 and 113 are now essential so we get c3 1100 1 N 0 10 0 A 0 3 1andsince5cltbbx O 01 1 10001 0 E CE 3060 Lecture 10 28 Now we consider the solution without P1 1 000 0 N 100 1 A NOWA 00 1056 x3 P1P3P4 P2P4P5 00 x4 10 01 x5 Now column 2 is essential leaving column 3 domi nated and row 4 is dominating leaving columns 4 and 5 as essentials E CE 3060 Lecture 10 29