Simplification of Switching Function

EEN1036 Digital Logic Design Chapter 4 part I Simplification of Switching Function 1 Objective s s s s Simplifying logic circuit Minimization using Karnaugh map Using Karnaugh map to obtain simplified SOP and POS expression Five-variable Karnaugh map 2 Simplifying Logic Circuits • • • A A Boolean expression for a logic circuit may be reduced to a simpler form The simplified expression can then be used to implement a circuit equivalent to the original circuit Consider the following example: B C A B C + A BC Y AB C + AB C Y = A B C + A BC + AB C + AB C 3 Continue …
Checking for common factor: Y = A B C + A BC + AB C + AB C = A C ( B + B ) + AB (C + C ) Reduce the complement pairs to ‘1’ Y = A C ( B + B ) + AB (C + C ) = A C + AB Draw the circuit based on the simplified expression A B C Y 4 Continue … • A Consider another logic circuit: B C Y Y = C( A + B + C ) + A + C Convert to SOP expression: Y = C( A + B + C ) + A + C = AC + B C + AC Checking for common factor: Y = A(C + C ) + B C = A + BC 5 Continue … • • Simplification of logic circuit algebraically is not always an easy task The following two steps might be useful: i.
The original expression is convert into the SOP form by repeated application of DeMorgan’s theorems and multiplication of terms ii. The product terms are then checked for common factors, and factoring is performed wherever possible 6 Continue … • Consider the truth table below: A 0 0 0 0 1 B 0 0 1 1 0 C 0 1 0 1 0 Y 0 0 1 0 0 Minterm Boolean expression: Simplify to yield: Y = A BC + ABC + AB C Y = BC ( A + A) + AB C = BC + AB C 1 0 1 1 1 1 0 1 1 1 1 0 • If minterms are only differed by one bit, they can be simplified, e. g.

