Gate Level Minimization

In the previous tutorial, all the possible boolean functions between two variables were discussed. In the tutorial – Boolean Algebra, various theorems and postulates were stated which are useful in simplifying a boolean expression or function. However, the simplification of a boolean expression using theorems and postulates is quite cumbersome and prone to errors. Therefore, for simplification of boolean expressions, some map methods were devised. The most commonly used map method is Karnaugh Map or K-Map.

These methods are based on the fact that every boolean function has a unique truth table. A boolean function can be represented by several boolean expressions but its truth table will always remain the same. This is due to the fact that a digital circuit will always have fixed outputs or response corresponding to the inputs. Let us first discuss, K-map.

Karnaugh Map –

The Karnaugh map is the most common simplification technique for boolean expressions. It is based on the following facts –

1) Any boolean function however may be represent able in several forms or boolean expressions always have a unique truth table. If two boolean expressions have same truth table, they are the same function.

2) Any boolean function can be represented by sum of products (Minterms) or product of sums (Maxterms).

3) The sum of Minterms or product of Maxterms is reducible by applying various boolean theorems.

The K-map is basically a tabular representation of the truth table. For example, a two-variable function can have the following truth table –

Its K-map will tabulate the function outputs corresponding to input variable values as follow –

Fig. 1: A Two-Variable K-Map

K-Map is useful is minimizing boolean expressions containing up to 5 variables or less. Once the map is constructed, the minimized expression can be deduced by the following process –

1) Enter 1s in those cells corresponding to the combinations for which the function value is 1 in the truth table. Then, fill 0s in the remaining cells of the K-map. Each cell in the map represents a Minterm. The boolean function represented by the map (the map is just a graphical representation of truth table) is sum of the minterms which may contain one or more boolean variables as literals.

2) Examine the map for 1-valued cells that cannot be combined with any other 1-valued cell or form groups with other 1-valued cells. That means identify 1-valued cells that have no adjacent 1-valued cell. Such groups represent minterms containing all the boolean variables as literals in the term as part of the boolean function.

3) Examine the map for 1-valued cells that are adjacent to only one another 1-valued cell and form groups containing only two 1-valued cells but are not part of any group containing four or eight 1-valued cells. Such groups represent minterms containing boolean variables as literals one less than the maximum number of boolean variables in the term as part of the function. Such groups are called pairs.

4) Examine the map for 1-valued cells that are adjacent to only three another 1-valued cells and form groups containing only four 1-valued cells but are not part of any group containing eight 1-valued cells. Such groups represent minterms containing boolean variables as literals two less than the maximum number of boolean variables in the term as part of the function. Such groups are called quads. In a 2-variable function, the formation of quad means the output of function is 1.

5) Examine the map for 1-valued cells that are adjacent to seven another 1-valued cells and form groups containing eight 1-valued cells but are not part of any group containing sixteen or higher 1-valued cells. Such groups represent minterms containing boolean variables as literals three less than the maximum number of boolean variables in the term as part of the function. Such groups are called octets. In a 3-variable function, the formation of octet means the output of function is 1.

6) Form all the groups of singles, pairs, quads and octets such that there are minimum number of groups. The pairs, quads and octets can also be formed with the combination of 1-valued cells at opposite edges of the map. Like in the following K-map for 3-variable boolean function, m0 and m8 at the corners are forming a pair.

Fig. 2: A Three-Variable K-Map

7) Remove any redundant groups.

8) A 1-valued cell with no adjacent 1-valued cell gives a Minterm containing 2, 3, 4, 5 variable term for 2-variable, 3-variable, 4-variable and 5-variable boolean function or K-map respectively. A pair of 1-valued cells gives a Minterm containing 1, 2, 3, 4 variable term for 2-variable, 3-variable, 4-variable and 5-variable boolean function or K-map respectively. A quad of 1-valued cells gives a Minterm containing 1, 2, 3 variable term for 3-variable, 4-variable and 5-variable boolean function or K-map respectively. The formation of quad for a 2-variable function means it is equal to 1. An octet of 1-valued cells gives a Minterm containing 2 or 3 variable term for 4-variable and 5-variable boolean function or K-map respectively. The formation of octet for a 3-variable function means it is equal to 1.

9) If a single 1-valued cell is identified, it represents a Minterm having the boolean variable as literal in the term for been matched to value of 1 for the respective boolean variable and/or having complement of the boolean variable as literal in the term for been matched to value 0 for the respective boolean variable. Such 1-valued cell will induct a Minterm in the function containing all the boolean variables either in compliment or normal form. If a pair is identified, one boolean variable will be eliminated and a Minterm containing one less number of maximum boolean variables is inducted in the boolean function. Similarly, a quad leads to elimination of two boolean variables in the Minterm and so on. The boolean variable having a bit change within the pair, quad or octet is eliminated in the term.

10) The boolean function is the logical sum of the Minterms generated by all the groups. The boolean function as product of sum can be similarly generated by groups of 0s.

