Karnaugh Map Lecture Notes PDF

Points Addressed in this Lecture Standard form of Boolean Expressions Lecture 5: Logic Simplication & – Sum-of-Products (SOP), Product-of-Sum...

Points Addressed in this Lecture Standard form of Boolean Expressions Lecture 5: Logic Simplication & – Sum-of-Products (SOP), Product-of-Sums (POS) Karnaugh Map – Canonical form Professor Peter Cheung Boolean simplification with Boolean Algebra Department of EEE, Imperial College London Boolean simplification using Karnaugh Maps (Floyd 4.5-4.11) (Tocci 4.1-4.5) “Don’t cares” E1.2 Digital Electronics I 5.1 Cot 2007 E1.2 Digital Electronics I Cot 2007 Forms of Boolean Expressions Canonical Form Sum-of-products form (SOP) Canonical form is not efficient but sometimes – first the product (AND) terms are formed then these are summed (OR) useful in analysis and design – eg: ABC + DEF + GHI In an expression in canonical form, every Product-of-sum form (POS) variable appears in every term – first the sum (OR) terms are formed then the products f(A, B,C, D) = ABCD + ABCD + ABCD are taken (AND) – note that the dot (meaning AND) is often omitted – eg: (A+B+C) (D+E+F) (G+H+I) It is possible to convert between these two forms using Boolean algebra (DeMorgan’s) E1.2 Digital Electronics I Cot 2007 E1.2 Digital Electronics I Cot 2007  A Notation using Canonical Form – An SOP expression can be forced into canonical form by ANDing the incomplete terms with terms of the Previous example: form (X + X ) where X is the name of the missing Construct the truth table for this function variable – use a 0 when the variable is complemented, 1 otherwise – eg: f ( A, B , C ) = ABC + ABC + ABC f ( A, B, C) = AB + BC R o w N u m ber A B C f 0 0 0 0 0 = AB(C + C) + ( A + A) BC 1 2 0 0 0 1 1 0 0 0 3 0 1 1 1 = ABC + ABC + ABC + ABC 4 5 1 1 0 0 0 1 0 0 6 1 1 0 1 = ABC + ABC + ABC 7 1 1 1 1 – f can be written as the sum of row numbers having TRUE minterms – The product term in a canonical SOP expression is f = ∑ ( 3,6,7 ) called a 'minterm' E1.2 Digital Electronics I Cot 2007 E1.2 Digital Electronics I Cot 2007 Simplifying Logic Circuits Method 1: Minimization by Boolean Algebra First obtain one expression for the circuit, then try to simplify. Example: Make use of relationships and theorems to simplify Boolean Expressions – perform algebraic manipulation resulting in a complexity reduction – this method relies on your algebraic skill – 3 things to try Two methods for simplifying – Algebraic method (use Boolean algebra theorems) – Karnaugh mapping method (systematic, step-by-step approach) E1.2 Digital Electronics I 5.7 Cot 2007 E1.2 Digital Electronics I Cot 2007  a) Grouping – Given b) Multiplication by redundant variables A + AB + BC – Multiplying by terms of the form A + A does not alter the logic – write it as – Such multiplications by a variable missing from a term A(1 + B ) + BC may enable minimization – then apply – eg: 1+ B = 1 AB + AC + BC = AB ( C + C ) + AC + BC = ABC + ABC + AC + BC – Minimized form = BC (1 + A ) + AC (1 + B ) A + BC = BC + AC E1.2 Digital Electronics I Cot 2007 E1.2 Digital Electronics I Cot 2007 Example of Logic Design c) Application of DeMorgan's Theorem Design a logic circuit having 3 inputs, A, B, C will have its – Expressions containing several inversions stacked one upon output HIGH only when a majority of the inputs are HIGH. the other may often by simplified by applying DeMorgan's Theorem. – DeMorgan's Theorem "unwraps" the multiple inversion Step 1 Set up the truth table A B C x – eg: 0 0 0 0 ABC + ACD + BC = ( A + B + C ) + ( A + C + D ) + BC 0 0 1 0 0 1 0 0 = ( A + B + C + D ) + BC Step 2 Write the AND term for 0 1 1 1 → ABC each case where the output 1 0 0 0 = ( A + B + C + D) 1 0 1 1 → A BC is a 1. = ABCD 1 1 0 1 → ABC 1 1 1 1 → ABC E1.2 Digital Electronics I Cot 2007 E1.2 Digital Electronics I 5.12 Cot 2007  Step 5 Implement the circuit Step 3 Write the SOP form the output Step 4 Simplify the output expression x = ABC + A BC + AB C + ABC x = ABC + ABC + A BC + ABC + AB C + ABC = BC ( A + A) + AC ( B + B ) + AB (C + C ) = BC + AC + AB E1.2 Digital Electronics I 5.13 Cot 2007 E1.2 Digital Electronics I 5.14 Cot 2007 Minimization by Karnaugh Maps – 4 Variable example What is a Karnaugh map? AB\CD 00 01 11 10 – 3 Variable Example: A\BC 00 01 11 10 00 0 01 ? ?? 1 11 – A grid of squares 10 – Each square represents one minterm eg: top-left represents A. B. C , bottom-right represents A. B. C – The minterms are ordered according to Gray code – The square marked ? represents A. B.C. D only one variable changes between adjacent squares – Squares on edges are considered adjacent to squares on opposite – The square marked ?? represents A. B.C. D edges – Karnaugh maps become clumsier to use with more than 4 variables – Note that they differ in only the C variable. E1.2 Digital Electronics I Cot 2007 E1.2 Digital Electronics I Cot 2007  Filling out a Karnaugh Map Minimization Technique Write the Boolean expression in SOP form Minimization is done by spotting patterns of 1's and 0's For each product term, write a 1 in all the squares which Simple theorems are then used to simplify the Boolean are included in the term, 0 elsewhere description of the patterns – canonical form: one square Pairs of adjacent 1's – one term missing: two adjacent squares – remember that adjacent squares differ by only one variable – two terms missing: 4 adjacent squares – hence the combination of 2 adjacent squares has the form Eg: X = A BC + A B C + AB C + ABC P(A + A) – this can be simplified (from before) to just P A\BC 00 01 11 10 0 0 0 1 0 1 0 1 1 1 E1.2 Digital Electronics I Cot 2007 E1.2 Digital Electronics I Cot 2007 X = A BC + AB C + ABC + ABC Take out previous example (Slide 12) “Cover” all the 1’s with maximum grouping: A\BC 00 01 11 10 A\BC 00 01 11 10 0 0 0 1 0 0 0 0 1 0 1 0 1 1 1 1 0 1 1 1 the adjacent squares A B C and A B C differ only in A The simplified Boolean equation is one that sums all the terms – hence they can be combined into just BC corresponding to each of the group: – normally indicated by grouping the adjacent squares to be combined X = AC + BC + AB Adjacent Pairs – The same idea extends to pairs of pairs E1.2 Digital Electronics I Cot 2007 E1.2 Digital Electronics I Cot 2007  More examples More Examples of grouping AB\CD 00 01 11 10 AB\CD 00 01 11 10 00 0 1 0 0 00 0 0 0 0 01 0 1 0 0 01 1 0 0 1 11 1 1 1 1 11 1 0 1 1 10 0 1 0 0 10 0 0 0 0 AB + C D BD + ABC E1.2 Digital Electronics I Cot 2007 E1.2 Digital Electronics I 5.22 Cot 2007 E1.2 Digital Electronics I 5.23 Cot 2007 E1.2 Digital Electronics I 5.24 Cot 2007 Complete Simplification Process 1. Construct the K map and place 1s and 0s in the squares according to the truth table. 2. Group the isolated 1s which are not adjacent to any other 1s. (single loops) 3. Group any pair which contains a 1 adjacent to only one other 1. (double loops) 4. Group any octet even if it contains one or more 1s that have already been grouped. 5. Group any quad that contains one or more 1s that have not already been grouped, making sure to use the minimum number of groups. 6. Group any pairs necessary to include any 1s that have not yet been grouped, making sure to use the minimum number of groups. 7. Form the OR sum of all the terms generated by each group. E1.2 Digital Electronics I 5.25 Cot 2007 E1.2 Digital Electronics I 5.26 Cot 2007 Don’t Care Conditions More “Don’t Care” examples In certain cases some of the minterms may never occur “Don’t care” conditions should be changed to either 0 or 1 or it may not matter what happens if they do to produce K-map looping that yields the simplest – In such cases we fill in the Karnaugh map with and X expression. meaning don't care – When minimizing an X is like a "joker" X can be 0 or 1 - whatever helps best with the minimization – Eg: A\BC 00 01 11 10 0 0 0 1 X 1 0 0 1 1 – simplifies to B if X is assumed 1 X = B E1.2 Digital Electronics I Cot 2007 E1.2 Digital Electronics I 5.28 Cot 2007  The Karnaugh Map with 5 variables OPEN = M F1 + M F 3 + M F 2 E1.2 Digital Electronics I 5.29 Cot 2007 E1.2 Digital Electronics I 5.30 Cot 2007 Summary K Map Method Summary SOP and POS –useful forms of Boolean equations Design of a comb. Logic circuit Compared to the algebraic method, the K-map process is a (1) construct its truth table, (2) convert it to a SOP, (3) more orderly process requiring fewer steps and always simplify using Boolean algebra or K mapping, (4) producing a minimum expression. implement The minimum expression in generally is NOT unique. K map: a graphical method for representing a circuit’s truth table and generating a simplified expression For the circuits with large numbers of inputs (larger than four), other more complex techniques are used. “Don’t cares” entries in K map can take on values of 1 or 0. Therefore can be exploited to help simplification E1.2 Digital Electronics I 5.31 Cot 2007 E1.2 Digital Electronics I 5.32 Cot 2007