Ask a question from expert

Ask now

Simplification and Implementation of Boolean Functions - Desklib

10 Pages6918 Words170 Views
   

Added on  2021-07-13

About This Document

This paper presents a fast systematic method for minimization of Boolean functions without any visual representation such as Karnough map or arrangement technique such as Tabulation method. The simplified functions are implemented with minimum amount of components using modular neural nets (MNNs) that divide the input space into several homogenous regions. This approach is applied to implement XOR functions, 16 logic function on one bit level, and 2-bit digital multiplier. Compared to previous non- modular designs, a clear reduction in the order of computations and hardware requirements is achieved.

Simplification and Implementation of Boolean Functions - Desklib

   Added on 2021-07-13

BookmarkShareRelated Documents
Simplification and Implementation of Boolean Functions Hazem M. El-Bakry*, Ahmed Atwan*** Department of Information Systems, Faculty of Computer Science and Information Systems, Mansoura University, Mansoura, EGYPT tel: +2 050 2349 340, fax: +2 050 2221 442 e-mail: helbakry20@yahoo.com** Department of Information Technology, Faculty of Computer Science and Information Systems, Mansoura University, Mansoura, EGYPT Submitted: 26/12/2009 Accepted: 10/01/2010 Appeared: 16/01/2010HyperSciences.Publisher AbstractIn previous work (El-bakry, H. M., Mastorakis N., (2009)), a fast systematic method for minimization of the Boolean functions was presented. Such method is a simple because there is no need for any visual representation such as Karnough map or arrangement technique such as Tabulation method. Furthermore, it is suitable for boolean function with large number of variables (more than 4 variable). Moreover, it is very simple to understand and use. In this paper, the simplified functions are implemented with minimum amount of components. A powerful solution for realization of more complex functions is given. This is done by using modular neural nets (MNNs) that divide the input space into several homogenous regions. Such approach is applied to implement XOR functions, 16 logic function on one bit level, and 2-bit digital multiplier. Compared to previous non- modular designs, a clear reduction in the order of computations and hardware requirements is achieved. Keywords: Boolean Functions, Simplification, Implementation, MNNs 1. INTRODUCTION The simplification of Boolean functions is mainly used to reduce the number of gates in a logic circuit. Less number of gates means less power consumption, sometimes the circuit works faster and also when number of gates is reduced, cost also comes down (Marcovitz, A. B., (2007), Mano, M. M., and Ciletti, M. D., (2003) & Mano, M. M., (1984)). There are many ways to simplify a logic design, such as algebraic simplification, Karnough maps, Tabulation Method and Diagrammatic technique using 'Venn-like diagram' some of them are discussed in detail in this introduction (Marcovitz, A. B., (2005), Arntson, A. E., (2005), Mano, M. M., Ciletti, M. D., (2003), & Mano, M. M., (1984)). In this paper, a new fast systematic method for minimization of the Boolean function is introduced. Such method is a very simple because there is no need to any visual representation such as Karnough map or arrangement technique such as Tabulation method and very easy for programming. This method is very suitable for high variables (more than 4 variable) boolean function, and very simple for students (Mano, M. M., and Ciletti, M. D., (2003) & Mano, M. M., (1984)). Furthermore, neural networks are used to implement Boolean functions because they can recognize patterns even with noise, distortion or deformation in shape. This is very important especially in communication applications. 1.1 Boolean FunctionsA Boolean function is an expression consisting of binary variable operators OR, AND, the operator NOT, parentheses, and an equal sign. For a given value of these variables, the function can be either 0 or 1. Consider, for example, the following Boolean function (Atwan, A. (2006), Marcovitz, A. B., (2007) & Mano, M. M., Ciletti, M. D., (2003)): F=X+Y'Z , F equal 1, when X=1 or Y=0, while Z=1. 1. Rules of Boolean Algebra: The standard rules of Boolean algebra which reproduce for simplicity are introduced in table 1: Table 1: Rules of Boolean algebra X + X = X X . X = X X + 0 = X X . 1 = X X + 1 = 1 X . 0 = 0 X + X' = 1 X . X' = 0 2. Canonical and Standard Form (Minterms) A binary variable may come into view either in its normal form, X, or in its complement form, X'. Now consider two binary variables X and Y combined with AND operations. Since each variable may appear in each form, there are four possible combinations, namely, XY, XY', X'Y, and X'Y'. Each of these four terms is called a Minterm or a standard product. In a similar way, N variables can be combined to form 2nMinterms. The 2ndifferent Minterms may be determined by a method similar to the one shown in Table 1 which shows the case of 3 variables (Marcovitz, A. B., (2007), Arntson, A. E., (2005), Vahid, F., (2006) & Hayes, J. P. (1993)). Table 2. Combination of Minterms for 3 variables International Journal of Universal Computer Sciences (Vol.1-2010/Iss.1) El-Bakry and Atwan / Simplification and Implementation of Boolean Functions / pp. 41-50Copyright © 2010 HyperSciences_Publisher. All rights reserved41www.hypersciences.org
Simplification and Implementation of Boolean Functions - Desklib_1
Decimal Form X Y Z Term Designation 0 0 0 0 X'Y'Z' m0 1 0 0 1 X'Y'Z m1 2 0 1 0 X'YZ' m2 3 0 1 1 X'YZ m3 4 1 0 0 XY'Z' m4 5 1 0 1 XY'Z m5 6 1 1 0 XYZ' m6 7 1 1 1 XYZ m7 A Boolean function may be expressed algebraically from a given truth table by forming a minterm for each combination of the variable which produces a 1 in the function and then taking the OR of all those terms. For example, the function F1in Table 2 is determined by expressing the combination 001, 100, and 111 as X'Y'Z, XY'Z', and XYZ. Each one of these minterms results in the expression, so F1can be expressed as: F1= xyz + xyz +xyz = m1+m4+m7 It may be more suitable to express the boolean function in the following short notation: F1(x,y,z) = ( 1,4,7 ) Table 3. Representation of F1 X Y Z F10 0 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 1 1.2 Traditional Methods for Simplification of Boolean Functions There are many Traditional Methods to simplify a Boolean Functions, such as Algebraic Simplification, Karnough Maps and Tabulation Method. This part discusses the frequently used method such as Karnough Map and Tabulation Method. 1. Map Method (Karnough Map) Karnough Map is a visual representation diagram of all possible ways a function may be expressed. Map method is introduced by Veich and slightly modified by Karnough .A K-map consists of a grid of squares, each square representing one canonical minterm combination of the variables or their inverse. The map is arranged so that squares representing minterms which differ by only one variable are adjacent both vertically and horizontally. Therefore XY'Z' would be adjacent to X'Y'Z' and would also adjacent to XY'Z and XYZ' (Marcovitz, A. B., (2007), Hayes, J. P. (1993), Arntson, A. E., (2005), & Mano, M. M., (1984)). Example : Simplify the boolean function: F=W'X'Y'Z + W'X'YZ + W'XY'Z + W'XYZ + WXY'Z'+ WX'Y'Z' or F(X,Y,Z,W) = (1,3,5,7,8,12) Solution: YZ 00 01 11 10 00 1 1 01 1 1 11 1 WX10 1 Fig. 1. Karnough Map F = W'Z + WY'Z' 2. Tabulation Method (QUINE AND MC CLUSKEY ) The Map method of simplification is convenient as long as the number of variable is suitable number. The excessive number of squares prevents a reasonable selection of adjacent squares .The tabulation methods overcomes this difficulty. It is a specific step by step procedure that is guarantied to produce a simplified standard -form expression for the function. the tabular method of simplification consists of two parts. The first is to find by an exhaustive search of all the term that are candidates for inclusion in the simplified function. These terms are called Prime-Implicants .The second operation is to choose among the prime-Implicants those that give an expression with the least number of literals (Mano, M. M., (1984), Floyd, T. L., (2006), Hayes, J. P. (1993), Biswas, N. N., (1984) & Dueck, R., (2004)).Example: Simplify the following Boolean function by using the tabulation methods: F(W,X,Y,Z) = (0,1,2,8,10,11,14,15) SOLUTON: Table 4. The Prime Implicants a B c wxyz wxyz wxyz 0 0000 0,1 000- 0,2,8,10 -0-0 0,2 00-0 0,8,2,10 -0-0 1 0001 0,8 -000 2 0010 10,11,14,15 1-1- 8 1000 2,10 -010 10,14,11,15 1-1- 8,10 10-0 10 1010 10,11 101- 11 1011 10,14 1-10 14 1110 11,15 1-11 15 1111 14,15 111- International Journal of Universal Computer Sciences (Vol.1-2010/Iss.1) El-Bakry and Atwan / Simplification and Implementation of Boolean Functions / pp. 41-5042
Simplification and Implementation of Boolean Functions - Desklib_2
2. A NEW METHOD FOR SIMPLIFICATION OF BOOLEAN FUNCTIONS Starting point is offering the main definitions andterminology to be used throughout this method. The number of Minterms equals 2nwhere n is the number of variables. The maximum Minterm to be obtained equals 2n-1. The 1's complement of any binary number turns 0 to 1 and vise versa , for instance 1's complement f 110101 equals 001010 . Definition 1: The combination of two Minterms is called "double minimization ".The smaller Minterm is called The base and The other is called The follower. Definition 2: The combination of four Minterms is called " quadruple minimization " in which the smaller two Minterms are called the base and the other two Minterms are the followers . Theorem 1: If X is the number which represent any Minterm of Boolean function and , Y is the binary number which represent the maximum Minterm then The 1's complement of X equal Y – X. Proof : 1's complement of X = 2n-1-X where n equal the number of digits of X which represent the numberof variables . The maximum Minterm Y= 2n- 1 . From 1 and 2 , the 1,s complement of X is Y- X. 2.1 The Method for generating The Prime Implicants Terms Procedure : 1. Minterms which are included in the function are put in order from the smaller to bigger in a column way. 2. Every Minterm included in the function is subtracted from the maximum Minterm whether it (maximum Minterm) isincluded in the function or not (For instance the maximum Minterm of a function include 3 variables equals 7 which resulted from 23-1). 3. The result of step 2 should be segmented into its initial values of digits but in a decimal form as shown in table 4. Table 5. Initial values of digits in a decimal form The maximum minterm(MAX) for 3 variable is 23-1=7 Minterms (Base) (MAX- Minterm) Initial Value SET 0 7 (1) (2) (4) 0'set 1 6 (2) (4) 1'set 2 5 (1) (4) 2'set 3 4 (4) 3'set 4 3 (1) (2) 4'set 5 2 (2) 5'set 6 1 (1) 6'set 7 0 - - The minterm 3 is subtracted from the maximum minterm 7 to result in 4 that could not be divided. The minterm 4 is subtracted from 7 to result 3 that could be divided into 1 and 2. 1.Each minterm X can be combined with each minterm Y when Y equal X plus the numbers resulted from the pervious division . -Minterms 3 combined with minterm 7 which result from 3+4 to form a new term 3,7(4) that becomes one variable less than the two combined minterms . -The number between brackets is called "reference" that determine the position of the omitted variables. -at the same way; minterm 4 combined with minterm 5 which result from 4+1 to from the term 4,5(1). and minterm 4 also combined with minterm 6 to form the term 4,6(2) . 2.The probabilities of minimization of the minterms included in the function are taken. This will lead to the probabilities of the double minimization. Example: Determine the probabilities of the double minimization of the following function: F(X,Y,Z) = (1,2,3,4,5) Solution: Table 6. The maximum minterm for 3 variable is 23-1=7 Minterms (Base) (MAX- Minterm) Initial Value SET 1 6 (2)1,3 (4)1,5 1'set 2 5 (1)2,3 (4)- 2'set 3 4 (4)- 3'set 4 3 (1)4,5 (2)- 4'set 5 2 (2)- 5'set Notice that the name of set is the name of base. Table 7. The probabilities of double minimizationTERM X Y Z Name (2)1,3 0 - 1 X'Z (4)1,5 - 0 1 Y'Z (1)2,3 0 1 - X'Y (1)4,5 1 0 - XY' International Journal of Universal Computer Sciences (Vol.1-2010/Iss.1) El-Bakry and Atwan / Simplification and Implementation of Boolean Functions / pp. 41-5043
Simplification and Implementation of Boolean Functions - Desklib_3

End of preview

Want to access all the pages? Upload your documents or become a member.