Digital Electronics . .

Digital ElectronicsDigital ElectronicsDigital ElectronicsDigital ElectronicsDigital ElectronicsDigital ElectronicsDigital ElectronicsDigital ElectronicsDigital ElectronicsDigital ElectronicsDigital ElectronicsDigital ElectronicsDigital ElectronicsDigital ElectronicsDigital ElectronicsDigital ElectronicsDigital Electronics

1. 10211CS201-DIGITAL ELECTRONICS Slot : S3/S1 Category : Program Core UNIT-I School of Computing Department of Computer Science & Engineering Course Handling Faculty : Dr. S. Yazhinian Associate Professor

2. Program Core 2 Preamble The primary aim of this course is to understand the fundamentals behind the digital logic design. From that students can gain the experience, to design any digital circuits and systems. The course includes fundamentals of Boolean algebra, combinational, sequential circuits and applications of digital electronics. Students can learn the basic programming concepts to implement digital circuits using hardware description language.

3. CO Nos. Course Outcomes Knowledge Level (Based on revised Bloom’s taxonomy) CO1 Apply the simplification of Boolean expressions using K – Map method and designing Combinational circuits. K3 7/4/2024 Dr. S. Yazhinian, AP/ CSE Digital Electronics Program Core 3

4. Correlation of COs with POs 7/4/2024 Dr. S. Yazhinian, AP/ CSE Digital Electronics Program Core 4 COs PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12 PSO1 PSO 2 PSO 3 CO1 H M     M         L     H   L CO2 M M     M         L     L     CO3 H     M H     L           M   CO4 M M                     M     CO5 M M     M     L       L     L

5. Course Outcome – NBA-EAC-CAC 7/4/2024 Dr. S. Yazhinian, AP/ CSE Digital Electronics Program Core 5 Course Outcomes Correlates to Program Outcomes: NBA Correlates to Student Outcomes: EAC Correlates to Student Outcomes: CAC CO1: Apply the simplification of Boolean expressions using K – Map method and designing Combinational circuits. a, b, c, d, g, j 1,2,3,4,5,6 1,2,6 CO2: Outline the combinational building blocks & memory elements. a, b, d, j   1,2,3,6 1,2,6 CO3: Design the combinational and sequential circuits using hardware description language. a, b, c, d, g 1,2,3,4,5,6 1,2,6 CO4: Solve the asynchronous sequential circuits for given applications a, b, g   1,2,6,7 1,2,6 CO5: Explain the applications of digital electronics a, b, g, j 1,2,4,5,6,7   1,2,6

6. Syllabus 7/4/2024 Dr. S. Yazhinian, AP/ CSE Digital Electronics Program Core 6 UNIT–I: DIGITAL FUNDAMENTALS AND COMBINATIONAL CIRCUITS 10 Introduction to Boolean algebra and Switching Functions; Boolean Minimization using K Map and Tabulation method; combinational circuits: Design procedure – Half adder – Full Adder – Half subtractor – Full subtractor – Parallel binary adder, parallel binary Subtractor – Fast Adder - Carry Look Ahead adder – Serial Adder/Subtractor - BCD adder – Binary Multiplier – Binary Divider - Multiplexer/ Demultiplexer – decoder - encoder – parity checker – parity generators – code converters - Magnitude Comparator. UNIT -II: SEQUENTIAL CIRCUITS 10  Flip Flops and Memory devices: RAM – Static and Dynamic, ROM, PROM, EPROM, EEPROM; Counters and Shift registers: Binary, BCD and programmable modulo counters, Shift register counters; Sequential circuit design: using Mealy and Moore model.  UNIT III: INTRODUCTION TO HARDWARE DESCRIPTION LANGUAGE 10 Introduction to Verilog / VHDL- Structural, Dataflow and Behavioral modeling. Structural, Dataflow and Behavioral modeling of combinational logic circuits (Multiplexer, Demultiplexer, decoder and encoder). Structural, Dataflow and Behavioral modeling of sequential logic circuits (counters and shift registers).  UNIT IV: ASYNCHRONOUS SEQUENTIAL CIRCUITS 10 Analysis Procedure, Circuits with latches; Design Procedure, Reduction of state and flow table; Race free state assignment; Hazards; ASM chart; Design examples. UNIT V: APPLICATIONS OF DIGITAL ELECTRONICS 5 Multiplexing displays - Frequency counters - Time measurements - using the ADC0804 - Slope alone operation, span adjust, zero shift, testing - microprocessor compatible A/D converters. 

