What is The Advantage Of Boolean Algebraic Simplification Technique

Digital electronics deals with the discrete-valued digital signals. In general, any electronic system based on the digital logic uses binary notation (zeros and ones) to represent the states of the variables involved in it. Thus, Boolean algebraic simplification is an integral part of the design and analysis of a digital electronic system.

Although Boolean algebraic laws and DeMorgan’s theorems can be used to achieve the objective, the process becomes tedious and error-prone as the number of variables involved increases. This necessitates the use of a suitable, relatively-simple simplification technique like that of Karnaugh map (K-map), introduced by Maurice Karnaugh in 1953.

A Typical K-Map

The K-map method of solving the logical expressions is referred to as the graphical technique of simplifying Boolean expressions. K-maps are also referred to as 2D truth tables as each K-map is nothing but a different format of representing the values present in a one-dimensional truth table.

K-maps basically deal with the technique of inserting the values of the output variable in cells within a rectangle or square grid according to a definite pattern. The number of cells in the K-map is determined by the number of input variables and is mathematically expressed as two raised to the power of the number of input variables, i.e., 2n, where the number of input variables is n.

Thus, to simplify a logical expression with two inputs, we require a K-map with 4 (=22) cells. A four-input logical expression would lead to a 16 (=24) celled-K-map, and so on.

Gray Coding

Further, each cell within a K-map has a definite place-value which is obtained by using an encoding technique known as Gray code.

The specialty of this code is the fact that the adjacent code values differ only by a single bit. That is, if the given code-word is 01, then the previous and the next code-words can be 11 or 00, in any order, but cannot be 10 in any case.

In K-maps, the rows and the columns of the table use Gray code-labeling which in turn represent the values of the corresponding input variables. This means that each K-map cell can be addressed using a unique Gray Code-Word.

These concepts are further emphasized by a typical 16-celled K-map shown in Figure 1, which can be used to simplify a logical expression comprising of 4-variables (A, B, C and D mentioned at its top-left corner).

Here the rows and the columns of the K-map are labeled using 2-bit Gray code, shown in the figure, which assigns a definite address for each of its cells.

For example, the grey colored cell of the K-map shown can be addressed using the code-word “0101” which is equivalent to 5 in decimal (shown as the green number in the figure) and corresponds to the input variable combination A̅BC̅D or A+B̅+C+D̅, depending on whether the input–output relationship is expressed in SOP (sum of products) form or POS (product of sums) form, respectively.

Similarly, AB̅CD or A̅+B+C̅+D̅ refers to the Gray code-word of “1011”, equivalent to 11 in decimal (again, shown in green in the figure), which in turn means that we are addressing the pink-colored K-map cell in the figure.

K-Map Simplification Technique

With this general idea of K-maps, let us now move on to the procedure employed in designing an optimal (in terms of the number of gates used to realize the logic) digital system. We’ll start with a given problem statement.

Example 1:

Design a digital system whose output is defined as logically low if the 4-bit input binary number is a multiple of 3; otherwise, the output will be logically high. The output is defined if and only if the input binary number is greater than 2.

Step 1: Truth Table / Canonical Expression Leading to Min- or Max-Terms

The first step in designing any digital system is to have a clear idea of the variables involved in the process, along with their state-values. Further, depending on the problem statement, we have to arrive at the number of output variables and their values for each and every combination of the input literals, which can be conveniently represented in the form of a truth table.

In the given example:

Number of input variables = 4, which we will call A, B, C and D.

Number of output variables = 1, which we will call Y

where

         Y = Don’t Care, if the input number is less than 3 (orange entries in the truth table)

         Y = 0, if the input number is an integral multiple of 3 (green entries in the truth table)

         Y = 1, if the input number is not an integral multiple of 3 (blue entries in the truth table)

Note that, in addition to the input and output columns, the truth table also has a column which gives the decimal equivalent of the input binary combination, which makes it easy for us to arrive at the minterm or maxterm expansion for the given problem. Thus for the given example,

Minterm expansion will be  ∑m(4,5,7,8,10,11,13,14) + ∑d (0,1,2)

Maxterm expansion will be ∏M(3,6,9,12,15) · ∏D (0,1,2)

However, sometimes the logical expression which is to be simplified might be directly given in terms of SOP or POS forms. In this case, the requirement for the truth table can be overlooked provided that we express the given expression in its canonical form, from which the corresponding minterms or maxterms can be obtained.

Step 2: Select and Populate K-Map

From Step 1, we know the number of input variables involved in the logical expression from which size of the K-map required will be decided. Further, we also know the number of such K-maps required to design the desired system as the number of output variables would also be known definitely. This means that, for the example considered, we require a single (due to one output variable) K-map with 16 cells (as there are four input variables).

Next, we have to fill the K-map cells with one for each minterm, zero for each maxterm, and X for Don’t Care terms. The procedure is to be repeated for every single output variable. Hence for this example, we get the K-map as shown in Figure 2.