Class Note for ECE 474A with Professor Lysecky at UA
Class Note for ECE 474A with Professor Lysecky at UA
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.
Reviews for Class Note for ECE 474A with Professor Lysecky at UA
Report this Material
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
Are you sure you want to buy this material for
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'