A discussion of the solution for the best technique for Boolean function minimization

A discussion of the solution for the best technique for Boolean function minimization

R.Mohana Ranga Rao T. Santosh Kumar

Asstistant Professor Associate Professor

Department of ECE Department of ECE

MLRIT, Dundigal MLRIT, Dundigal

ABSTRACT:

In this paper a case study on Boolean function minimization techniques is discussed. The problem of Boolean function minimization may be old but in environments like PLA Design , design of control systems, or design of built – in self tests (BIST) equipment and also in software engineering

,artificial intelligence problems etc., it shows a significant affect. Obviously there is a necessity of discussing this Boolean functions as the size of the circuit, power and cost minimization, area optimization are the considerable factors while designing a Digital circuit. The main theme of any technique is to eliminate the redundant pairs which help in minimizing the size of the Boolean expression. In this Paper a comparison of different methods is mentioned based on their pros and cons. The techniques that are considered are Karnaugh [8] map (K-map), Quine [6]-McCluskey [1] (QM) and M-Term Based Boolean function minimization techniques.

Keywords: Boolean functions, minimization, K-Map, QM, M-Terms, Prime Implicants, literals

1. INTRODUCTION

   The digital gates (Logic gates) are basic electronic components of any digital circuit. A logic gate performs a logical operation based on one or more inputs and produces a single output voltage value (i.e. voltage levels high and low). Logically these voltage values can be referred to as 1s and 0s and are used in designing and analyzing the operations of logic gates. A logic gate represents a Boolean function. A Boolean function is an algebraic expression formed with Boolean variables (having values true or 1 and false or 0) and the logical operators (i.e. OR, AND, and NOT). These may be a large number of Boolean algebraic expressions that

   specify a given Boolean function. It is therefore important to find the simplest one.

   A Boolean function can be represented by a truth table. A truth table is a tabular arrangement of representing all the input-output relationships of a digital circuit. It displays all possible input values combinations with their respective output values. Normally a Boolean expression can be given using two forms: SOP and POS. SOP Boolean expressions may be generated from truth tables quite easily by forming an OR of the ANDs of all input variables (standard products or min terms) for which the output is 1. POS expressions are based on the 0s, in a truth table and generated oppositely as SOP by taking an AND of the ORs of all input variables (standard sums or max terms).

2. HISTORY

   The idea of Boolean function minimization is first introduced by an English mathematician and philosopher George Boole who invented the Boolean algebra in 1854 using which the minimization is done by minimizing the number of literals, later C.E. Shannon [7] showed how the Boolean algebra can be used in the design of digital circuits (Shannon [7], 1938).Digital gates are basic component of any digital circuit. Boolean logic is the basic concept that underlies all modern electronic digital computers. Using Boolean laws it is possible to minimize digital logic circuits by reducing the original number of digital components (gates) required to implement digital circuits. This will reduce the chip size, the cost and increases the speed of circuit. The laws proposed by Boole are neither systematic nor suitable for computer implementation, more over they consumes more time for the simplification. Later number of algorithms was introduced in order to overcome the implementation issue. Karnaugh [8] proposed a technique for

   simplifying Boolean expressions using an elegant visual technique, which is actually a modified truth table intended to allow minimal sum-of products (SOP) and product-of-sums (POS) expressions to be obtained (Karnaugh [8], 1953). The Karnaugh [8] Map (K-Map) based technique breaks down beyond six variables. Quine [6] and McCluskey [1] proposed an algorithmic based technique for simplifying Boolean logic functions (McCluskey [1]-1956, Quine [6]-1952).A novel technique [4] is proposed by R.Mohana ranga rao [4], in which minimization is done by using M-Terms to simplify a function using Decimal Values.

3. DEFINITIONS

1. Sum of products (SOP): This is the more common form of Boolean expressions. The expressions are implemented as AND gates (products) feeding a single OR gate (sum).

2. Product of sums(POS): This is less commonly used form of Boolean expressions. The expressions are implemented as OR gates (sums) feeding into a single AND gate (product).

3. Face value: List the powers of two from right to left. Start at 20; evaluate it as "1", 21 as 2 and 22 as 4, similarly Increment the exponent by one for each power. Stop when the amount of elements in the list is equal to the amount of digits in the binary number.

   The example number, 10011011, has eight digits, so the list, to eight elements, would look like this: 128, 64, 32, 16, 8, 4, 2, 1 these elements are called face values of corresponding elements of respective positions.

4. M-TERMS: M-terms are generated by addition/subtraction of corresponding min term with its face values. Based on the bit value i.e., Addition, if the Binary value is a 0, subtraction, if the Binary value is a 1.

   For example: 5 is the given min term

   Minterm Binary notation face value M-terms 5 0 1 0 1 8 4 2 1 13 1 7 4

5. MINTERM LIST:

   It is the set of minterm which can be combined.

   E.g. (1, 5) and (0, 1, 2, 3) are minterm list.

6. PRIME IMPLICANT

It is the minterm list which cannot be combined with any other minterm list.