7. 7/4/2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics Recommended Textbooks 7 T1. M. Morris Mano, Digital Design, 3rd Edition, Prentice Hall of India Pvt. Ltd., Pearson Education (Singapore) Pvt. Ltd., New Delhi, 2003. T2. Donald . P.Leach , Digital principles and applications, 7th Edition, McGraw-Hill, 2012. Recommended References R1. John F.Wakerly , Digital Design, Fourth Edition, Pearson/PHI, 2006. R2. Thomas L. Floyd, Digital Fundamentals, 8th Edition, Pearson Education Inc , New Delhi, 2003 Donald D.Givone , Digital Principles and Design, TMH. R3. William H. Gothmann , Digital Electronics, 2nd Edition, PHI, 1982.

8. 7/4/2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics ONLINE RESOURCES 8 http://www.wiley.com/legacy/wileychi/mblin/supp/student/LN08CombinationalLogicModules.pdf http://www.learnabout-electronics.org www.nptel.com/digitalelectronics/iitkanpur/ www.mooc.org

9. Applications of Digital Electronics 7/4/2024 Dr. S. Yazhinian, AP/ CSE Digital Electronics Program Core 9 Digital circuits are a part of all the important electronic devices. It can be used for designing the display of watch or a countdown timer. We use digital circuits in complex processes like Rocket Science and Quantum Computing. Digital circuits are also used in traffic lights and automatic glass doors in offices and restaurants.

10. Opportunities 7/4/2024 Dr. S. Yazhinian, AP/ CSE Digital Electronics Program Core 10 Electronics Hardware Engineer Hardware Circuit Design Engineer

11. 7/4/2024 Unit I - Syllabus 11 UNIT–I: DIGITAL FUNDAMENTALS AND COMBINATIONAL CIRCUITS 10 Introduction to Boolean algebra and Switching Functions; Boolean Minimization using K Map and Tabulation method; combinational circuits: Design procedure – Half adder – Full Adder – Half subtractor – Full subtractor – Parallel binary adder, parallel binary Subtractor – Fast Adder - Carry Look Ahead adder – Serial Adder/ Subtractor - BCD adder – Binary Multiplier – Binary Divider - Multiplexer/ Demultiplexer – decoder - encoder – parity checker – parity generators – code converters - Magnitude Comparator. Dr. S. Yazhinian, AP/ CSE Digital Electronics

12. 7/4/2024 Recommended Textbooks 12 T1. M. Morris Mano, Digital Design, 3rd Edition, Prentice Hall of India Pvt. Ltd., Pearson Education (Singapore) Pvt. Ltd., New Delhi, 2003. T2. Donald . P.Leach , Digital principles and applications, 7th Edition, McGraw-Hill, 2012. Recommended References R1. John F.Wakerly , Digital Design, Fourth Edition, Pearson/PHI, 2006. R2. Thomas L. Floyd, Digital Fundamentals, 8th Edition, Pearson Education Inc , New Delhi, 2003 Donald D.Givone , Digital Principles and Design, TMH. R3. William H. Gothmann , Digital Electronics, 2nd Edition, PHI, 1982. Dr. S. Yazhinian, AP/ CSE Digital Electronics

13. 7/4/2024 Unit 1 - Syllabus 13 UNIT I - The Wireless Channel 9 Introduction to Boolean algebra and Switching Functions Boolean Minimization using K Map and Tabulation method Combinational circuits: Half adder and Full Adder Half subtractor and Full subtractor Parallel binary Adder, Subtractor Fast Adder - Carry Look Ahead adder Serial Adder/ Subtractor BCD adder Dr. S. Yazhinian, AP/ CSE Digital Electronics

14. 7/4/2024 Unit 1 - Syllabus 14 Binary Multiplier and Divider Multiplexer and Demultiplexer Decoder and Encoder Parity checker and Parity generators Code converters Magnitude Comparator. Dr. S. Yazhinian, AP/ CSE Digital Electronics

15. 7/4/2024 Unit 1 15 Introduction to Boolean Algebra Introduction to Boolean algebra and Switching Functions Dr. S. Yazhinian, AP/ CSE Digital Electronics

16. 7/4/2024 Introduction to Boolean algebra and Switching Functions 16 Introduction to Boolean Algebra As well as the logic symbols “0” and “1” being used to represent a digital input or output, we can also use them as constants for a permanently “Open” or “Closed” circuit or contact respectively. A set of rules or Laws of Boolean Algebra expressions have been invented to help reduce the number of logic gates needed to perform a particular logic operation resulting in a list of functions or theorems known commonly as the  Laws of Boolean Algebra . Dr. S. Yazhinian, AP/ CSE Digital Electronics

