Chapter - 9: Minimization Techniques/Methods

Following are the Minimization Techniques used in DLD

1. Boolean Algebra Techniques
2. Karnaugh's Map
3. Tabulation Method

1. Boolean Algebra Techniques

• Minimization of Boolean Expression depends upon rules, laws and theorems and ability to apply them
• It is a good method for minimization of simple expression
• Major problem is when we have a very large and complete Boolean Expression used Boolean Algebra techniques

2. Karnaugh's Map (K-Map) Method

• What is K-Map?

  A k-map is a standard method for minimization of Boolean expression. If it is properly used then k-map provides minimized or simplified form of Boolean Expression.

• Structure of K-Map

  The structure of K-map is based on adjacent cells. A k-map contains 2n adjacent cells each representing 1 input combination in product form, where n is the number of variables.

  Two cells or minterms are said to be adjacent to each other if and only if they differ by single input variable. Example: A ̅B and AB are adjacent minterms which A ̅B and AB are not adjacent minterms

  1. Structure of 2-Variable K-Map
  2. Structure of 3-Variable K-Map
  3. Structure of 4-Variable K-Map

• How to minimize/simplify the boolean expression using K-Map?

  Procedure:
• Step 1: Plotting Boolean expression in K-Map

  Sum of minterms Boolean expression can be plotted in K-Map by placing 1 for each minterm. Similarly products of minterms Boolean expression can be plotted in k-map by placing 0 for each maxterms

• Step 2: Making combinations
  1. Combination of (2) min-terms or max-terms is called a pair. Pair elements (1) variable
  2. Combination of (4) main terms or Max term is called a quad. A quad elements (2) variables
  3. Combination of (8) midterms or Max term is called octate. And octate elements (3) variables

• Step 3: Writting down the minimized form of Boolean expression from K-Map
• Basic Rules:

  minimum numbers of combinations that will cover maximum number of minterms. From k-map you can obtain two types of Boolean expression

  1. Sum of Products (SOP) - Minterm

     When we will make combination of 1’s then type of expression we will get from k-map is called Sum of Product in Boolean expression

  2. Products of Sum (POS) - Maxterm

     We will make combinations of 0’s then type of expression we will get from k-map is called product of sums Boolean expression

Difference between K-Map & Truth Table

Both truth table and K-map describes the behavior of logic ckt or Boolean Expressions. The truth table contains all possible input combinations of their input variables with corresponding outputs in sequence form, while k-map also contains all possible input combinations of their input variable with corresponding outputs in adjacency form but the main advantage of k-map is that we can get minimized form of Boolean Expressions.