Two Level Simplification All Boolean expressions can be represented in twolevel forms Sum of products Product of sums 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 efficient Seattle Pacific University Canonical S O P form f a b c a bc ab c ab c Reduced S O P form f a b c abc ab c ab c f a b c abc ab c c f a b c abc ab EE 1210 Logic System Design KMaps 1 Venn Diagrams Consider a Venn Diagram for 2 sets A and B A B B AB AB A B 0 Seattle Pacific University A B B 1 A 0 A B A 1 AB AB A B EE 1210 Logic System Design KMaps 2 Karnaugh maps 2 variable K map F A B A B 0 0 0 Space for A B Space for AB Seattle Pacific University 1 1 A 0 0 1 1 1 00 10 B 0 1 0 1 1 0 01 Space for A B 11 F 0 1 1 0 Space for AB EE 1210 Logic System Design KMaps 3 Karnaugh maps K maps can represent up to four variables easily f A B C C C 0 AB 1 C 01 11 10 00 000 001 00 0000 0001 0011 0010 01 010 011 01 0100 0101 0111 0110 m0 m2 A f A B C D CD AB 00 m1 m3 11 110 111 m6 m7 m5 3 variable K map m5 m4 B 10 100 101 m4 m1 m0 A m3 m7 m2 m6 B 11 1100 1101 1111 1110 m12 m13 m15 m14 10 1000 1001 1011 1010 m9 m8 m11 m10 D 4 variable K map Numbering Scheme 00 01 11 10 Gray Code only a single bit changes from one number to the next Seattle Pacific University EE 1210 Logic System Design KMaps 4 Filling in a K map F A B C D ABC D AB CD ABC D AB CD A BCD F A B C A B C ABC A B C AB C f A B C C 0 AB A CD AB 00 C 01 11 10 C 00 0 0 0 0 1 00 1 1 01 0 0 1 0 01 0 0 11 1 1 0 0 1 0 0 10 0 0 1 1 11 10 B A D 1 3 variable K map Seattle Pacific University 4 variable K map EE 1210 Logic System Design KMaps 5 B Finding Combinations with K maps B 0 1 0 0 1 1 0 1 A We can combine A B and AB F A B AB B B 0 1 0 1 1 1 0 0 A We can combine A B and A B G A B A B A With Karnaugh maps adjacent 1 s mean we can combine them Seattle Pacific University EE 1210 Logic System Design KMaps 6 Adjacencies in the K map Neighbors C AB C 0 1 00 01 Wrap from top to bottom B A 11 10 Wrap from left to right Seattle Pacific University EE 1210 Logic System Design KMaps 7 3 variable K map examples F C 0 AB A F 1 00 1 1 01 1 0 11 0 0 10 0 1 C 0 AB A C 1 1 1 01 1 0 10 B C 00 11 F C B A A BC AB C A B 0 0 0 1 In the K map adjacency wraps from left to right and from top to bottom B Seattle Pacific University F C B A A C B C Same function alternative circling Note Larger circles are better EE 1210 Logic System Design KMaps 8 3 variable K map examples G C 0 AB A C We can use the combining theorem on larger units as well 1 00 0 0 01 1 1 11 1 1 10 0 0 B 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 Seattle Pacific University Find the smallest number of the largest possible rectangles that cover all the 1 s at least once overlapping circles are allowed EE 1210 Logic System Design KMaps 9 4 variable K map example F A B C D m 0 1 2 3 4 5 6 7 8 10 11 13 14 F CD 00 AB 00 01 A 11 10 01 11 10 1m 0 1m 1 1m 3 1m 2 1m 4 1m 5 1m 7 1m 6 12 1m 13 0m 15 1m 0m 1 Find the smallest number of the largest possible rectangles that cover all the 1 s C m8 0 m9 1 m11 D 1 14 m10 B Start at upper left corner and search for 1 s Circled Go to next 1 Not circled Circle largest term that contains this 1 and go to next 1 Tie Skip this square for now and come back to it later F A B C D A BC D CD B D B C Seattle Pacific University EE 1210 Logic System Design KMaps 10 K maps for XORs and XNORs B 0 1 0 0 1 1 1 0 A C 0 AB G A B C A BC ABC AB C A B C A Q CD AB 00 00 01 A 11 10 1 00 0 1 01 1 0 11 0 1 10 1 0 B C 01 11 10 0 1 0 1 1 0 1 0 0 1 0 1 1 C G F A B AB A B 0 1 Q A B C D AB B A 0 D PCD P A B C D C 00 01 11 10 00 1 0 1 0 01 0 1 0 1 11 1 0 1 0 10 0 1 0 1 D Seattle Pacific University EE 1210 Logic System Design KMaps 11 B Product of Sums We can circle 0 s to find a sum of products for the complement F C CD 00 AB 00 01 A 11 10 1 0 1 1 m0 m4 m12 m8 01 11 1 0 1 0 0 m1 m5 m13 m9 0 m3 m7 0 0 F A C A BD AD m2 m6 0 1 0 1 m15 m11 F A B C D m 0 1 5 8 10 12 14 10 m14 m10 B F A C A BD AD F A C A B D A D DeMorgan s Law Product of Sums D 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 F …