ECE2030 Introduction to Computer Engineering Lecture 7 Simplification using K map Prof Hsien Hsin Sean Lee School of Electrical and Computer Engineering Georgia Tech Hamming Distance The count of bits different in two binary patterns Examples Dh 1001 0101 2 Dh 0xADF4 0x9FE3 Unit Distance Codes Reduce errors during transmission such as rotary positional sensor E g Gray Code 2 Gray Code Construction 0 1 00 01 11 10 000 001 011 010 110 111 101 100 0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000 3 Gray Code Binary Encoding Gray Code Encoding Decimal b3 b2 b1 b0 g3 g2 G1 g0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 2 0 0 1 0 0 0 1 1 3 0 0 1 1 0 0 1 0 4 0 1 0 0 0 1 1 0 5 0 1 0 1 0 1 1 1 6 0 1 1 0 0 1 0 1 7 0 1 1 1 0 1 0 0 8 1 0 0 0 1 1 0 0 9 1 0 0 1 1 1 0 1 10 1 0 1 0 1 1 1 1 11 1 0 1 1 1 1 1 0 12 1 1 0 0 1 0 1 0 13 1 1 0 1 1 0 1 1 14 1 1 1 0 1 0 0 1 15 1 1 1 1 1 0 0 0 g i b i b i 1 where b 4 0 4 Rotary Position Sensor 5 Karnaugh Map K Map A graphical map method to simplify Boolean function up to 6 variables A diagram made up of squares Each square represents one minterm or maxterm of a given Boolean function 6 Karnaugh Map Examples Note that the Hamming Distance between adjacent columns or adjacent rows including cyclic ones must be 1 for simplification purposes 7 Karnaugh Map Adjacent columns or rows allow grouping of minterms maxterms for simplification 8 Implicant Definition A product term is an Implicant of a Boolean function if the function has an output 1 for all minterms of the product term In K map an Implicant is bubble covers only 1 bubble size must be a power of 2 CD 00 01 11 10 00 1 1 0 0 01 0 0 1 0 11 0 1 1 1 10 1 1 0 0 AB 9 Prime Implicant Definition If the removal of any literal from an implicant I results in a product term that is not an implicant of the Boolean function then I is an Prime Implicant Implicant Examples BCD is an implicant but CD or BD or BC do not imply a 1 in this function BCD is a PI B C D is an implicant but B C is not an implicant thus B C D is not a PI CD 00 01 11 10 00 1 1 0 0 01 0 0 1 0 11 0 1 1 1 10 1 1 0 0 AB In K map a Prime Implicant PI is bubble that is expanded as big as possible bubble size must be a power of 2 10 Essential Prime Implicant Definition If a minterm of a Boolean function is included in only one PI then this PI is an Essential Prime Implicant Implicant In K map an Essential Prime Implicant is Bubble that contains a 1 covered only by itself and no other PI bubbles CD 00 01 11 10 00 1 1 0 0 01 0 0 1 0 11 0 1 1 1 10 1 1 0 0 AB 11 Non Essential Prime Implicant Definition A Non Essential Prime Implicant is a PI that is not an Essential PI In K map an NonEssential Prime Implicant is A 1 covered by more than one PI bubble CD 00 01 11 10 00 1 1 0 0 01 0 0 1 0 11 0 1 1 1 10 1 1 0 0 AB 12 Simplification for SOP Form K Map for the given Boolean function Identify all Essential Prime Implicants for 1 s in the K map Identify non Essential Prime Implicants in the Kmap for the 1 s which are not covered by the Essential Prime Implicants Form a sum of products SOP with all Essential Prime Implicants and the necessary non Essential Prime Implicants to cover all 1 s 13 Example for SOP Identify all the essential PIs for 1 s Identify the nonessential PIs to cover 1 s Form an SOP based on the selected PIs F m 0 1 4 6 7 A BC 00 01 11 10 0 1 1 0 0 1 1 0 1 1 F A B AB BC or F A B AB A C 14 Example for SOP Identify all the essential PIs for 1 s Identify the nonessential PIs to cover 1 s Form an SOP based on the selected PIs F m 0 1 7 8 9 13 14 15 CD 00 01 11 10 00 1 1 0 0 01 0 0 1 0 11 0 1 1 1 10 1 1 0 0 AB F BC ABC BCD ACD or F BC ABC BCD ABD 15 Example for SOP Identify all the essential PIs for 1 s Identify the nonessential PIs to cover 1 s Form an SOP based on the selected PIs F M 1 3 4 6 11 12 CD 00 01 11 10 00 1 0 0 1 01 0 1 1 0 11 0 1 1 1 10 1 1 0 1 AB F BD BD ABC ACD or F BD BD ABC A BC 16 Prime Implicants All the prior definitions apply to 0 or maxterm as well Consider these implicants imply a 0 output 17 Simplification for POS Form K Map for the given Boolean function Identify all Essential Prime Implicants for 0 s in the K map Identify non Essential Prime Implicants in the Kmap for the 0 s which are not covered by the Essential Prime Implicants Form a product of sums POS with all Essential Prime Implicants and the necessary non Essential Prime Implicants to cover all 0 s 18 Example for POS Identify all the essential PIs for 0 s Identify the nonessential PIs to cover 0 s Form an POS based on the selected PIs F M 2 3 5 A BC 00 01 11 10 0 1 1 0 0 1 1 0 1 1 F A B A B C 19 Example for POS Identify all the essential PIs for 0 s Identify the nonessential PIs to cover 0 s Form an POS based on the selected PIs F M 1 3 4 6 11 12 CD 00 01 11 10 00 1 0 0 1 01 0 1 1 0 11 0 1 1 1 10 1 1 0 1 AB F B C D A B D B C D A B D 20 Don t Care Condition X Don t care X Those input combinations which are irrelevant to the target function i …
View Full Document
Unlocking...