1. Karnaugh-Map

   The idea behind a Karnaugh [8] Map (Karnaugh [8], 1953) is to draw an expressions truth table as a matrix in such a way that each row and each column of the matrix puts minterms that differ in the value of a single variable adjacent to each other. Then, by grouping adjacent cells of the matrix, you can identify product terms that eliminate all complemented literals, resulting in a minimized version of the expression.

   4.1 Advantages of K-Map

   It is a fast method for simplifying expression up to four variables it gives a visual method of logic simplification different possible combinations can be visually seen and the required ones selected fast.it is more suitable for classroom teachings on logic simplifications Prime implicants and essential prime implicants are identified fast this principle has been extended to the very large scale integration design by incorporating it in the pass transistor logic design method and it is suitable for both SOP and POS forms of reduction.

   K- maps are not suitable when the number of variables involved exceed four. It may be used with difficulty up to five and six variable systems. But , beyond 'Six Variables" k maps cannot be physically visualized.

   It is not suitable for Computer reduction, the important point is that the k-map simplification is manual technique and simplification process is heavily depends on the human abilities. Care must be taken to fill in every cell with the relevant entry, such a 0, 1 or don't care term. A cell left unfilled may be mistaken for a dont-care term entry, leading to erroneous results.

2. Quine -McCluskey Method (Tabular Method)

The Quine[6]-McCluskey [1] method is not dependent on the visual patterns as it becomes difficulty when the numbers of variables are more, thus Q-M particularly useful when Boolean functions having a large number of variables, e.g.for more than five-variable functions. The algorithm cant be done manually because of lengthy procedure, so Computer programs have been developed employing this algorithm by using different flat forms. The method reduces a function in standard sum of products form to a set of prime implicants from which as many variables are eliminated as possible. These prime implicants are then examined to see if some are redundant. Essential prime implicants, which are not evident in k map, can be clearly seen in the final results by using a prime implicant chart.

1. Cons:

   1. Lengthy procedure than k map required several groupings and steps as compared to the k map it is much slower

   2. No visual identification of reduction process

   3. The QM method is essentially A COMPUTER REDUCTION METHOD.

6. A NOVEL SIMPLIFICATION PROCEDURE M-TERM BASED SIMPLIFICATION

The main advantage of proposed method over the conventional methods is, the entire simplification is based on the decimal values (E.g. M-terms) which are well known to each and every designer, so in practice it is easy to implement this method to improve the performance.

The procedure for M-terms based simplification is presented using the proposed algorithm: [4]

1. Transform given Boolean unction into canonical SOP form and obtain binary notation for each minterm.

2. Now obtain the face values of all the given min terms. (Usually it would be same for all the min terms).

3. Calculate the M-terms for the given min terms.

4. Compare each M-term with provided input (min terms), to identify the adjacent terms. If a M- term is Equivalent to any min term of provided input then the min term and the M-term has to be grouped together to make a pair (prime implicant).While grouping the two terms follow ascending order.

5. Repeat the above step until it is impossible to compare the terms, and exclude all the repeated pairs.

6. Compare Prime implicants with each other such that the difference between the elements of a prime implicant should be same and it should be equal to the 2L , L=0,1,2..N. While comparing make sure that the comparison is done between like elements i.e. the first elements of two pairs and the second elements of two pairs has to be compared. Once there are any two terms that differ by 2L ,then group the two pairs as a single Quad. Now repeat the same procedure among all pairs.

7. Swap all the combined terms, and terms that were not combined at all and the prime implicants which are not a part of any single quad.

8. Now repeat the VI & VII steps to minimize the given Boolean function/min terms until it is impossible to combine the terms.

9. Now eliminate the redundant prime implicants by using Prime implicant chart as in Quine [6]-McCluskey [1] method.

   1. CONCLUSION

      In this paper the comparisons among the three methods are carried out and the conclusion obtained that novel method, M-Term based minimization can with stand even with the major cons of Karnaugh [8] map and Quine [6]-McCluskey

      [1] as it is simple, faster and possible to reduce the number of required comparisons. The new method can be used even when the numbers of variables are more. Based on the table 1 results [9] one can surely consider the M-Term method for Boolean function

      simplification. One more reason to go for this technique is computer reduction is possible.

      TABLE- 1 [9]

      No. of Variable (n)	Total Comparisons in worst case
      	QM Method	MQM Method
      2	4	4
      3	15	12
      4	56	32
      5	210	80
      6	792	192
      7	3003	448
      8	11440	1024

   2. REFERENCES

1. McCluskey E.J., minimization of Boolean function, Bell system Tech. Journal, vol.35, No.5, pp. 1417-1444, 1956.

2. SP Tomaszeweski , WWW Based Boolean function minimization, International journal of applied mathematics and computer sciences, vol. 13,No. 1,pp. 577-583, 2003.

3. Jain T.K., Kushwaha D.S., Misra A.K., Optimization of the Quine [6]-McCluskey Method for the Minimization of the Boolean Expressions, International Conference on Autonomic and Autonomous Systems, (ICAS) , 2008.

4. R. Mohan Ranga Rao ,An Innovative procedure to minimize Boolean function , International Journal of Advanced Engineering Sciences and Technologies (IJAEST), vol.3 , issue No. 1 , pp. 012-014,2011.

5. Arunachalam Solairaju, Rajupillai Periyasamy, Optimal Boolean Function Simplification through K-Map using Object-Oriented Algorithm, International Journal of Computer Applications (IJCA), Vol.15,issue No.7,pp. 28-32, February 2011.

6. Quine W.V.(1952): The problem of simplifying truthtables-

   .Amer.Math.Month.,Vol.59,No.8,pp.521531.

7. Shannon C.E.(1938): symbolic analysis of relay and switchingcircuits. Trans.AIEE, Vol.57,No.6,pp.713723.

8. Karnaugh M.(1953):The map method for synthesis of combinatorial logic circuits.Trans.AIEEComm.Electron.,Vol.72, No.4, pp.593598.

9. Jadhav, Vitthal, and Amar Buchade. "Modified Quine -McCluskey Method." arXiv preprint arXiv:1203.2289 (2012).