EEE303-Week02 - Boolean Algebra and Num.pptx

Boolean Algebra

1. Weekly Lecture Plan Week Topic  Textbook 1 Introduction to Number Systems and codes, Introduction to VerilogHDL Harris 1.4, 5.3, 1.5 2-3 Introduction to Boolean algebra, Analysis and synthesis of digital logic circuits: Basic logic function, combinational logic design, Universal logic gates, Minimization of combinational logic, k-map Harris 2.1-2.9 4 Programming and structural and behavioral design of digital systems using VerilogHDL , Verilog Timing analysis and test bench. Verilog synthesis with combinational logic Harris 4 5 ALU design (Adder, Subtractor, Comparator) Harris 5.2- Floyd 6.1-6.3   Winter Vacation   6 Decoder, encoder, Multiplexer, demultiplexer Floyd 6.4-6.9

2. Boolean Algebra Week 02

3. Boolean Logic: Introductions, Basic Gates Lecture 02.1

4. Introduction to Logic: State and Output If a given switch is controlled by an input variable x, then we will say that the switch is open if x = 0 and closed if x = 1. Such switches are implemented with transistors.

5. Variable and States The output is defined as the state (or condition) of the light L. If the light is on, we will say that L = 1. If the light is off, we will say that L = 0. Since L = 1 if x = 1 and L = 0 if x = 0, we can say that L(x) = x. We say that L(x) = x is a logic function and that x is an input variable.

6. Logical AND Operation Symbol Operation: A.B

7. AND operation

8. Application of AND logic

9. Logical OR Operation Symbol Operation: A+B

10. OR operation

11. Application of OR logic

12. Application of NOT logic

13. NAND Operation NOR Operation

14. Example of NAND

15. Example of NOR

16. XOR Exclusive OR XNOR

17. Application of XOR gate

18. Implementing Boolean Logic Integrated Circuits Programmable Logic 20

19. Implementation of Boolean Logic: Integrated Circuits Standard Integrated circuits are available for Use that has logic IC built in. 14 Pin Dual-Inline-Package (DIP) IC are suitable to be plugged into a breadboard Most commonly starts with 74 IC number

20. AND ICs Available AND Gate ICs

21. NAND ICs Available NAND Gate ICs

22. OR, NOR ICs

23. Logic IC family Most common in lab

24. A 74HC IC will regard 2-6 V as logic 1, where as 74LS IC will recognize only above 4.5V as 1 So care should be taken while mixing them Source: Wikipedia

25. Implementation of Boolean Logic: Programmable Logic Programmable Logic Devices has internally gate arrays that can be connected through programming. Useful for prototyping

26. Implementation of Boolean Logic: Programmable Logic Programmable logic devices can be programmed to perform specified logic functions and operations by the manufacturer or by the user. Many types of programmable logic are available, ranging from small devices that can replace a few fixed-function devices to complex high-density devices that can replace thousands of fixed-function devices. Two major categories of user-programmable logic are PLD (programmable logic device) and FPGA (field-programmable gate array)

27. SPLD (Simple Programmable Logic Device) The SPLD was the original PLD and is still available for small-scale applications. Generally, an SPLD can replace up to ten fixed-function ICs and their interconnections, depending on the type of functions and the specific SPLD. Most SPLDs are in one of two categories: PAL and GAL. A PAL (programmable array logic) is a device that can be programmed one time. It consists of a programmable array of AND gates and a fixed array of OR gates, as shown in Figure 1–30(a). A GAL (generic array logic) is a device that is basically a PAL that can be reprogrammed many times. It consists of a reprogrammable array of AND gates and a fixed array of OR gates with programmable ouputs ,

28. Programmable AND Array 30 Most types of PLDs use some form of AND array . Basically, this array consists of AND gates and a matrix of interconnections with a programmable link at each cross point. Programmable links allow a connection between a row line and a column line in the interconnection matrix to be opened or left intact. For each input to an AND gate, only one programmable link is left intact in order to connect the desired variable to the gate input.

