Looking for a Tutor Near You?

Post Learning Requirement »
x

Choose Country Code

x

Direction

x

Ask a Question

x

x
x
For better view click here
x
Hire a Tutor
DISCOVER

DPSD Notes

Loading...

Published in: Computer Science | Information Technology and Strategic Management
11,438 Views

This note is useful for B.E. CSE IT students.

Prakash / Chennai

17 years of teaching experience

Qualification: M.Tech (Anna University, Chennai - 2006)

Teaches: Computer Science, IT & Computer Subjects, B.Tech Tuition, IT, M.Tech Tuition, Data Structures, DBMS & RDBMS, Oracle Training, PL/SQL, Computer, C / C++, Java And J2EE, Shell Scripting, Visual Basic, Java Script, PHP And MySQL

Contact this Tutor
  1. CS8351-DIGITAL PRINCIPLES AND SYSTEM DESIGN 11 YEAR - 111 SEMESTER - R2017 UNIT- 1 INTRODUCTION: In 1854, George Boole, an English mathematician, proposed algebra for symbolically representing problems in logic so that they may be analyzed mathematically. The mathematical systems founded upon the work of Boole are called Boolean algebra in his honor. The application of a Boolean algebra to certain engineering problems was introduced in 1938 by C.E. Shannon. For the formal definition of Boolean algebra, we shall employ the postulates formulated by E. V. Huntington in 1904. Fundamental postulates of Boolean algebra: The postulates of a mathematical system forms the basic assumption from which it is possible to deduce the theorems, laws and properties of the system. The most common postulates used to formulate various structures are— i) Closure: A set S is closed w.r.t. a binary operator, if for every pair of elements of S, the binary operator specifies a rule for obtaining a unique element of S. The result of each operation with operator (+) or (.) is either 1 or o and 1, o €B. ii) Identity element: A set S is said to have an identity element w.r.t a binary operation * on S, if there exists an element e e S with the property, 1.1=1 1.0=0. 1=1 iii) Commutative law: A binary operator x*y=y*x on a set S is said to be commutative if, for all x, y e S Department of Information Technology
  2. O . 1=1.0 iv) Distributive law: If * and • are two binary operation on a set S, • is said to be distributive over + whenever, Similarly, + is said to be distributive over • whenever, v) Inverse: A set S having the identity element e, w.r.t. binary operator * is said to have an inverse, whenever for every x e S, there exists an element x' e S such that, a) x+ x' = 1, since o + o' = 0+ 1 and 1+ 1' b) x. x' = 1, since o . o' = o. 1 and 1. 1' = 1.0=0 Summary: Postulates of Boolean algebra: POSTULATES Postulate 2 (Identity) Postulate 3 (Commutative) Postulate 4 (Distributive) Postulate 5 (Inverse) (a) x (y+ z) = xy+ xz x+x' = 1 (b) x.l=x x+ yz = (x+ y). (x+ z) Basic theorem and properties of Boolean algebra: Basic Theorems: Department of Information Technology
  3. The theorems, like the postulates are listed in pairs; each relation is the dual of the one paired with it. The postulates are basic axioms of the algebraic structure and need no proof. The theorems must be proven from the postulates. The proofs of the theorems with one variable are presented below. At the right is listed the number of the postulate that justifies each step of the proof. 1) a) x+x=x 4(b) [ X+yz = (x+Y)(x+z)] = X+ xx' = X+ x'.l by postulate 2(b) [ x. 1 = x ] 5(a) [ x+ x' = 1] 5(b) [x. x' —o] by postulate 2(a) [ x+ o = x] 5(b) [ x. x' — o] 4(a) [ x (Y+Z) = (xy)+ (xz)] 5(a) [x+ x' = 1] 2(b) [ x.l = x] by postulate 2(b) [ x. 1 = x ] 5(a) [ x+ x' = 1] 4(b) [ X+yz = (x+Y)(x+z)] 2(b) [x. 1 = x] 5(a) [ x+ x'= 1] From postulate 5, we have x+ x' = 1 and x. x' = o, which defines the complement of x. The complement of x' is x and is also (x')'. Therefore, since the complement is unique, 4) Absorption Theorem: a) x+xy=x Department of Information Technology
  4. x+ xy = x. 1 + xy by postulate 2(b) 4(a) [ x (Y+Z) = (xy)+ (xz)] by theorem 2(a) by postulate 2(a) 4(a) [ x (Y+Z) = (xy)+ (xz)] b) c) x+ x' y = x+y x+ x'y = x+ xy+ x'y d) x. (x'+Y) = xy x. (x'+Y) = x.x'+ xy = 0+ xy = xy. Properties of Boolean algebra: 1. Commutatiye-uopecty: by theorem I(b) by theorem 4(a) by theorem 4(a) [x+ xy = x] [x+ xy = x] ----------------- by postulate 4(a) [x (Y+Z) = (xy)+ (xz)] - ---------------- by postulate 4(a) [x (Y+Z) = (xy)+ (xz)] 2(a) Boolean addition is commutative, given by According to this property, the order of the OR operation conducted on the variables makes no difference. Boolean algebra is also commutative over multiplication given by, This means that the order of the AND operation conducted on the variables makes no difference. 2. Associatiye-uopecty: Department of Information Technology
  5. The associative property of addition is given by, The OR operation of several variables results in the same, regardless of the grouping of the variables. The associative law of multiplication is given by, It makes no difference in what order the variables are grouped during the AND operation of several variables. 3. Pjs-t!ibutiye-uopecty: The Boolean addition is distributive over Boolean multiplication, given by A+ BC = (A+B) (A+C) The Boolean addition is distributive over Boolean addition, given by 4. Duality: It states that every algebraic expression deducible from the postulates of Boolean algebra remains valid if the operators and identity elements are interchanged. If the dual of an algebraic expression is desired, we simply interchange OR and AND operators and replace I's by o's and o's by I's. x+ x' = 1 is x. x' = O Duality is a very important property of Boolean algebra. Department of Information Technology
  6. Summary: Theorems of Boolean algebra: 1 2 3 4 5 THEOREMS Idempotent Involution Absorption Associative DeMorgan's Theorem (a) x+x=x x +1=1 x+ xy x+(y+ z)= (x+ y)+ z (b) x.x=x x. (x'+ y)= xy x (yz) = (xy) z DeMorgan's Theorems: Two theorems that are an important part of Boolean algebra were proposed by DeMorgan. The first theorem states that the complement of a product is equal to the sum of the complements. (AB)' = A'+ B' The second theorem states that the complement of a sum is equal to the product of the complements. Consensus Theorem: In simplification of Boolean expression, an expression of the form AB+ A'C+ BC, the term BC is redundant and can be eliminated to form the equivalent expression AB+ A'C. The theorem used for this simplification is known as consensus theorem and is stated as, AB+ A'C+ BC = AB+ A'C The dual form of consensus theorem is stated as, (A+B) (A'+C) (B+C) = (A+B) (A'+C) Department of Information Technology
  7. 2. BOOLEAN FUNCTIONS: Minimization of Boolean Expressions: The Boolean expressions can be simplified by applying properties, laws and theorems of Boolean algebra. Simplify the following Boolean functions to a minimum number of literals: 1. x (x'+y) = 01 = xx'+ xy = 0 + xy = xy. x+ x'y = x + xy + x'y = x+ y (x+x') = x.x+ xy'+ xy+ yy' = x+ xy'+ xy+ 0 4. xy + x'z +yz. = xy + x'z + yz( x+ x') — xy + x'z + xyz + x'yz Re-arranging, 5. = xy + xyz + x'z +x'yz = xy (1+ z) +x'z (1+y) = xy+ x'z. xy+ yz+ y'z = xy+ z ( y+ y') = xy+ z (1) = xy+ z. [ x+ xy= x] [ x+ x'= Il -1] Department of Information Technology
  8. 7. 8. 9. ?'?+ ??+ ?'?' = ? ( ?'+ ?) + ?'?' = ? (1) + ?'?' = ? + ?'?' ?+ ??'+ ?'? = ? (1+ ?')+ ?'? = ? (1) + ?'? = ?+ ?'? ?? + (??? + ??'? (?? + ?) = ?? + (??? + ???'?? + ??'?? = ?? + (??? + 0+ ??'?? = ?? + (??? + ??'? = ?? + ?' + ? +??'? Re- arranging, = ? ' + ???- ?+ ? = 4-14- 10. (?'+ ?) (?+ ?) = ?'.?+ ?'?+ ??+ ?.? = 0+ ?'?+ ??+ ? 11. ??+ xyz+ ?? (w+ z) = ?? ( 1+ z+ w+ z) [ dual form of consensus theorem, [ ? (?+ z) = ??+ xz ] [ ?+ ?'?' = ?+ ? ' ] [1+x=1] [ ?+ ?'? = ?+ ?] [?' + ??'? = ? + ??'] [ ?.?'= 01; [?. ?= ?] [1+x=1] Department of lnformation Technology
  9. = ?? ( 1 ) = ??. 12. ??+ xyz+ xyz'+ x'yz = ?? ( 1+ z+ z')+ x'yz = ?? (1) + x'yz = ??+ x'yz = ? ( ?+ x'z ) 13. xyz+ xy'z+ xyz' = ?? (z+ z') + xy'z = ??+ xy'z = ?(?+ y'z) = ?(?+ z) 14. x'y'z'+ x'yz'+ xy'z'+ xyz' = x'z' (? '+ ?)+ xz' (?'+ ?) = x'z'+ xz' 15. w'xyz'+ xyz'+ xy'z'+ xy'z xyz' (w'+ 1) + xy'z'+ xy'z = xyz'+ xy'z'+ xy'z = xz' (?+ ?') + xy'z = xz'+ xy'z = ? (z'+ y'z) 16. w'xy'z+ w'xyz+ wxz = w'xz (?'+ ?)+ wxz = w'xz (1)+ wxz — w'xz+ wxz = xz (w'+ = xz. 17. x'y'z'+ x'y'z+ x'yz'+ x'yz+ xy'z' = ?' ?' (z'+z) + ?' ? (z'+z)+ xy'z' = ?' ?' (1) + ?' ? (1)+ xy'z' = ?' ?' + ?'? + xy'z' = ?'(?'+?) + xy'z' [1+?=1] [1+?=1] [1+?=1] [ ?'+ ??' = ?'+ ?'] Department of lnformation Technology
  10. = x' (1) + xy'z' = x' + xy'z' — x'+ y'z'. 18. w' y (w'xz)' + w'xy'z' + wx'y = w' y (w' '+ x'+ z') + w'xy'z' + wx'y = w' y (w+ x'+ z') + w'xy'z' + wx'y = w'yw+ w' y x'+ w' y z' + w'xy'z' + wx'y = 0 + w'x'y+ w' y z' + w'xy'z' + wx'y Re-arranging, — w'x'y+ wx'y + w' y z' + w'xy'z' = x' y (w' + w) + w'z' (y+ xy') = x' y (1) + w'z' (y+ xy') = x'y+ w'z' (y+x) 19. xy+ x (y+ z) + y (y+ z) = xy+ xy+ xz+ yy+ yz = xy+ xz+ y+ yz = xy+ xz+ y = Y+ xz 20. [ xy' (z+ wy) + x' y'] z = [ xy'z+ xy'wy+ x' y'] z = [ xy'z+ O+x'y'l z xy'z. z+ x' y 'z = xy'z+ x'y'z = y'z (x+ x') = y'z (1) 21. x'yz+ xy'z'+ x'y'z'+ xy'z+ xyz = yz (x'+x) + xy'z'+ x'y'z'+ xy'z = yz (1) + y'z' (x+ x') + xy'z = yz+ y 'z' (1)+ xy'z = yz+ y'z'+ xy'z = yz+ y' (z' + xz) = yz+ y' (z'+ x) = yz+ y'z'+ xy' 22. l(xy)'+ x'+ xy? = I x'+ y'+ x'+ xy? = I x'+ y'+ xy? [ x+ x'= 11 I x'+ xy' = x'+ y'] Ix” = x] I x+ x'= Il [x+ xy= x] [x+ xy= x] I x+ x'= Il [ x+ x'=l] [ x+ x'=l] I x'+ xy = x'+ y] Department of Information Technology
  11. 23. [ ??+ xzl'+ x'y'z = (??)'. (xz)'+ x'y'z = (?'+ ?'). (?'+ z')+ x'y'z = ?'?'+ x'z'+ ?'?'+ y'z'+ x'y'z = ?'+ x'z'+ ?'?'+ y'z'+ x'y'z = ?'+ x'z'+ ?'?'+ ? ' [z'+ x'zl = ?'+ x'z'+ ?'?'+ ? ' [z'+ ?'] = ?'+ ?'?'+ ? ' [z'+ ?'] = ?'+ ?'?'+ y'z'+ ?'?' = ?'+ y'z'+ ?'?' = ?'+ y'z'. 24. ??+ ??'( x'z')' = ??+ ?? ' (?”+ z”) = ??+ ?? ' (?+ z) = ??+ ??'?+ xy'z = ??+ ??'+ xy'z — ??+ ?? ' [1+ z] = ??+ ?? ' [1] = ??+ ?? ' 25. ??'+ xyz)'+ ? (?+ ??')]' = [ ?( y'+yz)'+ ? (?+ ??')]' = [ y'+z)'+ ? (?+ = [ ?( y'+z)'+ ??+ ?.?)]' = [ (xy'+xz)'+ ??+ = [ ( xy'+xz)'+ = [ (??')'. (xz)'+ ?] ' = [ (?'+?”). (x'+z')+ ?] ' = [ (?'+?). (x'+z')+ ?] ' = [ (x'+yz')+ ?] ' = [?'+ yz'+ ?] ' = [ 1+ yz']' [ ?'+ ?? = ?'+ ?] [1+x=1] [ ?'+ ?? = ?'+ ?] [?+ ?? = ?] [?+ ?? = ?] [?+ ?? = ?] [1+?=1] [ ?'+ ?? = ?'+ ?]; [?+ ?'? = ?+ ?] [?+ ?? = ?] [ (?+ ?) (?+ z)= ?+ yz] [1+x=1] Department of lnformation Technology
  12. 26. [ (??+ z') ((?+ y)'+z) ] ' = [ (??+ z') ((?'. y')+z) ] ' = [ ??. ?'?'+ ??. z+ z'. ?'?'+ z'. zl' = [ 0+ xyz+ x'y'z'+ 0]' = [ xyz+ x'y'z' ] ' = (xyz)'. ( x'y'z')' 27. (?+ ?) (x'z'+ z) (?' + xz)' = (?+ ?) (x'z'+ z) (?”. (xz)') = (?+ ?) (?' + z) (?. (xz)') = (?+ ?) (?' + z) (?. (x'+z')) ( ?.?'+ xz+ ?'?+ yz) (?'?+ yz') = ( 0+ xz+ ?'?+ yz) (?'?+ yz') = (xz+ ?'?+ yz) (?'?+ yz') = xz. ?'?+ xz. yz'+ ?' ?. ?'?+ ?' ?. yz'+ yz. ?'?+ yz. yz' = 0+ 0+ ?'?+ x'yz'+ x'yz+ 0 — ?'?+ x'yz'+ x'yz 28. ?? (1, ?, 5, 7) = x'y'z+ x'yz+ xy'z+ xyz — x'z( ?'+?) + xz( ?'+?) = x'z (1)+ xz (1) — x'z+ xz [ ?+ ?'? [1+?=1] Department of lnformation Technology
  13. COMPLEMENT OF A FUNCTION: The complement of a function F is F' and is obtained from an interchange of o's for ?s and ?s for o's in the value of F. The complement of a function may be derived algebraically through DeMorgan's theorem. DeMorgan's theorems for any number of variables resemble in form the two- variable case and can be derived by successive substitutions similar to the method used in the preceding derivation. These theorems can be generalized as Find the complement of the following functions, 1. 2. F= x'yz'+ x'y'z F'= (x'yz'+ x'y'z)' = (x”+ y'+ z”) . (x”+ y”+Z') F= (xy + y 'z + xz) x. F' = [(xy + y'z + xz) x]' = (xy + y'z + xz)' + x' = [(xy)' . (y'z)'. (xz)'] + x' = [(x'+Y'). (Y+Z'). (x'+Z')] + X' = [(x'Y+ x'z'+ 0+ y'z') ( x'+Z')] + x' = x'x'Y+ x'x'z'+ x'y'z'+ x'yz'+ x'z'z'+ y'z'z'+ x' = x'Y+ x'z'+ x'y'z'+ x'yz'+ x'z'+ y'z'+ x' = x'Y+ x'z'+ x'z' (y' + y) + y'z'+ x' = x'Y+ x'z'+ x'z' (1) + y'z'+ x' = x'Y+ x'z'+ y'z'+ x' = x'Y+ x'+ x'z'+ y'z' = x'(Y+1) + x'Z+ y'z' = x' (1+z) + y'z' = x'+ y'z' Department of Information Technology
  14. ?. 4. 5. F= ? (y'z'+ yz) F'= [? (y'z'+yz)]' = ?'+ (y'z'+ yz)' = ?'+ (y'z')'. (yz)' F= ??' + ?' ? F'= (??'+ ?'?)' — (??')'. (?'?)' = (?'+?) (?+?') = ?'?+ ?'?'+ ??+ ??' = ?'?'+ ??. f = wx'y + ??' + wxz f = (wx'y + ??'+ wxz)' — (vvx'y)' (??')' (wxz)' = (w'x'+ w'Y+ ??'+ ??+ ?'?'+ ??') (w'+ ?'+ z') = (w'x'+ w'Y+ ??+ ?'?') (w'+ ?'+ z') = w'x'. w'+ w'y. w'+ ??. w'+ ?'?'. w'+ w'x'. x'+w'y. ?'+ ??. ?'+ ?'?'. ?'+ w'x'. z'+ w'y. z'+ ??. z'+ x'y'.z' = w'x'+ w'Y+ w'xy+ w'x'f+ w'x'+ w'x'Y+ ? + ?? + w'x'z'+ w'yz'+ xyz'+ x'y'z' = w'x'+ w'Y+ w'xy+ w'x'y'+ w'x'Y+ ?'?'+ w'x'z'+ w'yz'+ xyz'+ x'y'z' = w'x'( 1+ ?'+ ?+ z')+ w'y( 1+ ?+ z')+ ?'?'(1+ z')+ xyz' = w'x'(1)+ w'y(1)+ ?'?'(1)+ xyz' = w'x'+ w'Y+ ?'?'+ xyz' Department of lnformation Technology
  15. CANONICAL AND STANDARD FORMS: Minterms and Maxterms: A binary variable may appear either in its normal form (x) or in its complement form (x'). Now either two binary variables x and y combined with an AND operation. Since each variable may appear in either form, there are four possible combinations: x'y', x'y, xy' and xy Each of these four AND terms is called a 'minterm'. In a similar fashion, when two binary variables x and y combined with an OR operation, there are four possible combinations: x'+ y', x'+ y, x+ y' and x+ y Each of these four OR terms is called a 'maxterm'. The minterms and maxterms of a 3- variable function can be represented as in xyz = m7 table below. Variables Minterms Maxterms x 1 1 1 1 1 1 1 1 z 1 1 1 1 x'y'z' x'y'z x'yz' x'yz xy'z' xyz xyz' = mo — ml = m6 o 2 4 Sum of Minterm: (Sum of Products) The logical sum of two or more logical product terms is called sum of products expression. It is logically an OR operation of AND operated variables such as: 1. 2. Y- AC S urn Y- B C+ AC Product terms Department of Information Technology
  16. Sum of Maxterm: (Product of Sums) A product of sums expression is a logical product of two or more logical sum terms. It is basically an AND operation of OR operated variables such as, Product Sum tenns Canonical Sum of product expression: If each term in SOP form contains all the literals then the SOP is known as standard (or) canonical SOP form. Each individual term in standard SOP form is called minterm canonical form. F (A, B, C) = AB'C+ ABC+ ABC' Steps to convert general SOP to standard SOP form: 1. 2. 3. 4. Find the missing literals in each product term if any. AND each product term having missing literals by ORing the literal and its complement. Expand the term by applying distributive law and reorder the literals in the product term. Reduce the expression by omitting repeated product terms if any. Obtain the canonical SOP form of the function: 1. = AB+ AB'+ A'B. 2. Y (A, B, C) = A+ ABC = A. (B+ B'). (C+ C')+ ABC = (AB+ AB'). (C+ C')+ ABC = ABC+ ABC'+ AB'C+ AB'C'+ ABC = ABC+ ABC'+ AB'C+ AB'C' = 11174- m6-l- 1115 + m 4 Department of Information Technology
  17. 3. Y (A, B, C) BC = A. (B+ B'). (C+ A'). BC = (AB+ AB'). (C+ C')+ ABC+ A'BC = ABC+ ABC'+ AB'C+ AB'C'+ ABC+ A'BC = ABC+ ABC'+ AB'C+ AB'C'+ A'BC = 11174- m6-l- 1115 -l- m 4 + m3 Ern (3, 4, 5, 6, 7). 4. Y (A, B, C) = AC+ AB+ BC = AC (B+ B')+ AB (C+ C')+ BC (A+ A') = ABC+ AB'C+ ABC+ ABC'+ ABC+ A'BC = ABC+ AB'C+ ABC'+ A'BC Y (A, B, C, D) = AB+ ACD 5. - AB (C+ C') (D+ D') + ACD (B+ B') = (ABC+ ABC') (D+ D') + ABCD+ AB'CD = ABCD+ ABCD'+ ABC'D+ ABC'D'+ ABCD+ AB'CD = ABCD+ ABCD'+ ABC'D+ ABC'D'+ AB'CD. Canonical Product of sum expression: If each term in POS form contains all literals then the POS is known as standard (or) Canonical POS form. Each individual term in standard POS form is called Maxterm canonical form. Steps to convert general POS to standard POS form: 1. 2. 3. 4. Find the missing literals in each sum term if any. OR each sum term having missing literals by ANDing the literal and its complement. Expand the term by applying distributive law and reorder the literals in the sum term. Reduce the expression by omitting repeated sum terms if any. Department of Information Technology
  18. 0btain the canonical POS expression of the functions: [ ?+ ?? = (?+?) (?+?)] 5. = ?2. ??. ?? = ?? (?, 2, ?) = (?+?+?) (?+?+?') (?+?+?) (?'+?+?) (?+?+?) (?+?'+?) = (?+?+?) (?+?+?') (?'+?+?) (?+?'+?) = ??. ?1. ?4. ?2 = ?? (?, 1, 2, 4) = (?+?+?) (?+?+?') (?+?'+?) (? + ?'+?') (?+?+?) = (?+?+?) (?+?+?') (?+?'+?) (? + ?'+?') = ??. ?1. ?2. ?? = ?? (?, 1, 2, ?) = (?+?'+?) (.?+?'+?') (?+?+?) (?'+?+?) (?+?+?') (.?+?'+?') = (?+?'+?) (?+?'+?') (?+?+?) (?'+?+?) (?+?+?') = ?2. ??. ??. ?4. ?1 = ?? (?, 1, 2, 3, 4) ?= ??+ x'z = (??+ ?') (??+ z) Using distributive law, convert the function into 0R terms. = (?+?') (?+?') (X+Z) (Y+Z) = (?'+?) (X+Z) (Y+Z) = (?'+?+ z.z') (x+z+Y.y') (Y+Z+ ?.?') [?+ ?'=1] = ( ? ' + ? + 7, ) ( ? ' + ? + 7?) (??- ? + 7,) (? + y'-l- 7.) (??- ? 4- 7.4) ( ? ' + ? + Department of lnformation Technology
  19. = M4. M5. Mo.M2 = 11M (o, 2, 4, 5). KARNAUGH MAP MINIMIZATION: The simplification of the functions using Boolean laws and theorems becomes complex with the increase in the number of variables and terms. The map method, first proposed by Veitch and slightly improvised by Karnaugh, provides a simple, straightforward procedure for the simplification of Boolean functions. The method is called Veitch diagram or Karnaugh map, which may be regarded as a pictorial representation of a truth table. The Karnaugh map technique provides a systematic method for simplifying and manipulation of Boolean expressions. A K-map is a diagram made up of squares, with each square representing one minterm of the function that is to be minimized. For n variables on a Karnaugh map there are 2n numbers of squares. Each square or cell represents one of the minterms. It can be drawn directly from either minterm (sum-of- products) or maxterm (product-of-sums) Boolean expressions. Two- Variable, Three Variable and Four Variable Maps Karnaugh maps can be used for expressions with two, three, four and five variables. The number of cells in a Karnaugh map is equal to the total number of possible input variable combinations as is the number of rows in a truth table. For three variables, the number of cells is 23 = 8. For four variables, the number of cells is 24 = 16. fiä Äfiä Ä CD ÄÉc BC ÄBC ABC ÄBä ABä 1 -Variable map 2 -Variable map CD 3 -Variable map AB äö ÄÉäö AB ÄBäÖ AB ABäÖ A g A Éäö ÄÉäD ÄBäD ABäD A ÉäD ÄBCD ÄBCÖ ABCD ABCD GC•D GC•Ö 4 -Variable map Department of Information Technology
  20. Product terms are assigned to the cells of a K-map by labeling each row and each column of a map with a variable, with its complement or with a combination of variables & complements. The below figure shows the way to label the rows & columns of a 1, 2, 3 and 4- variable maps and the product terms corresponding to each cell. It is important to note that when we move from one cell to the next along any row or from one cell to the next along any column, one and only one variable in the product term changes (to a complement or to an uncomplemented form). Irrespective of number of variables the labels along each row and column must conform to a single change. Hence gray code is used to label the rows and columns of K-map as shown ow. Gray code Sequence BC 1 Inn ml 1 o Ina 1 Ina 01 1 111.0 nu 11 1117 10 Ina nu 1 -Variable map 2 -Variable map C D Gtzy code Sequence 3 -Variable map 00 Gray cade Sequence 01 11 10 m.o nu ma 01 1115 11M 3 mg 11 1117 10 ma nu 4- Variable map Grouping cells for Simplification: The grouping is nothing but combining terms in adjacent cells. The simplification is achieved by grouping adjacent I's or o's in groups of 2i, where i n and n is the number of variables. When adjacent I's are grouped then we get result in the sum of product form; otherwise we get result in the product of sum form. Department of Information Technology
  21. Grouping Two Adjacent I's: (Pair) In a Karnaugh map we can group two adjacent I's. The resultant group is called Pair. 10 AB moo ABD 113 aleua AB 10 AB BCD ABD 10 AB aaoa ABD Examples of Pairs ABD BCD Grouping Four Adjacent I's: (Quad) In a Karnaugh map we can group four adjacent I's. The resultant group is called Quad. Fig (a) shows the four I's are horizontally adjacent and Fig (b) shows they are vertically adjacent. Fig (c) contains four I's in a square, and they are considered adjacent to each other. 10 AB 10 AB 10 AB 10 AB
  22. Examples of Ouads The four I's in fig (d) and fig (e) are also adjacent, as are those in fig (f) because, the top and bottom rows are considered to be adjacent to each other and the leftmost and rightmost columns are also adjacent to each other. Grouping Eight Adjacent I's: (Octet) In a Karnaugh map we can group eight adjacent I's. The resultant group is called Octet. 10 AB 010010 10 10 AB 10 AB •goo Simplification of Sum of Products Expressions: (Minimal Sums) The generalized procedure to simplify Boolean expressions as follows: 1. Plot the K-map and place I's in those cells corresponding to the I's in the sum of product expression. Place o's in the other cells. 2. Check the K-map for adjacent I's and encircle those I's which are not adjacent to any other I's. These are called isolated I's. 3. Check for those I's which are adjacent to only one other 1 and encircle such pairs. Department of Information Technology
  23. 4. 5. 6. Check for quads and octets of adjacent I's even if it contains some I's that have already been encircled. While doing this make sure that there are minimum number of groups. Combine any pairs necessary to include any I's that have not yet been grouped. Form the simplified expression by summing product terms of all the groups. Three- Variable Map: 1. Simplify the Boolean expression, F(x, y, z) Soln: x o o 01 o 11 1 1 3 F = yz+ xz' 2. F(x, y, z) Soln: x o x 00 01 1 o 2, 1 11 o 3 10 10 1 x o o x 1 o x 01 o 01 o 11 1 11 o 10 10 1 F = z'+ xy' 3. F=A'C+A'B+AB'C+BC Soln: = A'C (B+ B') + A'B (C+ C') + AB'C + BC (A+ A') = A'BC+ A'B'C + A'BC + A'BC' + AB'C + ABC + A'BC = A'BC+ A'B'C + A'BC' + AB'C + ABC = myl- ml -l- 1115 -l- 1117 Department of Information Technology
  24. BC Éä Éc BC 01 F=C+A'B 10 4. BC BC Bä AB'C + A'B'C + A'BC + AB'C' +A'B'C' Soln: BC Éä F=A'C+B' 01 01 BC 01 Four - Variable Map: 1. Simplify the Boolean expression, Y = A'BC'D' + A'BC'D + ABC'D' + ABC'D + AB'C'D + A'B'CD' Soln: Therefore, äö äD c D c b Ääcfi ACO A'B'CD'+ AC'D+ BC' Department of Information Technology
  25. - E mW, 1, 2, 4, 5, 6, 8, 9, 12, 13, 14) Soln: Therefore, F= y' + w'z'+ xz' 3. F- A'B'C'+ B'CD'+ A'BCD'+ AB'C' ji jz = A'B'C' (D+ D') + B'CD' (A+ A') + A'BCD'+ AB'C' (D+ D') = A'B'C'D+ A'B'C'D'+ AB'CD'+ A'B'CD'+ A'BCD'+ AB'C'D+ AB'C'D' m (0, 1, 2, 6, 8, 9, 10) Therefore, F- B'D'+ B'C'+ A'CD'. äö ä D c D C ö Äc:f) Department of Information Technology
  26. 4. ABCD+ AB'C'D'+ AB'C+ AB = ABCD+ AB'C'D'+ AB'C (D+D')+ AB (C+C') (D+D') = ABCD+ AB'C'D'+ AB'CD+ AB'CD'+ (ABC+ ABC') (D+ D') = ABCD+ AB'C'D'+ AB'CD+ AB'CD'+ ABCD+ ABCD'+ ABC'D+ ABC'D' = ABCD+ AB'C'D'+ AB'CD+ AB'CD'+ ABCD'+ ABC'D+ ABC'D' = m15+ m8-l- mn -l- IT110+ mu-l- m13+ IT112 - m (8, 10, 11, 12, 13, 14, 15) a ô CD cô Therefore, AB+ AC+ AD'. 5. Y (A, B, C, m (7, 9, 10, 11, 12, 13, 14, 15) Therefore, AB+ AC+ AD+BCD. Department of Information Technology CD AC BCD AC AD
  27. 6. A'B'C'D+ A'BC'D+ A'BCD+ A'BCD'+ ABC'D+ ABCD+ AB'CD m (1, 5, 6, 7, 11, 13, 15) äö äD c D Cö ACD ABC ABD ACD In the above K-map, the cells 5, 7, 13 and 15 can be grouped to form a quad as indicated by the dotted lines. In order to group the remaining I's, four pairs have to be formed. However, all the four I's covered by the quad are also covered by the pairs. So, the quad in the above k-map is redundant. Therefore, the simplified expression will be, Y = A'C'D+ A'BC+ ABD+ ACD. 7. m (1, 5, 10, 11, 12, 13, 15) Therefore, A'C'D+ ABC'+ ACD+ AB'C. ACD äö äD c D Cö ACD ABC Department of Information Technology
  28. 8. A'B'CD'+ ABCD'+ AB'CD'+ AB'CD+ AB'C'D'+ ABC'D'+ A'B'CD+ A'B'C'D' äö c D Cö Therefore, AD'+ B'C+ B'D' 9. F (A, B, C, D) m (0, 1, 4, 8, 9, 10) äö äD CD cn ACD Therefore, A'C'D'+ AB'D'+ B'C'. Simplification of Sum of Products Expressions: (Minimal Sums) ABD = Ml. M3. M7. M4. Mo BC Éä Éc BC Bä AC 01 10 Department of Information Technology
  29. Y' = B'C'+ A'C+BC. Y" = (B'C'+ A'C+ BC)' - (B'C')'. (A'C)'. (BC)' = (B"+ C"). (A"+C'). (B'+ C') Y = (B+ C). (A+C'). (B'+ C') = M12. M14. M15. M8. M6. M7. Mo. M13 = 11M (o, 6, 7, 8, 12, 13, 14, 15) CD tö CD CD CC, 01 01 Y' = B'C'D'+ AB+ BC Y" = (B'C'D'+ AB+ BC)' = (B'C'D')'. (AB)'. (BC)' = (B"+ C"+D"). (A'+B'). (B'+ C') Therefore, (B+ C+ D). (A'+ B'). (B'+ C') 3. F(A, B, C, 11M (o, 2, 3, 8, 9, 12, 13, 14, 15) CD äö CID CD CD 01 10 Y' = A'B'D'+ A'B'C+ ABD+ AC' Department of Information Technology Äiö Ric ABD
  30. Y" = (A'B'D'+ A'B'C+ ABD+ AC')' - (A'B'D')'. (A'B'C)'. (ABD)'. (AC')' Therefore, Y = (A + B-l- D). (A-F B-l- (A' + B' + (A' + C) 4. F(A, B, C, Em (o, 1, 2, 5, 8, 9, 10) = 11M (3, 4, 6, 7, 11, 12, 13, 14, 15) CD äö CID CD CD 01 10 CID CD CD 00 AB 11 10 Y' = BD'+ CD+ AB Y" = (BD'+ CD+ AB)' - (CD)'. (AB)' Therefore, (B'+ D). (C'+ D'). (A'+ B') Don't care Conditions: A don't care minterm is a combination of variables whose logical value is not specified. When choosing adjacent squares to simplify the function in a map, the don't care minterms may be assumed to be either o or 1. When simplifying the function, we can choose to include each don't care minterm with either the I's or the o's, depending on which combination gives the simplest expression. 1. F (x, y, z) = Em (o, 1, 2, 4, 5)+ Ed (3, 6, 7) yz "z yz yä Department of Information Technology
  31. 2. F (w, x, y, z) = Em (1, 3, 7, 11, 15)+ Yd (o, 2, 5) wx x F (w, x, y, z) = w'x'+ yz 3. F (w, x, y, z) = Em (o, 7, 8, 9, 10, wx F (w, x, y, z) = w'xz+ wy' + x'z'. 12)+ Yd (2, nwx wx 5, 13) wx jž jz jž 9z jž 9z wxz 4. F (w, x, y, z) = Em (o, 1, 4, 8, 9, 10)+ Yd (2, 11) Soln: Wjž F (w, x, y, z) = wx'+ x' y' + w'y'z'. Department of Information Technology
  32. 5. A, B, C, D) = (o, 6, 8, 13, 14)+ Ed (2, 4, 10) Soln: 01 10 01 x A, B, C, D) = CD'+ B'D'+ A'B'C'D'. Five- Variable Maps: äö CID CD CD ABCD A 5- variable K- map requires 32 cells, but adjacent cells are difficult to identify on a single 32-cell map. Therefore, two 16 cell K-maps are used. If the variables are A, B, C, D and E, two identical 16- cell maps containing B, C, D and E can be constructed. One map is used for A and other for A'. In order to identify the adjacent grouping in the 5- variable map, we must imagine the two maps superimposed on one another ie., every cell in one map is adjacent to the corresponding cell in the other map, because only one variable changes between such corresponding cells. DE O 01 10 11 01 00 16 25 31 24 Five- Variable Karnaugh map (Layer Structure) Department of Information Technology
  33. Thus, every row on one map is adjacent to the corresponding row (the one occupying the same position) on the other map, as are corresponding columns. Also, the rightmost and leftmost columns within each 16- cell map are adjacent, just as they are in any 16- cell map, as are the top and bottom rows. DE DE DE DE Adjacent Adjacent calurnns DE DE DE DE / Adjacent —Adjacent --- --—— cells A djacent gnaups Typical subcubes on a five-variable map However, the rightmost column of the map is not adjacent to the leftmost column of the other map. 1. Simplify the Boolean function F (A, B, C, D, E) = Em (o, 2, 4, 6, 9, 11, 13, 15, 17, 21, 25, 27, 29, 31) Soln: ABE DE DE DE F (A, B, C, D, E) = A'B'E'+ BE+ AD'E ADE DE DE DE Department of Information Technology
  34. - Em (o, 5, 6, 8, 9, 10, 11, 16, 20, 24, 25, 26, 27, 29, 31) Soln: ÂÛCÔE tôÉ DE DE DE DE DE DÉ ÂÛCDÉ ABDE F (A, B, C, D, E) = C'D'E'+ A'B'CD'E+ A'B'CDE'+ AB'D'E'+ ABE+ BC' 3. F (A, B, C, D, E) = ( 1, 4, 8, 10, 11, 20, 22, 24, 25, 26)+Ed (o, 12, 16, 17) Soln: ÂôÉ DE DE DE DÉ ABE ABCE ACD ABCD F (A, B, C, D, E) = B'C'D'+ A'D'E'+ BC'E'+ A'BC'D+ AC'D'+ AB'CE' Department of Information Technology
  35. 4. (?, ?, ?, D, ?) = ?? (?, 1, 2, 6, 7, 9, 12, 28, 29, 31) Soln: ???? ???? ???? ???? ???? F (?, ?, ?, D, ?) = BCD'E'+ ????+ ?'?'?'?'+ A'C'D'E+ A'B'CD 5. F (?, ?, ??, ?, ?5) = ?? (2, ?, 6, 7, 11, 12, 13, 14, 15, 23, 28, 29, 30, 31 ) Soln: ?: ?I?2?4 ?4?5 ?4?5 ??? ??? ?4?5 ?2?? ?2?? ???4?? ?1???4?? ?2?? ???? ?4?5 ?2?? 0 ?2?? 0 ?2?? ?2?? 0 F (?, ?, ??, ?, ?5) = ???+ ???4?5+ ? '?2'?4+ ? '??'?4?5 Department of lnformation Technology
  36. Soln: X4X5 X2X3 XlX2X3X5 XZXB 9, 14, 17, 24, 25, 26, 27, 30, 31 )+ Ed (4, 5) X2X3 X4X5 XaX4X5 X2X3 X2Xs 0 X2X3 XlX2X4 X2XBX4X5 F (Xl, X2, X3, X4, X5) = X2X3'X4'+ X2X3X4X5'+ X3'X4'X5+ XlX2X4+ 'X2'X3X5'+ 'X2'X3'X4 LOGIC GATES BASIC LOGIC GATES: Logic gates are electronic circuits that can be used to implement the most elementary logic expressions, also known as Boolean expressions. The logic gate is the most basic building block of combinational logic. There are three basic logic gates, namely the OR gate, the AND gate and the NOT gate. Other logic gates that are derived from these basic gates are the NAND gate, the NOR gate, the EXCLUSIVE- OR gate and the EXCLUSIVE-NOR gate. GATE NOT (7404) AND (7408) SYMBOL OPERATION NOT gate (Invertion), produces an inverted output pulse for a given input pulse. AND gate performs logical multiplication. The output is HIGH only when all the inputs are HIGH. When any of the inputs are low, the output is LOW. Department of Information Technology TRUTH TABLE
  37. OR (7432) NAND (7400) NOR (7402) EX- OR (7486) EX- NOR Y ASB ASB ASB OR gate performs logical addition. It produces a HIGH on the output when any of the inputs are HIGH. The output is LOW only when all inputs are LOW. It is a universal gate. When any of the inputs are LOW, the output will be HIGH. LOW output occurs only when all inputs are HIGH. It is a universal gate. LOW output occurs when any of its input is HIGH. When all its inputs are LOW, the output is HIGH. The output is HIGH only when odd number of inputs is HIGH. The output is HIGH only when even number of inputs is HIGH. Or when all inputs are zeros. o o 1 1 o o 1 1 o o 1 1 o o 1 1 o 1 1 o 1 o 1 o 1 o 1 o 1 o 1 o 1 o 1 o 1 o 1 o 1 1 1 1 1 1 1 0 ASB 1 1 ASB 1 o 1 UNIVERSAL GATES: The NAND and NOR gates are known as universal gates, since any logic function can be implemented using NAND or NOR gates. This is illustrated in the following sections. a) NAND Gate: The NAND gate can be used to generate the NOT function, the AND function, Department of Information Technology
  38. the OR function and the NOR function. i) By connecting all the inputs together and creating a single common input. NOT function using NAND gate ii) AND function: By simply inverting output of the NAND gate. i.e., AB = AB iii) OR function: AB = AB AND function using NAND gates By simply inverting inputs of the NAND gate. i.e., OR function using NAND gates Department of Information Technology
  39. Bubble at the input of NAND ate indicates inverted in ut. iv) NOR function: By inverting inputs and outputs of the NAND gate. NOR function using NAND gates b) NOR Gate: Similar to NAND gate, the NOR gate is also a universal gate, since it can be used to generate the NOT, AND, OR and NAND functions. i) NOT_functiQ.n: By connecting all the inputs together and creatin a sin le common input. NOT function using NOR gates Department of Information Technology
  40. ii) QR_mctjon: By simply inverting output of the NOR gate. i.e., OR function using NOR gates iii) AND function: By simply inverting inputs of the NOR gate. i.e., AND function using NOR gates Bubble at the input of NOR ate indicates inverted in ut. Truth table Department of Information Technology
  41. iv) NAND Function: By inverting inputs and outputs of the NOR gate. NAND function using NOR gates Conversion of AND/OR/NOT to NAND/NOR: 1. 2. 3. 4. 5. 1. Draw AND/OR logic. If NAND hardware has been chosen, add bubbles on the output of each AND gate and bubbles on input side to all OR gates. If NOR hardware has been chosen, add bubbles on the output of each OR gate and bubbles on input side to all AND gates. Add or subtract an inverter on each line that received a bubble in step 2. Replace bubbled OR by NAND and bubbled AND by NOR. Eliminate double inversions. Implement Boolean expression using NAND gates: Original Circuit: C Department of Information Technology
  42. Soln: NAND Circuit: Elirninatian af double inversion Elirrdnatian af double inversion Department of Information Technology
  43. 2. Soln: gate. Implement Boolean expression for EX-OR gate using NAND gates. AB AB+ AB AB Adding bubbles on the output of each AND gates and on the inputs of each OR Adding an inverter on each line that received bubble, Eliminating double inversion, Department of Information Technology
  44. Replacing inverter and bubbled OR with NAN D, we have = ÄB+ Afi Department of Information Technology

Need a Tutor or Coaching Class?

Post an enquiry and get instant responses from qualified and experienced tutors.

Post Requirement

Related Study Notes

Upload Study Notes

If you have your own Study Notes which you think can benefit others, please upload on LearnPick. For each approved Study Note you will get 100 Credit Points and 100 Activity Score which will increase your profile visibility.

Upload Now
Home > Study Notes > DPSD Notes