### Create a StudySoup account

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

Already have a StudySoup account? Login here

# LOGIC DESIGN CS 120A

UCR

GPA 3.88

### View Full Document

## 19

## 0

## Popular in Course

## Popular in ComputerScienence

This 7 page Class Notes was uploaded by Adele Schaden MD on Thursday October 29, 2015. The Class Notes belongs to CS 120A at University of California Riverside taught by Staff in Fall. Since its upload, it has received 19 views. For similar materials see /class/231756/cs-120a-university-of-california-riverside in ComputerScienence at University of California Riverside.

## Reviews for LOGIC DESIGN

### 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: 10/29/15

Lab 3 Hierarchical Design and Technology Mapping Objectives To get familiar with the XilinX Schematic Editor Tool To get familiar with the XilinX Simulation Tool To design and implement simple combinational logic circuits using the Schematic Editor and Simulator To download your circuits onto the prototyping board and test it Laboratory Instructions Create a directory with your name on the C drive of your lab PC Use this directory to create your project store your results bitstreams etc during the lab session You can bring complete project les on a oppy disk and then use the Copy Project command from the Project Manager menu to copy it into the directory you created above Alternatively you can create a new project in your directory on the C drive and then copy your les to that new project directory Remember to Add your SCH le to the project Perform functional simulation of your design and have it checked by your TA Refer to appendix A for instructions on performing functional simulation Refer to appendix B for instructions on how to download the circuit to the prototyping board Test and demonstrate your circuit to your TA Before you leave the lab please remove the files and directories that you created on your lab PC and leave our workplace clean and tidy Section 41 Karnaugh Map Page 1 of7 41 Karnaugh Map The Karnaugh map method is a simple straightforward procedure for minimizing the number of operations in standardform expressions The Boolean ncubes provide the basis for these maps Each vertex in each ncube represents a minterm of an nvariable Boolean function Each Boolean function could be represented visually in the form of an ncube by marking those vertices in which the value of that function is a 1 ie the 1minterms Ex for the carry and sum functions x l 0 0 W 010 0 01 0 5y 00 l 0 101 41 0 0 0 l 000 CM c39xy cx39y cxy39 cxy s c x y c39xy39 cx39y39 cxy xycycx To find the standard form of a function that contains the minimal number of operators we use the concept of a Boolean subcube In general an msubcube of an ncube can be defined as that set of 239 vertices in which n m of the variables will have the same value at every vertex while the remaining m variables will take on the 239 possible combinations of the values 0 and 1 l 0 l l For example in the 3cube The 2subcube is defined as that set of 239 22 4 vertices in which n m 3 2 010 011 1 of the variable will have the same value at every vertex 0xx or lxx while the remaining variables will take on the 239quot 22 4 possible combinations x00 x01 x10 and x11 00 01 The 1subcube is defined as that set of 239quot 21 2 vertices in which n m 3 1 2 of the variables will have the same value at every vertex 00x 01x 10x or 11x while the remaining variable will take on the 239quot 21 2 possible combinations xx0 and xxl Each subcube can be characterized by the n m variable values that are the same for every vertex in the subcube If a Boolean function has a value of 1 in each vertex of the msubcube the 239quot 1minterms in that subcube could be expressed by a single term of n m literals For example in the carry function CM the two 1minterms 011 and 111 form a 1subcube which could be expressed by the single term ofn m 31 2 literals xy 00 01 0 To minimize the number of OR operators we have to choose as few subcubes as possible while still covering all its 1minterms 0 To minimize the number of AND operators we have to choose the largest possible subcubes We can determine and select the subcubes visually from a cube representation or we could derive them from the twodimensional form of this cube which is called a Karnaugh map or map for short There is a onetoone correspondence between Boolean cubes and Karnaugh maps Karnaugh maps are just two dimensional representation of Boolean cubes The map is an array of squares Each square corresponds to one vertex of the cube ie one minterm of the Boolean function Section 41 Karnaugh Map Page 2 of 7 A twovariable map consists of 4 squares which i 11111111111 correspond to te m1nterms of a twovariable x 0 1 11111111215 x 11 1 Boolean function The largest subcube in a Itwo 0 1 Subwbex1 variable map is a lcube which represents a Single 0 W W 0 subcubey39 variable or its complement Z 3 subwbe Y 1 1y 1y 1 subcube x A threevariable map consists of 8 squares The largest subcubes are of size 2 These 2subcubes can be expressed by a single literal The lsubcubes can be expressed by two literals z 00 01 11 10 z 00 01 11 10 x x u 1 3 z u 1quot l u x y z x y z x yz x yz u 1 i 1 h 4 5 7 6 I 1 x z x z x z x z 1 39 y y y y lti xy threevariable map Examples of 2subcubes Examples of lsubcubes A fourvariable map consists of 16 squares Y2 on 01 11 10 no 01 11 10 wx wx W X O w x l W X 3 W X Z 00 y z y z yz yz Z 0 w39z W1 W39XS w x7 W39x 39 l l 01 Z 01 WYZ yz yz yz z 12 13 15 14 H w w w w H Y Y y z y z yz yz xyz 10 Wt 8 WX399 le l W11quot w 10 Y Y y z y z yz 2 KY and lsubcubes fourvariable map Examples of 3subcubes If the minterm is a lminterm a 1 will be placed inside its square otherwise it is left empty Example for the carry and sum functions s c x y c39xy39 cx39y39 cxy 01 7 Section 41 Karnaugh Map Page 3 of 7 42 Map Method of Simplification Four steps 1 Map generation from truth table or functional expression Place a 1 in the squares that correspond to 1 minterms 2 Prime implicant generation A prime implicant P1 is defined as a subcube that is not contained within any other subcube eg In figure 413 below w z is a P1 but w y z is not because w39y z39 is inside w i A list of prime implicants is generated by inspecting each 1minterm finding the largest possible subcube of 1 minterms that includes the minterm in question and then adding that subcube to the list of prime implicants If two or more different subcubes are discovered they are all added to the list If we rediscover a subcube that is already on the list it will not be added the second time Essential prime implicant selection An essential prime implicant EPl is the subcube that includes a 1minterm that is not included in any other subcube eg In figure 413 below w39z is an EPI because m0 is not in any other PI However w y is not an EPI because all four of its 1minterms are in another P1 Look for any 1minterm that is included in only one prime implicant This prime implicant is an EPI and is added to the cover list Create minimal cover Generate a cover list consisting of the smallest possible number of prime implicants such that every 1minterm is contained in at least one prime implicant The cover list must include all the EMS L V 4 V Example Using the map method simplify the Boolean function F w39y z39 wz xyz w y Step 2 Do the 1minterms in or er v m0 is in w z m2 is in w z and w39y W Z m3 is in w y and yz m4 m5 m7 same as me yz m2 m3 m9 and mm are in wz wz mm and mu are in wz and yz step 2 Therefore P1 list w z wz Figure 413 W W Step 3 EP1 list m0 and m are covered only by the P1 w i m9 and mm are covered only by the P1 wz Therefore EPI list w z wz Step 4 Cover list The two EPls w39z and wz must be in the cover list w i also covers m2 and ms wz also covers mm and m15 There are only two 1minterms m3 and m7 that are not covered These two 1minterms can be covered by either yz or w39y since both of them are of the same size Note that if one was larger than the other we would only use the larger one Therefore there are two cover lists 1 w i wz yz and 2 w39z39 wz w y Thus there are two simplified equivalent functional expressions forF w y z wz xyz w y 1 F w z wzyz 2 F w z wz w y Section 41 Karnaugh Map Page 4 of 7 Example Using the map method simplify the Boolean function F w39x yi w xy wxz wx y w x y z Pl list w x z w39xy wxz wx y and x39y i wy39z xyz w yz EPI list empty Cover lists 1 w x z w39xy wxz wx y 2 x39y z39 wy39z xyz w39yz39 The two simplified equivalent functional expressions are w x z w39xy wxz wx y wy39z xyz w39yz39 2 F x y z wy z xyz w yi However bad if we had selected the two Pls w x z and xyz because now we would need 5 Pls to cover all the l minterms eg w39x39z xyz w39xy wxz and wx y 43 Don39tCare Conditions Previously we have considered only those Boolean functions that are completely specified There are situations where the outputs are not specified for some input combinations ie we do not specify whether the output is a 0 or a l for an input combination Such a Boolean function is called an incompletely specified function and the minterms for which the function is not specified are called don39tcare minterms dminterms or don39tcare conditions We can use dminterms to further simplify the Boolean expression because we can assign either a 0 or a l to them in a way that will make our subcubes larger Example Convert BCD to nine39s complements y3 x339x239x139 7 V V 7 7 l y2 7xle x2xl 7 x2 9 x1 y1 7 x1 yo x0 Section 41 Karnaugh Map Page 5 of 7 44 Tabulation Method Previously finding subcubes in a map is essentially a trialanderror procedure because it requires a person to recognize subcube patterns in a map Gets more difficult with more variables The tabulation method is an algorithmic exhaustive search method to find the subcubes in a map Quite tedious for human but good for computers Example Find the prime implicants for the Boolean function F w39y z39 wz xyz w39y From figure 413 we see that there are ten lminterms Step 1 Generate a list of 0subcubes Cov ere d Group the lminterms such that each group G contains those minterms whose l39s count number of variables whose values are equal to l is equal to 139 Thus in G0 the minterms have no l39s In G1 the minterms have one l39s In G2 the minterms have two l39s etc The quotyesquot and quotnoquot flag indicates whether or not that subcube is covered by a larger subcube The flag will be set to quotyesquot or quotnoquot after we have generated the list of nextlarger subcubes Step 2 Generate a list of lsubcubes Covered In the list of 0subcubes compare each of the minterms in group G with each of the minterms in group GM and generate a lsubcube for group G in the list of lsubcubes if these minterms differ in one variable Note tha quot is not an indication of the value of a variable but is rather a placeholder for a variable that has already been eliminated from the expression Step 3 Generate a list of 2subcubes In the list of lsubcubes compare each of the minterms in group G with each of the minterms in group GM and generate a 2subcube for group G in the list of 2subcubes if these minterms differ in one variable Step 4 Repeat until all the subcube covered are quotnoquot From the subcube values of all the quotnoquot rows the prime implicants are w z w y yz wz Section 41 Karnaugh Map Page 6 of 7 Example Find the essential prime implicants and the minimal covers for the Boolean function F w y z wz xyz w y Using the four Pls w39z39 w y yz wz obtained in the last example we construct the EM table Prime Prime lmplicant lmplicant lmplicant Minterms ame Expression WZ EPl covered minterms Not covered minterms Step 1 Enter an X to indicate Where a given minterm is covered by a given Pl Step 2 Indicate those columns that have only one x by circling that X Step 3 A Pl row having a is an EPI Thus EPl w z wz Step 4 The EPls will cover the other X39s in the same row Step 5 Find the best way to cover the remaining minterms m3 and m7 Can use either w y or yz Pl list w z w y yz wz EPl list w z wz Cover list 1 w z wz w y 2 w z wz yz Minim alcover expressions 1 F w z wz w y 2 F w z wzyz

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

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

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