29. CPLD (Complex Programmable Logic Device) CPLD is a device containing multiple SPLDs and can replace many fixed-function ICs. Figure 1–32 shows a basic CPLD block diagram with four logic array blocks (LABs) and a programmable interconnection array (PIA). Depending on the specific CPLD, there can be from two to sixty-four LABs. Each logic array block is roughly equivalent to one SPLD

30. The Programming Process 32 An SPLD, CPLD, or FPGA can be thought of as a “blank slate” on which you implement a specified circuit or system design using a certain process. This process requires a software development package installed on a computer to implement a circuit design in the programmable chip.

31. FPGA (Field Programmable Gate Array) An FPGA is generally more complex and has a much higher density than a CPLD. The FPGA has a different internal structure (architecture). The three basic elements in an FPGA are the logic block, the programmable interconnections, and the input/output (I/O) blocks . The distributed programmable interconnection matrix provides for interconnection of the logic blocks and connection to inputs and outputs

32. Programming Gate Array

33. Fuse vs Antifuse

34. EPROM

35. SRAM

36. Boolean Algebra: Axioms Lecture 02.2

37. Boolean Algebra Based on a set of rules derived from a small number of basic assumptions- Axioms Think of Euclidean Geometry Axio m s Found application in engineering after almost 100 years Introduced by George Boole In 1849

38. Boolean Operators Addition Multiplication

39. Venn Diagram to Understand Logic 41

40. A logic circuit is composed of: Inputs Outputs Functional specification Timing specification Introduction

41. Nodes Inputs: A , B , C Outputs: Y , Z Internal: n1 Circuit elements E1, E2, E3 Each a circuit Circuits

42. Combinational Logic Memory less Outputs determined by current values of inputs Sequential Logic Has memory Outputs determined by previous and current values of inputs Types of Logic Circuits

43. Every element is combinational Every node is either an input or connects to exactly one output The circuit contains no cyclic paths Example: Rules of Combinational Composition

44. Functional specification of outputs in terms of inputs Example: S = F( A , B , C in ) C out = F( A , B , C in ) Boolean Equations

45. Complement : variable with a bar over it A , B , C Literal : variable or its complement A , A , B , B , C , C Implicant : product of literals ABC , AC , BC Minterm : product that includes all input variables ABC , ABC , ABC Maxterm : sum that includes all input variables (A+B+C) , (A+B+C) , (A+B+C) Some Definitions

46. Sum-of-Products (SOP) Form All Boolean equations can be written in SOP form Each row has a minterm A minterm is a product (AND) of literals Each minterm is TRUE for that row (and only that row) Form function by ORing minterms where output is 1 Thus, a sum (OR) of products (AND terms) Y = F( A , B ) = AB + AB 1 1 = Σ (1, 3)

47. Product-of-Sums (POS) Form All Boolean equations can be written in POS form Each row has a maxterm A maxterm is a sum (OR) of literals Each maxterm is FALSE for that row (and only that row) Form function by ANDing maxterms where output is Thus, a product (AND) of sums (OR terms) Y = F( A , B ) = ( A + B ) ● ( A + B ) 1 1 = Π (0, 2)

48. Boolean Equations Example You are going to the cafeteria for lunch You won’t eat lunch (E=0) If it’s not open (O=0) or If they only serve corndogs (C=1) Write a truth table for determining if you will eat lunch (E). 1

49. SOP & POS Form SOP – sum-of-products POS – product-of-sums E = ( O + C )( O + C )( O + C ) = Π (0, 1, 3) E = OC = Σ (2)

50. Axioms and theorems to simplify Boolean equations Like regular algebra, but simpler: variables have only two values (1 or 0) Duality in axioms and theorems: ANDs and ORs, 0’s and 1’s interchanged Boolean Algebra

51. Boolean Axioms Number Axiom Name A1 B = 0 if B ≠ 1 Binary Field A2 = 1 NOT A3 • 0 = 0 AND/OR A4 1 • 1 = 1 AND/OR A5 • 1 = 1 • 0 = 0 AND/OR Dual: Replace: • with + 0 with 1

52. Boolean Axioms Number Axiom Dual Name A1 B = 0 if B ≠ 1 B = 1 if B ≠ Binary Field A2 = 1 1 = 0 NOT A3 • 0 = 0 1 + 1 = 1 AND/OR A4 1 • 1 = 1 0 + 0 = 0 AND/OR A5 • 1 = 1 • 0 = 0 1 + 0 = 0 + 1 = 1 AND/OR Dual: Replace: • with + 0 with 1

