International Journal of Universal Computer Sciences

Added on - 13 Jul 2021

  • 10


  • 6918


  • 44


  • 0


Trusted by +2 million users,
1000+ happy students everyday
Showing pages 1 to 3 of 10 pages
Simplification and Implementation of Boolean FunctionsHazem M. El-Bakry*,Ahmed Atwan***Department of Information Systems, Faculty of Computer Scienceand Information Systems, Mansoura University, Mansoura, EGYPTtel: +2 050 2349 340, fax: +2 050 2221 442e-mail:**Department of Information Technology, Faculty of ComputerScience and Information Systems, Mansoura University, Mansoura,EGYPTSubmitted: 26/12/2009Accepted: 10/01/2010Appeared: 16/01/2010HyperSciences.PublisherAbstractIn previous work (El-bakry, H. M., Mastorakis N., (2009)), a fast systematic method forminimization of the Boolean functions was presented. Such method is a simple because there is no needfor any visual representation such as Karnough map or arrangement technique such as Tabulationmethod. Furthermore, it is suitable for boolean function with large number of variables (more than 4variable). Moreover, it is very simple to understand and use. In this paper, the simplified functions areimplemented with minimum amount of components. A powerful solution for realization of more complexfunctions is given. This is done by using modular neural nets (MNNs) that divide the input space intoseveral homogenous regions. Such approach is applied to implement XOR functions, 16 logic functionon one bit level, and 2-bit digital multiplier. Compared to previous non- modular designs, a clearreduction in the order of computations and hardware requirements is achieved.Keywords:Boolean Functions, Simplification, Implementation, MNNs1. INTRODUCTIONThe simplification of Boolean functions is mainly used toreduce the number of gates in a logic circuit. Less number ofgates means less power consumption, sometimes the circuitworks faster and also when number of gates is reduced, costalso comes down (Marcovitz, A. B., (2007), Mano, M. M.,and Ciletti, M. D., (2003) & Mano, M. M., (1984)). There aremany ways to simplify a logic design, such as algebraicsimplification,Karnoughmaps,TabulationMethodandDiagrammatic technique using 'Venn-like diagram' some ofthem 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 minimizationof the Boolean function is introduced. Such method is a verysimple because there is no need to any visual representationsuch as Karnough map or arrangement technique such asTabulationmethodand very easy for programming. Thismethodisverysuitableforhighvariables(morethan4variable)booleanfunction,andverysimpleforstudents(Mano, M. M., and Ciletti, M. D., (2003) & Mano, M. M.,(1984)). Furthermore, neural networks are used to implementBoolean functions because they can recognize patterns evenwith noise, distortion or deformation in shape. This is veryimportant especially in communication applications.1.1 Boolean FunctionsA Boolean function is an expression consisting of binaryvariable operators OR, AND, the operator NOT, parentheses,and an equal sign. For a given value of these variables, thefunction can be either 0 or 1. Consider, for example, thefollowing Boolean function (Atwan, A. (2006), Marcovitz, A.B.,(2007)&Mano,M.M.,Ciletti,M.D.,(2003)):F=X+Y'Z , Fequal1, whenX=1orY=0, whileZ=1.1. Rules of Boolean Algebra:The standard rules of Boolean algebra which reproduce forsimplicity are introduced in table 1:Table 1: Rules of Boolean algebraX + X = XX . X = XX + 0 = XX . 1 = XX + 1 = 1X . 0 = 0X + X' = 1X . X' = 02. Canonical and Standard Form (Minterms)A binary variable may come into view either in its normalform,X, or in its complement form,X'. Now consider twobinary variables X and Y combined with AND operations.Since each variable may appear in each form, there are fourpossible combinations, namely,XY, XY', X'Y,andX'Y'. Eachof these four terms is called a Minterm or a standard product.In a similar way,Nvariables can be combined to form2nMinterms. The2ndifferent Minterms may be determined by amethod similar to the one shown in Table 1 which shows thecase 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 variablesInternational 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
DecimalFormXYZTermDesignation0000X'Y'Z'm01001X'Y'Zm12010X'YZ'm23011X'YZm34100XY'Z'm45101XY'Zm56110XYZ'm67111XYZm7A Boolean function may be expressed algebraically from agiventruthtablebyformingamintermforeachcombination of the variable which produces a 1 in thefunction and then taking the OR of all those terms. Forexample,thefunctionF1inTable2isdeterminedbyexpressing the combination 001, 100, and 111 as X'Y'Z,XY'Z', and XYZ. Each one of these minterms results in theexpression, so F1can be expressed as:F1= xyz + xyz +xyz = m1+m4+m7It may be more suitable to express the boolean function in thefollowing short notation:F1(x,y,z) =( 1,4,7 )Table 3. Representation of F1XYZF1000000110100011010011010110011111.2TraditionalMethodsforSimplificationofBooleanFunctionsThere are many Traditional Methods to simplify aBooleanFunctions, such as Algebraic Simplification, Karnough Mapsand Tabulation Method. This part discusses the frequentlyused method such asKarnough MapandTabulation Method.1. Map Method (Karnough Map)KarnoughMapisavisualrepresentationdiagramofallpossible ways a function may be expressed. Map method isintroduced by Veich and slightly modified by Karnough .AK-map consists of a grid of squares, each square representingone canonical minterm combination of the variables or theirinverse. The map is arranged so that squares representingminterms which differ by only one variable are adjacent bothverticallyandhorizontally.ThereforeXY'Z'wouldbeadjacent 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 theboolean 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:YZ0001111000110111111WX101Fig. 1. Karnough MapF = W'Z + WY'Z'2. Tabulation Method (QUINE AND MC CLUSKEY )The Map method of simplification is convenient as long asthe number of variable is suitable number. The excessivenumber of squares prevents a reasonable selection of adjacentsquares .The tabulation methods overcomes this difficulty. Itis a specific step by step procedure that is guarantied toproduceasimplifiedstandard-formexpressionforthefunction. the tabular method of simplification consists oftwo parts. The first is to find by an exhaustive search of allthe term that are candidates for inclusion in the simplifiedfunction.ThesetermsarecalledPrime-Implicants.Thesecond operation is to choose among the prime-Implicantsthose 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 usingthetabulationmethods:F(W,X,Y,Z)=(0,1,2,8,10,11,14,15)SOLUTON:Table 4. The Prime ImplicantsaBcwxyzwxyzwxyz000000,1000-0,2,8,10-0-00,200-00,8,2,10-0-0100010,8-0002001010,11,14,151-1-810002,10-01010,14,11,151-1-8,1010-010101010,11101-11101110,141-1014111011,151-1115111114,15111-International Journal of Universal Computer Sciences (Vol.1-2010/Iss.1)El-Bakry and Atwan / Simplification and Implementation of Boolean Functions / pp. 41-5042
2. A NEW METHOD FOR SIMPLIFICATION OFBOOLEAN FUNCTIONSStartingpointisofferingthemaindefinitionsandterminology to be used throughout this method.The number of Minterms equals 2nwhere n is thenumber of variables.The maximum Minterm to be obtained equals 2n-1.The 1's complement of any binary number turns 0to 1 and vise versa , for instance 1's complement f110101 equals 001010 .Definition 1:ThecombinationoftwoMintermsiscalled"doubleminimization ".The smaller Minterm is called The baseand The other is called The follower.Definition 2:The combination of four Minterms is called " quadrupleminimization " in which the smaller two Minterms are calledthe base and the other two Minterms are the followers .Theorem 1:If X is the number which represent any Minterm of Booleanfunction and ,Yis the binary number which represent themaximum Minterm then The 1's complement of X equalY – X.Proof :1's complement of X = 2n-1-X where n equal thenumber 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 TermsProcedure :1. Minterms which are included in the function are put inorder from the smaller to bigger in a column way.2. Every Minterm included in the function is subtracted fromthe maximum Minterm whether it (maximum Minterm) isincluded in the function or not (For instance the maximumMinterm of a function include 3 variables equals 7 whichresulted from 23-1).3. The result of step 2 should be segmented into its initialvalues of digits but in a decimal form as shown in table 4.Table 5. Initial values of digits in a decimal formThe maximum minterm(MAX) for 3 variableis 23-1=7Minterms(Base)(MAX-Minterm)InitialValueSET07(1)(2)(4)0'set16(2)(4)1'set25(1)(4)2'set34(4)3'set43(1)(2)4'set52(2)5'set61(1)6'set70--The minterm 3 is subtracted from the maximum minterm7 to result in 4 that could not be divided.The minterm 4 is subtracted from 7 to result 3 that couldbe divided into 1 and 2.1.Each minterm X can be combined with eachminterm Y when Y equal X plus the numbersresulted from the pervious division .-Minterms 3 combined with minterm 7 whichresult from 3+4 to form a new term 3,7(4) thatbecomesonevariablelessthanthetwocombined minterms .-Thenumberbetweenbracketsiscalled"reference" that determine the position of theomitted variables.-at the same way; minterm 4 combined withminterm 5 which result from 4+1 to from theterm 4,5(1). and minterm 4 also combined withminterm 6 to form the term 4,6(2) .2.The probabilities of minimization of the mintermsincluded in the function are taken. This will lead tothe probabilities of the double minimization.Example:Determine the probabilities of the double minimization of thefollowing function:F(X,Y,Z) =(1,2,3,4,5)Solution:Table 6. The maximum minterm for 3 variable is 23-1=7Minterms(Base)(MAX-Minterm)InitialValueSET16(2)1,3(4)1,51'set25(1)2,3(4)-2'set34(4)-3'set43(1)4,5(2)-4'set52(2)-5'setNotice that the name of set is the name of base.Table 7. The probabilities of double minimizationTERMXYZName(2)1,30-1X'Z(4)1,5-01Y'Z(1)2,301-X'Y(1)4,510-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
You’re reading a preview
Preview Documents

To View Complete Document

Click the button to download
Subscribe to our plans

Download This Document