17. 7/4/2024 Introduction to Boolean algebra and Switching Functions 17 Introduction to Boolean Algebra Boolean Algebra is the mathematics we use to analyse digital gates and circuits. We can use these “Laws of Boolean” to both reduce and simplify a complex Boolean expression in an attempt to reduce the number of logic gates required. The variables used in Boolean Algebra only have one of two possible values, a logic “0” and a logic “1” but an expression can have an infinite number of variables all labelled individually to represent inputs to the expression, For example, variables A, B, C etc , giving us a logical expression of A + B = C, but each variable can ONLY be a 0 or a 1. Dr. S. Yazhinian, AP/ CSE Digital Electronics

18. 7/4/2024 Introduction to Boolean algebra and Switching Functions 18 Introduction to Boolean Algebra Examples of these individual laws of Boolean, rules and theorems for Boolean Algebra are given in the following table. Dr. S. Yazhinian, AP/ CSE Digital Electronics

19. 7/4/2024 Introduction to Boolean algebra and Switching Functions 19 Introduction to Boolean Algebra Truth Tables for the Laws of Boolean Dr. S. Yazhinian, AP/ CSE-Digital Electronics

20. 7/4/2024 Introduction to Boolean algebra and Switching Functions 20 Introduction to Boolean Algebra Truth Tables for the Laws of Boolean Dr. S. Yazhinian, AP/ CSE Digital Electronics

21. Logic Gates Logic gates are abstractions of electronic circuit components that operate on one or more input signals to produce an output signal. 2- Input AND 2- Input OR NOT (Inverter) A A A B B F G H F = A • B G = A+ B H = A’ 04-07-2024 21 Dr. S. Yazhinian, AP/ CSE - Digital Electronics

22. Boolean Algebra Properties Let X : boolean variable, 0,1 : constants X + 0 = X -- Zero Axiom X • 1 = X -- Unit Axiom X + 1 = 1 -- Unit Property X • 0 = 0 -- Zero Property X + X = X -- Idepotence X • X = X -- Idepotence X + X’ = 1 -- Complement X • X’ = 0 -- Complement (X’)’ = X -- Involution 04-07-2024 22 Dr. S. Yazhinian, AP/ CSE - Digital Electronics

23. Duality With respect to duality , Identities 1 – 8 have the following relationship : 1. X + 0 = X 2. X • 1 = X (dual of 1 ) 3. X + 1 = 1 4. X • 0 = 0 (dual of 3 ) 5. X + X = X 6. X • X = X (dual of 5 ) 7. X + X’ = 1 8. X • X’ = 0 (dual of 8 ) 04-07-2024 23 Dr. S. Yazhinian, AP/ CSE - Digital Electronics

24. Basic Properties (Laws ) Commutative Law X + Y = Y + X X · Y = Y · X Associative Law X+(Y+Z)=(X+Y)+Z X(YZ) = (XY)Z Distributive Law X(Y+Z) =XY+XZ X+YZ=(X+Y)(X+Z) DeMorgan’s Theorem (X + Y)’ = X’ · Y’ (XY)’ = X’ + Y’ 04-07-2024 24 Dr. S. Yazhinian, AP/ CSE - Digital Electronics

25. Minterm 04-07-2024 25 Dr. S. Yazhinian, AP/ CSE - Digital Electronics

26. Maxterm 04-07-2024 26 Dr. S. Yazhinian, AP/ CSE - Digital Electronics

27. Truth Table notation for Minterms and Maxterms x 4 y 2 z 1 Minterm Maxterm x’y’z ’ = m x+y+z = M 1 x’y’z = m 1 x+y+z’ = M 1 1 x’yz ’ = m 2 x+y ’+z = M 2 1 1 x’yz = m 3 x+y ’+z’= M 3 1 xy’z ’ = m 4 x’+ y+z = M 4 1 1 xy’z = m 5 x’+ y+z ’ = M 5 1 1 xyz’ = m 6 x’+y’+z = M 6 1 1 1 xyz = m 7 x’+y’+z ’ = M 7 04-07-2024 27 Dr. S. Yazhinian, AP/ CSE - Digital Electronics