53. Boolean Theorems of One Variable Number Theorem Name T1 B • 1 = B Identity T2 B • 0 = 0 Null Element T3 B • B = B Idempotency T4 B = B Involution T5 B • B = Complements Dual: Replace: • with + 0 with 1

54. Boolean Theorems of One Variable Number Theorem Dual Name T1 B • 1 = B B + 0 = B Identity T2 B • 0 = 0 B + 1 = 1 Null Element T3 B • B = B B + B = B Idempotency T4 B = B Involution T5 B • B = B + B = 1 Complements Dual: Replace: • with + 0 with 1

55. B 1 = B B + 0 = B T1: Identity Theorem

56. B 0 = 0 B + 1 = 1 T2: Null Element Theorem

57. B B = B B + B = B T3: Idempotency Theorem

58. B = B T4: Identity Theorem

59. B B = 0 B + B = 1 T5: Complement Theorem

60. Boolean Theorems of Several Vars Number Theorem Name T6 B•C = C • B Commutativity T7 (B•C) • D = B • (C • D) Associativity T8 B • (C + D) = (B • C) + (B • D) Distributivity T9 B• (B+C) = B Covering T10 (B•C) + (B•C) = B Combining T11 (B•C) + (B•D) + (C•D) = (B • C) + (B • D) Consensus How do we prove these are true?

61. How to Prove Method 1: Perfect induction Method 2: Use other theorems and axioms to simplify the equation Make one side of the equation look like the other

62. Proof by Perfect Induction Also called: proof by exhaustion Check every possible input value If the two expressions produce the same value for every possible input combination, the expressions are equal

63. 0 0 0 0 0 0 1 1 Number Theorem Name T6 B•C = C • B Commutativity Example: Proof by Perfect Induction 0 0 0 1 1 0 1 1 B C BC CB

64. Dual: Replace: • with + 0 with 1 # Theorem Dual Name T6 B•C = C • B B+C = C+B Commutativity T7 (B•C) • D = B • (C • D) (B + C) + D = B + (C + D) Associativity T8 B • (C + D) = (B • C) + (B • D) B + (C • D) = (B+C) (B+D) Distributivity T9 B • (B+C) = B B + (B•C) = B Covering T10 (B•C) + (B•C) = B (B+C) • (B+C) = B Combining T11 (B•C) + (B•D) + (C•D) = (B • C) + (B • D) (B+C) • (B+D) • (C+D) = (B+C) • (B+D) Consensus Boolean Theorems of Several Vars

65. # Theorem Dual Name T6 B•C = C • B B+C = C+B Commutativity T7 (B•C) • D = B • (C • D) (B + C) + D = B + (C + D) Associativity T8 B • (C + D) = (B • C) + (B • D) B + (C • D) = (B+C) (B+D) Distributivity T9 B • (B+C) = B B + (B•C) = B Covering T10 (B•C) + (B•C) = B (B+C) • (B+C) = B Combining T11 (B•C) + (B•D) + (C•D) = (B • C) + (B • D) (B+C) • (B+D) • (C+D) = (B+C) • (B+D) Consensus Boolean Theorems of Several Vars Warning: T8’ differs from traditional algebra: OR (+) distributes over AND (•)

66. Simplifying an Equation Reducing an equation to the fewest number of implicants , where each implicant has the fewest literals Recall: Implicant : product of literals ABC , AC , BC Literal: variable or its complement A , A , B , B , C , C Simplifying the equation is also called minimizing the equation

67. Simplification methods Distributivity (T8, T8’) B (C+D) = BC + BD B + CD = (B+ C)(B+D) Covering (T9’) A + AP = A Combining (T10) PA + PA = P Expansion P = PA + PA A = A + AP Duplication A = A + A “Simplification” theorem PA + A = P + A PA + A = P + A

68. Proving the “Simplification” Theorem “Simplification” theorem PA + A = P + A Method 1: PA + = PA + ( + P) T9’ Covering = PA + P + T6 Commutativity = P(A + ) + T8 Distributivity = P (1) + A T5’ Complements = P + A T1 Identity  

