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

## 13

## 0

## Popular in Course

## Popular in Department

This 15 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 13 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

ECE 474A57A Compute Aided Logic Design Lecture 7 Logic Optimization sue wxew Logic Optimization We now know now to buiid digitai 1 N CircuiB y quotW F W now can we buid bemcirmnsquot Y quot x3 V Lets consider two important design criteria Fiquotv quotxv rzu Deiay enne one from irputs V onangng no new correctstabie WM wwi W I Size 7 the mmber of Uansismrs Assurnpuon m m Every gate nas deiay of 1 93 g 5 oeiay39 g W Every gate mputrequres 2 5 m h ansismrs i 2 a igrore inverters newoau m nmmnnv r to r2 veviesents n o imin ion Betta n i omen at must sue wxew Twolevel Logic Optimization Twonievei iogic Are tnese twoeievei inng Ormit wmn onw two ieveis cued AND gates Basicaiiy surneoteproducts torrn An eqtauon Written as an ORH ig ofprocuctterms rom gt n technicawv butnatwhmwe mequot n tevms m We nrnnrmn L 73quot SIin wxew Optimization vs Tradeoff Opt mizauon 7 De ned as better in aii criteria of interest Deiay and size 7 we oorsioer size minimizaton oniy Zrievei iogic onw in reaiity recuires a baianoe of many criteria metrics I Cast YEiiabiiiWi nmermrmavka at Tradeoff 7 improve some but worsens other criteria ofinterest zyeaem u ixutxtrmx lama eeee x N teee tree eaeemveetete m New ihteier quotto e v I m w x u unreal gt432 fxv39z m m m Pareto Points owhimiens We obwousy prefer opt mizauons but often must accept Uadeoffs Vou can39tpuiig a car thatis the teatieme most oomfortapie arid has the bestmei ef ciency arid is the fastest 7 you have to gve Lp somethng no gain other thngs size Mews Same emeii atimeiest iehpiwee whie thee Many opuons in soiuuori space iewmenee Pareto point point in sdu un SUSIE in which m deiay mha Duntbettev in AU mam shmh in red when paints wad the quotscent cuva Combinational Logic Optimization and Tradeoffs Tworievei size opumzauon using aigebraic methods ExamI2 Goai ormit with miy two ieveis Oiled AND F 9 quotV V X W gates with minimum Uansismrs wizoz39tox y39izo z39t I Mug vansismvs getnng mEaFEY MEUVE39S w 1 0 xy 1 Law that stii cost something w o x y De ne probiem aigebraicaiiy Serofrprodmts yieids two ieveis I F abt ab 5 sumrEW39DEdunS G WOW z is not Transform sumrofrprodmts eqetaum to have fewest iiterais arid arms I Sada iitaai and tam vansiates m a Data input ash at mm vansiates to sham 2 sgeehpms ztrensaerhput vansismvs manager I Ernie invEtEvs fa simDiiuW sue mew Boolean Algebra How do We use Booieari aigebra to obtain fewest iiterais and terrm7 Ina mmmm Inh 1 la Marxian 1 lb 123 Dumunlfl 12h XY39XI 133 Mm1mm 13h Na ambml gl Nb 15a Demgal 39 lmem 15h Isa 16h em new Algebraic TwoLevel Size Minimization Uniting Tneorem Whitiin out to sumrofrproducs men apin Urimrig Tineorem abab39abb39a1a combinng terms m eiiminam a variabie Formaiiy caiied tine Uniting theorem Someu mes after combining terms can combine resuiting terms Fxy1 xyz x y z39x y z Fgtltyzz39 x y zz39 F xw x y F deiav 2 gaie deiav p XWW i SiZE is 2 aziiansisiois i G xy z xy z gtltyz xyz G xy z z xyzz t sex gtlt nwdoa in daiav Zgaiedeiav em new Algebraic TwoLevel Size Minimization Dupiicatiun Dupiicaung a term someu mes neips Note matdoesritdnange funcnori cdcddcdddd F x y z x39y39z x yz F x y x39y39z x39y39z x yz F x yzz X zy F xv x z em new Algebraic TwoLevel Size Minimization Cumpiex and Errur Prune Aigebraici lianipuiation me mies to use and when Easy m miss Seeing39 possibie oppormnnes to combine terms Fasbs b bia b a b Fas us b o a b Fas us as d a b cd d ab d and a bcd a c d Fas bscs d d Fas us s as es is g a b d ffa 29 a bcd e f g a bc efg Fas bscs ds esrs g 7 mm 3amp3 M 5 K maps Karnaugh Maps Giapnicai mednod to neip us nd oppormniues to combine term Graphcai meinod to neip LS i39ind oppormnines to combine uerms Geate map Where adaaenrmimerms dffer in one variabie Cari deariysee oppormnines m oomoine Erms riook for adiacen 1s sm new TwoLevel Size Minimization Using K maps Exampie MinimIZEG a a w b c obc Generai Knmap mednod stem enmeiemmpmems 1 cmvertnnefmcuoris ecuanoninto G was Di mi mi sumnofnprod icm form sis Visesiismineappmpnaieseiis 2 Piece 15in me appropriate Knmap G be oeiis for eacn uerm m m M m 3 raver aii 1s by draWii ig ine fewest iargestordes Winn every 1 induded i s s s s at ieast once write me corresponding uerm for eadn arcie Step 3 now is 4 OR aii ihe resuung uerms to create 16 minimized iuncnori 3129A D iams sciiams G quot393 sunWWW TwoVaria ble K Maple Example Flii ii l eacn cell Wldn Corresponding vaiue ofF Draw Clrcies around adjacent 139s erpsof120r4 Clrde il ldicates opurnlzauon oppormnlty We Carl remove a variabie To obtain funcuol39l OR all product terms Contained ii l Clrcies Make sure aii 1 are W at ieast me clrde M XZ mzl MXZ x r m le xmlwm mz wz ml mm m m Siamf W 5 Generalized ThreeVariable K Map ThreesVariable Map 5 r H nnm um n no ml Ymihiz e REMEMBER Knmap grapnlcallv place nrlnlerrns Yvuih ome nexl in eacn mnerwnen they dmer by Ellie vallabie mi Lannm b2 placed nExHu rnz am a bc mi can b2 placed nemd m an m can b2 placed nemd m an a bc r a bc sue new ThreeVariable K Map Optimization Guidelines Circles can cross leftright sides Remember edges are adjacent Mlnmrrns dffer ii l one variabie miy Circles must have 1 2 4 or 8 cells 7 v1 3 5 or 7 not allowed c c c c c 357 doesl39lt correspond to aigebralc x Ual lsformauorls mat combine terms 1 i i i D to eilmll late a variabie Circling all me cells is OK Funcuol ljustequaisl sue new ThreeVariable K Map Optimization Guidelines Two adjacent 1 means one x variabies can be eiiminated Same as ii i twovariabie Knmaps Four adjacent 1 rneans two variabies can be eiimii iated I Makes inmmve sense rihose two variabies appear ii i aii oombirianors so one mustbe x mniiiin EE XV true Gxvt In M M um nehgyxlcimh m w w mnumm Wm WWW Draw one big orcie e mama7d MW 0 w 1 mm quotmm for the aigebraic Uarsformanons sw w above Gx Four adjacent ceiis can be ii i H mqupm shape of a square xv ivvurs in ii cumming sum new ThreeVariable K Map Optimization Guidelines lay to cover a ltwice i w ix Lstiike cupiicaunga uenn an m u in IREnEnbaddd n n i n n T mm W mm m m m m m im Nu m m m m iw m No NEEDto cover 1 more than once u Vieids extra terms i iotmii iimized sum new FourVariable KMap Optimization Guidelines Fournvariabie Knmap foiiows same principie Lemrigwt adjacent Top00mm aiso adjacei39it FW xyyz Adjacent ceiis differ ii i one variabie Two adjacei39it 1 mean two vanabies can be eiimii39iated Four adjacent 15 nears two variabies can be eiimii39iated agnt adjaoei39it 15 means thee variabies can be eiimii39iated sum new FourVariable KMaple Example 1 cmvertm mm H a b cd a ab cd and a bcd 5m mew FourVariable KMaple Example Continued a b39cd c d ab39c d ab cd39 a bd a bcd dh c d39 2mm 1 Convertu sum H a b cd a ab cd and a bcd ab 1ha m 2 Place 15 m Krmap cells an zh m39 5m mew FourVariable KMaple Example Continued ab cd and a bcd 2 Place 15 m Krmap cells 3 Covey 1 WW ng cwle nutmmemnerma legMqu andmphomm mice 5m mew FourVariable KMaple Example Continued I Minimize H a b39od c d ab39c d ab cd39 a bd a bcd 1 cmvertm sumrofrproduds H a b cd a b c d ab c d ab cd a bd a bcd 2 Piece 15 m Krmap oeiis 3 Coka z39hc 4 oRresuungmrms 2hquot H b d a bc a bd Zilw M Larger NVariable K Maps Graphicai minimizing by hand 5 and s variabie maps exist but hard m Lse May not yieid minimum cover depending on order We choose is error prone Mnimizauon mus typicaiiy done by automated tOOiS Sixrvanabie Map 5m mew Fivervanabie Map Don t Care Input Combinations Dun39tCareinput b c z inputumbinatiunnattnedesigner fgnnjjegfggg E E j39 duesn tcarewnattne uutputis D 1 D D Ii2inpuicundiiiuncannwevuccuv E 1 1 E Thus makeumputbeiur furtnuse 1 u u 1 casesinawaytnarbesiminimizesme 1 U 1 1 equation 1 1 j 1 Representeuasxwwmap X mm in km 1 1 1 1 mummy mm m m W mmmmr 5m mew Exact Algorithms vs Heuristic Aigorimm Finiue setofirisimcuorssmps to sdve a probiem Terminate ii i i iiE we ate Known endsizte Many aigorimms can exist that soive me same probiem mm makes one aigorimm better man another7 Op maiity e besf aniity soiunori fomd Ef oerio e good qLaiity soiunori fomd fast ExactAigorimm Finds opumaisdunm Mavnotoee icierit I Heuristic I Ef oerit Finds good soiuuori mtmtnecessariiv oonmai sum mew Quine McCIuskey Overview Exact Aigorimm Deveioped ii i me midrSO39s Find me minimized representauon of a Booieari mneuon Provides svstemauc Way of generaurig aii prime impiicai iB men ltUac g a mriimum set of prime covering me orirset Accompiishes mi by repeatediv appiving me Uniting theorem Urimrig theorem ab ab abb 31 a sum mew Review Definitions Mule111 Habit a b coab prode term Whose iiuerais indude every variabie of ihe fmcuom exaciiv moo ii i irue or oompiemenueo form literals a hi 2 mlmElmS a b c gtlt lt3 Aii minmrms matde rie when F1 017156 nn sen a b c am am Aii minmrms matde i39ie when FO miss emu aim i ainci anion ab c sum mew Review Definitions r he s e 41m We 39 Imp 5 i an D1 11 1 p Awpomcttermmimermoroiherwwat DD when 1musesF1 D D o D D Dc QWKrmapjriyiegai UJti iOti ieOeSSariW 1 u u o 1 an iargest arcie I I I r be am 2pm anelmpIcan a m m M m mime Manmaiiyewandedimpiicanteany D D 0 D D iuriher expai39siom woud cover 1s norm onset 1 u u 1 1 am Essmiiapnine hipinanl The omiy prime impiicaritmatcwers a m D1 11 1B was parucuiar miriuerm iri a funcnori s onset H W importance We mrindude aIessermai u i i u u 2 swim PIS iri a rmcuoris cover 1 In 1 1 w sum in oomast some but not aii new I essermai P W be induded ahi er in rimmimm msnm Mammy em mew Quine McCIuskey Algorithm 1 Find aii me prime impiicai iB Find aii me essenuai prime impiicai iB 3 Seiect a minimai set of remaining prime impiicai iB mar covers me onset or me funcuori sum iiier Quine McCIuskey Example 1 Minimize F a39b39e39 a39b39c ab39c abc39 abc Step 1 Find aii me prime impiicanrs Li staii eiemenis of onsetand dm tcare set represerred as a binary mmber Group miriuerms aopordrig m me riumber of 139s iri ihe miriuerm a D Em GD D Em Vimsumminiimmieims ab39 gt 1 um 61 1 mm mumiimiieimwimmmiu ain39t y 5 1D 32 5 1D View e2 ii mime 111mm W15 six gt a 11m a 1113 sh y 7111 33 7 111 vvaupwcanningaiiminlemscanlaimnvimeeis this QVOWNQ smiegy Will help us cowere me mimelms svsiemaiicaW sum iiier 10 Quine McCIuskey Example 1 Step 1 PM all me pllme lmpllcal lBcol lt Compare eadw emy ll l Gl m each emy ll l 3H 1 I quot111v dlffev W 1 lat we can EDF V WE unmng WE39EH and Ellmlnafa a lltalal I Am ma k m mlmalmlmulltant m lmllrd us that lt ls nm a DYlmE lmdltam mmblnad Wllh anmha amen m mm a lavas lleltanU cu u mm on mg no nu newlmpllcamsaleugnelaledrend 7 Uls12p1 c 1 mm c 15rm 32 l 5 1m 32 57 171 we have mum all pllme lmpllcam a 1m 57 117 uneswnhuul checkmalks 33 I 7 111 m mew Quine McCIuskey Example 1 Step 2 and all essenual prlme lmpllcanB cream prlme lmpllcant chart I Cdmlrls ale mlntalm lr lDES YDWS ale WE DYlmE lleltarlts WE detamlnad F a b c39 a39b39c ab c abc39 abc nun um lnl 11B 111 I I u 1 5 5 7 mm 15 57 171 57 117 C derlved m Ste 1 ans 1 ms ml 5 p m mew Quine McCIuskey Example 1 Step 2 Flnd all essennal prlme lmpllcams LCol lt Place xllln a row lfl e prlme lmpllcamcmrs me mlmerm Essel39mal prlme lmpllcal lB are found mlodmg for rows Ma 3 smge x I If mlntam ls ElmElm W are 2rd mlv are Ulme lleltant rlt s an Essemal D We lleltarlt Add essermal pl39lme lmpllcal lB to me cover 2552quot Karl me lmpllms Eh DD CW 39 F aboab mm 3 3 57 171 g x 57 117 x 5m mew 11 Quine McCIuskey Example 1 Step 3 Select a mlmmal set ol remammg pllme lmpllcal lB that covers the on set of the fumed on Step 2 determmed essermal prl me lmpllcane and added to wet I Essmnal Ulme lleltants mav 021me mlntams muss cut all mlntams mvaad W E Fume lleltants I Mlntam mlv needs to be waved mtg 5 cm no W t b 1 15 rm 3 57 171 x 57 117 sue mew Quine McCIuskey Example 1 Step 3 Select a mlrllmal set of remamlng prlme lmpllcans that covers the on set of me tuncuom com Based m mm mmtetms are left add mln mal set of prlme lmpllcanls m cover 0an mmlevm 5 vemamsr enhEV mum lrmllcanl 115 mm Wlllwuvk 5 cm mun r on 15em amp 57 171 x 57 117 sue mew Quine McCIuskey Example 1 Summary lsmlsanopumalsoluuor I YES We generate all lhe mmetms and make sure they are all covered m the prlme lmpllcants ls me soluuon unlque7 I NOT NEESSARILV I There ooud be dll fererlt 5613 of mlnmum covers sue mew 12 QuineMcCIuskey Example 2 Minimize F wwz39 W39x39yz W39x39yz39 w39xyz W39xyz W39xyz39 ny39z nyz Wsz Wx39yz step 1 Find all the prime implicams List all eiemmts utmset 3rd mrit cave set represented as a blHEW rumba GmuD riiiritariis scraping m the HLIleE Bf 139s iri the riiiritarii 7m trim wa39 ninnnn G 2mm WW ZJHHH Wmquot WM mm W W mm pm my mini aim mi mm 7 W mm a mum Wm 15 m wx39ix mm mm W mm BEE 1 am a is im W 5 5m mew QuineMcCIuskey Example 2 step Find all the prime implicanls cont urinate each mar in ei to 23m m v in GM r ireidrrer bii bi we 2in mt wing imam 2nd eimmie 2 i itui detain mmmmami ia Mind m imi i i mi 2 pm impimi an mm 33 a 4 Him a twp 7 mi l mm 6 rziim W 6 WW I mm W H a I mm UH mm lt2 mm ii 462 miiii W mm aims 5 m mi i min on lt2 I warn mi min ruiEWimiicaiisaie W 23 i I mm geraiaiemimmpi m in M i m m mm gm mm 7 em a Siam 6 wmm 9D friiisim 3 4 ms in his mum 1m miner QuineMcCIuskey Example 2 Step 2 Find all essenn al prime implicants Cream prime impiicarit hart I Cdumns ave mintam lr lDESi YUNS ave 12 D We ileitants WE detaminad Place XHll i a row itme prime impiicart covers the mirterm Esseriuai prime lmpllcal iB are found m locking for rows Wll a Sll ige x I Am zsmnal DYlmE ileitantm Hi we essmiiai prime imviims u 3 4 7 9 11 13 15 2 5 my mm n 8 X r WINu 2357 ii a x X 37nl5n x x x mums H amp x 5m mew 13 Quine McCIuskey Example 2 Step 3 Select a ml lmal set ol remammg pllme lmpllcal lB that covers the on set M d7e ful39lcuon Cmss cut all mmcams tweed luv the Emma mumms Easad m mm mlntavms 272 left m1 mlnmal semfpnme mullcants m we Mlmevm 3 and 7 vemlnrellhwmlme lmpllcanl 236 m 371115 mlqu 3 7 my mm s H r Wt wz VX 2357 M g x 27ms m g g mums H WWW Quine McCIuskey Example 3 Petrlck s M ethud VWat f determlnlng mlnlmum prl me lmpllcal vt cover lS not so easy7 Asmme We have the lmpllcant table below Demrmme prlme lmpllcanls add to cover 2552 PM me DE7E91315 V 25 m x F mum 57 x m x mm x x ms x 5m mew Quine McCIuskey Example 3 Petrlck s M ethud Example 3 Cont Remove mmmrms covered by prl me lmpllcal lB I Leaves 3 mlrlters 7 m7 ml and WIS I lem YEHalanE Dllme lleltams shmld WE use to almaer HE mlnlmum mva 7 13 15 25 m W m on F W m 57 m 913 m 715 an x x3 5 m 5m mew 14 Quine McCIuskey Example 3 F39Etrmk s Methud Parmk s Manna fused m daenmne mwmmum wer 7 B 5 1 Reduce puma muhcantchavt bv amman puma mdwtam mm 2rd mnesumdnu dumns 2 Labd ms Bf mum Fume muhcant n m m 3 u an m 39 mm 2 0 J quot 39 3 3 mm mm Summary mm s we Mm quot J quot 3 2H dumns NEED215d 4 Rama m mmmum sun ufpmums m V w 39 mm mm 39 m mundvmg m and sw vm x xv x V m 7W2 mwm WM 5 Sam cammsdunumwyesms a mu m cavaan summary cm rumba y m m uzh mm m zuvreipondmg m the m mum numbev m mm mwm m H mm m m mm OP27A m H mm m m mm m y szmommomnmomm mm pm 7 Mnmommonmomm WW mm W Wm mormmsman Nyym haepmv de mcznemumm mmzlmgemer mherm mmns mmmummw 5m mew Quine McCIuskey Example 3 F39Etrmk s Methud 7 x3 5 Fma cover essenua pnme mphcans mmmum pnme mphcant cover u m Bauhmmmuns u g u m mm D M WWpummphcmnwm quot um 3 WW WWW Wm WWW y mezmomm apmna VCWIIJXVXWVX H AnyuHhESEDm m mummy new numher m was Minimixed Equation F w39y139 x39y39x xyz wyz 5m mew Quine McCIuskey I Alternative memods to determine Minimum Cover Row vs Cohmn Domnance I What about don39t cares 5m mew 15

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

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

#### "Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

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

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

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