28. Canonical Forms Any Boolean function F( ) can be expressed as a unique sum of min terms and a unique product of max terms (under a fixed variable ordering). In other words, every function F() has two canonical forms: Canonical Sum-Of-Products (sum of minterms )- ∑ Eg : F( a,b,c ) = ∑ m (1,2,4,6) Canonical Product-Of-Sums (product of maxterms)- ∏ Eg : f 1 ( a,b,c ) = ∏ M(0,3,5,7) 04-07-2024 28 Dr. S. Yazhinian, AP/ CSE - Digital Electronics

29. Conversion Between Canonical Forms Replace ∑ with ∏ (or vice versa ) and replace those j’ s that appeared in the original form with those that do not. Example : f 1 (a, b,c ) = a’b’c + a’bc ’ + ab’c ’ + abc ’ = m 1 + m 2 + m 4 + m 6 = ∑ ( 1,2,4,6 ) = ∏ ( 0,3,5,7 ) = (a+ b+ c )•(a+ b ’+ c’)•(a’+ b+ c ’)•(a’+ b’+c ’) 04-07-2024 29 Dr. S. Yazhinian, AP/ CSE - Digital Electronics

30. Conversion of SOP from standard to canonical form Expand non-canonical terms by inserting equivalent of 1 in each missing variable x: (x + x’) = 1 Remove duplicate minterms f 1 ( a,b,c ) = a’b’c + bc ’ + ac’ = a’b’c + ( a+a ’) bc ’ + a ( b+b ’) c’ = a’b’c + abc ’ + a’bc ’ + abc ’ + ab’c ’ = a’b’c + abc ’ + a’bc ’ + ab’c ’ = m1,m6,m2,m4 f1( a,b,c )= ∑ (1,2,4,6) 04-07-2024 30 Dr. S. Yazhinian, AP/ CSE - Digital Electronics

31. Conversion of POS from standard to canonical form Expand noncanonical terms by adding 0 in terms of missing variables ( e.g. , xx’ = 0) and using the distributive law Remove duplicate maxterms f 1 ( a,b,c ) = ( a+b+c )•( b’+c ’)•( a’+c ’) = ( a+b+c )•( aa’ +b’+c ’)•( a’+ bb’ +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,M3,M7,M5 F1( a,b,c )= ∏(0,3,5,7) 04-07-2024 31 Dr. S. Yazhinian, AP/ CSE - Digital Electronics

32. Boolean Minimization using K Map and Tabulation method 04-07-2024 32 Dr. S. Yazhinian, AP/ CSE - Digital Electronics

33. Karnaugh Maps ( K Map ) Karnaugh maps (K-maps) are graphical representations of boolean functions. One map cell corresponds to a row in the truth table. Also, one map cell corresponds to a minterm or a maxterm in the boolean expression 04-07-2024 33 Dr. S. Yazhinian, AP/ CSE - Digital Electronics

34. K Map Types 04-07-2024 34 Dr. S. Yazhinian, AP/ CSE - Digital Electronics

35. m 3 m 2 1 m 1 m 1 x y 1 2 3 NOTE: ordering of variables is IMPORTANT for f( x,y ), x is the row, y is the column. Cell represents x’y ’; Cell 1 represents x’y ; etc. If a minterm is present in the function, then a 1 is placed in the corresponding cell. Cell = 2 n ,where n is a number of variables 04-07-2024 35 Dr. S. Yazhinian, AP/ CSE - Digital Electronics

36. For the case of 2 variables, we form a map consisting of 2 2 =4 cells as shown in Figure Y X 1 1 Y X 1 1 Y X 1 1 Maxterm Minterm 1 2 3 00 01 10 11 04-07-2024 36 Dr. S. Yazhinian, AP/ CSE - Digital Electronics

37. 2-variable Karnaugh maps are trivial but can be used to introduce the methods you need to learn . Simplify the following Boolean function F( x,y )=∑(1,2,3) y x 1 1 1 1 1 x y F( x,y )= x+y 1 2 3 04-07-2024 37 Dr. S. Yazhinian, AP/ CSE - Digital Electronics

38. Simplify the following Boolean function F( x,y )=∑(0,1) y x 1 1 1 1 1 2 3 04-07-2024 38 Dr. S. Yazhinian, AP/ CSE - Digital Electronics

39. Simplify the following Boolean function F( x,y )=∑(1,2) y x 1 1 1 1 1 2 3 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics 39

40. Simplify the following Boolean function F( x,y )=∑(0,3) y x 1 1 1 1 1 2 3 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics 40

41. 10 1 11 1 x yz NOTE: ordering of variables is IMPORTANT for f( x,y,z ), x is the row, y&z is the column. Cell represents x’y’z ’; Cell 1 represents x’y’z ; etc. If a minterm is present in the function, then a 1 is placed in the corresponding cell. Cell = 2 n ,where n is a number of variables 4 5 6 7 m m 1 m 3 m 2 m 4 m 5 m 7 m 6 2 3 1 Three-Variable K Map 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics 41

42. 10 1 11 1 A BC 4 5 6 7 1 1 1 1 2 3 1 Example 1 on Three-Variable K Map Simplify the following Boolean function F(A,B,C)=∑(2,3,4,5) 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics 42

43. 10 1 11 1 A BC 4 5 6 7 1 1 1 1 2 3 1 Example 2 on Three-Variable K Map Simplify the following Boolean function F(A,B,C)=∑(3,4,6,7) 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics 43

44. 10 1 11 1 A BC 4 5 6 7 1 1 1 1 1 2 3 1 Example 3 on Three-Variable K Map Simplify the following Boolean function F(A,B,C)=∑(0,2,4,5,6) 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics 44

45. 10 1 11 1 A BC 4 5 6 7 1 1 1 1 1 2 3 1 Example 4 on Three-Variable K Map Simplify the following Boolean function F(A,B,C)=∑(0,2,3,4,6) 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics 45

46. 10 1 11 1 A BC 4 5 6 7 1 1 1 1 2 3 1 Example 5 on Three-Variable K Map Simplify the following Boolean function F(A,B,C)=∑(0,1,5,7) 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics 46

47. 10 1 11 1 A BC 4 5 6 7 1 1 1 1 1 2 3 1 Example 6 on Three-Variable K Map Simplify the following Boolean function F(A,B,C)=∑(1,2,3,6,7) 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics 47

48. 10 1 11 1 A BC 4 5 6 7 1 1 1 1 2 3 1 Example 7 on Three-Variable K Map Simplify the following Boolean function F(A,B,C)=∑(3,5,6,7) 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics 48

49. 10 1 11 1 A BC 4 5 6 7 1 1 1 1 1 2 3 1 Example 8 on Three-Variable K Map Simplify the following Boolean function F(A,B,C)=∑(1,2,3,5,7) 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics 49

50. 10 1 11 1 A BC 4 5 6 7 1 1 1 1 1 1 2 3 1 Example 9 on Three-Variable K Map Simplify the following Boolean function F(A,B,C)=∑(0,2,4,5,6,7) 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics 50

51. 10 1 11 1 wx yz Cell = 2 n ,where n is a number of variables 4 5 6 7 m m 1 m 3 m 2 m 4 m 5 m 7 m 6 2 3 1 Four -Variable K Map 8 9 10 11 m 12 m 13 m 15 m 14 m 8 m 9 m 11 m 10 14 15 13 12 1 1 1 Top cells are adjacent to bottom cells. Left-edge cells are adjacent to right-edge cells. Note variable ordering ( wxyz ) or (ABCD) or (PQRS). 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics 51

52. 10 1 11 1 AB CD 4 5 6 7 Example 1 on Four -Variable K Map 8 9 10 11 1 1 1 1 1 14 15 13 12 1 1 1 Simplify the following Boolean function F(A,B,C,D)=∑(0,1,2,4,5,7,8,9,10,12,13) 1 1 1 1 1 1 2 3 1 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics 52

53. 10 1 11 1 AB CD 4 5 6 7 Example 2 on Four -Variable K Map 8 9 10 11 1 14 15 13 12 1 1 1 Simplify the following Boolean function F(A,B,C,D)=∑(4,6,7,15) 1 1 1 2 3 1 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics 53

54. 10 1 11 1 AB CD 4 5 6 7 Example 3 on Four -Variable K Map 8 9 10 11 1 1 1 1 14 15 13 12 1 1 1 Simplify the following Boolean function F(A,B,C,D)=∑2,3,12,13,14,15) 1 1 2 3 1 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics 54

55. 10 1 11 1 AB CD 4 5 6 7 Example 4 on Four -Variable K Map 8 9 10 11 1 1 1 1 1 14 15 13 12 1 1 1 Simplify the following Boolean function F(A,B,C,D)=∑(0,1,2,4,5,6,8,9,12,13,14) 1 1 1 1 1 1 2 3 1 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics 55

56. 10 1 11 1 AB CD 4 5 6 7 Example 5 on Four -Variable K Map 8 9 10 11 1 1 1 1 14 15 13 12 1 1 1 Simplify the following Boolean function F(A,B,C,D)=∑(0,2,4,5,6,7,8,10,13,15) 1 1 1 1 1 1 2 3 1 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics 56

57. 10 1 11 1 AB CD 4 5 6 7 Example 6 on Four -Variable K Map 8 9 10 11 1 1 1 1 14 15 13 12 1 1 1 Simplify the following Boolean function F(A,B,C,D)=∑(1,2,5,6,9,10,13,14) 1 1 1 1 2 3 1 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics 57

58. Example 6 on Four -Variable K Map Simplify the following Boolean function F=A’B’C’+B’CD’+A’BCD’+AB’C’ 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics 58

59. Simplify the following Boolean function F( x,y )=∏ (0,3) y x 1 1 1 1 1 2 3 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics 59

60. 10 1 11 1 A B+C 4 5 6 7 1 1 1 1 1 2 3 1 Example 10 on Three-Variable K Map Simplify the following Boolean function F(A,B,C)= ∏(1,3,5,6,7) 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics 60

61. 10 1 11 1 A+B C+D 4 5 6 7 Example 8 on Four -Variable K Map 8 9 10 11 1 1 1 1 14 15 13 12 1 1 1 Simplify the following Boolean function F(A,B,C,D)= ∏(0,1,4,5,10,11,14,15) 1 1 1 1 2 3 1 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics 61

62. 10 1 11 1 A BC 4 5 6 7 1 1 1 X X 2 3 1 Example 11 on Three-Variable K Map Simplify the following Boolean function F(A,B,C)=∑ m (0,2,4)+ ∑ d (5,6) 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics 62

63. 10 1 11 1 A BC 4 5 6 7 1 1 X 1 1 1 X X 2 3 1 Example 12 on Three-Variable K Map Simplify the following Boolean function F(A,B,C)=∑ m (0,1,2,4,5)+ ∑ d (3,6,7) 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics 63

64. 10 1 11 1 AB CD 4 5 6 7 Example 9 on Four -Variable K Map 8 9 10 11 1 1 1 X 14 15 13 12 1 1 1 Simplify the following Boolean function F(A,B,C,D)= ∑ m (0,6,8,13,14)+ ∑ d (2,4,10) 1 X X 1 2 3 1 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics 64

65. 10 1 11 1 AB CD 4 5 6 7 Example 10 on Four -Variable K Map 8 9 10 11 X X 1 1 14 15 13 12 1 1 1 Simplify the following Boolean function F(A,B,C,D)= ∑ m (1,3,5,7,9,15)+ ∑ d (4,6,12,13) 1 1 X 1 1 X 2 3 1 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics 65

66. 10 1 11 1 WX YZ 4 5 6 7 Example 11 on Four -Variable K Map 8 9 10 11 X 1 X 1 14 15 13 12 1 1 1 Simplify the following Boolean function F(W,X,Y,Z)= ∑ m (0,1,2,3,7,8,10)+ ∑ d (5,6,11,15) 1 1 1 1 X 1 X 2 3 1 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics 66

67. Quine-McCluskey Method Write minterms using binary values. Group minterms by the number of 1’s Apply adjacency ( a b´ + a b = a ) to each pair of terms, forming a second list. Check those terms in the first list that are covered by the new terms. Note that only terms in adjacent groups (that differ by one 1) need be paired. Repeat process with second list (and again if multiple terms are formed on a third list). 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics 67

68. Simplify the following Boolean function F(A,B,C,D)=∑(0,1,2,8,10,11,14,15) using Tabulation Method Group 1 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics 68 8421 0000 1 2 8 10 11 14 15 0001 0010 1000 1010 1011 1110 1111 Group 2 Group 3 Group 4 Group 5 Group 1 ABCD 000_ (0,1) (0,2) (0,8) (2,10) (8,10) (10,11) (10,14) (11,15) 00_0 _000 _010 10_0 101_ 1_10 1_11 Group 2 Group 3 Group 4 (14,15) 111_ Group 1 ABCD _0_0 (0,2,8,10) (0,8,2,10) (10,11,14,15) (10,14,11,15) _0_0 1_1_ 1_1_ Group 2 Prime Implicants 000_ (0,1) _0_0 (0,2,8,10) (10,11,14,15) 1_1_ ABCD Term A’B’C’ B’D’ AC

69. 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics 69 PRIME IMPLICANT NUMERIC 1 2 8 10 11 14 15 A’B’C’ B’D’ AC 000_ _0_0 1_1_ (0,1) (0,2,8,10) (10,11,14,15) X X X X X X X X X X

70. Simplify the following Boolean function F(A,B,C,D)=∑(0,1,2,5,6,7,8,9,10,14) using Tabulation Method Group 1 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics 70 8421 0000 1 2 8 5 6 9 7 0001 0010 1000 0101 0110 1001 0111 Group 2 Group 3 Group 4 Group 1 ABCD 000_ (0,1) (0,2) (0,8) (1,5) (1,9) (5,7) (6,7) (6,14) 00_0 _000 0_01 _001 01_1 011_ _110 Group 2 Group 3 (10,14) 1_10 Group 1 ABCD _00_ (0,1,8,9) (0,8,2,10) (2,6,10,14) (2,10,6,14) _0_0 _ _10 _ _10 Group 2 8421 0000 1 2 5 6 7 9 10 0001 0010 0101 0110 0111 1001 1010 14 8 1000 1110 10 1010 14 1110 (2,6) (8,9) 0_10 100_ (2,10) (8,10) _010 10_0 _0_0 (0,2,8,10) _00_ (0,8,1,9)

71. 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics 71 Prime Implicants (1,5) (5,7) (2,6,10,14) ABCD Term A’C’D A’BD CD’ (6,7) (0,1,8,9) (0,2,8,10) A’BC B’C’ B’D’ 0_01 01_1 011_ _0_0 _ _10 _00_

72. 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics 72 PRIME IMPLICANT NUMERIC 1 2 5 6 7 8 9 10 14 X X X X X X X X X X A’C’D A’BD CD’ A’BC B’C’ B’D’ 0_01 01_1 011_ _0_0 _ _10 _00_ (1,5) (5,7) (2,6,10,14) (6,7) (0,1,8,9) (0,2,8,10) X X X X X X X X

73. Combinational Circuit 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics 73

74. Logic circuits for digital systems may be combinational or sequential . A combinational circuit consists of input variables, logic gates, and output variables. 74 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics

75. Half Adder A combinational circuit that performs the addition of two bits is called a half adder . The truth table for the half adder is S = x ’ y + xy ’ C = xy 75 S: Sum C: Carry 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics 1 1 1 1 1 1 1 x y C S 1 1 x y 2 3 1 1 1 1 x y 2 3 1 1 1 C: Carry S: Sum

76. Implementation of Half-Adder 76 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics S = x ’ y + xy ’  x ⊕ y C = xy xy = c x ’ y + xy ’ = s

77. Full Adder A combinational circuit that performs the addition of three bits is called a full adder . The truth table for the full adder is 77 S: Sum C: Carry 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics x y S C 10 1 11 1 x yz 4 5 6 7 m m 1 m 3 m 2 m 4 m 5 m 7 m 6 2 3 1 10 1 11 1 x yz 4 5 6 7 m m 1 m 3 m 2 m 4 m 5 m 7 m 6 2 3 1

78. Full-Adder One that performs the addition of three bits(two significant bits and a previous carry) is a full adder . 78 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics

79. Simplified Expressions S = x ’ y ’ z + x ’ yz ’ + xy ’ z ’ + xyz C = xy + xz + yz 79 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics

80. Full Adder implementation Full-adder can also implemented with two half adders and one OR gate (Carry Look-Ahead adder) . S = z ⊕ (x ⊕ y) = z ’ (xy ’ + x ’ y) + z(xy ’ + x ’ y) ’ = xy ’ z ’ + x ’ yz ’ + xyz + x ’ y ’ z C = z(xy ’ + x ’ y) + xy = xy ’ z + x ’ yz + xy 80 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics

81. Binary adder This is also called Ripple Carry Adder ,because of the construction with full adders are connected in cascade. 81 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics

82. Binary subtractor M = 1 subtractor ; M = 0adder 82 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics

83. Overflow It is worth noting that binary numbers in the signed-complement system are added and subtracted by the same basic addition and subtraction rules as unsigned numbers . Overflow is a problem in digital computers because the number of bits that hold the number is finite and a result that contains n+1 bits cannot be accommodated. 83 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics

84. Overflow on signed and unsigned When two unsigned numbers are added, an overflow is detected from the end carry out of the MSB position . When two signed numbers are added, the sign bit is treated as part of the number and the end carry does not indicate an overflow. An overflow can ’ t occur after an addition if one number is positive and the other is negative . An overflow may occur if the two numbers added are both positive or both negative. 84 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics

85. BCD adder BCD adder can ’ t exceed 9 on each input digit. K is the carry. 85 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics

86. Rules of BCD adder When the binary sum is greater than 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. To distinguish them from binary 1000 and 1001, which also have a 1 in position Z 8 , we specify further that either Z 4 or Z 2 must have a 1. C = K + Z 8 Z 4 + Z 8 Z 2 86 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics

87. Implementation of BCD adder A decimal parallel adder that adds n decimal digits needs n BCD adder stages. The output carry from one stage must be connected to the input carry of the next higher-order stage. 87 If =1 0110 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics

88. 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. 88 And 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics

89. Magnitude comparator The equality relation of each pair of bits can be expressed logically with an exclusive-NOR function as: A = A 3 A 2 A 1 A ; B = B 3 B 2 B 1 B x i =A i B i +A i ’B i ’ for i = 0, 1, 2, 3 (A = B) = x 3 x 2 x 1 x 89 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics

90. Magnitude comparator We inspect the relative magnitudes of pairs of MSB . If equal, we compare the next lower significant pair of digits until a pair of unequal digits is reached. If the corresponding digit of A is 1 and that of B is 0, we conclude that A>B. (A>B)= A 3 B ’ 3 +x 3 A 2 B ’ 2 +x 3 x 2 A 1 B ’ 1 +x 3 x 2 x 1 A B ’ (A<B)= A ’ 3 B 3 +x 3 A ’ 2 B 2 +x 3 x 2 A ’ 1 B 1 +x 3 x 2 x 1 A ’ B 90 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics

91. Decoders The decoder is called n-to-m-line decoder, where m≤2 n . the decoder is also used in conjunction with other code converters such as a BCD-to-seven_segment decoder. 3-to-8 line decoder: For each possible input combination, there are seven outputs that are equal to 0 and only one that is equal to 1. 91 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics

92. Implementation and truth table 92 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics

93. Decoder with enable input Some decoders are constructed with NAND gates, it becomes more economical to generate the decoder minterms in their complemented form. As indicated by the truth table , only one output can be equal to 0 at any given time, all other outputs are equal to 1 . 93 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics

94. Demultiplexer A decoder with an enable input is referred to as a decoder/demultiplexer. The truth table of demultiplexer is the same with decoder. 94 Demultiplexer D0 D1 D2 D3 E A B 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics

95. Encoders An encoder is the inverse operation of a decoder . We can derive the Boolean functions by table z = D 1 + D 3 + D 5 + D 7 y = D 2 + D 3 + D 6 + D 7 x = D 4 + D 5 + D 6 + D 7 95 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics

96. Priority encoder If two inputs are active simultaneously , the output produces an undefined combination . We can establish an input priority to ensure that only one input is encoded. Another ambiguity in the octal-to-binary encoder is that an output with all 0 ’ s is generated when all the inputs are 0 ; the output is the same as when D is equal to 1. The discrepancy tables can resolve aforesaid condition by providing one more output to indicate that at least one input is equal to 1. 96 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics

97. Priority encoder V=0 no valid inputs V=1valid inputs X ’ s in output columns represent don ’ t-care conditions X ’ s in the input columns are useful for representing a truth table in condensed form. Instead of listing all 16 minterms of four variables. 97 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics

98. 4-input priority encoder Implementation of table x = D 2 + D 3 y = D 3 + D 1 D ’ 2 V = D + D 1 + D 2 + D 3 98 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics

99. Multiplexers S = 0, Y = I Truth Table  S Y Y = S ’ I + SI 1 S = 1, Y = I 1 0 I 1 I 1 99 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics

100. 4-to-1 Line Multiplexer 100 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics

101. Boolean function implementation A more efficient method for implementing a Boolean function of n variables with a multiplexer that has n-1 selection inputs. F(x, y, z) =  (1,2,6,7) 101 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics

102. 4-input function with a multiplexer F(A, B, C, D) =  (1, 3, 4, 11, 12, 13, 14, 15) 102 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics

103. Code Conversion Code-Conversion example, first, we can list the relation of the BCD and Excess-3 codes in the truth table. 103 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics

104. Karnaugh map For each symbol of the Excess-3 code, we use 1 ’ s to draw the map for simplifying Boolean function. 104 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics

105. Circuit implementation z = D ’ ; y = CD + C ’ D ’ = CD + (C + D) ’ x = B ’ C + B ’ D + BC ’ D ’ = B ’ (C + D) + B(C + D) ’ w = A + BC + BD = A + B(C + D) 105 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics

106. Thank You 04-07-2024 Dr. S. Yazhinian, AP/ CSE - Digital Electronics 106