69. “Simplification” theorem PA + A = P + A Proving the “Simplification” Theorem Method 2: PA + = ( + A) ( + P) T8’ Distributivity = 1( + P) T5’ Complements = + P T1 Identity  

70. Y = AB + AB Simplifying Boolean Equations Example 1:

71. Y = AB + AB Y = A T10: Combining or = A ( B + B ) T8: Distributivity = A (1) T5’: Complements = A T1: Identity Simplifying Boolean Equations Example 1:

72. Y = A ( AB + ABC) = A ( AB( 1 + C )) T8: Distributivity = A ( AB (1)) T2’: Null Element = A ( AB ) T1: Identity = ( AA ) B T7: Associativity = AB T3: Idempotency Example 2: Simplifying Boolean Equations

73. Y = A’BC + A’ Recall: A’ = A Note: A‘ is shorthand for A. But use the tick symbol (‘) only when typing. It’s easy to lose ticks (‘) when writing by hand! It is strongly recommended that you simplify equations by writing by hand. Example 3: Simplifying Boolean Equations

74. Y = A’BC + A’ Recall: A’ = A = A’ T9’ Covering: X + XY = X or = A’(BC + 1) T8: Distributivity = A’(1) T2’: Null Element = A’ T1: Identity Example 3: Simplifying Boolean Equations

75. Y = AB’C + ABC + A’BC = AB’C + ABC + ABC + A’BC T3’: Idempotency = (AB’C+ABC) + (ABC+A’BC) T7’: Associativity = AC + BC T10: Combining Example 4: Simplifying Boolean Equations

76. Y = AB + BC +B’D’ + AC’D’ Method 1: Y = AB + BC + B’D’ + (ABC’D’ + AB’C’D’) T10: Combining = (AB + ABC’D’) + BC + (B’D’ + AB’C’D’) T6: Commutativity T7: Associativity = AB + BC + B’D’ T9: Covering Method 2: Y = AB + BC + B’D ’ + AC’D’ + AD’ T11: Consensus = AB + BC + B’D’ + AD’ T9: Covering = AB + BC + B’D’ T11: Consensus Example 5: Simplifying Boolean Equations

77. Y = (A + BC)(A + DE) Apply T8’ first when possible: W+XZ = (W+X)(W+Z) Make: X = BC, Z = DE and rewrite equation Y = (A+X)(A+Z) substitution (X=BC, Z=DE) = A + XZ T8’: Distributivity = A + BCDE substitution or Y = AA + ADE + ABC + BCDE T8: Distributivity = A + ADE + ABC + BCDE T3: Idempotency = A + ADE + ABC + BCDE = A + ABC + BCDE T9’: Covering = A + BCDE T9’: Covering Example 6: Simplifying Boolean Equations This is called multiplying out an expression to get sum-of-products (SOP) form.

78. SOP – sum-of-products POS – product-of-sums E = ( O + C )( O + C )( O + C ) = Π (0, 1, 3) E = OC = Σ (2) Review: Canonical SOP & POS Forms

79. An expression is in sum-of-products (SOP) form when all products contain literals only. SOP form: Y = AB + BC’ + DE NOT SOP form: Y = DF + E(A’+B) SOP form: Z = A + BC + DE’F Multiplying Out: SOP Form

80. Y = (A + C + D + E)(A + B) Apply T8’ first when possible: W+XZ = (W+X)(W+Z) Make: X = (C+D+E), Z = B and rewrite equation Y = (A+X)(A+Z) substitution (X=(C+D+E), Z=B) = A + XZ T8’: Distributivity = A + (C+D+E)B substitution = A + BC + BD + BE T8: Distributivity or Y = AA+AB+AC+BC+AD+BD+AE+BE T8: Distributivity = A +AB+AC+AD+AE+BC+BD+BE T3: Idempotency = A + BC + BD + BE T9’: Covering Example: Multiplying Out: SOP Form

81. An expression is in product-of-sums (POS) form when all sums contain literals only. POS form: Y = (A+B)(C+D)(E’+F) NOT POS form: Y = (D+E)(F’+GH) POS form: Z = A(B+C)(D+E’) Factoring: POS Form

