DE_MF

Solution: (Figure below)  Write the Boolean expression for the original logic diagram as shown below  Transfer the product terms to the Karnaugh map  Form groups of cells as in previous examples  Write Boolean expression for groups as in previous examples  Draw simplified logic diagramExample:Simplify the logic diagram below.Solution: Write the Boolean expression for the original logic diagram shown above Transfer the product terms to the Karnaugh map. It is not possible to form groups. No simplification is possible; leave it as it is.No logic simplification is possible for the above diagram. This sometimeshappens. Neither the methods of Karnaugh maps nor Boolean algebra cansimplify this logic further. We show an Exclusive-OR schematic symbolabove; however, this is not a logical simplification. It just makes a schematicNTTF DIGITAL ELECTRONICS (Common for CP04 & CP15) _ 3rd Sem._ June 2017 Page 51

diagram look nicer. Since it is not possible to simplify the Exclusive-OR logicand it is widely used, it is provided by manufacturers as a basic integratedcircuit (7486).3-VARIABLE K MAPWe show our previously developed Karnaugh map. We will use the form onthe right.Note the sequence of numbers across the top of the map. It is not in binarysequence which would be 00, 01, 10, 11. It is 00, 01, 11 10, which is Graycode sequence. Gray code sequence only changes one binary bit as we gofrom one number to the next in the sequence, unlike binary. That means thatadjacent cells will only vary by one bit, or Boolean variable. This is what weneed to organize the outputs of a logic function so that we may viewcommonality. Moreover, the column and row headings must be in Gray codeorder, or the map will not work as a Karnaugh map. Cells sharing commonBoolean variables would no longer be adjacent, nor show visual patterns.Adjacent cells vary by only one bit because a Gray code sequence varies byonly one bit.If we sketch our own Karnaugh maps, we need to generate Gray code forany size map that we may use. This is how we generate Gray code of anysize.NTTF DIGITAL ELECTRONICS (Common for CP04 & CP15) _ 3rd Sem._ June 2017 Page 52

Note that the Grey code sequence, above right, only varies by one bit as wego down the list, or bottom to top up the list. This property of grey code isoften useful in digital electronics in general. In particular, it is applicable toKarnaugh maps.Let us move on to some examples of simplification with 3-variable Karnaughmaps. We show how to map the product terms of the un simplified logic tothe K-map. We illustrate how to identify groups of adjacent cells which leadsto a Sum-of-Products simplification of the digital logic.NTTF DIGITAL ELECTRONICS (Common for CP04 & CP15) _ 3rd Sem._ June 2017 Page 53

Above we, place the 1‘s in the K-map for each of the product terms, identify agroup of two, then write a p-term (product term) for the sole group as oursimplified result.Mapping the four product terms above yields a group of four covered byBoolean A’Mapping the four p-terms yields a group of four, which is covered by onevariable C.After mapping the six p-terms above, identify the upper group of four, pick upthe lower two cells as a group of four by sharing the two with two more fromthe other group. Covering these two with a group of four gives a simplerresult. Since there are two groups, there will be two p-terms in the Sum-of-Products result A’+BNTTF DIGITAL ELECTRONICS (Common for CP04 & CP15) _ 3rd Sem._ June 2017 Page 54

The two product terms above form one group of two and simplifies to BCMapping the four p-terms yields a single group of four, which is BMapping the four p-terms above yields a group of four. Visualize the group offour by rolling up the ends of the map to form a cylinder, then the cells areadjacent. We normally mark the group of four as above left. Out of thevariables A, B, C, there is a common variable: C‘. C‘ is a 0 over all four cells.Final result is C’.NTTF DIGITAL ELECTRONICS (Common for CP04 & CP15) _ 3rd Sem._ June 2017 Page 55

The six cells above from the un simplified equation can be organized into twogroups of four. These two groups should give us two p-terms in our simplifiedresult of A’ + C’.Below, we revisit the Toxic Waste Incinerator from the Boolean algebrachapter. See Boolean algebra chapter for details on this example. We willsimplify the logic using a Karnaugh map.The Boolean equation for the output has four product terms. Map four 1‘scorresponding to the p-terms. Forming groups of cells, we have three groupsof two. There will be three p-terms in the simplified result, one for each group.See ―Toxic Waste Incinerator‖, Boolean algebra chapter for a gate diagram ofthe result, which is reproduced below.NTTF DIGITAL ELECTRONICS (Common for CP04 & CP15) _ 3rd Sem._ June 2017 Page 56