UNIT 2.pdf

UNIT-II COMBINATIONAL LOGIC DESIGN 2.1. Boolean Algebra  George Boole invented a symbolic logic known as Boolean algebra is a Boolean Algebra in 1854.  Bathematical technique used to solve problem...

UNIT-II COMBINATIONAL LOGIC DESIGN 2.1. Boolean Algebra  George Boole invented a symbolic logic known as Boolean algebra is a Boolean Algebra in 1854.  Bathematical technique used to solve problems in logic nature. The elements used in boolean algebra are '0' and 1.  There are four connecting symbols used in boolean algebra.  They are (i) equal sign (=) (ii) plus sign (+) (ii) dot sign (.) and (iv) bar sign (-, ').  The bar, sign represents complement function.  The theorems, postulates and laws of boolean algebra are given below. 2.1.1. Postulates i) A+0=A ii) A+1=1 ⅲ) A.0=0 iv) A. 1=A 2.1.2. Theorems i) A+AA; ii) A.A=A; iii) A. (A + B) = AB iv) (A')= A [A=A] [: A = A] v) A + AB = A v) A + A = 1 vi) A. A = 0 vii) A + BC = (A + B). (A + C) vi) (A… 2.1.3. Laws a. Commutative law i) A+B=B+A ii) A. B = B. A b. Associative law i) A+ (B+C) = (A + B) + C ii) A. (B. C) = (A.B). C C. Distributive law i) A. (B+C) = A.B +A. C ii) (A + B). (C+D) = A. C+B.C+A.D+B.D 2.2. De-Morgan's theorem   The De-Morgan's theorem is very much used for simplifying boolean equations.  It contains two laws. (a) FIRST LAW:  The complement of sum of the variables is equal to the product of their complements. A+B=A.B The logic diagram for the first law is shown in the Fig.2.1.Logic diagram for De-morgan's first law  The truth table used for verifying the De-morgan first law is shown below.  From the truth table A + B = A. B, is verified. (b) SECOND LAW.  The complement of product of the variables is equal to the sum of their complements.  A.B=A+B fig.2.2.  The logic diagram for the second law is shown in the Fig.2.2.  Logic diagram for De-morgan's second law  The truth table for verifying the De-morgans second law is shown in the table below.  From the truth table A.B = A + B, is verified. 2.3. Standard representation of logic functions   Logic functions are usually represented by logic expressions or logic diagrams using AND and OR operators.  However some functions have more compact representatiorss with Ex-OR operator.  The standard form of boolean function is sum of products or product of sums fashion.  The example of sum of product form is Y = AB + BC + AC and product of sum form is Y = (A + B) (B+C) (C+A) 2.4. Karnaugh map (K - map)  A karnaugh map is a visual display of the fundamental products needed for a sum of products solution.  By using this map we can easily simplify the boolean equations in sum of product form.  The karnaugh map for two, three, four etc variables are different.  The karnaugh map for different variables are discus…  karnaugh map, because the corresponding outputs are high.  The remaining spaces are entered with O's.  The karnaugh map for the given truth table is shown in the fig.2.3(b). (ii) Three variable map  An example of a three variable truth table and their corresponding karnaugh map is shown in the fig.2.4.  The vertical column is labelled as AB, AB, A B and AB. This order is not a binary progress of 00, 01, 10 and 11.  In the karnaugh map the variables order are assigned in a sequence of, only one variable changes from complemented to uncomplemented form (or vice versa).  The horizontal row is marked as C and C. (a) Truth table (b) Three variable map Fig. 2.4. Three variab… 2.6  looping.  Pairs, quads and octets are the group of looping used in karnaugh map for  simplification. (i) Pairs  The typical karnaugh maps for representing 3 variables are shown in the fig.2.5.  A karnaugh map that contains a group of two 1's placed adjacent to each other in vertical or thorizontal position is called pair.  The first map (fig.2.5(a) contains a pair of 1's that are vertically adjacent to each other.  The first 1 represents A B C and the second 1 represents A B C.  Note that, in these two terms only the A variable appears in both normal and complemented form. B and C remain unchanged.  These two terms can be combined to give a resultant that eliminates the variable A.  since it appears in both uncomplemented and complemented forms.  This is easily…  The second map (fig. 2.5(b) contains a pair of 1's that are horizontally adjacent to each other.  These two 1's can be looped and the C variable eliminated since it appears in both its uncomplemented and complemented forms.  YABC+ABC = AB (C+C) = AB  In the pair looping, only one variable is in uncomplemented and complemented form hence pairs eliminate single variable. The pair eliminates only one variable and their complement. (ii) Quads  A karnaugh map that contains a group of four 1's placed adjacent to each other in a form of line or square is called quad.  In the fig. 2.6(a), four 1's are placed vertically adjacent to each other.  The 1's are placed in the positions of ABC.ABC.ABC and ABC. All the four terms, only the variable C remains unchanged. Bo…= AB unchanged, and both C and D are in complemented and uncomplemented forms.  Thus the resultant output is A B. Y = ABCD+ABCD+ABCD+ABCD = ABC(D+D)+ABC (D+D) = ABC+ABC = AB (C+C) Fig. 2.6. Karnaugh map representing quads  The fig.2.6 (c) contains four 1's in a form of square. and they are also considered as adjacent to each other. They are ABCD, ABCD, ABCD and ABCD.  The variables B 2.9  and D remain unchanged, and the variables A and C are in complemented and uncomplemented forms.  Thus the resultant output is BD. Y = ABCD+ABCD+ABCD+ABCD = ABD (C+C) + ABD (C + C) = ABD+ABD = (A+A) BD = BD The quad eliminates two variables and their complements. (iii) Octets  A group of eight 1's that are adjacent to each other is called octet.  In fig.2.7(a), eight 1s are in a form of rectangle, in horizontal direction.  The eight 1s are considered as adjacent to each other. The 1's are placed in ABCD, ABCD. ABCD.ABCD, ABCD, ABCD, ABCD and ABCD positions.  The variable B remains unchanged, and the variables A. C and D are in complemented and uncomplemented forms.  Thus the resultant output is B. Y = ABCD+ABCD+ABCD+ABCD+ ABCD+ABCD+ABCD+ABCD = (A+A) B C D +… 2.10 = B(C+C) B  The fig.2.7(b) contains eight 1's in a form of rectangle, in vertical direction.  The eight 1s are considered ABCD, ABCD. The ABCD. ABCD, ABCD, ABCD, ABCD and/ variable D remains unchanged and the variables A, B and C are in complemented and uncomplemented forms.  Thus the resultant output is D. Fig. 2.7.  Karnaugh map for representing octet Y = ABCD+ABCD+ABCD+ABCD+ ABCD+ABCD+ABCD+ABCD = (A+A) BCD + (A+A) B C D + (A+A) BCD + (A+A) BCD = BCD+BCD+BCD+BCD = (B + B) CD + (B + B) CD = CD+CD = (C + C) D = D 2.11  The octet eliminates three variables and their complements.  2.4.2. Karnaugh simplifications  A pair in a karnaugh map eliminates one similarly a quad eliminates two variables and an octet eliminates three variables.  The first option goes to octets.  the quads second and the pairs last.  In this way, the greatest simplification takes place. variable  (1) An Example - Truth table  A four variable karnaugh map is shown in the fig.2.8. It contains ten 1's  This map contains two quads, only one pair and no octet loops  In the square type quad, the variables A and C remain unchanged and the variables B and D are in complemented and uncomplemanted forms. Thus the output of first quad is A C 12 13 1… 2.12  In the pair, the variables A, B and D remain unchanged and the variable C is in complemented and uncomplemented forms.  Thus the output of pair is ABD. Hence the resultant output, Y = AC+CD+ (ii) Overlapping groups  We can use 1's in more than one loops of pairs, quads and octets.  This type of group is called overlapping groups.  For example as shown in the fig.2.9, a '1' that represents ABCD is not covered by any loop before considering overlapping group.  Thus the output of this karnaugh map before considering overlapping. Y = A + ABCD.  Thus A is the result of the octet loop and A BCD is the output of single 1.   In the overlapping type, the 1 that represents ABCD is combined with another nearest '1' of ABCD in the octet loop to form a pair loop. Now it… (iii) Rolling the map 2  In the fig. 2.10 (a) the bottom row contains two 15. not combined by any looping method.  Hence the output, YABCD+ABCD = ABD (C+C) = ABD  This output represents the variables A, B and D that are unchanged and the variable C is in complemented and uncomplemented forms. So the output is A B D.  This shows both 1s are adjacent and form a pair called rolled pair. Fig.2.10 Rolling karnaugh map  The rolling shows that the first row and the last row are adjacent to each other. Similarly the first … at d S not 2.14  The output of quad is AD because the variables A Dremain unchanged, hence it produces the output as BCD and D remain unchanged. In the pair, the variables B. C and The resultant output is AD + BCD. (M) Redundant groups  A group whose 1s are all overlapped by other groups is called a redundant group.  In boolean simplification, we can eliminate any group whose 1s are completely overlapped by other groups. Fig.2.12. Don't care condition  Some logic circuits can be designed so that there are certain input conditions that do not produce any specified output levels i.e. '0' or '1'.  That means, certain input conditions of some logic circuits produce the output as neither '0' nor '1'. This type of output is in an unspecified form, called don't cares.  The truth table shown in the fig.2.12(a) contains some don't care outputs, for some input   conditions.   Don't care outputs of "…  SRI NALLA   EST   2.16   Thes gives one octet, one quad and one pair loops in the given figure.   We visualise all remaining x's an Os. (ABCD = 0) In this way, the x's are used to the best advantage We are free to do this because the don't cares can be either Os of 1s, whichever we prefer.  Now it contains one octet loop, one quad loop and one pair loop.  The output of this karnaugh map B+CD+ACD   244. Simplification of logic functions  The procedure for simplifying a boolean expression is shown below.   Construct a karnaugh map and place '1's in those squares corresponding to the '1's in the truth table. Place 'O's in the other squares.   (Encircle (loop) the possible octets, quads and pairs   (i) If any isolated '1's remains, encircle each.   (v) Eliminate any redun…  2.17   C   P1   AB00   11   AB 0   2   13   AB   6   7   ABO   05   Pair 1 = AC   Pair 2 = A B   AG   Example 2:   Y = ABCD+ABCD+ABCD+ABCD+ABCD +ABCD+ABCD+ABCD+ABCD+ABCD+ABCD CD CD  CD CD  Fig.2.13. Karnaugh map  Simplify the given logic equation by using karnaugh map.   AB  0  0  0   0   1   3   2   AB   1   1   1   1   Octet = B   4   5   7   6   Quad = A D   AB   1   1   1   Pair = ACD   12   13 15   14   AB 1   0   0   1   8   9   11   10   Fig.2.14. Karnaugh map   The given function is a four variable function: The karnaugh map for that function is shown in the fig.2.14.  It contains one octet, one quad and one pair loops.   Output, Y = B + AD+ACD   Example 3:   Simplify the given logic equation by using karnaugh map and simulate its output.  4   Y   2.18   ABCD+ABCD+ABCD+ABCD+ ABCD+ABCD+ABCD.   CD   CD   CD   CD   AB   0   0   1   0   0   1   3   2   AB   1   1   1   4   7   quad 1 = BC   6   1   1   0   AB   0   quad 2 = A B   12   13   15   14   pair = ACD   AB   0   0   0   0   8   9   11   10   (a) Karnaugh map   D   C   B   B   AB   BC   Y   Y=AB+BC+ACD   ACD   (b) Logic diagram   Fig.2.15   The karnaugh for the given four variable logic function is shown in the fig.2.15(a).  It contains two quad loops and one pair loop.  The output after simplication Y=BC + AB+ ACD. The logic diagram for the resultant output is shown in the fig.2.15(b).  Example 4: Simplify the given logic diagram shown in the fig.2.16.  using karnaugh map and also draw the logic diagram for its output.  2.19   Y=ABCD+ABCD+ABCD + ABCD The output of the given logic diagram +ABCD+ABCD+ABCD It is a four variable logic function.   ABCD   AB   ABCD   ABCD   DABCD   DABCD   DAB DABCD   D AB   Fig.2.16.Logic diagram   ABCD   The karnaugh map for the given logic function is shown in the fig.2.17(a).  It contains one quad and two pair loops.  Hence the resultant output Y= B C + ABD + BCD The logic diagram for the resultant output is shown in the fig.2.17(b). It contains only four basic gates.  The input side also contains 4 NOT gates for getting complement inputs.   CD   CD   CD   CD   01   AB   0   0   0   1   3   AB   2   1   0   1   4   quad 1 = B C   5   7   AB   6   1   1   0   0   pair 1 = ABD pair 2 = B C D   12   13   15   14   AB 0   0   0   8   9   11   10   Fig.2.17(a)  D   2.20   ABD   BCD   Fig.2.17(b) Logic diagram   Example 5: Simplify the given logic function using kamaugh map.  1 = 2 (0, 1, 2, 3, 5, 7, 8, 9, 10, 11, 13, 15) The karnaugh map for the given function is shown   CD   CD   CD   CD   below.   AB   1   1   11   0   1   3   B   2   AB   0   1   1   0   4   5   7   6   AB   0   1   1   0   12   13   15   D   14   AB   1   1   1   8   9   11   10   Karnaugh map   It contains only two octet loops. Hence its output is Y=B+D   Example 6: Simplify the given logic function using karnaugh map.   F = Σ (0, 1, 3, 4, 5, 6, 8, 9, 11, 12, 13, 14)