Minimization

Amu_Ke_Fundye

Minimization

Minterm

• Each product term is known as minimum term that contains all the variables used in a function.
• A minterm is also called a canonical product term.
• A minterm is a product term, but a product term may or may not be a minterm.

Maxterm

• Each sum term is known as maximum term that contains all of the variables used in the function.
• A maxterm is a sum term of all variables in which each variable is either in complemented form or in uncomplemented form.
• A maxterm is also called a canonical sum term.
• A maxterm is a sum term, but a sum term may or may not be a maxterm.

The following are examples of product term, minterm, sum term, and maxterm for a function of three variables a, b, and c:

• product terms: a, ac, b’c, abc, a’bc, a’b’c’, …
• minterms: ab’c, abc, a’b’c, a’b’c’, …
• sum terms: a, (a+b), (b+c), (a’+b), (a’+b’), …
• maxterms: (a+b+c), (a+b’+c), (a’+b’+c’), …

Representations of Minterm and Maxterm

Note: With’ n’ variables maximum possible minimum and maximum terms = 2ⁿ

With’ n’ variables maximum possible logic expression = 

SOP (Sum of Product): A sum of product expression is two or more AND functions or functions together.

• SOP expression is used when output becomes logic 1.
• Example: 
  • three minterms are there in the expression

POS (Product of Sum): It is the AND function of two or more OR function.

• POS expression is used when output is logic ‘0’.
• Example: 
  • Three maxterms are there in the expression

Example: SOP and POS Equivalences for function F and Its Inverse F’.

Duality Theorem: To convert positive logic into negative logic and vice-versa, dual function are used.

• Change each AND sign by OR sign and vice versa (↔ +)
• Complement any 0 or l appearing in expression.
• Keep variable as it is.
• Example: 

Minimization of Boolean Expressions

The following two approaches can be used for simplification of a Boolean expression:

1. Algebraic method (using Boolean algebra rules)
2. Karnaugh map method

Representation of K-map

With n-variable Karnaugh-map, there are 2ⁿ cells.

Example:

• 2 –variable K Map:

• 3 –variable K Map:

• 4 –variable K Map:

NOTE: Once the Karnaugh map has been populated with 1s, 0s and Xs as specified the only task that remains is to group adjacent terms of the same state (usually 1) in groups of 2 raised to any rational power, i.e. 1, 2, 4, 8, 16, 32, 64 and so on. The larger the group the simpler the final expression. It is also possible for groups to overlap. This is often done to achieve a larger group size, hence simplifying the final expression.

Minimization Procedure of Boolean Expression using K-map

1. Construct a K-map.
2. Find all groups of horizontal or vertical adjacent cells that contain 1.
   • Each group must be either rectangular or square with 1, 2, 4, 8, or 16 cells.
   • Each group should be as large as possible.
   • Each cell with 1 on the K-map must be covered at least once. The same
   • cell can be included in several groups if necessary.
   • Select the least number of groups so as to cover all the 1’s.
   • Adjacency applies to both vertical and horizontal borders.
3. Translate each group into a product term. (Any variable whose value changes from cell to cell drops out from the term)
4. Sum all the product terms.

Note: Don’t care conditions can be used to provide further simplification of a Boolean Expression.

EXAMPLE: Simplify the following equation using a K-map (Karnaugh-map):

SOLUTION: Draw the K-map and minimise.

Regards 

Amrut Jagdish Gupta