# CSCE 790: Computer Network Security

CSCE 211: Digital Logic Design Chin-Tser Huang [email protected] University of South Carolina Chapter 3: The Karnaugh Map Karnaugh Map (K-map)

The algebraic simplification method in Ch. 2 is not systematical and does not tell us whether the result is a minimum We introduce the Karnaugh map, a graphical approach to finding suitable product terms for use in SOP expressions Particularly useful for problems of three or four variables 09/15/2015

3 Introduction to the K-map K-map consists of one square for each possible minterm in a function A two-variable map has 4 squares A three-variable map has 8 squares

A four-variable map has 16 squares 09/15/2015 4 Example: Two-Variable Kmap The upper right square correspond to A = 1, B = 0, i.e. minterm 2 of f(A, B) 09/15/2015

5 Example: Three-Variable Kmap Notice that the last two columns are not in numeric order! By organizing the map this way, the minterms in adjacent squares can be combined using the adjacency property P9a. ab + ab = a 09/15/2015 6

Example: Four-Variable Kmap 09/15/2015 7 Plot a Function on the Kmap Two ways to do it

Use minterms and plot each square corresponding to each minterm Put the function in SOP form and plot each of the product terms How to plot the function F = AB + AC + ABC ? 09/15/2015 8

Implicant An implicant of a function is a product term that can be used in an SOP expression for that function From the point of view of the map, an implicant is a rectangle of 1, 2, 4, 8, (any power of 2) 1s. That rectangle may not include any 0s.

09/15/2015 9 Implicant Example The implicants of F are Minterms ABCD ABCD ABCD ABCD ABCD ABCD

ABCD 09/15/2015 Groups of 2 ACD BCD ACD BCD ABC ABD Groups of 4 CD

10 Prime Implicant A prime implicant is an implicant that (from the point of view of the map) is not fully contained in any one other implicant. An essential prime implicant is a prime implicant that includes at least one 1 that is not included in any other prime implicant. 09/15/2015 11

Why Prime Implicants? The purpose of the map is to help us find minimum SOP expressions The only product terms we need to consider are prime implicants Essential prime implicants are the prime implicants that must be used in any minimum SOP expression

09/15/2015 12 Minimum SOP using K-map We will start with the most isolated 1s on the map The 1s with the fewest (or no) adjacent squares with 1 in it

09/15/2015 13 Map Method 1 1. 2. Find all essential prime implicants. Circle them on the map and mark the minterm(s) that make them essential with an asterisk (*). Do this by examining each 1 on the map that has not already been circled. It is usually quickest to

start with the most isolated 1s, that is, those that have the fewest adjacent squares with 1s in them. Find enough other prime implicants to cover the function. Do this using two criteria: a. Choose a prime implicant that covers as many new 1s (that is, those not already covered by a chosen prime implicant). b. Avoid leaving isolated uncovered 1s. 09/15/2015 14 Example 1

minimum f = yz + wyz + wxz 09/15/2015 all prime implicants 15 Example 2 Find the minimum SOP expression for xyz + xyz + xyz + xyz + xyz 09/15/2015 16

Example 2 x y + x y + x z 09/15/2015 x y + x y + y z 17 Example 3: Dont be greedy Bad

move! minimum G = ABC + ACD + ABC + ACD 09/15/2015 18 Dont Cares When there are dont cares: An implicant is a rectangle of 1, 2, 4, 8, 1s or Xs A prime implicant is a rectangle of 1, 2, 4, 8, 1s or Xs not included in any one larger rectangle. Thus, from the

point of view of finding prime implicants, Xs (dont cares) are treated as 1s. An essential prime implicant is a prime implicant that covers at least one 1 not covered by any other prime implicant (as always). Dont cares (Xs) do not make a prime implicant essential. 09/15/2015 19 Example 1 minimum

other p.i.s F = BD + ACD + ABC 09/15/2015 20 Example 2 g1 = xz + wyz + wyz + wxy g2 = xz + wyz + xyz + wxy 09/15/2015 g3 = xz + wyz + xyz + wyz

21 Example 3 g1 = cd + ab + bd + acd g2 = cd + ab + bd + abc 09/15/2015 g3 = cd + ab + ad + abc 22 Finding Minimum Product of

Sums Expression Finding a minimum product of sums expression requires no new theory. The following approach is the simplest: 1. 2. 3. Map the complement of the function. (If there is already a map for the function, replace all 0s by 1s, all 1s by 0s and leave Xs unchanged.) Find the minimum sum of products expression for the complement of the function (using the techniques of the

last two sections). Use DeMorgans theorem (P11) to complement that expression, producing a product of sums expression. 09/15/2015 23 Example f(a, b, c, d) = m(0, 1, 4, 5, 10, 11, 14) 09/15/2015 24

Example (cont.) f = ac + abc + acd f = ac + ac + abd f = ac + ac + bcd f = (a + c)(a + c)(a + b + d) f = (a + c)(a + c)(b + c + d) 09/15/2015 25

## Recently Viewed Presentations

• Calibri Arial 宋体 Symbol Times New Roman Wingdings Default Design Microsoft Equation 3.0 BYU Deposition Facility Slide 2 BYU - Previous Testing Goal 1: Increase gas temperatures to 1400 C Temperature Range BYU - Facility Modification BYU - New Coupon...
• Tabloid Thinking By Erin, Hunter, Kelly ... Tabloid Thinking A. If you choose Coach Nolan he will drill you to death. B. My aunt won't let me have any toys. But she never uses them. It is not fair. C....
• However, in every case where parental rights are intact, parents are involved as much as possible. DCBS can consent for medical treatment. Termination of Parental Rights (TPR) The Court has determined that the parents no longer have legal rights regarding...
• Biosignaling Types of signal transducers Biosignaling I. Ligand-gated Ion Channel Nicotinic Acetylcholine receptor opens in response to neurotransmitter acetylcholine and to nicotine Found in neurons and muscle fibers Receptor = Allosteric protein Cooperative binding of Ach Desensitization Specificity Biosignaling I....
• Edgar Degas Shape 2D: The area enclosed by an outline SHAPE "When the subject is strong, simplicity is the only way to treat i" ""Jacob Lawrence Form 3D: height, width and depth FORM "There is no retirement for an artist,...
• Introduction to Lease Analysis. ... Owner's Leased Fee Interest. Tenant's Leasehold Estate. ... Consideration (deposit or something of value) Legality of leased space (building and zoning code compliance, etc.) Offer and acceptance of the contract. Requirements of a Valid Commercial...
• The order that you stated your supporting reasons in your thesis/claim will be the order of your body paragraphs. (only for closed claims) Body Paragraphs. The Body Paragraph of an Argumentative Essay has five basic parts. 1. Topic Sentence:
• Arrangement of a Muscle. Muscle Fascicle Muscle Fiber (cell) Myofibril Myofilaments (thick/thin) Muscle Fiber [cell] structure. up to .5 meter long yet only .1 mm in thickness. multinucleated (several nuclei) ... Muscular System Last modified by: