EC3352 Digital Systems Design Lecture Notes PDF

EnggTree.com EC3352 DSD IIYR/III SEM R2021 MSAJCE/ECE LECTURE NOTES EC3352-DIGITAL SYSTEM DESIGN II YEAR – III SEMESTER –...

EnggTree.com EC3352 DSD IIYR/III SEM R2021 MSAJCE/ECE LECTURE NOTES EC3352-DIGITAL SYSTEM DESIGN II YEAR – III SEMESTER – R2021 UNIT- I BASIC CONCEPTS 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 0 and 1, 0 Є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 Є S with the property, e* x = x * e = x Eg: 0+ 0 = 0 0+1=1+0=1 a) x+ 0= x 1.1=1 1.0=0.1=1 b) x. 1 = x iii) Commutative law: A binary operator * on a set S is said to be commutative if, x*y=y*x for all x, y Є S 1 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD IIYR/III SEM R2021 MSAJCE/ECE Eg: 0+ 1 = 1+ 0 = 1 a) x+ y= y+ x 0.1=1.0=0 b) x. y= y. x iv) Distributive law: If * and are two binary operation on a set S, is said to be distributive over + whenever, x. (y+ z) = (x. y) + (x. z) Similarly, + is said to be distributive over whenever, x + (y. z) = (x+ y). (x+ z) 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 Є S, there exists an element x’ Є S such that, x. x’ Є e a) x+ x’ = 1, since 0 + 0’ = 0+ 1 and 1+ 1’ = 1+ 0 = 1 b) x. x’ = 1, since 0. 0’ = 0. 1 and 1. 1’ = 1. 0 = 0 Summary: Postulates of Boolean algebra: POSTULATES (a) (b) Postulate 2 (Identity) x+0=x x.1=x Postulate 3 (Commutative) x+ y = y+ x x. y = y. x Postulate 4 (Distributive) x (y+ z) = xy+ xz x+ yz = (x+ y). (x+ z) Postulate 5 (Inverse) x+x’ = 1 x. x’ = 0 Basic theorem and properties of Boolean algebra: Basic Theorems: 2 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD IIYR/III SEM R2021 MSAJCE/ECE 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 x+ x = (x+ x). 1------------------- by postulate 2(b) [ x. 1 = x ] = (x+ x). (x+ x’)------------------- 5(a) [ x+ x’ = 1] = x+ xx’------------------- 4(b) [ x+yz = (x+y)(x+z)] = x+ 0------------------- 5(b) [ x. x’ = 0 ] = x------------------- 2(a) [ x+0 = x ] b) x. x = x x. x = (x. x) + 0------------------- by postulate 2(a) [ x+ 0 = x ] = (x. x) + (x. x’)------------------- 5(b) [ x. x’ = 0] = x ( x+ x’)------------------- 4(a) [ x (y+z) = (xy)+ (xz)] = x (1)------------------- 5(a) [ x+ x’ = 1 ] = x------------------- 2(b) [ x.1 = x ] 2) a) x+ 1 = 1 x+ 1 = 1. (x+ 1)------------------- by postulate 2(b) [ x. 1 = x ] = (x+ x’). (x+ 1)------------------- 5(a) [ x+ x’ = 1] = x+ x’.1------------------- 4(b) [ x+yz = (x+y)(x+z)] = x+ x’------------------- 2(b) [ x. 1 = x ] = 1------------------- 5(a) [ x+ x’= 1] b) x.0 = 0 3) (x’)’ = x From postulate 5, we have x+ x’ = 1 and x. x’ = 0, which defines the complement of x. The complement of x’ is x and is also (x’)’. Therefore, since the complement is unique, (x’)’ = x. 4) Absorption Theorem: a) x+ xy = x 3 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD IIYR/III SEM R2021 MSAJCE/ECE x+ xy = x. 1 + xy------------------- by postulate 2(b) [ x. 1 = x ] = x (1+ y)------------------- 4(a) [ x (y+z) = (xy)+ (xz)] = x (1)------------------- by theorem 2(a) [x+ 1 = x] = x.------------------- by postulate 2(a) [x. 1 = x] b) x. (x+ y) = x x. (x+ y) = x. x+ x. y------------------- 4(a) [ x (y+z) = (xy)+ (xz)] = x + x.y------------------- by theorem 1(b) [x. x = x] = x.------------------- by theorem 4(a) [x+ xy = x] c) x+ x’y = x+ y x+ x’y = x+ xy+ x’y------------------- by theorem 4(a) [x+ xy = x] = x+ y (x+ x’)------------------- by postulate 4(a) [ x (y+z) = (xy)+ (xz)] = x+ y (1)------------------- 5(a) [x+ x’ = 1] = x+ y------------------- 2(b) [x. 1= x] d) x. (x’+y) = xy x. (x’+y) = x.x’+ xy------------------- by postulate 4(a) [ x (y+z) = (xy)+ (xz)] = 0+ xy------------------- 5(b) [x. x’ = 0] = xy.------------------- 2(a) [x+ 0= x] Properties of Boolean algebra: 1. Commutative property: Boolean addition is commutative, given by x+ y = y+ x 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, x. y = y. x This means that the order of the AND operation conducted on the variables makes no difference. 2. Associative property: 4 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD IIYR/III SEM R2021 MSAJCE/ECE The associative property of addition is given by, A+ (B+ C) = (A+B) + C 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, A. (B. C) = (A.B). C It makes no difference in what order the variables are grouped during the AND operation of several variables. 3. Distributive property: 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 A. (B+C) = (A.B)+ (A.C) 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 1’s by 0’s and 0’s by 1’s. x+ x’ = 1 is x. x’ = 0 Duality is a very important property of Boolean algebra. 5 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD IIYR/III SEM R2021 MSAJCE/ECE Summary: Theorems of Boolean algebra: THEOREMS (a) (b) x+x=x x.x=x 1 Idempotent x+1=1 x.0=0 2 Involution (x’)’ = x 3 x+ xy = x x (x+ y) = x Absorption x+ x’y = x+ y x. (x’+ y)= xy 4 Associative x+(y+ z)= (x+ y)+ z x (yz) = (xy) z 5 DeMorgan’s Theorem (x+ y)’= x’. y’ (x. y)’= x’+ y’ 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. (A+ B)’ = A’. B’ 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) 6 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD IIYR/III SEM R2021 MSAJCE/ECE 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) = xx’+ xy [ x. x’= 0 ] = 0 + xy [ x+ 0 = x ] = xy. 2. x+ x’y = x + xy + x’y [ x+ xy= x] = x+ y (x+x’) = x+ y (1) [ x+ x’ = 1] = x+ y. 3. (x+ y) (x+ y’) = x.x+ xy’+ xy+ yy’ = x+ xy’+ xy+ 0 [ x. x= 0]; [ y. y’= 0] = x (1+ y’+ y) = x (1) [ 1+y= 1 ] = x. 4. xy + x’z + yz. = xy + x’z + yz( x+ x’) [ x+ x’= 1] = xy + x’z + xyz + x’yz Re-arranging, = xy + xyz + x’z +x’yz = xy (1+ z) + x’z (1+y) [1+y= 1] = xy+ x’z. 5. xy+ yz+ y’z = xy+ z ( y+ y’) = xy+ z ( 1 ) [ y+ y’ = 1] = xy+ z. 7 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD IIYR/III SEM R2021 MSAJCE/ECE 6. (x+ y) (x’+ z) (y+ z) = (x+ y) (x’+ z) [ dual form of consensus theorem, (A+ B) (A’+ C) (B+ C) = (A+ B) (A’+ C) ] 7. x’y+ xy+ x’y’ = y ( x’+ x) + x’y’ [ x (y+ z) = xy+ xz ] = y ( 1 ) + x’y’ [ x+ x’ = 1] = y+ x’y’ [ x+ x’y’ = x+ y’ ] = y+ x’. 8. x+ xy’+ x’y = x (1+ y’)+ x’y = x (1) + x’y [ 1+ x = 1 ] = x+ x’y [ x+ x’y = x+ y ] = x+ y. 9. AB + (AC)' + AB’C (AB + C) = AB + (AC)' + AAB'BC + AB'CC = AB + (AC)' + 0+ AB'CC [B.B' = 0] = AB + (AC)' + AB'C [C.C = 1] = AB + A' + C' +AB'C [(AC)' = A' + C'] = AB+A’+C'+AB' [C’ + AB’C = C’ + AB’] = A' + B+ C’+ AB’ [A’+AB=A’+B] Re- arranging, =A'+AB’+B+C' [A’+AB=A’+B] =A'+B’+B+C' [B’+B=1] = A'+1+C’ [ A+ 1=1] =1 10. (x’+ y) (x+ y) = x’.x+ x’y+ yx+ y.y = 0+ x’y+ xy+ y [ x.x’= 0]; [ x. x= x] = y ( x’+ x+ 1) = y( 1 ) [ 1+ x = 1 ] = y. 11. xy+ xyz+ xy (w+ z) = xy ( 1+ z+ w+ z) 8 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD IIYR/III SEM R2021 MSAJCE/ECE = xy ( 1 ) [ 1+ x = 1 ] = xy. 12. xy+ xyz+ xyz’+ x’yz = xy ( 1+ z+ z’)+ x’yz = xy ( 1 ) + x’yz [ 1+ x = 1 ] = xy+ x’yz = y ( x+ x’z ) [ x+ x’y = x+ y] = y ( x+ z ). 13. xyz+ xy’z+ xyz’ = xy (z+ z’) + xy’z = xy+ xy’z [ x+ x’= 1] = x(y+ y’z) [ x+ x’y = x+ y] = x(y+ z) 14. x’y’z’+ x’yz’+ xy’z’+ xyz’ = x’z’ (y’+ y)+ xz’ (y’+ y) = x’z’+ xz’ [ x+ x’= 1] = z’ (x’+ x) = z’ [ x+ x’= 1] 15. w’xyz’+ xyz’+ xy’z’+ xy’z = xyz’ (w’+ 1) + xy’z’+ xy’z = xyz’+ xy’z’+ xy’z [ 1+ x = 1 ] = xz’ (y+ y’) + xy’z = xz’+ xy’z [ x+ x’= 1] = x (z‘+ y’z) = x (z’+ y’). [ x’+ xy’ = x’+ y’] 16. w’xy’z+ w’xyz+ wxz = w’xz (y’+ y)+ wxz = w’xz (1)+ wxz [ x+ x’= 1] = w’xz+ wxz = xz (w’+ w) = xz. [ x+ x’= 1] 17. x’y’z’+ x’y’z+ x’yz’+ x’yz+ xy’z’ = x’y’ (z’+z) + x’y (z’+z)+ xy’z’ = x’ y’ (1) + x’y (1)+ xy’z’ [ x+ x’= 1] = x’y’ + x’y + xy’z’ = x’(y’+y) + xy’z’ 9 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD IIYR/III SEM R2021 MSAJCE/ECE = x’ (1) + xy’z’ [ x+ x’= 1] = x’ + xy’z’ = x’+ y’z’. [ x’+ xy’ = x’+ y’] 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 [ x’’ = x] = 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 [x. x’= 0] 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+ x’= 1] = x’y+ w’z’ (y+x) [ x+ x’y = x+ y] 19. xy+ x (y+ z) + y (y+ z) = xy+ xy+ xz+ yy+ yz = xy+ xz+ y+ yz [x+ x= x]; [x. x= x] = xy+ xz+ y [x+ xy= x] = y+ xz [x+ xy= x] 20. [ xy’ (z+ wy) + x’y’] z = [ xy’z+ xy’wy+ x’y’] z = [ xy’z+ 0+ x’y’] z [x. x’= 0] = xy’z. z+ x’y’z = xy’z+ x’y’z [x. x= x] = y’z (x+ x’) = y’z (1) [ x+ x’= 1] = y’z. 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 [ x+ x’= 1] = yz+ y’z’ (1) + xy’z [ x+ x’= 1] = yz+ y’z’+ xy’z = yz+ y’ (z’+ xz) = yz+ y’ (z’+ x) [ x’+ xy = x’+ y] = yz+ y’z’+ xy’ 22. [(xy)’+ x’+ xy]’ = [ x’+ y’+ x’+ xy]’ = [ x’+ y’+ xy]’ [x+ x= x] 10 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD IIYR/III SEM R2021 MSAJCE/ECE = [x’+ y’+ x]’ [ x’+ xy = x’+ y] = [y’+ 1]’ [ x+ x’= 1] = [ 1 ]’ [ 1+ x = 1 ] = 0. 23. [ xy+ xz]’+ x’y’z = (xy)’. (xz)’+ x’y’z = (x’+ y’). (x’+ z’)+ x’y’z = x’x’+ x’z’+ x’y’+ y’z’+ x’y’z = x’+ x’z’+ x’y’+ y’z’+ x’y’z[x+ x= x] = x’+ x’z’+ x’y’+ y’ [z’+ x’z] = x’+ x’z’+ x’y’+ y’ [z’+ x’] [ x’+ xy = x’+ y] = x’+ x’y’+ y’ [z’+ x’] [x+ xy = x] = x’+ x’y’+ y’z’+ x’y’ = x’+ y’z’+ x’y’ [x+ xy = x] = x’+ y’z’. [x+ xy = x] 24. xy+ xy’( x’z’)’ = xy+ xy’ (x’’+ z’’) = xy+ xy’ (x+ z) [x’’ = x] = xy+ xy’x+ xy’z = xy+ xy’+ xy’z [x. x= x] = xy+ xy’ [1+ z] = xy+ xy’ [ 1+ x = 1 ] = xy+ xy’ = x( y+ y’) = x [ x+ x’= 1] = x. 25. [( xy’+ xyz)’+ x (y+ xy’)]’ = [ x( y’+yz)’+ x (y+ xy’)]’ = [ x( y’+z)’+ x (y+ x)]’ [ x’+ xy = x’+ y]; [ x+ x’y = x+ y] = [ x( y’+z)’+ xy+ x.x)]’ = [ (xy’+xz)’+ xy+ x)]’ [x. x= x] = [ ( xy’+xz)’+ x)]’ [x+ xy = x] = [ (xy’)’. (xz)’+ x]’ = [ (x’+y’’). (x’+z’)+ x]’ = [ (x’+y). (x’+z’)+ x]’ [x’’ = x] = [ (x’+ yz’)+ x]’ [ (x+ y) (x+ z)= x+ yz] = [ x’+ yz’+ x]’ = [ 1+ yz’]’ [ x+ x’= 1] = ’ [ 1+ x = 1 ] = 0. 11 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD IIYR/III SEM R2021 MSAJCE/ECE 26. [ (xy+ z’) ((x+ y)’+z) ]’ = [ (xy+ z’) ((x’. y’)+z) ]’ = [ xy. x’y’+ xy. z+ z’. x’y’+ z’. z]’ = [ 0+ xyz+ x’y’z’+ 0]’ [x. x’= 0] = [ xyz+ x’y’z’ ]’ = (xyz)’. ( x’y’z’)’ = ( x’+ y’+ z’). (x’’+ y’’+ z’’) = ( x’+ y’+ z’). (x+ y+ z). [x’’ = x] 27. (x+ y) (x’z’+ z) (y’+ xz)’ = (x+ y) (x’z’+ z) (y’’. (xz)’) = (x+ y) (x’+ z) (y. (xz)’) [ x+ x’y = x+ y]; [x’’ = x] = (x+ y) (x’+ z) (y. (x’+z’)) = ( x.x’+ xz+ x’y+ yz) (x’y+ yz’) = ( 0+ xz+ x’y+ yz) (x’y+ yz’) = (xz+ x’y+ yz) (x’y+ yz’) = xz. x’y+ xz. yz’+ x’y. x’y+ x’y. yz’+ yz. x’y+ yz. yz’ = 0+ 0+ x’y+ x’yz’+ x’yz+ 0 [x. x’= 0]; [x. x= x] = x’y+ x’yz’+ x’yz = x’y (1+ z’+ z) = x’y (1) [ 1+ x = 1 ] = x’y. 28. Y= ∑m (1, 3, 5, 7) = x’y’z+ x’yz+ xy’z+ xyz = x’z( y’+y) + xz( y’+y) = x’z (1)+ xz (1) [ x+ x’= 1] = x’z+ xz = z( x’+ x) = z (1) [ x+ x’= 1] = z. 12 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD IIYR/III SEM R2021 MSAJCE/ECE COMPLEMENT OF A FUNCTION: The complement of a function F is F’ and is obtained from an interchange of 0’s for 1’s and 1’s for 0’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 – (A+B+C+D+…+F)’=A’B’C’D’…F’ (A B C D … F)’ = A’+B’+ C’+ D’+ … +F’. Find the complement of the following functions, 1. F= x’yz’+ x’y’z F’= (x’yz’+ x’y’z)’ = (x”+ y’+ z”). (x”+ y”+z’) = (x+ y’+ z). (x+ y+ z’). 2. 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+ x = x], [x. x = x] = x’y+ x’z’+ x’z’ (y’+ y) + y’z’+ x’ [x+ x’= 1] = 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’ [y+1= 1] = x’ (1+z) + y’z’ [y+1= 1] = x’+ y’z’ 13 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD IIYR/III SEM R2021 MSAJCE/ECE 3. F= x (y’z’+ yz) F’= [x (y’z’+ yz)]’ = x’+ (y’z’+ yz)’ = x’+ (y’z’)’. (yz)’ = x’+ (y”+ z”). (y’+ z’) = x’+ (y+ z). (y’+ z’). 4. F= xy’+ x’y F’= (xy’+ x’y)’ = (xy’)’. (x’y)’ = (x’+y) (x+y’) = x’x+ x’y’+ yx+ yy’ = x’y’+ xy. 5. f = wx’y + xy’+ wxz f’ = (wx’y + xy’+ wxz)’ = (wx’y)’ (xy’)’ (wxz)’ = (w’+x+ y’) (x’+ y) (w’+ x’+ z’) = (w’x’+ w’y+ xx’+ xy+ x’y’+ yy’) (w’+ x’+ z’) = (w’x’+ w’y+ xy+ x’y’) (w’+ x’+ z’) = w’x’. w’+ w’y. w’+ xy. w’+ x’y’. w’+ w’x’. x’+w’y. x’+ xy. x’+ x’y’. x’+ w’x’. z’+ w’y. z’+ xy. z’+ x’y’.z’ = w’x’+ w’y+ w’xy+ w’x’y’+ w’x’+ w’x’y+ 0 + x’y’+ w’x’z’+ w’yz’+ xyz’+ x’y’z’ = w’x’+ w’y+ w’xy+ w’x’y’+ w’x’y+ x’y’+ w’x’z’+ w’yz’+ xyz’+ x’y’z’ = w’x’( 1+ y’+ y+ z’)+ w’y( 1+ x+ z’)+ x’y’(1+ z’)+ xyz’ = w’x’(1)+ w’y(1)+ x’y’(1)+ xyz’ = w’x’+ w’y+ x’y’+ xyz’ 14 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD IIYR/III SEM R2021 MSAJCE/ECE 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 table below. Variables Minterms Maxterms x y z mi Mi 0 0 0 x’y’z’ = m0 x+ y+ z= M0 0 0 1 x’y’z = m1 x+ y+ z’= M1 0 1 0 x’yz’ = m2 x+ y’+ z= M2 0 1 1 x’yz = m3 x+ y’+ z’= M3 1 0 0 xy’z’ = m4 x’+ y+ z= M4 1 0 1 xy’z = m5 x’+ y+ z’= M5 1 1 0 xyz’ = m6 x’+ y’+ z= M6 1 1 1 xyz = m7 x’+ y’+ z’= M7 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: 15 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD IIYR/III SEM R2021 MSAJCE/ECE 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, 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. Find the missing literals in each product term if any. 2. AND each product term having missing literals by ORing the literal and its complement. 3. Expand the term by applying distributive law and reorder the literals in the product term. 4. Reduce the expression by omitting repeated product terms if any. Obtain the canonical SOP form of the function: 1. Y(A, B) = A+ B = A. (B+ B’)+ B (A+ A’) = AB+ AB’+ AB+ A’B = 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’ = m7+ m6+ m5+ m4 16 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD IIYR/III SEM R2021 MSAJCE/ECE = ∑m (4, 5, 6, 7). 3. Y(A,B,C)=A+BC = A. (B+ B’). (C+ C’)+(A+ 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 = m7+ m6+ m5+ m4+ m3 = ∑m (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 = ∑m (3, 5, 6, 7). 5. Y (A, B, C, D) = AB+ ACD = 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. F (A, B, C) = (A+ B+ C). (A+ B’+ C). (A+ B+ C’) F (x, y, z) = (x+ y’+ z’). (x’+ y+ z). (x+ y+ z) Steps to convert general POS to standard POS form: 1. Find the missing literals in each sum term if any. 2. OR each sum term having missing literals by ANDing the literal and its complement. 3. Expand the term by applying distributive law and reorder the literals in the sum term. 4. Reduce the expression by omitting repeated sum terms if any. 17 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD IIYR/III SEM R2021 MSAJCE/ECE Obtain the canonical POS expression of the functions: 1. Y= A+ B’C = (A+ B’) (A+ C) [ A+ BC = (A+B) (A+C)] = (A+ B’+ C.C’) (A+ C+ B.B’) = (A+ B’+C) (A+ B’+C’) (A+ B+ C) (A+ B’+ C) = (A+ B’+C). (A+ B’+C’). (A+ B+ C) = M2. M3. M0 = ∏M (0, 2, 3) 2. Y= (A+B) (B+C) (A+C) = (A+B+ C.C’) (B+ C+ A.A’) (A+C+B.B’) = (A+B+C) (A+B+C’) (A+B+C) (A’+B+C) (A+B+C) (A+B’+C) = (A+B+C) (A+B+C’) (A’+B+C) (A+B’+C) = M0. M1. M4. M 2 = ∏M (0, 1, 2, 4) 3. Y= A. (B+ C+ A) = (A+ B.B’+ C.C’). (A+ B+ C) = (A+B+C) (A+B+C’) (A+B’+C) (A+ B’+C’) (A+B+C) = (A+B+C) (A+B+C’) (A+B’+C) (A+ B’+C’) = M0. M1. M2. M3 = ∏M (0, 1, 2, 3) 4. Y= (A+B’) (B+C) (A+C’) = (A+B’+C.C’) (B+C+ A.A’) (A+C’+ B.B’) = (A+B’+C) (A+B’+C’) (A+B+C) (A’+B+C) (A+B+C’) (A+B’+C’) = (A+B’+C) (A+B’+C’) (A+B+C) (A’+B+C) (A+B+C’) = M2. M3. M0. M4. M1 = ∏M (0, 1, 2, 3, 4) 5. Y= xy+ x’z = (xy+ x’) (xy+ z)Using distributive law, convert the function into OR terms. = (x+x’) (y+x’) (x+z) (y+z) [x+ x’=1] = (x’+y) (x+z) (y+z) = (x’+y+ z.z’) (x+z+y.y’) (y+z+ x.x’) = (x’+ y+ z) (x’+ y+ z’) (x+ y+ z) (x+ y’+ z) (x+ y+ z) (x’+ y+ z) = (x’+ y+ z) (x’+ y+ z’) (x+ y+ z) (x+ y’+ z) 18 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD IIYR/III SEM R2021 MSAJCE/ECE = M4. M5. M0.M2 = ∏M (0, 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. 19 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD IIYR/III SEM R2021 MSAJCE/ECE 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. Grouping cells for Simplification: The grouping is nothing but combining terms in adjacent cells. The simplification is achieved by grouping adjacent 1’s or 0’s in groups of 2i, where i = 1, 2, …, n and n is the number of variables. When adjacent 1’s are grouped then we get result in the sum of product form; otherwise we get result in the product of sum form. 20 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD IIYR/III SEM R2021 MSAJCE/ECE Grouping Two Adjacent 1’s: (Pair) In a Karnaugh map we can group two adjacent 1’s. The resultant group is called Pair. Examples of Pairs Grouping Four Adjacent 1’s: (Quad) In a Karnaugh map we can group four adjacent 1’s. The resultant group is called Quad. Fig (a) shows the four 1’s are horizontally adjacent and Fig (b) shows they are vertically adjacent. Fig (c) contains four 1’s in a square, and they are considered adjacent to each other. 21 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD IIYR/III SEM R2021 MSAJCE/ECE Examples of Quads The four 1’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 1’s: (Octet) In a Karnaugh map we can group eight adjacent 1’s. The resultant group is called Octet. Simplification of Sum of Products Expressions: (Minimal Sums) The generalized procedure to simplify Boolean expressions as follows: 1. Plot the K-map and place 1’s in those cells corresponding to the 1’s in the sum of product expression. Place 0’s in the other cells. 2. Check the K-map for adjacent 1’s and encircle those 1’s which are not adjacent to any other 1’s. These are called isolated 1’s. 3. Check for those 1’s which are adjacent to only one other 1 and encircle such pairs. 22 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD IIYR/III SEM R2021 MSAJCE/ECE 4. Check for quads and octets of adjacent 1’s even if it contains some 1’s that have already been encircled. While doing this make sure that there are minimum number of groups. 5. Combine any pairs necessary to include any 1’s that have not yet been grouped. 6. Form the simplified expression by summing product terms of all the groups. Three- Variable Map: 1. Simplify the Boolean expression, F(x, y, z) = ∑m (3, 4, 6, 7). Soln: F = yz+ xz’ 2. F(x, y, z) = ∑m (0, 2, 4, 5, 6). Soln: 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 = m3+ m1+ m2+ m5+ m7 23 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD IIYR/III SEM R2021 MSAJCE/ECE = ∑ m (1, 2, 3, 5, 7) F=C+A’B 4. AB’C + A’B’C + A’BC + AB’C’ + A’B’C’ Soln: = m5 + m1 + m3 + m4 + m0 = ∑ m (0, 1, 3, 4, 5) F=A’C+B’ 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, Y= A’B’CD’+ AC’D+ BC’ 24 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD IIYR/III SEM R2021 MSAJCE/ECE 2. F (w, x, y, z) = ∑ m(0, 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’ = 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’ = m1+ m0+ m10+ m2+ m6+ m9+ m8 = ∑ m (0, 1, 2, 6, 8, 9, 10) Therefore, F= B’D’+ B’C’+ A’CD’. 25 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD IIYR/III SEM R2021 MSAJCE/ECE 4. Y= 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+ m11+ m10+ m14+ m13+ m12 = ∑ m (8, 10, 11, 12, 13, 14, 15) Therefore, Y= AB+ AC+ AD’. 5. Y (A, B, C, D)= ∑ m (7, 9, 10, 11, 12, 13, 14, 15) Therefore, Y= AB+ AC+ AD+BCD. 26 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD IIYR/III SEM R2021 MSAJCE/ECE 6. Y= A’B’C’D+ A’BC’D+ A’BCD+ A’BCD’+ ABC’D+ ABCD+ AB’CD = m1+ m5+ m7+ m6+ m13+ m15+ m11 = ∑ m (1, 5, 6, 7, 11, 13, 15) 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 1’s, four pairs have to be formed. However, all the four 1’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. Y= ∑ m (1, 5, 10, 11, 12, 13, 15) Therefore, Y= A’C’D+ ABC’+ ACD+ AB’C. 27 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD IIYR/III SEM R2021 MSAJCE/ECE 8. Y= A’B’CD’+ ABCD’+ AB’CD’+ AB’CD+ AB’C’D’+ ABC’D’+ A’B’CD+ A’B’C’D’ Therefore, Y= AD’+ B’C+ B’D’ 9. F (A, B, C, D) = ∑ m (0, 1, 4, 8, 9, 10) Therefore, F= A’C’D’+ AB’D’+ B’C’. Simplification of Sum of Products Expressions: (Minimal Sums) 1. Y= (A+ B+ C’) (A+ B’+ C’) (A’+ B’+ C’) (A’+ B+ C) (A+ B+ C) = M1. M3. M7. M4. M0 =∏ M (0, 1, 3, 4, 7) = ∑ m (2, 5, 6) 28 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD IIYR/III SEM R2021 MSAJCE/ECE Y’ = B’C’+ A’C+ BC. Y= Y” = (B’C’+ A’C+ BC)’ = (B’C’)’. (A’C)’. (BC)’ = (B”+ C”). (A”+C’). (B’+ C’) Y = (B+ C). (A+C’). (B’+ C’) 2. Y= (A’+ B’+ C+ D) (A’+ B’+ C’+ D) (A’+ B’+ C’+ D’) (A’+ B+ C+ D) (A+ B’+ C’+ D) (A+ B’+ C’+ D’) (A+ B+ C+ D) (A’+ B’+ C+ D’) = M12. M14. M15. M8. M6. M7. M0. M13 = ∏M (0, 6, 7, 8, 12, 13, 14, 15) Y’ = B’C’D’+ AB+ BC Y= Y” = (B’C’D’+ AB+ BC)’ = (B’C’D’)’. (AB)’. (BC)’ = (B”+ C”+D”). (A’+B’). (B’+ C’) = (B+ C+ D). (A’+ B’). (B’+ C’) Therefore, Y= (B+ C+ D). (A’+ B’). (B’+ C’) 3. F(A, B, C, D)= ∏M (0, 2, 3, 8, 9, 12, 13, 14, 15) Y’ = A’B’D’+ A’B’C+ ABD+ AC’ 29 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD IIYR/III SEM R2021 MSAJCE/ECE Y= Y” = (A’B’D’+ A’B’C+ ABD+ AC’)’ = (A’B’D’)’. (A’B’C)’. (ABD)’. (AC’)’ = (A”+ B”+ D”). (A”+ B”+C’). (A’+ B’+ D’). (A’+ C”) = (A+ B+ D). (A+ B+ C’). (A’+ B’+ D’). (A’+ C) Therefore, Y= (A+ B+ D). (A+ B+ C’). (A’+ B’+ D’). (A’+ C) 4. F(A, B, C, D)= ∑m (0, 1, 2, 5, 8, 9, 10) = ∏M (3, 4, 6, 7, 11, 12, 13, 14, 15) Y’ = BD’+ CD+ AB Y= Y” = (BD’+ CD+ AB)’ = (BD’)’. (CD)’. (AB)’ = (B’+ D”). (C’+ D’). (A’+ B’) = (B’+ D). (C’+ D’). (A’+ B’) Therefore, Y= (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 0 or 1. When simplifying the function, we can choose to include each don’t care minterm with either the 1’s or the 0’s, depending on which combination gives the simplest expression. 1. F (x, y, z) = ∑m (0, 1, 2, 4, 5)+ ∑d (3, 6, 7) 30 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD IIYR/III SEM R2021 MSAJCE/ECE F (x, y, z) = 1 2. F (w, x, y, z) = ∑m (1, 3, 7, 11, 15)+ ∑d (0, 2, 5) F (w, x, y, z) = w’x’+ yz 3. F (w, x, y, z) = ∑m (0, 7, 8, 9, 10, 12)+ ∑d (2, 5, 13) F (w, x, y, z) = w’xz+ wy’+ x’z’. 4. F (w, x, y, z) = ∑m (0, 1, 4, 8, 9, 10)+ ∑d (2, 11) Soln: F (w, x, y, z) = wx’+ x’y’+ w’y’z’. 31 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD IIYR/III SEM R2021 MSAJCE/ECE 5. F( A, B, C, D) = ∑m (0, 6, 8, 13, 14)+ ∑d (2, 4, 10) Soln: F( A, B, C, D) = CD’+ B’D’+ A’B’C’D’. Five- Variable Maps: A 5- variable K- map requires 25= 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. Five- Variable Karnaugh map (Layer Structure) 32 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD IIYR/III SEM R2021 MSAJCE/ECE 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. 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) = ∑m (0, 2, 4, 6, 9, 11, 13, 15, 17, 21, 25, 27, 29, 31) Soln: F (A, B, C, D, E) = A’B’E’+ BE+ AD’E 33 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD IIYR/III SEM R2021 MSAJCE/ECE 2. F (A, B, C, D, E) = ∑m (0, 5, 6, 8, 9, 10, 11, 16, 20, 24, 25, 26, 27, 29, 31) Soln: 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) = ∑m ( 1, 4, 8, 10, 11, 20, 22, 24, 25, 26)+∑d (0, 12, 16, 17) Soln: F (A, B, C, D, E) = B’C’D’+ A’D’E’+ BC’E’+ A’BC’D+ AC’D’+ AB’CE’ 34 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD IIYR/III SEM R2021 MSAJCE/ECE 4. F (A, B, C, D, E) = ∑m (0, 1, 2, 6, 7, 9, 12, 28, 29, 31) Soln: F (A, B, C, D, E) = BCD’E’+ ABCE+ A’B’C’E’+ A’C’D’E+ A’B’CD 5. F (x1, x2, x3, x4, x5) = ∑m (2, 3, 6, 7, 11, 12, 13, 14, 15, 23, 28, 29, 30, 31 ) Soln: F (x1, x2, x3, x4, x5) = x2x3+ x3x4x5+ x1’x2’x4+ x1’x3’x4x5 35 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD IIYR/III SEM R2021 MSAJCE/ECE 6. F (x1, x2, x3, x4, x5) = ∑m (1, 2, 3, 6, 8, 9, 14, 17, 24, 25, 26, 27, 30, 31 )+ ∑d (4, 5) Soln: F (x1, x2, x3, x4, x5) = x2x3’x4’+ x2x3x4x5’+ x3’x4’x5+ x1x2x4+ x1’x2’x3x5’+ x1’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 SYMBOL OPERATION TRUTH TABLE NOT NOT gate (Invertion), produces an inverted output pulse for a (7404) given input pulse. AND gate performs logical multiplication. The output is AND HIGH only when all the inputs (7408) are HIGH. When any of the inputs are low, the output is LOW. 36 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD IIYR/III SEM R2021 MSAJCE/ECE OR gate performs logical addition. It produces a HIGH OR on the output when any of the (7432) inputs are HIGH. The output is LOW only when all inputs are LOW. It is a universal gate. When any NAND of the inputs are LOW, the output will be HIGH. LOW (7400) output occurs only when all inputs are HIGH. It is a universal gate. LOW NOR output occurs when any of its input is HIGH. When all its (7402) inputs are LOW, the output is HIGH. EX- OR The output is HIGH only when (7486) odd number of inputs is HIGH. The output is HIGH only when EX- NOR even number of inputs is HIGH. Or when all inputs are zeros. 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, 37 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD IIYR/III SEM R2021 MSAJCE/ECE the OR function and the NOR function. i) NOT function: 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., AND function using NAND gates iii) OR function: By simply inverting inputs of the NAND gate. i.e., OR function using NAND gates 38 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD IIYR/III SEM R2021 MSAJCE/ECE Bubble at the input of NAND gate indicates inverted input. 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 function: By connecting all the inputs together and creating a single common input. NOT function using NOR gates 39 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD IIYR/III SEM R2021 MSAJCE/ECE ii) OR function: 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 gate indicates inverted input. Truth table 40 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD IIYR/III SEM R2021 MSAJCE/ECE 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. Draw AND/OR logic. 2. 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. 3. Add or subtract an inverter on each line that received a bubble in step 2. 4. Replace bubbled OR by NAND and bubbled AND by NOR. 5. Eliminate double inversions. 1. Implement Boolean expression using NAND gates: Original Circuit: 41 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD IIYR/III SEM R2021 MSAJCE/ECE Soln: NAND Circuit: : 42 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD IIYR/III SEM R2021 MSAJCE/ECE 2. Implement Boolean expression for EX-OR gate using NAND gates. Soln: gate. 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, 43 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD IIYR/III SEM R2021 MSAJCE/ECE Replacing inverter and bubbled OR with NAND, we have 44 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD II YR III SEM MSAJCE/ECE UNIT II COMBINATIONAL LOGIC CIRCUITS: INTRODUCTION: The digital system consists of two types of circuits, namely (i) Combinational circuits (ii) Sequential circuits Combinational circuit consists of logic gates whose output at any time is determined from the present combination of inputs. The logic gate is the most basic building block of combinational logic. The logical function performed by a combinational circuit is fully defined by a set of Boolean expressions. Sequential logic circuit comprises both logic gates and the state of storage elements such as flip-flops. As a consequence, the output of a sequential circuit depends not only on present value of inputs but also on the past state of inputs. In the previous chapter, we have discussed binary numbers, codes, Boolean algebra and simplification of Boolean function and logic gates. In this chapter, formulation and analysis of various systematic designs of combinational circuits will be discussed. A combinational circuit consists of input variables, logic gates, and output variables. The logic gates accept signals from inputs and output signals are generated according to the logic circuits employed in it. Binary information from the given data transforms to desired output data in this process. Both input and output are obviously the binary signals, i.e., both the input and output signals are of two possible states, logic1 and logic 0. Block diagram of a combinational logic circuit For n number of input variables to a combinational circuit, 2n possible combinations of binary input states are possible. For each possible combination, there is one and only one possible output combination. A combinational logic circuit can be described by m Boolean functions and each output can be expressed in terms of n input variables. 1 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD II YR III SEM MSAJCE/ECE DESIGN PROCEDURE: Any combinational circuit can be designed by the following steps of design procedure. 1. The problem is stated. 2. Identify the input and output variables. 3. The input and output variables are assigned letter symbols. 4. Construction of a truth table to meet input -output requirements. 5. Writing Boolean expressions for various output variables in terms of input variables. 6. The simplified Boolean expression is obtained by any method of minimization— algebraic method, Karnaugh map method, or tabulation method. 7. A logic diagram is realized from the simplified boolean expression using logic gates. The following guidelines should be followed while choosing the preferred form for hardware implementation: 1. The implementation should have the minimum number of gates, with the gates used having the minimum number of inputs. 2. There should be a minimum number of interconnections. 3. Limitation on the driving capability of the gates should not be ignored. ARITHMETIC CIRCUITS – BASIC BUILDING BLOCKS: In this section, we will discuss those combinational logic building blocks that can be used to perform addition and subtraction operations on binary numbers. Addition and subtraction are the two most commonly used arithmetic operations, as the other two, namely multiplication and division, are respectively the processes of repeated addition and repeated subtraction. The basic building blocks that form the basis of all hardware used to perform the arithmetic operations on binary numbers are half-adder, full adder, half-subtractor, full- subtractor. Half-Adder: A half-adder is a combinational circuit that can be used to add two binary bits. It has two inputs that represent the two bits to be added and two outputs, with one producing the SUM output and the other producing the CARRY. 2 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD II YR III SEM MSAJCE/ECE Block schematic of half-adder The truth table of a half-adder, showing all possible input combinations and the corresponding outputs are shown below. Inputs Outputs A B Carry (C) Sum (S) 0 0 0 0 0 1 0 1 1 0 0 1 1 1 1 0 Truth table of half-adder K-map simplification for carry and sum: The Boolean expressions for the SUM and CARRY outputs are given by the equations, Sum, S = A’B+ AB’= A B Carry, C = A. B The first one representing the SUM output is that of an EX-OR gate, the second one representing the CARRY output is that of an AND gate. The logic diagram of the half adder is, Logic Implementation of Half-adder 3 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD II YR III SEM MSAJCE/ECE Full-Adder: A full adder is a combinational circuit that forms the arithmetic sum of three input bits. It consists of 3 inputs and 2 outputs. Two of the input variables, represent the significant bits to be added. The third input represents the carry from previous lower significant position. The block diagram of full adder is given by, Block schematic of full-adder The full adder circuit overcomes the limitation of the half-adder, which can be used to add two bits only. As there are three input variables, eight different input combinations are possible. The truth table is shown below, Truth Table: Inputs Outputs A B Cin Sum (S) Carry (Cout) 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 1 0 1 1 1 0 0 1 1 1 1 1 1 To derive the simplified Boolean expression from the truth table, the Karnaugh map method is adopted as, 4 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD II YR III SEM MSAJCE/ECE The Boolean expressions for the SUM and CARRY outputs are given by the equations, Sum, S = A’B’Cin+ A’BC’in + AB’C’in + ABCin Carry, Cout = AB+ ACin + BCin. The logic diagram for the above functions is shown as, Implementation of full-adder in Sum of Products The logic diagram of the full adder can also be implemented with two half- adders and one OR gate. The S output from the second half adder is the exclusive-OR of Cin and the output of the first half-adder, giving Sum = Cin (A B) [x y = x‘y+ xy‘] = Cin (A‘B+AB‘) = C‘in (A‘B+AB‘) + Cin (A‘B+AB‘)‘ [(x‘y+xy‘)‘= (xy+x‘y‘)] = C‘in (A‘B+AB‘) + Cin (AB+A‘B‘) = A‘BC‘in + AB‘C‘in + ABCin + A‘B‘Cin. 5 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD II YR III SEM MSAJCE/ECE and the carry output is, Carry, Cout = AB+ Cin (A’B+AB’) = AB+ A‘BCin+ AB‘Cin = AB (Cin+1) + A‘BCin+ AB‘Cin [Cin+1= 1] = ABCin+ AB+ A‘BCin+ AB‘Cin = AB+ ACin (B+B‘) + A‘BCin = AB+ ACin+ A‘BCin = AB (Cin+1) + ACin+ A‘BCin [Cin+1= 1] = ABCin+ AB+ ACin+ A‘BCin = AB+ ACin+ BCin (A +A‘) = AB+ ACin+ BCin. Implementation of full adder with two half-adders and an OR gate Half -Subtractor: A half-subtractor is a combinational circuit that can be used to subtract one binary digit from another to produce a DIFFERENCE output and a BORROW output. The BORROW output here specifies whether a ‗1‘ has been borrowed to perform the subtraction. Block schematic of half-subtractor The truth table of half-subtractor, showing all possible input combinations and the corresponding outputs are shown below. Input Output A B Difference (D) Borrow (Bout) 0 0 0 0 0 1 1 1 1 0 1 0 1 1 0 0 6 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD II YR III SEM MSAJCE/ECE K-map simplification for half subtractor: The Boolean expressions for the DIFFERENCE and BORROW outputs are given by the equations, Difference, D = A’B+ AB’= A B Borrow, Bout = A’. B The first one representing the DIFFERENCE (D)output is that of an exclusive-OR gate, the expression for the BORROW output (Bout) is that of an AND gate with input A complemented before it is fed to the gate. The logic diagram of the half adder is, Logic Implementation of Half-Subtractor Comparing a half-subtractor with a half-adder, we find that the expressions for the SUM and DIFFERENCE outputs are just the same. The expression for BORROW in the case of the half-subtractor is also similar to what we have for CARRY in the case of the half-adder. If the input A, ie., the minuend is complemented, an AND gate can beused to implement the BORROW output. Full Subtractor: A full subtractor performs subtraction operation on two bits, a minuend and a subtrahend, and also takes into consideration whether a ‗1‘ has already been borrowed by the previous adjacent lower minuend bit or not. As a result, there are three bits to be handled at the input of a full subtractor, namely the two bits to be subtracted and a borrow bit designated as B in. There are two outputs, namely the DIFFERENCE output D and the BORROW output Bo. The 7 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD II YR III SEM MSAJCE/ECE 8 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD II YR III SEM MSAJCE/ECE BORROW output bit tells whether the minuend bit needs to borrow a ‗1‘ from the next possible higher minuend bit. Block schematic of full-adder The truth table for full-subtractor is, Inputs Outputs A B Bin Difference(D) Borrow(Bout) 0 0 0 0 0 0 0 1 1 1 0 1 0 1 1 0 1 1 0 1 1 0 0 1 0 1 0 1 0 0 1 1 0 0 0 1 1 1 1 1 K-map simplification for full-subtractor: The Boolean expressions for the DIFFERENCE and BORROW outputs are given by the equations, Difference, D = A’B’Bin+ A’BB’in + AB’B’in + ABBin Borrow, Bout = A’B+ A’Cin + BBin. The logic diagram for the above functions is shown as, 9 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD II YR III SEM MSAJCE/ECE Implementation of full-adder in Sum of Products The logic diagram of the full-subtractor can also be implemented with two half- subtractors and one OR gate. The difference,D output from the second half subtractor is the exclusive-OR of Bin and the output of the first half-subtractor, giving Difference,D= Bin (A B) [x y = x‘y+ xy‘] = Bin (A‘B+AB‘) = B‘in (A‘B+AB‘) + Bin (A‘B+AB‘)‘ [(x‘y+xy‘)‘= (xy+x‘y‘)] = B‘in (A‘B+AB‘) + Bin (AB+A‘B‘) = A‘BB‘in + AB‘B‘in + ABBin + A‘B‘Bin. and the borrow output is, Borrow, Bout = A’B+ Bin (A’B+AB’)’ [(x‘y+xy‘)‘= (xy+x‘y‘)] = A‘B+ Bin (AB+A‘B‘) = A‘B+ ABBin+ A‘B‘Bin = A‘B (Bin+1) + ABBin+ A‘B‘Bin [Cin+1= 1] = A‘BBin+ A‘B+ ABBin+ A‘B‘Bin = A‘B+ BBin (A+A‘) + A‘B‘Bin [A+A‘= 1] = A‘B+ BBin+ A‘B‘Bin = A‘B (Bin+1) + BBin+ A‘B‘Bin [Cin+1= 1] = A‘BBin+ A‘B+ BBin+ A‘B‘Bin = A‘B+ BBin+ A‘Bin (B +B‘) = A‘B+ BBin+ A‘Bin. Therefore, we can implement full-subtractor using two half-subtractors and OR gate as, Implementation of full-subtractor with two half-subtractors and an OR gate 10 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD II YR III SEM MSAJCE/ECE Binary Adder (Parallel Adder): The 4-bit binary adder using full adder circuits is capable of adding two 4- bit numbers resulting in a 4-bit sum and a carry output as shown in figure below. 4-bit binary parallel Adder Since all the bits of augend and addend are fed into the adder circuits simultaneously and the additions in each position are taking place at the same time, this circuit is known as parallel adder. Let the 4-bit words to be added be represented by, A3A2A1A0= 1111 and B3B2B1B0= 0011. The bits are added with full adders, starting from the least significant position, to form the sum it and carry bit. The input carry C0 in the least significant position must be 0. The carry output of the lower order stage is connected to the carry input of the next higher order stage. Hence this type of adder is called ripple-carry adder. In the least significant stage, A0, B0 and C0 (which is 0) are added resulting in sum S0 and carry C1. This carry C1 becomes the carry input to the second stage. Similarly in the second stage, A1, B1 and C1 are added resulting in sum S 1 and carry C2, in the third stage, A2, B2 and C2 are added resulting in sum S 2 and carry C3, in the third stage, A3, B3 and C3 are added resulting in sum S3 and C4, which is the output carry. Thus the circuit results in a sum (S3S2S1S0) and a carry output (Cout). Though the parallel binary adder is said to generate its output immediately after the inputs are applied, its speed of operation is limited by the carry propagation delay 11 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD II YR III SEM MSAJCE/ECE through all stages. However, there are several methods to reduce this delay. One of the methods of speeding up this process is look-ahead carry addition which eliminates the ripple-carry delay. Carry Propagation–Look-Ahead Carry Generator: In Parallel adder, all the bits of the augend and the addend are available for computation at the same time. The carry output of each full-adder stage is connected to the carry input of the next high-order stage. Since each bit of the sum output depends on the value of the input carry, time delay occurs in the addition process. This timedelay is called as carry propagation delay. For example, addition of two numbers (0011+ 0101) gives the result as 1000. Addition of the LSB position produces a carry into the second position. This carry when added to the bits of the second position, produces a carry into the third position. This carry when added to bits of the third position, produces a carry into the last position. The sum bit generated in the last position (MSB) depends on the carry that was generated by the addition in the previous position. i.e., the adder will not produce correct result until LSB carry has propagated through the intermediate full-adders. This represents a time delay that depends on the propagation delay produced in an each full-adder. For example, if each full adder is considered to have a propagation delay of 30nsec, then S3 will not react its correct value until 90 nsec after LSB is generated. Therefore total time required to perform addition is 90+ 30 = 120nsec. 4-bit Parallel Adder The method of speeding up this process by eliminating inter stage carry delay is called look ahead-carry addition. This method utilizes logic gates to look at the lower order bits of the augend and addend to see if a higher-order carry is to be generated. It uses two functions: carry generate and carry propagate. 12 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD II YR III SEM MSAJCE/ECE Full-Adder circuit Consider the circuit of the full-adder shown above. Here we define two functions: carry generate (Gi) and carry propagate (Pi) as, Carry generate, Gi = Ai Bi Carry propagate, Pi = Ai Bi the output sum and carry can be expressed as, Si = P i Ci Ci+1 = Gi Pi C i Gi (carry generate), it produces a carry 1 when both Ai and Bi are 1, regardless of the input carry Ci. Pi (carry propagate) because it is the term associated with the propagation of the carry from Ci to Ci+1. The Boolean functions for the carry outputs of each stage and substitute for each Ci its value from the previous equation: C0= input carry C1 = G 0 + P 0 C 0 C2= G1 + P1C1 = G1 + P1 (G0 + P0C0) = G1 + P 1 G0 + P 1P 0C 0 C3= G2 + P2C2 = G2 + P2 (G1 + P1G0 + P1P0C0) = G 2 + P 2 G 1 + P 2 P 1 G 0 + P 2 P 1 P 0 C0 13 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD II YR III SEM MSAJCE/ECE Since the Boolean function for each output carry is expressed in sum of products, each function can be implemented with one level of AND gates followed by an OR gate. The three Boolean functions for C 1, C2 and C3 are implemented in the carry look-ahead generator as shown below. Note that C3 does not have to wait for C2 and C1 to propagate; in fact C3 is propagated at the same time as C1 and C2. Logic diagram of Carry Look-ahead Generator Using a Look-ahead Generator we can easily construct a 4-bit parallel adder with a Look-ahead carry scheme. Each sum output requires two exclusive-OR gates. The output of the first exclusive-OR gate generates the Pi variable, and the AND gate generates the Gi variable. The carries are propagated through the carry look-ahead generator and applied as inputs to the second exclusive-OR gate. All output carries are generated after a delay through two levels of gates. Thus, outputs S 1 through S3 have equal propagation delay times. 14 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD II YR III SEM MSAJCE/ECE 4-Bit Adder with Carry Look-ahead Binary Subtractor (Parallel Subtractor): The subtraction of unsigned binary numbers can be done most conveniently by means of complements. The subtraction A-B can be done by taking the 2‘s complement of B and adding it to A. The 2‘s complement can be obtained by taking the 1‘s complement and adding 1 to the least significant pair of bits. The 1‘s complement can be implemented with inverters and a 1 can be added to the sum through the input carry. 15 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD II YR III SEM MSAJCE/ECE The circuit for subtracting A-B consists of an adder with inverters placed between each data input B and the corresponding input of the full adder. The input carry C0 must be equal to 1 when performing subtraction. The operation thus performed becomes A, plus the 1‘s complement of B, plus1. This is equal to A plus the 2‘s complement of B. 4-bit Parallel Subtractor Parallel Adder/ Subtractor: The addition and subtraction operation can be combined into one circuit with one common binary adder. This is done by including an exclusive-OR gate with each full adder. A 4-bit adder Subtractor circuit is shown below. 4-Bit Adder Subtractor The mode input M controls the operation. When M= 0, the circuit is an adder and when M=1, the circuit becomes a Subtractor. Each exclusive-OR gate receives input M 16 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD II YR III SEM MSAJCE/ECE and one of the inputs of B. When M=0, we have B 0= B. The full adders receive the value of B, the input carry is 0, and the circuit performs A plus B. When M=1, we have B 1= B‘ and C0=1. The B inputs are all complemented and a 1 is added through the input carry. The circuit performs the operation A plus the 2‘s complement of B. The exclusive- OR with output V is for detecting an overflow. Decimal Adder (BCD Adder): The digital system handles the decimal number in the form of binary coded decimal numbers (BCD). A BCD adder is a circuit that adds two BCD bits and producesa sum digit also in BCD. Consider the arithmetic addition of two decimal digits in BCD, together with an input carry from a previous stage. Since each input digit does not exceed 9, the output sum cannot be greater than 9+ 9+1 = 19; the 1 is the sum being an input carry. The adder will form the sum in binary and produce a result that ranges from 0 through 19. These binary numbers are labeled by symbols K, Z 8, Z4, Z2, Z1, K is the carry. The columns under the binary sum list the binary values that appear in the outputs of the 4- bit binary adder. The output sum of the two decimal digits must be represented in BCD. Binary Sum BCD Sum Decimal K Z8 Z4 Z2 Z1 C S8 S4 S2 S1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1 0 2 0 0 0 1 1 0 0 0 1 1 3 0 0 1 0 0 0 0 1 0 0 4 0 0 1 0 1 0 0 1 0 1 5 0 0 1 1 0 0 0 1 1 0 6 0 0 1 1 1 0 0 1 1 1 7 0 1 0 0 0 0 1 0 0 0 8 0 1 0 0 1 0 1 0 0 1 9 17 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD II YR III SEM MSAJCE/ECE 0 1 0 1 0 1 0 0 0 0 10 0 1 0 1 1 1 0 0 0 1 11 0 1 1 0 0 1 0 0 1 0 12 0 1 1 0 1 1 0 0 1 1 13 0 1 1 1 0 1 0 1 0 0 14 0 1 1 1 1 1 0 1 0 1 15 1 0 0 0 0 1 0 1 1 0 16 1 0 0 0 1 1 0 1 1 1 17 1 0 0 1 0 1 1 0 0 0 18 1 0 0 1 1 1 1 0 0 1 19 In examining the contents of the table, it is apparent that when the binary sum is equal to or less than 1001, the corresponding BCD number is identical, and therefore no conversion is needed. When the binary sum is greater than 9 (1001), we obtain a non- valid BCD representation. The addition of binary 6 (0110) to the binary sum converts it to the correct BCD representation and also produces an output carry as required. The logic circuit to detect sum greater than 9 can be determined by simplifying the boolean expression of the given truth table. 18 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD II YR III SEM MSAJCE/ECE To implement BCD adder we require: 4-bit binary adder for initial addition Logic circuit to detect sum greater than 9 and One more 4-bit adder to add 01102 in the sum if the sum is greater than 9 or carry is 1. The two decimal digits, together with the input carry, are first added in the top4- bit binary adder to provide the binary sum. When the output carry is equal to zero, nothing is added to the binary sum. When it is equal to one, binary 0110 is added to the binary sum through the bottom 4-bit adder. The output carry generated from the bottom adder can be ignored, since it supplies information already available at the output carry terminal. The output carry from one stage must be connected to the input carry of the next higher-order stage. Block diagram of BCD adder Binary Multiplier: Multiplication of binary numbers is performed in the same way as in decimal numbers. The multiplicand is multiplied by each bit of the multiplier starting from the least significant bit. Each such multiplication forms a partial product. Such partial 19 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD II YR III SEM MSAJCE/ECE products are shifted one position to the left. The final product is obtained from the sum of partial products. Consider the multiplication of two 2-bit numbers. The multiplicand bits are B1 and B0, the multiplier bits are A 1 and A0, and the product is C3, C2, C1 and C0. The first partial product is formed by multiplying A 0 by B1B0. The multiplication of two bits such as A0 and B0 produces a 1 if both bits are 1; otherwise, it produces a 0. This is identicalto an AND operation. Therefore the partial product can be implemented with AND gates as shown in the diagram below. The second partial product is formed by multiplying A 1 by B1B0 and shifted one position to the left. The two partial products are added with two half adder (HA) circuits. 2-bit by 2-bit Binary multiplier Usually there are more bits in the partial products and it is necessary to use full adders to produce the sum of the partial products. The least significant bit of the product does not have to go through an adder since it is formed by the output of thefirst AND gate. A combinational circuit binary multiplier with more bits can be constructed in a similar fashion. A bit of the multiplier is ANDed with each bit of the multiplicand in as many levels as there are bits in the multiplier. The binary output in each level of AND gates are added with the partial product of the previous level to form a new partial product. The last level produces the product. For J multiplier bits and K multiplicand bits we need (J x K) AND gates and (J-1) k-bit adders to produce a product of J+K bits. Consider a multiplier circuit that multiplies a binary number of four bits by a number of three bits. Let the multiplicand be represented by B3, B2, B1, B0 and the multiplier by A2, A1, and A0. Since K= 4 and J= 3, we need 12 AND gates and two 4-bit adders to produce a product of seven bits. The logic diagram of the multiplier is shown below. 20 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD II YR III SEM MSAJCE/ECE 4-bit by 3-bit Binary multiplier PARITY GENERATOR/ CHECKER: A Parity is a very useful tool in information processing in digital computers to indicate any presence of error in bit information. External noise and loss of signal strength causes loss of data bit information while transporting data from one device to other device, located inside the computer or externally. To indicate any occurrence of error, an extra bit is included with the message according to the total number of 1s in a set of data, which is called parity. If the extra bit is considered 0 if the total number of 1s is even and 1 for odd quantities of 1s in a set of data, then it is called even parity. On the other hand, if the extra bit is 1 for even quantities of 1s and 0 for an odd number of 1s, then it is called oddparity. 21 Downloaded from EnggTree.com  EnggTree.com EC3352 DSD II YR III SEM