Slide 1Hamming DistanceGray Code ConstructionGray CodeRotary Position SensorKarnaugh Map (K-Map)Karnaugh Map ExamplesKarnaugh MapImplicantPrime ImplicantEssential Prime ImplicantNon-Essential Prime ImplicantSimplification for SOPExample for SOPSlide 15Slide 16Prime ImplicantsSimplification for POSExample for POSSlide 20Don’t Care Condition XDon’t Care Example BCD to Gray CodeBCD to Gray Code (Do not use Don’ Care)What g2 is?Example: g2 of BCD-to-GrayAnother Example of Don’t Care (SOP)Another Example of Don’t Care (POS)Use Karnaugh Map in B5 or B6Karnaugh Map Example in B5Karnaugh Map Example in B6Minimal SOP and POS w/ Don’t careSlide 32ECE2030 Introduction to Computer EngineeringLecture 7: Simplification using K-mapProf. Hsien-Hsin Sean LeeProf. Hsien-Hsin Sean LeeSchool of Electrical and Computer EngineeringSchool of Electrical and Computer EngineeringGeorgia TechGeorgia Tech2Hamming 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 Code3Gray Code Construction010110001100011110101101000000111100000101101011011110110010010111111001001100100000000000111111114Gray CodeBinary Encoding Gray Code EncodingDecimal b3 b2 b1 b0 g3 g2 G1 g00 0 0 0 0 0 0 0 01 0 0 0 1 0 0 0 12 0 0 1 0 0 0 1 13 0 0 1 1 0 0 1 04 0 1 0 0 0 1 1 05 0 1 0 1 0 1 1 16 0 1 1 0 0 1 0 17 0 1 1 1 0 1 0 08 1 0 0 0 1 1 0 09 1 0 0 1 1 1 0 110 1 0 1 0 1 1 1 111 1 0 1 1 1 1 1 012 1 1 0 0 1 0 1 013 1 1 0 1 1 0 1 114 1 1 1 0 1 0 0 115 1 1 1 1 1 0 0 00b e wherbbg41iii5Rotary Position Sensor6Karnaugh 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 function7Karnaugh Map Examples Note that the Hamming DistanceHamming Distance between adjacent columnsadjacent columns or adjacent rows adjacent rows (including cyclic ones) (including cyclic ones) must be 1 for simplification purposes8Karnaugh MapAdjacent columns or rows allow grouping of minterms (maxterms) for simplification9Implicant•Definition–A product term is an ImplicantImplicant of a Boolean function if the function has an output 1 for all minterms of the product term.•In K-map, an ImplicantImplicant is –bubble covers only 1 (bubble size must be a power of 2)00 01 11 10001 1 0 0010 0 1 0110 1 1 1101 1 0 0ABCD10Prime Implicant•Definition–If the removal of any literal from an implicant II results in a product term that is not an implicant of the Boolean function, then II is an Prime ImplicantPrime Implicant.–Examples•BCDBCD is an implicant, but CDCD or BDBD or BCBC do not imply a 1 in this function; BCDBCD is a PIPI•B’C’DB’C’D is an implicant, but B’C’B’C’ is not an implicant, thus B’C’DB’C’D is not a PI•In K-map, a Prime Implicant (PI)Prime Implicant (PI) is –bubble that is expanded as big as possible (bubble size must be a power of 2)00 01 11 10001 1 0 0010 0 1 0110 1 1 1101 1 0 0ABCD11Essential Prime Implicant•Definition–If a minterm of a Boolean function is included in only one PI, then this PI is an Essential Prime Essential Prime ImplicantImplicant. •In K-map, an Essential Essential Prime ImplicantPrime Implicant is –Bubble that contains a 1 covered only by itself and no other PI bubbles00 01 11 10001 1 0 0010 0 1 0110 1 1 1101 1 0 0ABCD12Non-Essential Prime Implicant•Definition–A Non-Essential Prime Non-Essential Prime ImplicantImplicant is a PI that is not an Essential PI. •In K-map, an Non-Non-Essential Prime Essential Prime ImplicantImplicant is –A 1 covered by more than one PI bubble 00 01 11 10001 1 0 0010 0 1 0110 1 1 1101 1 0 0ABCD13Simplification 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 K-map 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’s14Example for SOP•Identify all the essential PIs for 1’s•Identify the non-essential PIs to cover 1’s•Form an SOP based on the selected PIs 7) 6, 4, 1, m(0,F00 01 11 1001 1 0 011 0 1 1 ABCCAABBAForCBABBAF15Example for SOP•Identify all the essential PIs for 1’s•Identify the non-essential PIs to cover 1’s•Form an SOP based on the selected PIs 15) 14, 13, 9, 8, 7, 1, m(0,F00 01 11 10001 1 0 0010 0 1 0110 1 1 1101 1 0 0ABCDABDBCDABCCBForDCABCDABCCBF16Example for SOP•Identify all the essential PIs for 1’s•Identify the non-essential PIs to cover 1’s•Form an SOP based on the selected PIs 12) 11, 6, 4, 3, M(1,F00 01 11 10001 0 0 1010 1 1 0110 1 1 1101 1 0 1ABCDCBAABCBDDBForDCAABCBDDBF17Prime Implicants•All the prior definitions apply to ‘0’ (or maxterm) as well•Consider these implicants imply a ‘0’ output18Simplification 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 K-map 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’s19Example for POS•Identify all the essential PIs for 0’s•Identify the non-essential PIs to cover 0’s•Form an POS based on the selected PIs)CBA)(B(AF 00 01 11 1001 1 0 011 0 1 1 ABC5) 3, M(2,F20Example for POS•Identify all the essential PIs for 0’s•Identify the non-essential PIs to cover 0’s•Form an POS based on the selected PIsD)B)(ADC)(BDBD)(ACB(F 00 01 11 10001 0 0 1010 1 1 0110 1 1 1101 1 0 1ABCD 12) 11, 6, 4, 3, M(1,F21Don’t Care Condition X•Don’t care (X)–Those input combinations which are irrelevant to the target function (i.e. If the input combination signals can be guaranteed never occur)–Can be used to simplify Boolean equations, thus simply logic design•In K-map–Use XX to express Don’t Care in the map–Don’t care can be bubbled as 11 or 00 depending on SOP or POS simplification to result into bigger bubble22Don’t Care Example BCD to Gray
View Full Document
Unlocking...