82. Y = (A + B’CDE) Apply T8’ first when possible: W+XZ = (W+X)(W+Z) Make: X = B’C, Z = DE and rewrite equation Y = (A+XZ) substitution (X=B’C, Z=DE) = (A+B’C)(A+DE) T8’: Distributivity = (A+B’)(A+C)(A+D)(A+E) T8’: Distributivity Example 1: Factoring: POS Form

83. Y = AB + C’DE + F Apply T8’ first when possible: W+XZ = (W+X)(W+Z) Make: W = AB, X = C’, Z = DE and rewrite equation Y = (W+XZ) + F substitution W = AB, X = C’, Z = DE = (W+X)(W+Z) + F T8’: Distributivity = (AB+C’)(AB+DE)+F substitution = (A+C’)(B+C’)(AB+D)(AB+E)+F T8’: Distributivity = (A+C’)(B+C’)(A+D)(B+D)(A+E)(B+E)+F T8’: Distributivity = (A+C’+F)(B+C’+F)(A+D+F)(B+D+F)(A+E+F)(B+E+F) T8’: Distributivity Example 2: Factoring: POS Form

84. Boolean Algebra: De Morgan’s Theorem Lecture 02.3

85. De Morgan’s Theorem 27 June 1806 – 18 March 1871 The  complement  of the union of two sets is the same as the intersection of their complements The complement of the intersection of two sets is the same as the union of their complements

86. De Morgan’s Theorem Number Theorem Name T12 B •B 1 • B 2 … = B +B 1 +B 2 … DeMorgan’s Theorem The complement of the product is the sum of the complements

87. DeMorgan’s Theorem: Dual The complement of the product is the sum of the complements . # Theorem Dual Name T12 B •B 1 • B 2 … = B +B 1 +B 2 … B + B 1 +B 2 … = B • B 1 • B 2 … DeMorgan’s Theorem Dual: The complement of the sum is the product of the complements .

88. Y = AB = A + B Y = A + B = A B DeMorgan’s Theorem

89. Y = (A+BD)C = (A+BD) + C = (A•(BD)) + C = (A•(BD)) + C = ABD + C DeMorgan’s Theorem Example 1

90. Y = (ACE+D) + B DeMorgan’s Theorem Example 2

91. Y = AB = A + B Y = A + B = A B DeMorgan’s Theorem

92. Backward: Body changes Adds bubbles to inputs Forward: Body changes Adds bubble to output Bubble Pushing

93. What is the Boolean expression for this circuit? Y = AB + CD Bubble Pushing

94. Begin at output, then work toward inputs Push bubbles on final output back Draw gates in a form so bubbles cancel Bubble Pushing Rules

95. Bubble Pushing Example

96. Bubble Pushing Example

97. Bubble Pushing Example

98. Bubble Pushing Example

99. Two-level logic: ANDs followed by ORs Example: Y = ABC + ABC + ABC From Logic to Gates

100. Inputs on the left (or top) Outputs on right (or bottom) Gates flow from left to right Straight wires are best Circuit Schematics Rules

101. Wires always connect at a T junction A dot where wires cross indicates a connection between the wires Wires crossing without a dot make no connection Circuit Schematic Rules (cont.)

102. Multiple-Output Circuits Example: Priority Circuit Output asserted corresponding to most significant TRUE input

103. Example: Priority Circuit Output asserted corresponding to most significant TRUE input Multiple-Output Circuits

104. Priority Circuit Hardware

105. Don’t Cares

106. Contention: circuit tries to drive output to 1 and Actual value somewhere in between Could be 0, 1, or in forbidden zone Might change with voltage, temperature, time, noise Often causes excessive power dissipation Warnings: Contention usually indicates a bug . X is used for “don’t care” and contention - look at the context to tell them apart. Contention: X

107. Floating, high impedance, open, high Z Floating output might be 0, 1, or somewhere in between A voltmeter won’t indicate whether a node is floating Tristate Buffer Floating: Z

108. Floating nodes are used in tristate buses Many different drivers Exactly one is active at once Tristate Buses