COE/EE 243, Lec #12 ** Don't Cares (this is covered Wakerly, section 4.3.7) There are times when we don't care what the value of a combinational network is for a given input combination. Consider: A B C | f -------+--- 0 0 0 | 0 0 0 1 | 0 0 1 0 | 1 0 1 1 | 1 1 0 0 | 0 1 0 1 | X 1 1 0 | 1 1 1 1 | 1 To realize the function, a value must be specified for the don't care. It is best to choose a value that simplifies the function. F = B (X = 0) is simpler than F = B + AC (X = 1) When writing a canonical sum we will use "d" to indicate don't care minterms. F = m + m + m + m + d 2 3 6 7 5 Similarly, we will use "D" to indicate don't care maxterms. F = M M M D 0 1 4 5 If f = SUM m(0,3,5) + SUM d(4,7) then = A'B'C' + A'BC + AB'C + d(AB'C') + d(ABC) f = PROD M(1,2,6) x PROD D(4,7) = (A+B+C')(A+B'+C)(A'+B'+C) [D(A'+B+C)] [D(A'+B'+C')] Don't care terms are the same in both expressions! The don't cares are useful for simplifying expressions, but they can make it difficult to figure out how to simplify. To simplify, you need to assign the don't cares to be an output of either 0 or 1 and then simplify. If you have 2 don't cares, you have 4 different To simplify, you need to assign the don't cares to be an output of either 0 or 1 and then simplify. If you have 2 don't cares, you have 4 different cases to try (0,0) (0,1) (1,0) and (1,1) We'll look at other approaches later. ** Multi-Level Gate Networks -- Maximum number of gates cascaded in series between a network input and output is the number of LEVELS of gates (inverters are generally not counted). Any function in sum-of-products form or product-of-sums form corresponds directly to a two-level network. 1. AND-OR network: two-level network of AND gates followed by an OR gate at the output. 2. OR-AND network: two-level network of OR gates followed by an AND gate at the output. 3. OR-AND-OR network: three-level network by a level of OR gates followed by a level of AND gates followed by a single OR gate at the output. 4. Network of AND and OR gates: no particular order of AND and OR gates with either being the output gate. Example of counting gates, gate inputs, and levels: _____ a' --| | _____ | + |------| | _____ b --|_____| c'--| & |------| | d --|_____| | + |----- f _____ +---|_____| _____ c --| | | a --| | d'--| & |--+ | + |------|_____| b --|_____| 3 Levels 5 Gates 12 Gate Inputs Can use boolean algebra and other simplification methods to find networks with different number of levels, gates, and gate inputs. Example (all are the same f): f = a'c'd + bc'd + bcd' + acd' (AND-OR network) (5 gates, 16 inputs) f = c'd(a' + b) + cd'(a + b) (3-level network - OR output) (5 gates, 12 gate inputs) f = (c + d)(a' + b + c)(c' + d')(a + b + c') (OR-AND network) (5 gates, 14 inputs) ** Functionally Complete Sets of Logic Gates -- AND, OR, and NOT are functionally complete because any Boolean function can be expressed as a sum of products. NAND is functionally complete NOR is functionally complete 1. Write a minimum SOP expression for function realized by each gate. - If no complement appears in any of the expressions, NOT cannot be realized. - Otherwise, a careful choice of inputs can generally be made to realize NOT. 2. Next try to realize OR or AND - remember NOT is available. - If either can be found, other can be realized using DeMorgan's law. XY = (X' + Y')' So AND-NOT and OR-NOT are also functionally complete. In some circumstances it is beneficial to have a network made up of all NAND or all NOR gates, since NAND gates have a simpler structure than AND or OR. Similar for NOR. ** Converting to NAND and NOR networks -- To realize NAND network, start with minimum SOP expression and use F = (F')'. Example: AC + BC + D = ((AC + BC + D)')' = ((AC)'(BD)'D')' To realize NOR network, start with minimum POS expression. Example: (A + B')(A + C)D = ((A + B')' + (A + C)' + D')' A minimum 2-level NAND-NAND network is found by: 1. Find a minimum SOP. 2. Draw corresponding OR-AND network. 3. Replace all AND and OR gates with NAND gates and if output gate has any single literals as inputs, complement these literals. Same procedure to find minimum 2-level NOR-NOR network except steps 1 and 2 utilize the minimum POS instead. ** Minimum Forms of Switching Functions The cost of realizing a switching function is directly related to the number of gates and gate inputs used. Switching functions can be simplified by using algebraic techniques, but: - The procedures are difficult to apply systematically - It is hard to tell if you have a minimum solution A MINIMUM SUM-OF-PRODUCTS expression for a function has - a minimum number of product terms - of all expressions with same number of terms, has a minimum number of literals A MINIMUM PRODUCT-OF-SUMS expression for a function has - a minimum number of factors - of all expressions with same number of factors, has a minimum number of literals The above minimums correspond directly to a two-level gate network that has - a minimum number of gates - a minimum number of gate inputs The methods we've employed so far for simplifying Boolean expressions have been sort of random. As a result, it can be pretty difficult to see if you have it simplified all of the way, and in some cases to even see where to start. So we'll look at some more systematic methods for simplifying expressions. The first of these is the use of Karnaugh maps. Works best for expressions with up to 4 variables, but it can be extended to more complicated cases too, up to 6 variables Utilize the following Theorems: for SOP expression: AB+AB' = A(B+B') = A for POS expression: (A+B)(A+B') = (A+BB') = A ** 2-Variable Karnaugh Maps \ A B\ 0 1 \____________ | | | Each square of the map corresponds to a pair 0 | A=0 | A=1 | of values for A and B as indicated. | B=0 | B=0 | |_____|_____| | | | 1 | A=0 | A=1 | | B=1 | B=1 | |_____|_____| \ A B\ 0 1 \_______ | | | A B | F Minterms in adjacent squares can 0 | 0 | 1 | -----+--- be combined since they differ in |___|___| 0 0 | 0 only one variable. | | | 0 1 | 0 1 | 0 | 1 | 1 0 | 1 F = AB' + AB = sum m(2,3) = A |___|___| 1 1 | 1 1 cell covering corresponds to a 2-variable term 2 cell covering corresponds to a 1-variable term if have 2 variables.