### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Class Note for ECE 474A with Professor Lysecky at UA

### View Full Document

## 18

## 0

## Popular in Course

## Popular in Department

This 7 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Arizona taught by a professor in Fall. Since its upload, it has received 18 views.

## Popular in Subject

## Reviews for Class Note for ECE 474A with Professor Lysecky at UA

### 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: 02/06/15

Twolevel Logic Optimization Part 2 Exact Algorithm vs Heuristics QuineMcCluskey 39 Calculated all prime implicaan to derive the optimal solutions 39 Petrick s Method derives all covers to determine minimum cover sets 39 Number of prime implicants grow quickly solution space is huge 39 Finding the minimum cover set in aclass of NP complete problems Determining optimal solution is difficult 0 Move to heuristics 39 Look at generating a quality solution quickly not necessarily optimal Eon 67625752 2 at u Sum Lyszcky Logic Optimization Techniques Logic Optimization Techniques 39 Kmaps Graphical 39 QuineMcCluskey Exact Algorithm 39 Espresso Heuristic Other Generalized Heuristics 39 Branchandbound 39 Simulated Annealing 39 Dynamic Programming 39 manymore exists aca 67625752 Susan Lysecky 3am Local Search Don t generating all prime implicants and minterrns Instead ESPRESSO successively modify a given initial cover 39 This technique is called a local search algorithm Idea behind local search 39 Search space or solution space set of all possible Values and cost associated with solution 39 Start with an initial Value 39 Search allpoints inneighborhoodfor afeasible point whose cost is less than current Different problems have different neighborhood de nitions 39 If one is found start process over aca 67625752 Susan Lysecky cost of a Soiutioi i possibie soiutions mu Local Search Drawback of local searches is local optimality 39 Solution is locally optimal if its neighborhood does not contain any solutions with a lower cost 39 Locally optimal solution may not be the optimal solution 0 Modify local search so we don t get stuck at the local minimum PM local mlmmum x globalabsolute mlmmum ECE 67625752 int n Susan Lyszcky Espresso Espresso utilizes local search keeping in mind local minimum problem 0 Composed of three main operations 39 EXPAND REDUCE IRREDUNDANT Espresso Heuristic in a nutshell 39 Apply Expand and Itredundant operators to optimize the current function specification 39 Uses the reduce operator to get out of local minimum 39 This is iterated till the solution converges ECE 67625752 5 at u Susan Lyszcky Espresso Expand Operator EXPAND F be F be a DeletingoneormoreofiLs Z T 101 ionm rm n1 11 1n 39 0 0 l 0 0 literals b Checkforvahdity 1 0 0 0 1 1 o o C Expand abc by removing c results in ab Is it valid Yes F be F be a no 01 11 10 a 00 01 11 10 0 0 1 0 0 b 0 0 1 0 0 b 1000 1 1001 Expand abc by removing c results in ab Is it valid No ECE 67625752 7 a u Susan Lyszcky Espresso Expand Operator n a 2 0 Goal is to expand a nonprime implicants to prime with the D O 1 D 1 least number of literals Expand a b o by removrrrg a is 1mm Yes F b bquot39 a an 11 11 1n n 1 u 1 1 u u x Expand be by removrrrg b l5 1Lvalrd7 Yes o 15 an prrme 1mplroarrt ECE 67625752 3 a u Susan Lyszcky Espresso Reduce Operator REDUCE F bc 1 F be b 39 Adding oneormore terals a 00 ml 11 m Checkforvalidity o C 1 1 1 0 0 1 1 Reduce a by adding b results in a b Is it valid Yes F be c a 00 m 11 10 Reduce a by adding c results in ac Is it valid Yes Eon nod575 9 at to Susan Lysecky Espresso Reduce Operator 0 Goal is to decrease the size of X implicants such that expansion B may lead to a better solution 1 39 Avoiding alocal minimum No tmphcant can be expanded Reduce w to x yz 1s ttYahd Yes xz39 F w x39z x39yz39 D 1 Reduce xz to xyz D D 1Sttvahd7 Yes 1 1 x F w x39z x39yz39 Expand x yz to yz 1s ttYahd Yes Fx zyz xy Reduction helped find a better solution xy yz39 Eon nod575 Susan Lysecky m at u Espresso Irredundant Operator IRREDUNDAN T I Implicant in a cover is redundant if all the mintenns covered by it are contained in other implicants in the cover yz is redundant x y and xz cover all minterms contained in yz F W x z x y xz Ecn 67625752 11am Susiquot Lyszcky Espresso Irredundant Operator Irredunth cover Is not the same as minimal cover irredundant cover F W x z X 00 m M m V o 0 myz t q e V 1 xy irredundant cover minimal cover Ecn 67625752 12 at u Susiquot Lyszcky Espresso Additional Concerns 0 Additional concerns F be a I Vahdity check operations F be m m M m a on m M in 0 0 i 0 0 b I Whlchdn39ectionshould the 0 0 1 0 0 a C 1 0 0 D ab move make 1 0 0 0 1 F be a on m M in 0 Methods outlmedlnthe heunstlc Whlch Way shouldwe Ac expand 0 0 i 0 I We W111 not cover these 1 0 0 which implicant should we reduce which literal should we add ECE 67625752 13 mi N Susiquot Lyszcky Espresso espressoa p 4 F is the onset D is the don t care set R complememF U D F expandFR initial Expansion F redundaritFD initiai medmdantcover E essentialsFD detect essentiai prime implicants F F E Hiemove prime implicanis fromf D D U E add eesentiai prime implicanis toD repeat 1 IF I F reduceCED repeated application of REDUCE EXPAN D F expandaz R IRREDUNDANT operations while cost keeps decreasing F irredundantFD until F 2 M F F U E D D E RETURN F ECE 67625752 N mi N Susiquot Lyszcky

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

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I made $350 in just two days after posting my first study guide."

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

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