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
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
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
End of preview
Want to access all the pages? Upload your documents or become a member.