A BC & ABC 7 Continue … • More example: A 0 0 0 0 1 1 1 1 B 0 0 1 1 0 0 1 1 C 0 1 0 1 0 1 0 1 Y 0 1 1 0 0 1 1 0 Minterm Boolean expression: Y = A B C + A BC + AB C + ABC Minterms 1 and 5, 2 and 6 are only differ by one bit: Y = B C ( A + A) + BC ( A + A) = BC + B C A B C Y 0 0 0 1 0 0 1 0 0 0 1 1 1 1 1 1 0 0 1 1 0 1 0 1 0 1 1 0 1 0 1 0 Minterm Boolean expression: Y = A B C + A BC + AB C + ABC Checking and factoring minterms differed by only by one bit: Y = A C ( B + B ) + AC ( B + B ) = A C + AC = C ( A + A) =C 8 Continue … • • • Though truth table can help us to detect minterms which are only differed by one bit, it is not arranged in a proper way A Karnaugh map (K-map) is a tool, which help us to detect and simplify minterms graphically It is a rearrangement of the truth table where each adjacent cell is only differed by one bit By looping adjacent minterms, it is similar to grouping the minterms with a single bit difference on the truth table 9 Karnaugh Map • • A K-map is just a rearrangement of truth table, so that minterms with a single-bit difference can be detected easily Figure below shows 4 possible arrangement of 3-variable K-map A BC 0 0 01 1 11 3 10 2 C AB 00 0 01 2 11 6 10 4 0 1 4 5 7 6 0 1 1 3 7 5 AB C 0 0 1 1 BC A 0 0 1 4 00 01 2 3 00 01 1 5 11 6 7 11 3 7 10 4 5 10 2 6 10 Continue … • Figure below show two possible arrangement of 4variable K-map CD AB 00 0 01 1 11 3 10 2 AB 00 CD 01 4 11 12 10 8 00 01 4 5 7 6 00 0 01 1 5 13 9 11 12 13 15 14 11 3 7 15 11 10 8 9 11 10 10 2 6 14 10 • Notice that the K-map is labeled so that horizontally and vertically adjacent cells differ only by one bit. 11 Continue … • The K-map for both SOP and POS form are shown below: C D C D CD C D AB AB AB 0 1 3 2
C+D C+ D C + D C +D A +B 0 1 3 2 4 5 7 6 A+B A+B A +B 4 5 7 6 12 13 15 14 12 13 15 14 AB 8 9 11 10 8 9 11 10 SOP form (minterm) POS form (maxterm) • • The simplified SOP expression can be obtained by properly combining those adjacent cells which contains ‘1’ This process of combining adjacent minterms is known as 12 looping Continue … • • Each loop of minterms will form a group which can be represented by a product term When a variable appears in both complemented and uncomplemented form within a group, that variable is eliminated from the product term C D C D CD C D
AB AB AB AB 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 group 2 group 1: C D( AB + AB ) = AC D group 2: AB(C D + CD ) = ABD Simplified SOP expression: Y = AC D + ABD 13 group 1 Continue … • Consider another K-map: C D C D CD C D AB AB AB AB 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 group 1 C D C D CD C D AB AB AB AB 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 14 group 1: ( A B + AB )(C D + CD ) = BD Simplified SOP expression: Y = BD group 1: C D ( A B + A B + AB + AB ) = C D Simplified SOP expression: Y = CD group 1 From truth table to K-map • The content of each cell can be directly plot on the Kmap according to the truth table Consider the following example: 0 1 2 3 4 5 6 7 A 0 0 0 0 1 1 1 1 B C Y 0 0 1 0 1 1 1 0 1 1 1 0 0 0 0 0 1 0 1 0 1 1 1 0 B C B C BC B C A A 1 0 1 1 0 3 1 2 0 4 0 5 0 7 1 6 AB BC Simplified SOP expression: Y = A B + BC 15 Continue … • Consider the following 4-variable K-map A 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 B 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 C D Y 0 0 0 0 1 1 1 0 0 1 1 0 0 0 0 0 1 1 1 0 0 1 1 0 0 0 0 0 1 0 1 0 0 1 1 0 0 0 0 0 1 1 1 0 0 1 1 1 C D C D CD C D AB AB AB 0 0 0 1 1 1 0 1 0 0 1 0 3 0 0 0 ACD 2 4 5 7 6 12 13 15 14 AB 0 8 9 11 0 10 ABD Simplified SOP expression: Y = A C D + ABD 16 Continue … • Some guidelines: i. Construct K-map and fill it according to the truth table ii. Only loop cells in the power of 2, i. e. 2 cells, 4 cells, 8 cells and so on iii. Always start by looping the isolated minterms iv. Look for minterms which are adjacent to only one minterm and loop them together v. Proceed on to loop the largest possible groups, from eight minterms (octet), 4 minterms (quad) to 2 minterms (pair) vi.
Obtain the product term for each group vii. The sum of these product terms will be the simplified SOP expression 17 Continue … Example: a. Obtain the simplify SOP expression for the truth table: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 B 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 C 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 D 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 Y 0 0 1 0 0 1 0 1 0 0 0 1 0 1 0 1 C D C D CD C D AB AB AB AB A B CD 0 0 0 0 0 0 1 1 0 1 0 1 1 3 1 0 0 0 2 4 5 7 6 12 13 15 14 8 9 1 11 10 BD ACD Simplified SOP expression:
Y = A B CD + ACD + BD 18 Continue … b. Obtain the simplify SOP expression from the K-map: ACD C D C D CD C D AB AB ABC 0 0 1 0 1 1 1 0 0 1 1 1 ACD 0 1 0 0 A BC AB AB Simplified SOP expression: Y = A C D + A BC + ACD + ABC 19 Continue … c. Obtain the simplify SOP expression from the K-map: alternative solution: C D C D CD C D AB AB AB C D C D CD C D AB A CD 0 0 0 0 AC D 0 0 1 1 1 1 0 1 0 0 0 0 AB D 0 0 0 0 AC D 0 0 1 1 1 1 0 1 0 0 0 0 B CD A CD AB AB AB AB Y = A CD + AC D + AB D Y = A CD + AC D + B CD 20 General Terminology for Logic Minimization • • Here, we define four terms to provide the basis for general function minimization techniques These terms are implicant, prime implicant, essential prime implicant and cover We refer to the K-map below in explaining each term B C B C BC B C A A 1 0 1 1 3 2 1 4 1 5 1 7 6 • • An implicant is a product term that could be used to cover minterms of the function In the K-map above, there are 11 implicants: 5 minterms: {A B C , A BC , AB C , AB C , ABC} 5 group of two adjacent minterms: {AB , AC , A C , B C , BC} 1 group of four adjacent minterms:{C} 21 Continue … • • • A prime implicant is an implicant that is not part of any other mplicant In the K-map, there are two prime implicant: C and AB An essential prime implicant is a prime implicant that covers at least one minterm that is not covered by any other prime implicants Prime implicant AB is essential as it is the only prime implicant that covers minterm 4 Prime implicant C is also essential as it is the only prime implicant that covers minterm 1, 3 and 7 A cover of a function is a set of prime implicants for which each minterm of the function is contained in (covered by) at least one prime implicant All essential prime implicants must be used in any cover of a function 22 • • • Continue … • • For the K-map above, the set of implicants { AB , C} represents a cover of the function A minimum cover contains the minimum number of prime implicants which contains all minterm in the function Consider the 4-variable K-map below: C D C D CD C D AB AB AB AB 1 1 Prime implicants • C D C D CD C D AB AB AB 1 1 1 1 1 1 1 1 1 AB AB AB AB C D C D CD C D 1 1 1 1 Minimum cover 1 1 1 1 1 1 1 1 1 1 1 1 AB Essential prime implicants 23 Continue … • Consider another K-map C D C D CD C D AB AB AB AB 1 1 1 1 1 1 1 Prime implicants C D C D CD C D AB 1 1 1 1 1 1 1 1 1 1 AB AB 1 AB
Essential prime implicants (minimum cover) 24 Don’t Care Conditions • • • • Some logic circuit will have certain input conditions whereby the output is unspecified This is usually because these input conditions would never occur In other words, we “don’t care” whether the output is HIGH or LOW Consider the following example: An air conditioning system has two inputs, C and H: – C will be ‘1’ if temperature is too cold (below 15°C) Otherwise, it will be ‘0’ – H will be ‘1’ if temperature is too hot (above 25°C) Otherwise, it will be ‘0’ – Output Y will be ‘1’ if temperature is too cold or too hot.
If the temperature is acceptable, Y will be ‘0’ 25 Continue … As there are two inputs, there are 4 possible logical conditions: C 0 0 1 1 H 0 1 0 1 Y 0 1 1 X meaning just nice too hot too cold ? Input condition C = 1, H = 1 has no real meaning, as it is impossible to be too hot and too cold at the same time We put a ‘X’ at the output corresponds to this input condition as this input condition cannot occur 26 K-map and Don’t Care Term • Don’t care term, ‘X’ can be treated as ‘0’ or ‘1’ since they cannot occur In K-map, we can choose the don’t care term as ‘0’ or ‘1’ to our advantage A B C D Y 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 1 1 X 0 1 0 0 1 0 1 0 1 X 0 1 1 0 0 0 1 1 1 X 1 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1 X 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 X C D C D CD C D AB AB AB 0 1 1 0 1 X 1 0 X X X X 0 0 1 0 AB Simplified Boolean expression: Y = AB + BC + A D 27 More examples … C D C D CD C D AB AB AB AB C D C D CD C D AB AB AB AB 1 1 X 1 0 1 X 1 0 0 X X 0 1 X X 1 0 X 1 0 0 X 0 0 0 X X 1 X X Y = C D + BC + BD + A C D C D CD C D AB AB AB Y = B D + CD C D C D CD C D AB AB AB 0 0 1 0 1 X 1 1 0 1 X 0 0 0 0 0 1 1 X 0 1 X X 1 0 1 X X 0 0 X X 28 AB AB Y = ABC + C D + BD Y = A C + BD + AD Plotting function in Canonical Form • Logic function may be expressed in many forms, ranging from simple SOP/POS expression to more complex expressions However, each of them has a unique canonical SOP/POS form If a Boolean expression is expressed in canonical form, it can be readily plotted on the K-map Consider the following Boolean expression: • • • Y = ABC + B C
Convert to canonical SOP expression: Y = ABC + B C ( A + A) = ABC + A B C + AB C 29 Continue … Y = ABC + A B C + AB C Plotting the canonical SOP expression onto K-map B C B C BC B C A A 1 1 0 0 BC 0 0 0 1 AC Simplified SOP expression: Y = B C + AC • Consider plotting the following Boolean expression on K-map: Y = C ( A ? B) + A + B 30 Continue … First, convert to SOP expression Y = C ( A ? B) + A + B = C ( AB + A B) + A B = AB C + A BC + A B (C + C ) = AB C + A BC + A B C + A B C B C B C BC B C A A 1 0 AB 1 1 1 0 BC 0 0 AC ?Y = A B + B C + A C 31
Plotting K-map from SOP expression • • It is sometime too tedious to convert a Boolean expression to its canonical SOP form Consider the following Boolean expression: Y = AB (C + D )(C + D ) + A + B Convert to SOP form: Y = ( AB C + AB D )(C + D ) + A B = AB C D + AB CD + A B Convert to canonical form: Y = AB C D + AB CD + A B (C + C )( D + D) = AB C D + AB CD + ( A B C + A B C )( D + D) = AB C D + AB CD + A B C D + A B C D + A B CD + A B CD 32 Continue … Y = AB C D + AB CD + A B C D + A B C D + A B CD + A B CD Plot the minterm on K-map: C D C D CD C D AB AB
AB 1 0 0 1 1 0 0 0 1 0 0 1 1 0 0 0 AB AB B CD BC D Simplified SOP expression: Y = B C D + B CD + A B 33 Continue … • • • • • Boolean expression can be plotted on to the K-map from its SOP form Product terms with four variables are the minterms and correspond to a single cell on the K-map Product term with three variables corresponds to a loop of two adjacent minterms Product term with only two variables is a quad (a loop of four adjacent minterms) Product term with a single variable is an octet (a loop of eight adjacent minterms) 1 cell 2 cells
Y = A + BC + B CD + ABCD 4 cells 8 cells 34 Continue … • Consider the previous example: Y = AB C D + AB CD + A B minterms 4 cells • • • Both minterms are directly plotted on the K-map The loop which corresponds to A B is drawn on the K-map The cells inside the loops are filled with ‘1’ C D C D CD C D AB AB AB AB 1 0 0 1 1 0 0 0 1 0 0 1 1 0 0 0 AB AB C D A B CD 35 Continue … • Consider the following Boolean expression: Y = ( A + B )( AC + D ) Convert to SOP form: Y = AC + AD + ABC + BD Plot the SOP onto K-map C D C D CD C D AB AB AB AB AC BD C D C D CD C D AB AB ill cells in loops with ‘1’ 0 0 0 0 0 1 1 1 0 1 1 1 0 0 1 1 36 ABC AB AB AD Continue … Obtain the simplified SOP expression from K-map: C D C D CD C D AB AB AB AB 0 0 0 0 0 1 1 1 0 1 1 1 0 0 1 1 Simplified SOP expression: Y = AC + AD + BD 37 Continue … Example: Redesign the logic circuit below from its simplified SOP expression: A B C D Z Z = ( B + D )( B + D ) + B(CD + A D ) 38 Continue … Z = ( B + D )( B + D ) + B(CD + A D ) = B + D + B + D + BCD + A BD = BD + B D + BCD + A BD C D C D CD C D AB AB AB 1 1 0 1 0 1 1 0 0 1 1 0 1 1 0 1 AB Z = BD + B D + A B 39