Two-variable K-map –

A two-variable K-map has four cells as the maximum number of minterms possible with two boolean variables is 4 (2^2). There can be maximum 16 functions (2^2*2) generated by two boolean variables.

Fig. 3: Two-Variable K-Map and Minterms

A function generated by a two-variable K-map is reducible by single 1-valued cells or pairs. The formation of a quad in two-variable K-map means the function is equal to 1.

Three-variable K-map –

A three-variable K-map has eight cells as the maximum number of minterms possible with three boolean variables is 8 (2^3). There can be maximum 64 functions (2^2*3) generated by three boolean variables.

Fig. 4: Three-Variable K-Map and Minterms

A function generated by a three-variable K-map is reducible by single 1-valued cells, pairs or quad. The formation of an octet in three-variable K-map means the function is equal to 1.

Four-Variable K-map –

A four-variable K-map has sixteen cells as the maximum number of minterms possible with four boolean variables is 16 (2^4). There can be maximum 256 functions (2^2*4) generated by four boolean variables.

Fig. 5: Four-Variable K-Map and Minterms

A function generated by a four-variable K-map is reducible by single 1-valued cells, pairs, quads or octets. The formation of 16 single-valued cells in four-variable K-map means the function is equal to 1.

Five-Variable K-map –

A five-variable K-map has thirty two cells as the maximum number of minterms possible with five boolean variables is 32 (2^5). There can be maximum 1024 functions (2^2*5) generated by five boolean variables.

Fig. 6: Five-Variable K-Map and Minterms

A function generated by a five-variable K-map is reducible by single 1-valued cells, pairs, quads, octets or group of 16 1-valued cells. The formation of 32 single-valued cells in five-variable K-map means the function is equal to 1.

Don’t Care Combinations –

It is not necessary that all output for a boolean function be always known. In digital circuits, there can be possibility where for certain combinations, the output can be either 1 or 0. In such case, either d, x or Ø is inserted in the K-map for the corresponding input combinations. For deriving the boolean expression, either 1 or 0 can be assumed at don’t care combinations to deduce a minimal sum of products or product of sum expression.

Quine-McCluskey Method –

The K-map is useful in deducing boolean expressions involving four boolean variables or less. Further, it gets complex. So, another method called Quine-McCluskey method is used for deducing boolean expressions involving four or more boolean variables. Quine-McCluskey method is a tabular method for deriving the minimal boolean expression. From the truth table of a boolean function, the combinations for which the output of the function is 1 can be listed. These combinations can be indexed in ascending order as binary numbers. For example, suppose there is a boolean function involving four boolean variables (A, B, C, D) having the following truth table –

The combinations resulting into 1 on being indexed in ascending order as binary numbers gives the following table for the above case

This boolean function can be written as follow –The combinations resulting into 1 on being indexed in ascending order as binary numbers gives the following table for the above case –

F (A, B, C, D) = ∑ (0, 5, 8, 9, 10, 11, 14, 15)

In the first step of Quine-McCluskey method, the minterms are arranged in groups by the number of 1s in them as follow –

Any two minterms in adjacent groups like group 0 and 1, group 1 and 2 or group 2 and 3 and so on are now compared and examined for change in the value of only one boolean variable. Such minterms are selected as match and tabulated as pairs in the next step with a dash in place where single boolean variable has changed for the match like as follow –

In the next step, the matches in the adjacent groups from table in step 2 are compared and examined for dash for the same variable and change in the value of only one boolean variable. Such matches are selected as quads and tabulated in the next table with a dash in place where single boolean variable has changed for the match. The pairs in second table and minterms in first table that were not matched in the respective tables are also tabulated in the next table (third table) as follow –

The quads, pairs or singles derived in the third table (removing the redundant ones) are called prime implements. In the next step, the prime implements are tabulated against minterms and the minterms included in the respective prime implement (quad, pair or single) is marked by X against the respective prime implement as follow –

In the final table, the columns having a single X are examined and rows containing such X are identified. The prime implements respective to those rows are noted and the terms respective to those prime implements are included as sum of products in the boolean expression by comparison of prime implements and boolean variables from the third table. In the third table, the boolean variable against selected prime implement having value dash is not included, the boolean variable against selected prime implement having value 1 is included in normal form in the respective term and the boolean variable against selected prime implement having value 0 is included in compliment form in the respective term. The selected prime implements from fourth table are called essential implements. For the above boolean function, in the fourth table, all the rows are having an X which is single in at least one column. So all rows are selected and all prime implements are essential implements for the boolean function. From third table, the boolean expression for the function can be derived as follow –

F (A, B, C, D) = AB’ + AC + B’C’D’ + A’BC’D

Now with the knowledge of K-map and Quine-McCluskey method, any boolean function with a given truth table can be easily minimized. In the next tutorial, learn about logic gate implementation of a minimized boolean expression.