### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# VLSI & Adv Digital Dsgn ECE 3060

GPA 3.64

### View Full Document

## 15

## 0

## Popular in Course

## 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

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

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

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.