EE 2372 Section 05 Boolean Function Minimization.ppt

EE 2372 Modern Digital System Design Section 05 Boolean Function Minimization Goals of Minimization The goals of minimization are Reduce the number of logical operations. Reduce the number of input terms (literals). Reduce the number of variables.  Example: The switching function Contains 3 ANDs, 2 ORs and 2 NOTs, so there are 7 logical operations. Contains 5 literals. Contains 3 variables Goals of Minimization Example: The switching function Contains 3 ANDs, 3 ORs and 3 NOTs, so there are 9 logical operations. Contains 6 literals. Contains 3 variables. Through minimization we may be able to reduce the number of logical operation, variables or input terms. Algebraic Minimization Apply the Postulates and Theorems of Boolean Algebra to simplify statements. Example: with 5 ANDs, 3 ORs and 2 NOTs, 10 logical operations, 5 literals and 4 variables, may be simplified to Algebraic Minimization with 2 ANDs, 2 NOTs, 4 logical operations, 3 literals, 3 variables. Algebraic Minimization Examples Algebraic Minimization Note: The ?quality? of the simplification depends on the designer?s ability to apply the appropriate theorem or Postulate of Boolean Algebra. The approach taken by the designer is too often led by experience and intuition. Note: This task becomes more difficult as the complexity of the switching function increases. Note: There is no approach guaranteed to find the optimal minimal solution. As an alternative to the algebraic approach, we present an ?intuitive? graphical approach that does not depend upon exhaustive knowledge of Boolean Algebra. Karnaugh Maps Mapping of switching functions in the SOP form: Consider the Venn Diagram, illustrating all possible SOP combinations of the variables a and b, Karnaugh Maps This may also be demonstrated by the minterms. Karnaugh Maps Or in Karnaugh Map form. Karnaugh Maps Any SOP switching function of two variables may be directly mapped onto a truth table. Karnaugh Maps By grouping the terms that are logically adjacent to each other we simplify the function: Karnaugh Maps By grouping the terms that are logically adjacent to each other we simplify the function: Karnaugh Maps By grouping the terms that are logically adjacent to each other we simplify the function: Karnaugh Maps Mapping of switching functions in the POS form: Consider the Venn Diagram, with the complement of all possible POS combinations of the variables a and b. Karnaugh Maps This may also be demonstrated by the complement of the Maxterms Karnaugh Maps Or in Karnaugh Map form: Karnaugh Maps Any SOP switching function of two variables may be directly mapped onto a Karnaugh Map by entering the compliment of the Maxterms. Karnaugh Maps By grouping the terms that are logically adjacent to each other we may simplify the switching function. Karnaugh Maps By grouping the terms that are logically adjacent to each other we may simplify the switching function. Karnaugh Maps By grouping the terms that are logically adjacent to each other we may simplify the switching function. Karnaugh Maps of Three Variables A Karnaugh map of three variables f (a,b,c) is in the form: Note: The variables bc are listed in Gray Code form. (A change of only one bit from column to column.) Karnaugh Maps of Three Variables A Karnaugh map of three variables f (a,b,c) is in the form: Note: Cells that are logically adjacent to each other occur in groups of 4. Note: The map ?wraps around? in the horizontal direction. Karnaugh Maps of Three Variables A Karnaugh map of three variables f (a,b,c) is in the form: Note: Cells that are logically adjacent to each other occur in groups of 2. Note: The map ?wraps around? in the horizontal direction. Karnaugh Maps of Four Variables A Karnaugh map of three variables f (a,b,c,d) is in the form: Karnaugh Maps of Four Variables Note: The variables ab and cd are listed in Gray Code form (a change of only one bit from cell to cell. Karnaugh Maps of Four Variables Note: Cells that are logically adjacent to each other occur in groups of 8. The map ?wraps around? in the horizontal and vertical directions. Karnaugh Maps of Four Variables Note: Cells that are logically adjacent to each other occur in groups of 4. The map ?wraps around? in the horizontal and vertical directions. Karnaugh Maps of Four Variables Note: Cells that are logically adjacent to each other occur in groups of 2. The map ?wraps around? in the horizontal and vertical directions. Karnaugh Maps of Five Variables Note: Cells within the same ?square? are logically adjacent. Note: ?Upper right? cells are logically adjacent. ?Lower left? cells are logically adjacent. Note: Cells that are logically adjacent to each other occur in groups of 16, groups of 8, groups of 4 and groups of 2. Note: The map ?wraps around? in the horizontal and vertical directions. Karnaugh Maps of Six Variables Note: Cells within the same ?square? are logically adjacent. Note: ?Upper middle? cells are logically adjacent. ?Middle right? cells are logically adjacent. Note: ?Lower middle? cells are logically adjacent. ?Middle left? cells are logically adjacent. Note: Cells that are logically adjacent to each other occur in groups of 32, groups of 16, groups of 8, groups of 4 and groups of 2. Note: The map ?wraps around? in the horizontal and vertical directions. Karnaugh Maps of Four Variables Any switching function in canonical SOP form may be directly entered onto the map by entering a 1 in each appropriate cell. Karnaugh Maps of Four Variables Karnaugh Maps of Four Variables Any switching function in canonical POS form may be directly entered onto the map by entering a 0 in each appropriate cell. Karnaugh Maps of Four Variables The function in minterm list form: Has an equivalent function in Maxterm list form: The Canonical forms may be read from the Karnaugh Map. The Canonical forms may be read from the Karnaugh Map. Simplification Using Karnaugh Maps Group terms in groups of powers of 2 (2, 4, 8, 16, ...) to eliminate variables. The larger the group, the fewer the variables. Make as few groups as possible. Start with the ?loneliest? entries. Terminology: Implicant: A product term that can be used to cover any of the minterms of a Karnaugh Map. This example has 11 implicants. Implicants Terminology: Prime Implicant: An implicant that is not a subset of any other implicant. Prime Implicants Terminology: Essential Prime Implicant: Prime implicant that covers at least one minterm not covered by another prime implicant. Essential Prime Implicants Terminology: Cover: Set of prime implicants that includes each of the minterms in at least one prime implicant. Selection Rule Minimize the overlap among prime implicants as much as possible. Make sure that each prime implicant selected includes at least one minterm not included in any other prime implicant selected. The Exclusive-Or Operation The Exclusive-Or (XOR) operation is defined by: 0 ? 0 = 0 0 ? 1 = 1 1 ? 0 = 1 1 ? 1 = 0 The Exclusive-Or Operation The Exclusive-Or (XOR) operation is defined by the truth table: Karnaugh Maps of the XOR Operation Karnaugh Maps of the XOR Operation Karnaugh Maps of the XOR Operation Karnaugh Maps of the XOR Operation Karnaugh Maps of the XOR Operation Karnaugh Maps of the XOR Operation Karnaugh Maps of the XOR Operation Karnaugh Maps of the XOR Operation Karnaugh Maps of the XOR Operation Karnaugh Maps of the XOR Operation Karnaugh Maps of the XOR Operation Karnaugh Maps of the XOR Operation Incompletely Specified Functions Don?t Care conditions may be used to simplify functions: Incompletely Specified Functions It is not required (or even preferable!) to include all of the ?don?t-care conditions in the output function. Only those that may help in finding a simplified function. Variable Entered Map Variables may be entered directly on a map. Variable Entered Map