Functional Application and Minimization of Booleanfunction Using Gates, K-Map & Quine-Mccluskey
In:
Submitted By ashoky Words 7048 Pages 29
Vol 3 Issue 2 March 2013 Impact Factor : 0.2105
ORIGINAL ARTICLE
ISSN No : 2230-7850
Monthly Multidisciplinary Research Journal
Indian Streams Research Journal
Executive Editor Ashok Yakkaldevi
Editor-in-chief H.N.Jagtap
IMPACT FACTOR : 0.2105 Welcome to ISRJ RNI MAHMUL/2011/38595 ISSN No.2230-7850 Indian Streams Research Journal is a multidisciplinary research journal, published monthly in English, Hindi & Marathi Language. All research papers submitted to the journal will be double - blind peer reviewed referred by members of the editorial Board readers will include investigator in universities, research institutes government and industry with research interest in the general subjects.
International Advisory Board
Flávio de São Pedro Filho Federal University of Rondonia, Brazil Hasan Baktir Mohammad Hailat English Language and Literature Dept. of Mathmatical Sciences, University of South Carolina Aiken, Aiken SC Department, Kayseri Kamani Perera 29801 Regional Centre For Strategic Studies, Sri Ghayoor Abbas Chotana Lanka Department of Chemistry, Lahore Abdullah Sabbagh University of Management Sciences [ PK Engineering Studies, Sydney Janaki Sinnasamy ] Librarian, University of Malaya [ Anna Maria Constantinovici Catalina Neculai Malaysia ] AL. I. Cuza University, Romania University of Coventry, UK Romona Mihaila Spiru Haret University, Romania Delia Serbescu Spiru Haret University, Bucharest, Romania Anurag Misra DBS College, Kanpur Titus Pop Ecaterina Patrascu Spiru Haret University, Bucharest Loredana Bosca Spiru Haret University, Romania Fabricio Moraes de Almeida Federal University of Rondonia, Brazil George - Calin SERITAN Postdoctoral Researcher Horia Patrascu Spiru Haret University, Bucharest, Romania Ilie Pintea, Spiru Haret University, Romania Xiaohua Yang PhD, USA Nawab Ali Khan College of Business Administration
Editorial Board
Iresh Swami Pratap Vyamktrao Naikwade ASP College Devrukh,Ratnagiri,MS India Ex - VC. Solapur University, Solapur R. R. Patil Head Geology Department Solapur University, Solapur Rama Bhosale Prin. and Jt. Director Higher Education, Panvel Salve R. N. Department of Sociology, Shivaji University, Kolhapur Govind P. Shinde Bharati Vidyapeeth School of Distance Education Center, Navi Mumbai Chakane Sanjay Dnyaneshwar Arts, Science & Commerce College, Indapur, Pune N.S. Dhaygude Ex. Prin. Dayanand College, Solapur Narendra Kadu Jt. Director Higher Education, Pune K. M. Bhandarkar Praful Patel College of Education, Gondia Sonal Singh Vikram University, Ujjain Rajendra Shendge Director, B.C.U.D. Solapur University, Solapur R. R. Yalikar Director Managment Institute, Solapur Umesh Rajderkar Head Humanities & Social Science YCMOU, Nashik S. R. Pandya Head Education Dept. Mumbai University, Mumbai
Alka Darshan Shrivastava G. P. Patankar S. D. M. Degree College, Honavar, Karnataka Shaskiya Snatkottar Mahavidyalaya, Dhar Maj. S. Bakhtiar Choudhary Director,Hyderabad AP India. S.Parvathi Devi Ph.D.-University of Allahabad Rahul Shriram Sudke Devi Ahilya Vishwavidyalaya, Indore S.KANNAN Ph.D , Annamalai University,TN Satish Kumar Kalhotra
Awadhesh Kumar Shirotriya Secretary, Play India Play (Trust),Meerut Sonal Singh
Address:-Ashok Yakkaldevi 258/34, Raviwar Peth, Solapur - 413 005 Maharashtra, India Cell : 9595 359 435, Ph No: 02172372010 Email: ayisrj@yahoo.in Website: www.isrj.net
Indian Streams Research Journal
Volume 3, Issue. 2, March. 2013
ISSN:-2230-7850 ORIGINAL ARTICLE
Available online at www.isrj.net
FUNCTIONAL APPLICATION AND MINIMIZATION OF BOOLEANFUNCTION USING GATES,K-MAP & QUINE-MCCLUSKEY
BALACHANDRA PATTANAIK AND D.RANGANAYAKULU Research Schoolar ,Manonmanian Sundarnar University, Thirunelveli . Assoc. Professor of Mathematics,S.I.V.E.T,Gowrivakkam,Chennai.
Abstract: Minimization of Boolean Functions is one with an algorithm to estimation and implementation of a Boolean function using a gate is an important activity in designing the digital circuits. This minimization reduces the size and cost of these systems and the performance can be improved. There are some well established methods for doing these simplifications. In the present work an object-oriented algorithm is proposed for simplification of Boolean function through different method with examples. Also this proposed object oriented model can be implemented for more than 64 variables. The main objective of this process is to keep the number of digital gates as minimum as possible and this reduces the cost of the circuit design. KEY WORDS: Digital logic, Boolean functions, SOP, Java. 1.INTRODUCTION In 1854, George Boole introduced a systematic treatment of logic and developed for this purpose an algebraic system now called Boolean algebra called switching algebra. Boolean algebra is a system of mathematical logic. It differs from both ordinary algebra and the binary number system. The symbol which represents arbitrary elements of a Boolean algebra is known as Variable. Simplification of Boolean expressions by Boolean algebra we need better understanding of Boolean laws, rules and theorems. During the process of simplification we have to predict each successive step. For these reasons, we can never be absolutely certain that an expression simplified by Boolean algebra alone is the simplest possible expression. On the other hand, the map method gives us a systematic approach for simplifying a Boolean expression. NAND's and NOR's are the most common basic logic circuit element in use because they are simpler to built than AND and OR gates, and because each is logically complete. Many logical functions are expressed using AND's, OR's, and Inverters (NOT). The map method, first proposed by Veitch and modified by Karnaugh, hence it is known as the Veitch diagram or the Karnaugh map. The digital circuits can be represented and analyzed using the Boolean functions. K-map in fact a visual diagram of representing all possible ways a Boolean function may be expressed. Logic minimization uses a variety of techniques to obtain the simplest gate-level implementation of a logic function. The heart of digital logic design is the Boolean algebra (Boole, 1954). A few decades later C.E.Shannon showed how the Boolean algebra can be used in the design of digital circuits (Shannon,
Title : FUNCTIONAL APPLICATION AND MINIMIZATION OF BOOLEANFUNCTION USING GATES,K-MAP & QUINE-MCCLUSKEY Source:Indian Streams Research Journal [2230-7850] BALACHANDRA PATTANAIK AND D.RANGANAYAKULU yr:2013 vol:3 iss:2
FUNCTIONAL APPLICATION AND MINIMIZATION OF BOOLEANFUNCTION..........
1938). Using Boolean laws it is possible to minimize digital logic circuits (Huntington, 1904). Since minimization with the use of Boolean laws is neither systematic nor suitable for computer implementation, a number of algorithms were proposed in order to overcome the implementation issue. Karnaugh 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, 1953). The Karnaugh Map (K-Map) based technique breaks down beyond six variables. The Quine-McCluskey (M Q) method is a computer-based technique for simplification and The modified Quine-McCluskey (M Q-M) method is a very simple and systematic technique for minimizing Boolean functions. Why do we want to minimize a Boolean expression? By simplifying the logic function we can reduce the original number of digital components (gates) required to implement digital circuits. Therefore by reducing the number of gates, the chip size and the cost will be reduced, and the speed will be increased. 2. RELATED WORK 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: A. 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). B. 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). 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 minterms) 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 maxterms). The Unified Modeling Language (UML) was created as a result of unification of different Objectoriented design methodologies. The Object-oriented design using UML diagrams in hardware system modeling and designing have been proposed in some research papers, but there is very less work available on the applications of UML in digital logic minimization. The use of UML in real-time and embedded systems specification and design has been explored by Gomaa [1] ,Schattkowsky [2] and Saxena et al. [3] proposed the UML model for the Multiplex system for the processes which are executing in distributed environment. Al-Rababah [4] introduced a novel approach for the synthesis of reconfigurable hardware from UML modles. The presented approach enables the synthesis of Object oriented specifications into hardware circuits. Zhenxin, wong,zhu, yongxin et al. [5] suggested a new approach for modeling of Boolean and design of clocked circuits using UML. Recently Dr.Vipin Saxene [6] A performance estimation of karnaugh map through UML notations. The UML class, State chart and Component diagrams are used to model system specifications. 3. THE KARNAUGH MAP The simplification or minimization of any digital circuit is an important activity in digital circuit design. To simplify the circuit, the designer tries of find another circuit that produces the same output as the original bone but with less number of gates. The main objective of this process is to keep the number of digital gates as minimum as possible and thus get a minimal cost solution. There are various methods of simplification such as Boolean algebra, Karnaugh maps, Tabulation method, Computer Aided Design etc. All these methods use the simplification of Boolean unction that represents the digital logic[7][8].
Indian Streams Research Journal • Volume 3 Issue 2 • March 2013
2
FUNCTIONAL APPLICATION AND MINIMIZATION OF BOOLEANFUNCTION..........
Maurice Karnaugh developed the Karnaugh map in 1953 during designing of digital circuits for telephone switching circuits. This technique is quite easy and fast in comparison with Boolean algebra. Karnaugh maps work well for up to six input variables. A Karnaugh map consists of any arrays of rectangles or boxes arranged in rows and columns. The size of the Karnaugh map with n Boolean variables is equal to 2n. The size for maps of 2 variables is a 2x2 map (four boxes), for 3 variables it is a 2x4 map, and for 4 variables it is a 4x4 map and so on. The Boolean variables are arranged in an order according to the principles of gray code where only one variable changes in adjacent squares. Each square represents a minterm (sometimes a maxterm) corresponding to the truth table. A minterm is a Boolean expression consisting of a product term of those variables (or their complimented form). The minterms are identified by associating numbers to them like m0, m1, mn etc. For simplifying an input expression, the adjacent minterms are identified and a group of 2 (Pair), 4 (Quad) or 8 (Octet) adjacent minterms are formed. The minterms can only form a group if they are adjacent horizontally and vertically and not diagonally. The groups should be as large as possible and overlapping of any minterm on two or more groups is allowed. Similarly the wrap around of minterms is also allowed for forming a group. If a term and its compliment both appear in a group, delete both from the resultant product term. Finally the Boolean expression of the remaining terms can be obtained. 4. MODIFIED QUINE-MCCLUSKEY ALGORITHM Quine and McCluskey proposed an algorithmicbased technique for simplifying Boolean logic functions (McCluskey, 1956; Quine, 1952). The Quine-McCluskey (Q-M) method is a computer-based technique for simpli- fication and has mainly two advantages over the K-Map method. Firstly, it is systematic for producing a minimal function that is less dependent on visual patterns. Secondly, it is a viable scheme for handling a large number of variables. A number of methods have been developed that can generate optimal solutions directly at the expense of additional computation time. Another algorithm was reported by Petrick (1959). This algorithm uses an algebraic approach to generate all possible covers of a function[9]. A popular tool for simplifying Boolean expressions is the Espresso, but it is not guaranteed to find the best two-level expression (Katz, 1994). In this paper an Internet based implementation is proposed for simplifying two to four-variable Boolean functions, using a Modified Quine-McCluskey (M Q-M) method. The MQ-M technique is implemented as an applet in Java, and can be accessed on line, up to four variables, since it is posted on the World Wide Web. Due to the algorithmic nature of the technique, the proposed method and its implementation can easily be expanded to cover more than sixty four variables [10]. The main difference between the proposed algorithm and the Q-M method starts when the Q-M method groups the elements according to the number of ones in each element, but in the proposed algorithm grouping is not required. In the following steps the MQ-M follows Q-M up to the first step of the prime implicant table, which is identifying the essential prime implicants. For the next step, the Q-M uses several different techniques to eliminate the implicants efficiently. The M Q-M method simulates the elimination process of minterms and finally, when the most efficient combination is reached, it is taken out from the table. One of the example is shown below,The application of a mathematical system from the basic assumption from which it is possible to deduce the thermos, laws and properties of the system. Boolean algebra is formulated by a defined set of elements, together with two binary operators,+ and . , provided that the following function are satisfied [11]. CLOSURE (a): closure with respect to the operator + when two binary elements are operated by operator + the result is a unique binary element. CLOSURE (b): closure with respect to the operator. (Dot).When two binary elements are operated by operator.(dot),the result is unique binary elements. An identity element with respect with respect to +, designated by 0: A+0=0+A=A Commutative with respect to +: A+B = B+A Commutative with respect to: A.B = B.A Distributive property of over +: A. (B+C) = (A.B) + (A.C) Distributive property of + over A + (B.C) = (A+B).(A+C)
Indian Streams Research Journal • Volume 3 Issue 2 • March 2013
3
FUNCTIONAL APPLICATION AND MINIMIZATION OF BOOLEANFUNCTION..........
For every binary element, there exists complement element. For example, if A is an element, we have  is a complement of A. If A = 0, A' = 1 and if A = 1, A' = 0 There exists at least two element, say A and B in the set of binary element such that A•‚ B. 5.1 POSTULATES OF BOOLEAN ALGEBRA:
No. 1
FUNCTION Result of each operation is either 0 or 1 a) 0+0=0 b) 1.1=1 0+1 =1+0=1 1.0=0 =0
COMMENT 1, 0 å B
2
Identify elements 0 for + and 1 for.
3
a) (A+B) =(B+A) b) b) (A.B) = (B.A)
Commutative Law
4
a) A.(B+C) = (A.B) + (A.C) b) A+ (B.C) = (A+B). (A+C)
Distributive law
5
a) A+A’ = 1 since 0 +0’ =0 + 1 =1 and 1 + 1’ = 1 + 0 = 1 b) A. A’ = 0 since 0. 0’ = 0.1 = 0 and 1.1’ = 1.0 = 0
Complement
Table No.1. Postulates of Boolean algebra 5.2 Laws of Boolean algebra: Three of the basic laws of Boolean algebra are the same as the algebra is the same as in ordinary algebra. The commutative laws, associative laws, and distributive laws. Commutative laws: Law 1 : A + B = B +A this states that the order in which the variables are OR ed makes no difference in the
Indian Streams Research Journal • Volume 3 Issue 2 • March 2013
4
FUNCTIONAL APPLICATION AND MINIMIZATION OF BOOLEANFUNCTION..........
output. The truth table are identical. Therefore, A OR B is same as B OR
A 0 0 1 1
B 0 1 0 1
A +B 0 1 1 1
B 0 0 1 1
A 0 1 0 1
B +A 0 1 1 1
Table No.2. LAW 2 : AB = BA the commutative law of multiplication states that the order in which the variable makes no difference in the input. The truth table are identical. Therefore A AND B is same as B AND A.
A 0 0 1 1
B 0 1 0 1
AB 0 0 0 1
Table No.3
B 0 0 1 1
A 0 1 0 1
BA 0 0 0 1
It is important to that the commutative laws can be extended to any number of the variables. For example since A+B = B+A it follows that A+ B +C =B+ A+ C and since A + C =C +A it is true that B + A +C = B+ C + A. similarly A =BACD = BADC = ABDC and so on. ASSOCIATIVE LAWS: LAW 1 : A+ (B+C) = (A+B) + C this law sates that in the OR ing of several variables the result is the same regardless of the grouping of the variables for three variables A OR B OR ed with C is the same as A OR ed with B OR C.
A B C A+B (A+B)+C
0 0 0 0 1 1 1 1
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1
0 0 1 1 1 1 1 1
0 1 1 1 1 1 1 1
Table No.4
Indian Streams Research Journal • Volume 3 Issue 2 • March 2013
5
FUNCTIONAL APPLICATION AND MINIMIZATION OF BOOLEANFUNCTION..........
A
B
C
B+C
A+(B+C)
0 0 0 0 1 1 1 1
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1
0 1 1 1 0 1 1 1
0 1 1 1 1 1 1 1
Table No.5 LAWS 2 ( AB) C = A (BC): The associative law of multiplication states that it makes no difference in what order the variables are grouping when AND ing several variables. For three variables A AND B AND ed with C is the same as A AND ed with B and C.
A
B
C
AB
(AB) C
0 0 0 0 1 1 1 1
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1
Table No.6
0 0 0 0 0 0 1 1
0 0 0 0 0 0 0 1
A
B
C
BC
A(BC)
0 0 0 0 1 1 1 1
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1
0 0 0 1 0 0 0 1
0 0 0 0 0 0 0 1
Table No.7
Indian Streams Research Journal • Volume 3 Issue 2 • March 2013
6
FUNCTIONAL APPLICATION AND MINIMIZATION OF BOOLEANFUNCTION..........
DISTRIBUTIVE LAW. A (B+C) = AB + AC The distributive law states that OR ing several variables and AND the result with single variable is equivalent to AND ing the result with a single variable with each of the several variables and then OR ing particulars
A 0 0 0 0 1 1 1 1
B 0 0 1 1 0 0 1 1
C 0 1 0 1 0 1 0 1
(B+C) 0 1 1 1 0 1 1 1
A(B+C) 0 0 0 0 0 1 1 1
Table No.8
A 0 0 0 0 1 1 1 1
B 0 0 1 1 0 0 1 1
C 0 1 0 1 0 1 0 1
AB 0 0 0 0 0 0 1 1
AC 0 0 0 0 0 1 0 1
AB+AC 0 0 0 0 0 1 1 1
Table No.9 Its important to note that the distributive property is often used in reverse given AB + AC we replace it by its equivalent A(B+C) as in ordinary algebra this process is called factoring. We factored A out of the expression AB + AC. 2.4 BASIC THOREMS AND PROPERTIES: DUALITY: The principle of duality thermos says that starting with a Boolean relation you can derive another Boolean relation by 1. Changing each OR sign to an AND sign 2. Changing each AND sign to an OR sign and 3. Complementing any 0 or 1 appearing in the expression. FOR example dual of relation A+A' =1 is A. A'= 0 Duality is a very important property of Boolean algebra. We can define the following using fundamental postulates of Boolean algebra.
Indian Streams Research Journal • Volume 3 Issue 2 • March 2013
7
FUNCTIONAL APPLICATION AND MINIMIZATION OF BOOLEANFUNCTION..........
= A = 0 = 1 = (A+A).1 A + A ).(A + Â) A+AÂ A+0 A = A = 0 = 1 = A .A + 0 AA + A Â A (A+ Â) A .1 A 1 = 1 = 1
Proof;
THEORM 2 ;
Proof:
THEROM 3;
A + 1= 1+ 0 1+ 1 A+1 =
Proof; 1. (A + 1) = (A+ Â) (A + 1) = A + Â .1 = A+Â = 1 = A
THEROM 4; A + AB Proof; A+AB =
= A. 1 + AB A (1+B) = A.1 = A = AB = = = = =
THEROM 5; A. (Â+B)
(A + AB). (Â+B) A Â+AB+ABB AB+ABB AB+AB AB
The five basic thermos of Boolean algebra four of its postulates the postulates and theorems are listed in pairs and designed by part may be obtained from the other by using principle of duality. 2.5 DEMORGAN'S THEROM; (1) (AB)' = A'+ B' The complement of a product is equal to the sum of the complements.
A 0 0 1 1 B 0 1 0 1 (AB)’ 1 1 1 0 A’+B’ 1 1 1 0
Table No.10
Indian Streams Research Journal • Volume 3 Issue 2 • March 2013
8
FUNCTIONAL APPLICATION AND MINIMIZATION OF BOOLEANFUNCTION..........
2) (A+B)' = A'B’
A 0 0 1 1
B 0 1 0 1
Table. 11
(A+B)’ 1 0 0 0
A’ B’ 1 0 0 0
2.3 .CONSESUS THEROM; In simplification of Boolean expression an expression of the form AB+ A'C+BC = AB + A'C The term BC is redundant and can be eliminated to form the equivalent expression AB + A' C the theorem is used for the simplification known as consensus thermos and It is stated as Example: AB+ A'C + BC = AB + A'C Proof: AB+ A'C +BC = AB + A'C+ (A+A') BC = AB + A' C+AB+ A' C = AB + A'C. Step 7: Y'= (B'C' +BC + A'C)' = (B'C')' (BC)' (A'C)' = (B” + C”) (B' + C') (A” + C') = (B + C) (B' + C') (A + C') It is possible to directly write the expression for Y by using De Morgan's theorem for each minters as follows: Y' = B'C' + BC +A'C Y= (B + C) (B' + C') (A + C') 3.7 Don't Care Conditions: In some logic circuits, certain input conditions never occur, therefore the corresponding outputs never appears. In such cases the output level is not defined, it can be either HIGH or LOW. These output levels are indicated by 'X' or 'd' in the truth table 3.1 and are called don't care outputs or don't care conditions or incompletely specified functions. Let us see the output levels in the truth table as shown in table 2.14. Here outputs are defined for input conditions from 0 0 0 to 1 0 1. For remaining two conditions of input, output is not defined, A circuit designer is free to make the output for any “don't care” condition either a '0' or a '1' in order to produce the simplest output expression. 3.8 Describing Incomplete Boolean Function We describe the Boolean function using either a minterm canonical formula or a maxterm canonical formula. In order to obtain similar –type expressions for incomplete Boolean functions we use additional term to specify don't care conditions in the original expression. This illustrated in the following examples. In expression, f (A, B, C) = M (0, 2, 4) + d (1,5) minterms are 0, 2and 4. The additional term d(1,5) is introduced to specify the don't care conditions. This term specifies that outputs for minterms 1 and 5 are not specified and hence these are don't
Indian Streams Research Journal • Volume 3 Issue 2 • March 2013
9
FUNCTIONAL APPLICATION AND MINIMIZATION OF BOOLEANFUNCTION..........
care conditions. Letter d is used to indicate don't care conditions in the expression. The above expression indicates how to represent don't care conditions in the minterm canonical formula. For example, f (A, B, C) = M (2, 5, 7) + d (1,3) 3.9 Don't Care Conditions in Logic Design In this section, we see the example of incompletely specified Boolean function. Let us see the logic circuit for an even parity generator for 4-bit BCD number. The Table 12 shows the truth table for evenparity generator. The truth table shows that the output for last six input conditions cannot be specified, because such input condition does not occur when input is in the BCD form.
A 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 B 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 C 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 1 0 1 0 1 0 1 D 0 1 0 1 0 1 0 P 0 1 1 0 1 0 0 1 1 0 -
Table 12 Truth table for even parity generator with 4-bit BCD input. The Boolean function for even parity generator with 4-bit BCD input can be expressed in minterm canonical formula as 3.5 Grouping cells for simplification In the last section we have seen representation of Boolean function on the karnaugh map. We have also seen that minterms are marked by 1 st and maxterms are marked by 0s. Once the Boolean function is ploote on the karnaugh map we have to use grouping technique to simplify the Boolean function. The grouping is nothing but combining terms in adjacent cells. Two cells are said to be adjacent if they conform the single change rule. The simplification is achieved by grouping adjacent 1s or 0s in grouping of 2 i where i= 1, 2….n and n is the number of variables. When adjacent 1s or 0s in we get result in the sum of products from otherwise we get result in the product of sums from let us see the various grouping rules. Simplification of product of sums expression; In the above discussion we have considered the Boolean expression in sum of products from and grouped 2, 4, and 8 adjacent ones to get the simplified Boolean expression in the in the same form in
Indian Streams Research Journal • Volume 3 Issue 2 • March 2013
10
FUNCTIONAL APPLICATION AND MINIMIZATION OF BOOLEANFUNCTION..........
practice the designer should examine both the sum of products and product of sums reduction to assertion which is more simplified we have already seen the representation of products of sums on the k amp once the expression is plotted on k map once the expression is plotted on the k map of zero each of zero result a sum term and it is nothing but the prime implicate[14][15].The technique for using maps for POS reduction is simple step by step process and it is similar to the one used earlier. 1.Plot the ka map and place 0s in those cells corresponding to the 0s in the truth table or maxterm in the products of sum expression. 2.check the k map for adjacent 0 s and encircle 0s which are not adjacent to any other 0s these are called isolated 0s 3.Check for those 0s which are adjacent 0s to only other 0 and encircle such pairs. 4.Check for quad and octets of adjacent 0s even if it contains some 0s that have already been encircled while doing this make sure there are minimum number of groups. 5.Combine any pairs necessary to include any 0s that have not yet been grouped. 6.Form the simplified SOP expression for F by summing product terms of all the groups. 7.Use DeMorgan's theorem on F to produce the simplified expression in POS form. To get familiar with these steps we will solve some examples. Example 2.21: Minimize the expression Y = ( A + B + C') (A + B' + C') ( A” + B” + C') ( A' + B + C) (A+B+C) Solution : ( A + B + C') = M1, ( A + B' + C') = M3 ( A' + B' + C') =M7 ( A' + B + C) =M4 , ( A + B + C) =M0 Step 1: Fig. 3.9 (a) shows the K-map for three variables and it is plotted according to given maxterms.
BC
B’C’ 00
B’C 01
BC 11
BC’ 10
A’ 0 A1
Step 2: There are no isolated 0s.
0 0
0
0 0
Table. 13
Step 3: 0 in the cell 4 is adjacent only to 0 in the cell 0 and 0 in the cell 7 is adjacent only to 0 in the cell 3. These two pairs are combined and referred to as group 1 and group 2 respectively. Step 4: There are no quads and octets.
BC
B’C’ 00
0
B’C 01
0
BC 11
0
BC’ 10
A’ 0 A1
0 0 0
0
0 0
Fig.1
Indian Streams Research Journal • Volume 3 Issue 2 • March 2013
11
FUNCTIONAL APPLICATION AND MINIMIZATION OF BOOLEANFUNCTION..........
Step 5: The 0 in the cell 1 can be combined with 0 in the cell 3 to form a pair. This pair is referred to as group 3. Step 6: In group 1 and in group 2, A is eliminated, where as in group 3 variable B is eliminated and we get Y = BC +BC + AC
BC
B’C’ 00
B’C 01
BC 11
BC’ 10
00
A’ 0 0 A1 00
00 0
A’C
0
0 0
BC
B’C’
Fig.2
Step 7: Y'= {(B'C' +BC + A'C)}’ = (B'C')' (BC)' (A'C)' = (B” + C”) (B' + C') (A” + C') = (B + C) (B' + C') (A + C') It is possible to directly write the expression for Y by using De Morgan's theorem for each minterm as follows: Y' = B'C' + BC +A'C Y= (B + C) (B' + C') (A + C') 3.7 Don't Care Conditions: In some logic circuits, certain input conditions never occur, therefore the corresponding outputs never appears. In such cases the output level is not defined, it can be either HIGH or LOW. These output levels are indicated by 'X' or'd' in the truth table 3.1 and are called don't care outputs or don't care conditions or incompletely specified functions. Let us see the output levels in the truth table as shown in table 2.14. Here outputs are defined for input conditions from 0 0 0 to 1 0 1. For remaining two conditions of input, output is not defined, hence these are called don't care conditions for this truth table 3.1.
A 0 0 0 0 1 1 1 1 B 0 0 1 1 0 0 1 1 C 0 1 0 1 0 1 0 1 Y 0 1 0 1 0 1 X X
Table.14
Indian Streams Research Journal • Volume 3 Issue 2 • March 2013
12
FUNCTIONAL APPLICATION AND MINIMIZATION OF BOOLEANFUNCTION..........
A circuit designer is free to make the output for any “don't care” condition either a '0' or a '1' in order to produce the simplest output expression. 3.8 Describing Incomplete Boolean Function We describe the Boolean function using either a minterm canonical formula or a maxterm canonical formula. In order to obtain similar –type expressions for incomplete Boolean functions we use additional term to specify don't care conditions in the original expression. This illustrated in the following examples. In expression, f (A, B, C) = M (0, 2, 4) + d (1,5) Minterms are 0, 2and 4. The additional term d (1, 5) is introduced to specify the don't care conditions. These terms specifies that outputs for minterms 1 and 5 are not specified and hence these are don't care conditions. Letter d is used to indicate don't care conditions in the expression. The above expression indicates how to represent don't care conditions in the minterm canonical formula. For example, f (A, B, C) = M (2, 5, 7) + d (1,3) 3.9 Don't Care Conditions in Logic Design In this section, we see the example of incompletely specified Boolean function. Let us see the logic circuit for an even parity generator for 4-bit BCD number. The Table 3.2 shows the truth table for even-parity generator. The truth table shows that the output for last six input conditions cannot be specified, because such input conditions does not occur when input is in the BCD form.
A 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 B 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 C 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 1 0 1 0 1 0 1 D 0 1 0 1 0 1 0 P 0 1 1 0 1 0 0 1 1 0 -
Table.15
Indian Streams Research Journal • Volume 3 Issue 2 • March 2013
13
FUNCTIONAL APPLICATION AND MINIMIZATION OF BOOLEANFUNCTION..........
The algorithm was first implemented using simple Java. Then it was converted into the object oriented language. Simplified expression only will be obtained in sum of product form. It can applicable for any number of variables. It is suitable for machine computation. Prime implicant is a simplied term obtained[12][13]. To obtain the prime implicant the number of minterms should be grouped. Essential prime implicant is the prime implicant which is essential to express the function. The following flow chart is implemented as follows. The detailed is also discussed. D. Implementation: Detailed description for the flowchart with coding implementation. (a) Class1: QMacTable (b) Class Variables: int primtImplicant Table Number; String group Of Minterms; String group Of Minterms Expression; int number Of Ones;boolean minterm Group Selected; (c) Member Functions: QMacTable (); String get Group Of Minterms(); void set Group Of Minterms(String group Of Minterms); String get Group Of Minterms Expression(); void set Group Of Minterms Expression(String group Of Minterms Expression); int get Number Of Ones(); void set Number Of Ones(int number Of Ones); int get PrimtImplicant Table Number(); void set PrimtImplicant TableNumber (int PI Table Number); boolean isMinterm Group Selected(); void set Minterm Group Selected(Boolean selected); (d) Class2: QMacm PrimeImplicant Table Generation (e) Class Variables: String mintermsStr; int no Of Variables; Linked List qMacLL; Linked List qMacNewLL; (f) Member Functions: boolean is Existing Min Group(Linked List q, String minGp); String sort Minterms Group(String str); void view Linked List(Linked List qMacLL); int number Of OnesIn Number(long n, int base); int number Of Ones InString(String str); String combine Expression(String ex1, String ex2); String get Binary Expression(long num, int no Of Variables); Linked List prime Implicant Table Generation(String, int); Linked Listget Unselected Prime Implicants(Linked List); String Number String DivideBy2(String str); String Number String ModulusBy2(String str); String gets Binary Expression (String str, int unt); MODEL OF JAVA CODING FOR MQM import java.util.Arrays; import java.util.LinkedList; import java.util.ListIterator; ....... public class QMacPrimeImplicantTableGeneration {
Indian Streams Research Journal • Volume 3 Issue 2 • March 2013
14
FUNCTIONAL APPLICATION AND MINIMIZATION OF BOOLEANFUNCTION..........
Indian Streams Research Journal • Volume 3 Issue 2 • March 2013
15
FUNCTIONAL APPLICATION AND MINIMIZATION OF BOOLEANFUNCTION..........
public static LinkedList getUnselectedPrimeImplicants(LinkedList qMacLL) { if(qMacLL == null || qMacLL.size() < 1) return null; L i n k e d L i s t < Q M a c Ta b l e > q M a c N e w L L = n e w f o r ( i n t c u r r = 0 ; if(!qMacLL.get(curr).isMintermGroupSelected()) } return qMacNewLL; } }
CONCLUSION In this paper, a new modified Quine-McCluskey algorithm for minimizing Boolean expressions has been proposed and implemented. This method using Java can be implemented to simplify any Boolean function more than sixty four variables. The main objective is to keep the number of digital gates as minimum as possible and this reduces the cost of the compact circuit design. It is useful in digital logic design as a valuable tool and further enhanced. REFERENCES [1]Gomma, H. (2001), Designing Concurrent, Distributed, and Real-Time Applications with UML, Proceedings of the 23rd International Conference on Software Engineering (ICSE'01), IEEE Computer Society. [2]Schattkowsky, Tim (2005), UML 2.0 – Overview and Perspectives in SoC Design, IEEE. [3]Saxena, V., Arora D. and Ahmad S. (2007), Object Oriented Distributed Architecture System through UML, IEEE International Conference on Advanced in Computer Vision and Information Technology, ACVIT-01, Nov. 28-30, ISBN 978-81-89866-74-7, pp.305-310. [4]Al-Rababah Ahmad, A. (2009), UML – Models Implementations in Software Engineering System Equipments Representations, International Journal of Soft Computing Applications, Issue 4, pp. 25-34, Euro Journals Publishing, Inc., Retrieved from : [5] Sun, Zhenxin, Wong, Weng-Fai, Zhu, Yongxin and Pilakkat, Santhose Kumar (2005), Design of Clocked Circuits Using UML, IEEE ASP-DAC 2005 (901-904). [6]Dr. Vipin Saxena, Manish Shrivastava and Dr. Deepak Arora, Performance Estimation of Karnaugh Map through UML. IJCSNS International Journal of Computer Science and Network Security, VOL, 9 No.6, June 2009 [7] A.Sathish Kumar and A.Swetha Priya, Minization of Ternary Combinational Circuits- A Survey, International Journal of Engineering Science and Technology. ISSN: 0975-5462,Vol.2(8),2010,pp.3576-3589. [8]Masoud Nosrati and Ronak Karimi, Minization Of Boolean Functions Using Genetic Algorithm. Anale Seria Informatica. Vol. X fasc. 1- 2012,pp.73-76. [9] Rotar Dan “Vasile Alecsandri” University,Bacau,Romania “Software For The Minimization Of The Combinational Logic Functions” The Romanian Review Precision Mechanics, Optics & Mechatronics, 2010(20), No.37,pp.95-99. [10] Dele Oluwade. “A Comparative Analysis and Application of the Compression Properties of Two 7-Bit Subsets of Unicode” Journal of Emerging Trends in Computing and Information Sciences. ISSN 2079-8407, VOL.3.NO.4,April 2012,pp.577-584. [11] SM. Thamarai and Dr K.Kuppusamy,”Fault Detection and Test Minimization Methods for Combinational Circuits- A Survey” International Journal of Computer Trends and Technology- vol 2 Issue 2-2011,pp.140-146. [12] BalachandraPattanaik Dr.R.Sattanathan,”Structure of Boolean function Using Gates, K-map & QuineMcCluskey” ICISA 2010, ISBN 978-81-907677-9-8,pp34-37. [13] Balachandra Pattanaik and Dr.R.Sattanathan,”Estimation and Implementation of Boolean function Using Gates, K-map & Quine-McCluskey” Ciit International Journal 2011, ISBN 978-1-4507-6433-9. [14] Ledion Bitincka and George E. Antoniou”Pocket-PC Boolean Function Simplication” Journal of Electrical Engineering, ISSN 1335-3632 Vol.56,No.7-8,2005 [15]Hazem M.EI-Bakry and Ahmed Atwan, Simplication and Implementation of Boolean Functions,IJUCS Vol.12010/Iss.1,pp.41-50.
Indian Streams Research Journal • Volume 3 Issue 2 • March 2013
16
Publish Research Article International Level Multidisciplinary Research Journal For All Subjects
Dear Sir/Mam, We invite unpublished research paper.Summary of Research Project,Theses,Books and Books Review of publication,you will be pleased to know that our journals are
Associated and Indexed,India
¬ International Scientific Journal Consortium ¬ J-GATE OPEN
Scientific
Associated and Indexed,USA
?Scholar Google ? EBSCO ? DOAJ ? Index Copernicus ? Publication Index ? Journal Database Academic ? Contemporary Research Index ? Paper Databse Academic ? Digital Journals Database ?Index to Scholarly Journals Current ? Elite Scientific Journal Archive ? Of Academic Resources Directory ? Journal Index Scholar ? Recent Science Index ? Resources Database Scientific
Indian Streams Research Journal 258/34 Raviwar Peth Solapur-413005,Maharashtra Contact-9595359435 E-Mail-ayisrj@yahoo.in/ayisrj2011@gmail.com Website : www.isrj.net
