Map Simplification | Readstall

Map Simplification

11-02-19 Mounika Mayakuntla 0 comment

Map simplification:

                                                The complexity of the logic diagram that implements a Boolean function is related directly to the complexity of the algebraic expression from which the function is implemented. The truth table representation of a function is unique, but the function can appear in many different forms when expressed algebraically. The expression may be simplified using the basic relations of Boolean algebra. However this procedure is sometimes difficult because it lacks specific rules for predicting each succeeding step in the manipulative process. Two methods of simplifying Boolean algebraic expression are the Map method and the Tabular method.

          The map method is used for functions up to 6 variables. To manipulate functions of a large number of variables, the tabular method also known as the Quine-McCluskey method is used. Another tabular method, known as the iterative consensus method, begins the simplification process even if the function is not in a canonical form.

          The map method provides a simple, straight forward procedure for simplifying Boolean expressions. This method may be regarded as the pictorial arrangement of the truth table which allows an easy interpretation for choosing the minimum number of terms needed to express the function algebraically. The map method is also known as the Karnaugh map or k-map.

Minterm: Is a combination of variables in the truth table. If we represent n variables it will be having 2n minterms. A Boolean function is equal to 1 for some minterms and to 0 for others.

Grouping of minterms:

  • Group the elements in 2n ratio or minterms

                    n=0, 20 =1 minterm

                    n=1, 21 =2 minterms

                    n=2, 22 =4 minterms and so on

  • Diagonal mapping is not allowed
  • Corner grouping can reduce the expression size
  • Rounded grouping is used to have minimum variables
  • Avoid individual minterm grouping

k-maps are of three types. They are

  1. SOP[Sum Of Products]
  2. POS[Product Of Sums]
  3. Don’t care condition

SOP:

          The minterm produce 1 for the function are listed in their decimal equivalent. The minterms missing from the list are the ones that produces 0 for the function. The map is a diagram made up of squares, with each square representing one minterm. The squares corresponding to minterms that produce 1 for the function are marked by a 1 and others are marked by 0 or are left empty. By recognizing various patterns and combining squares marked by 1’s in the map, it is possible to derive alternative algebraic expressions for the function, from which the most convenient may be selected.

          The number of squares in a map of n variables is 2n. The 2n minterms are listed by an equivalent decimal number for easy reference.

Image result for k map simplifications

Image result for kmaps for 2,3,4 variable functions

POS:

          The product terms are AND terms and the sum denotes the OR of these terms. It is sometimes convenient to obtain the algebraic expression for the function in a Product of Sums form. The sums are OR terms and the product denotes the ANDing of these terms. With a minor modification, a product of sums form can be obtained from a map.

          The procedure for obtaining the Product of Sums expression follows from the basic properties of Boolean algebra. The 1’s in the map represents the minterms that produce 1 for the function. The squares not marked by 1 represent the minterms that produce 0 for the function. If we mark the empty squares with 0’s and combine them into groups of adjacent squares, we obtain the complement of the function, F’. taking the complement of F’ produces an expression for F in product of sums form.

Image result for k map simplifications

Don’t care condition:

                   The 1’s and 0’s in the map represent the minterms that make the function equal to 1 or 0. There are occasions when it doesn’t matter if the function produces 0 or 1 for a given minterm. Since the function may be either 1 or 0, we say that we don’t care what the function output is to be for this minterm. Minterms that may produce either 0 or 1 for the function are said to be Don’t care conditions and are marked with an X in the map. These don’t care conditions can be used to provide further simplification of the algebraic expression.

Image result for don't care condition maps



Leave a reply