Two-Level SimplificationVenn DiagramsKarnaugh mapsSlide 4Filling in a K-mapFinding Combinations with K-mapsAdjacencies in the K-map3-variable K-map examplesSlide 94-variable K-map exampleK-maps for XORs and XNORsProduct-of-SumsK-maps and Don’t CaresExample: 2-bit ComparatorK-maps for 2-bit comparatorBCD Decrement by 1BCD Decrement by OneSeattle Pacific University EE 1210 - Logic System Design KMaps-1Two-Level Simplification•All Boolean expressions can be represented in two-level forms•Sum-of-products•Product-of-sumscbacbabcacbaf ),,(Canonical S.O.P. formReduced S.O.P. form•Canonical forms are very easy to produce•Just read them off of a truth table•But, they’re not the most efficient representation•Reduced two-level forms are more efficientf a b c abc ab c ab cf a b c abc ab c cf a b c abc ab( , , )( , , ) ( )( , , )     Seattle Pacific University EE 1210 - Logic System Design KMaps-2Venn DiagramsConsider a Venn Diagram for 2 sets, A and BAB’A’BABA’B’B=0B=1A=0A=1ABA’B’AB’ABA’BSeattle Pacific University EE 1210 - Logic System Design KMaps-3Karnaugh maps2-variable K-mapA 0 0 1 1 B 0 1 0 1 F 0 1100110B A 0 1 0 1 00100111F(A,B)Space for A’BSpace for ABSpace for A’B’Space for AB’Seattle Pacific University EE 1210 - Logic System Design KMaps-4Karnaugh mapsK-maps can represent up to four variables easily3-variableK-map4-variableK-mapNumbering Scheme: 00, 01, 11, 10Gray Code — only a single bit changes from one number to the nextA f(A,B,C)f(A,B,C,D)ABC00 01 11 10 0 1 000 001010 011110 111100 101BABCD00 01 11 10 00 01 11 10 0000 00010100 01011100 11011000 10010011 00100111 01101111 11101011 1010A BC DC m0m1m2m3m6m7m4m5m0m1m4m5m12m13m8m9m3m2m7m6m15m14m11m10Seattle Pacific University EE 1210 - Logic System Design KMaps-5Filling in a K-mapF(A,B,C,D) = ABC’D’ + AB’CD’ + ABC’D + AB’CD + A’BCDF (A,B,C) = A’B’C’ + ABC’ + A’B’C + AB’C3-variableK-map4-variableK-map1 1110000111 110 0 0000000 00f(A,B,C)ABC00 01 11 10 0 1 BC A ABCD00 01 11 10 00 01 11 10 A BC DSeattle Pacific University EE 1210 - Logic System Design KMaps-6Finding Combinations with K-mapsF = A’B + AB = BG = A’B’ + A’B = A’We can combine A’B and ABWe can combine A’B’ and A’BWith Karnaugh maps, adjacent 1’s mean we can combine themB A 0 1 0 10 1 0 1 BA 0 1 1 1 0 0 0 1Seattle Pacific University EE 1210 - Logic System Design KMaps-7Adjacencies in the K-mapWrap from left to rightWrap from top to bottomNeighborsABC00 01 11 10 0 1 BC ASeattle Pacific University EE 1210 - Logic System Design KMaps-83-variable K-map examplesF(C,B,A) = A’C’ + B’CIn the K-map, adjacency wraps from left to rightand from top to bottomF(C,B,A) = A’BC’ + AB’C + A’B’Same function, alternative “circling”Note: Larger circles are better0 1 FABC00 01 11 10 0 1 BC A 1 1 1 0 0 0 0 1 FABC00 01 11 10 0 1 BC A 1 1 1 0 0 0Seattle Pacific University EE 1210 - Logic System Design KMaps-93-variable K-map examplesWe can use the combining theorem on larger units as well.G(A,B,C) = A’BC’ + A’BC + ABC’ + ABC = A’B(C’ + C) + AB(C’ + C) = A’B + AB = B(A’ + A) = B•What can we circle?•Any rectangle that contains all ones•As long as its size is a power of two•1, 2, 4, 8, 16, ...•No rectangles of 3, 5, 6, ...Find the smallest number of the largest possible rectangles that cover all the 1’s at least once (overlapping circles are allowed)GABC00 01 11 10 0 1 BC A 1 0 0 0 0 1 1 1Seattle Pacific University EE 1210 - Logic System Design KMaps-104-variable K-map example0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 F(A,B,C,D) = m(0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 13, 14)Find the smallest number of the largest possible rectangles that cover all the 1’sStart at upper left corner and search for 1’s:•Circled? – Go to next ‘1’•Not circled? – Circle largest term thatcontains this ‘1’ and go to next ‘1’• Tie? – Skip this square for now and come back to it later...F(A,B,C,D) = ABCD00 01 11 10 00 01 11 10 A BC DFm0m1m4m5m12m13m8m9m3m2m7m6m15m14m11m10A’ + BC’D + CD’ + B’D’ + B’CSeattle Pacific University EE 1210 - Logic System Design KMaps-11K-maps for XORs and XNORsB A 0 1 0 11 00 1 F = A’B + AB’ = A  BG = A’B’C + A’BC’ + ABC’ + AB’C = A  B  CP= A  B  C DQ= A  B  C  DGABC00 01 11 10 0 1 BC A 0 1 1 0 0 1 1 0 ABCD00 01 11 10 00 01 11 10 A BC D0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 QABCD00 01 11 10 00 01 11 10 A BC D0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 PSeattle Pacific University EE 1210 - Logic System Design KMaps-12Product-of-SumsF(A,B,C,D) = m(0,1,5,8,10,12,14)We can circle 0’s to find a sum-of-products for the complement• Circling 1’s gives S.O.P. for F• Complementing S.O.P. of F gives P.O.S. for F’• Circling 0’s gives S.O.P. for F’• Complementing S.O.P. for F’ gives P.O.S. for FProduct-of-Sums!F’ =ABCD00 01 11 10 00 01 11 10 A BC DFm0m1m4m5m12m13m8m9m3m2m7m6m15m14m11m100 0 1 1 1 1 0 0 0 0 0 0 0 1 1 1 A’C + A’BD’ + ADF = A’C + A’BD’ + ADF = (A+C’)(A+B’+D)(A’+D’)DeMorgan’s LawSeattle Pacific University EE 1210 - Logic System Design KMaps-13K-maps and Don’t CaresF(A,B,C,D) = m(1,3,5,7,9) + d(6,12,13)Invalid Inputs (Don’t Cares) can be treated as 1's or 0's if it is advantageous to do soBy treating this X as a "1", a largerrectangle can be formedF = assuming x’s are zeroTie! - Skip and come backABCD00 01 11 10 00 01 11 10 A BC DFm0m1m4m5m12m13m8m9m3m2m7m6m15m14m11m100 1 1 1 x 0 0 1 0 x 1 0 x 0 0 0 A’D+ B’C’DABCD00 01 11 10 00 01 11 10 A BC DFm0m1m4m5m12m13m8m9m3m2m7m6m15m14m11m100 1 1 1 x 0 0 1 0 x 1 0 x 0 0 0 F = using don’t caresA’D+ C’DSeattle Pacific University EE 1210 - Logic System Design KMaps-14Example: 2-bit ComparatorWill need a 4-variable K-map for each of the 3 output functions1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 1 1 1 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 1 1 1 0 =, >, < AB = CD AB < CD AB > CD AB C D N 1 N 2 F1F2F3DC and BA are two-bitbinary numbersF 1 F 2 F 3 D 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 C 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 B 0 1 0 1 A 0 0 1 1Seattle Pacific University EE 1210 - Logic System Design KMaps-15K-maps for 2-bit comparatorABCD00 01 11 10 00 01 11 10 A BC