Gate-level minimization
Karnaugh Map OR K-Map: A K-Map is a diagram made up of squares, with each square representing one minterm of the function that is to be minimized.
Since any Boolean function can be expressed as a sum of minterms, it follows that a Boolean function is recognized graphically in the map from the area enclosed by those square whose minterms are included in the function.
The simplified expressions produced by the map are always in one of the two standard forms: Sum of Products or Product of sums
It is sometimes possible to find two or more expressions that satisfy the minimization criteria.
The simplest algebraic expression is an algebraic expression with a minimum number of terms and with the smallest possible number of literals in each term. This expression produces a circuit diagram with a minimum number of gates and the minimum number of inputs to each gate.
Two-Variable Map
There are four minterms for two variables; hence, the map consists of four squares one for each minterm.
The 0 and 1 marked in each row and column designate the values of variables. Variable 'x' appears primed in row 0 and unprimed in row 1. Similarly 'y' appears primed in column 0 and unprimed in column 1.
Thus, a 2 * 2 square can be used for representing any two variable function. To represent a three variable function we need a 2 * 4 K-Map.
Three -Variable Map:There are eight minterms for three binary variables; therefore, the map consists of eight squares. But the minterms are arranged not in a binary sequence but in a sequence similar to the Gray code.
Simplify the Boolean function using K-Map
Q: F(x,y,z) = ∑(2,3,4,5)
First, a 1 is marked in each minterm that represents the function so the squares for minterms corresponding to value to 010, 011, 100 and 101 are marked with 1's.
The next step is to find possible adjacent squares. This is done by combining squares into rectangles (100, 101) and (011, 010).
Then to find the new equations that represent this rectangle: The upper rectangle represents the area enclosed by represents the area shown by x'y. This area is obtained as the rectangle lies in area corresponding to x = 0. Secondly, y = 1 is shared by both squares. Also for one square z = 0 and other has z = 1 so z isn't common.
Similarly, the lower left rectangle represents the product term xy'. The logical sum of these two product terms gives the simplified expression. F = x'y + xy'
Q: F(x,y,z) = ∑(3, 4, 6, 7)
There are 4 squares marked with 1's to correspond to the 4 minterms denoted by the numbers 3, 4, 6, 7.
Two adjacent squares are combined in the third column to give a two-literal term yz. The remaining two squares with 1's are also adjacent as the minterms representing them differ by only one variable i.e. 100 and 110
The simplified function now becomes: F = yz + xz'
Note : Any combination of four adjacent squares in the three-variable map represents the logical sum of four minterm sand results in an expression with only one literal. Thus, the logical sum of the four adjacent minterms 0, 2, 4, and 6 reduces to a single literal term z'. The number of adjacent squares that may be co mbined must always represent a number that is a power of two, such as 1, 2, 4, and 8. As more adjacent squares are combined, we obtain a product term with fewer literals.
Q. F(x, y, z) = ∑(0, 2, 4, 5, 6)
First we combine the four adjacent squares in the first and last columns to give the single literal term z'.
The remaining single square representing minterm 5, is combined with an adjacent square that has already been used once. This is not only permissible but rather desirable.
The two adjacent squares give the two-literal term xy' and the single square represents the three-literal minterm xy'z.
The simplified function is F = z' + xy'
Q. Express this function as a sum of minterms and Find the minimal sum of products expression for F = A'C + A'B + AB'C + BC
There are three literals and so we use a three variable KMap to represent them. The term A'C is represent by an intersection of row A' and columns 2 and 3 for C. So we get the squares belonging to the midterms 001 and 011.
Using the same method we find squares representing the other terms in the function.
AB'C belongs to square 101 (minterm 5)
Also with the second term, A'B has 1's in squares 011 and 010.
The term BC is represented by the third column with the square 011 and 111.
The function now has five minterms and can be represented as F (x, y, z) = ∑(1, 2, 3, 5, 7).
Simplify the equation by combining columns 2 and 3 to get the term as C and then combine squares 011 and 010 to get A'B
Ans . F = C + A'B
Four Variable K-Map
The map for Boolean functions of four binary variables has 16 squares with each corresponding to a minterm. The rows and columns are numbered in a Gray code sequence, with only one digit changing value between two adjacent rows or columns.
The minterm corresponding to each square can be obtained from the concatenation of the row number with the column number. For example. the numbers of the third row ( 11 ) and the second column (01), when concatenated, give the binary number 1101, the binary equivalent of decimal 13. Thus, the square in the third row and second column represents mintern m13.
Adjacent squares are defined to be squares next to each other. The squares on the top column touch the squares in the bottom column. In addition, squares in the leftmost column touch squares in the rightmost column.
The minterms shown in the sum are marked as 1 in the K-Map and we have 11 squares with 1.
Column 1 and 2 are clubbed to create a single variable y'.
Column 4 has three square with 1's but these cannot be combined as they are in power of 2.
We could now combine them as two rectangle of 2 squares each or two squares of size (2*2). Since we want a minimised term we choose to combine two squares of size (2*2).
This gives us w'z' and xz'.
Final equation: F = y' + w'z' + xz'
A'B'C' is represented in squares 0000 and 0001.
B'CD' is given by squares 0010 and 1010
A'BCD' is given by square 0110
AB'C' is given by squares 1000 and 1001
For simplification we combine minterms m0 m1, m8, m9. to get term B'C' and we also combine squares m = 0, 2, 8, 10 to get term B'D'. Finally we combine squares m = 2,6 to get term A'CD'.
Therefore, F = B'D' + B' C' + A'C D'
A prime implicant is a product term obtained by combining the maximum possible number of adjacent squares in the map. If a minterm in a square is covered by only one prime implicant that prime implicant is said to be essential.
This means that a single 1 on a map represents a prime implicant if it is not adjacent to any other 1's. Two adjacent 1's form a prime implicant provided that they are not within a group of four adjacent squares. Four adjacent 1's form a prime implicant if they are not within a group of eight adjacent squares and so on.
The essential prime implicants are found by looking at each square marked with a 1 and checking the number of prime implicants that cover it. The prime implicant is essential if it is the only prime implicant that covers the mintern .
The procedure for finding the simplified expression from the map requires that we first determine all the essential prime implicants. The simplified expression is obtained from the logical sum of all the essential prime implicants, plus other prime implicants that may be needed to cover any remaining minterms not covered by the essential prime implicants.
Find out the 1's which can be covered only under a single prime implicant. In the figure the 1's that fulfil this condition are in m = 0, 5, 8. These have to included in prime implicants as these are the essential prime implicants.
The essential prime implicants are obtained by combining minterms m = 0,3,8,10 to get the term B'D' and m = 5,7,13,15 to get the term BD
This leaves the minterms m = 9, 11, 3 which may be covered using prime implicants in multiple ways and we get mulitple solutions as.
F = BD + B'D' + CD + AD
= BD + B'D' + CD + AB'
= BD + B'D' + B' C + AD
= BD + B'D' + B'C + AB'
If we are given a function in Sum of Products form and we have to find the minimization in Product of Sum form we follow the procedure:
Mark all the minterms as 1 in the squares of the K-Map. The empty spaces are marked as 0's.
Then we use the procedure of combining adjacent squares to create larger squares or rectangles. However we shall combine squares containing 0's and not 1's.
This is the only difference from the Sum of Products procedure.
Applying DeMorgan's theorem (by taking the dual and complementing each literal), we obtain the simplified function in product-of-sums form
The 1's marked in the figure represent all the minterms of the function. The squares marked with 0's represent the minterms not included in F and therefore denote the complement of F. Combining the squares with 1's gives the simplified function in sum-of-products form:
F = B'D' + B' C' + A'C'D
If the squares marked with 0's are combined we obtain the simplified complemented function: F' = AB + CD + BD'
Applying DeMorgan ' s theorem (by taking the dual and complementing each literal), we obtain the simplified function in product-of-sums form:
F = ( A' + B' )(C' + D' )(B ' + D)
As three variables are present in the function we need a three variable K-Map.
Mark 0's in the positions corresponding to the maxterms given in the equation i.e. 0, 2, 5, 7
Then we apply the minimization logic to obtain the equation: The maxterms m = 0, 2 are combined to get the term (x + z). The term is expressed in Product of sum form and we get x when x = 0, x' when x = 1. (reverse of SOP form)
The maxterms m = 5, 7 are combined to get the term (x' + z').
Thus we have, F = (x+z)(x'+z')
Q. Simplify the Boolean function given by F(w,x,y,z) = ∑(0,1,2,4,5,6,8,9,12,13,14)
Q. Simplify the expression F = A'B'C' + B'CD' + A'BCD' + AB'C'
Prime Implicants
Q. Consider the following four-variable Boolean function: F(A, B, C, D) = ∑( 0, 2, 3, 5, 7, 8, 9, 10, 11, 13, 15)
PRODUCT-OF-SUMS SIMPLIFICATION
Q. Simplify the: following Boolean function into (a) sum-of-products form and (b) product-of sums form: F(A, B, C, D) = ∑(0, 1, 2, 5, 8, 9, 10)
Q. F(x,y,z) = ∏(0,2,5,7)
