Digital Design and Computer Organization Chapter 3 (PDF)

CENG 205 Digital Design and Computer Organization Chapter 3 Combinational Circuits 1 Combinational Circuits Reading: Mano: Chapter 2: 2.1 Binary Logic and Gates. 2.3 Standard Forms....

CENG 205 Digital Design and Computer Organization Chapter 3 Combinational Circuits 1 Combinational Circuits Reading: Mano: Chapter 2: 2.1 Binary Logic and Gates. 2.3 Standard Forms. 2  Course Objectives  CLOs: After the completion of this chapter you will be able to: 1. Convert between different number systems and represent signed numbers in both 1's and 2's complement representation. 2. Analyze combinational and sequential circuits. 3. Design and implement combinational and sequential circuits. 4. Define a modern computer system's major components, their functions and inter-relationships. 5. Explain the memory hierarchy structure and the importance and characteristics of each level. 6. Describe the components of the instruction sets and the different types of instructions and addressing modes. 3  Outline Truth Table Logic Gates Circuit Analysis Functions in Standard Forms Standard Design Procedure 4  Truth Table A truth table is a method for describing how a logic circuit’s output depends on its inputs. A ? X B inputs output A B X For a circuit with n inputs 0 0 1 and m outputs, the truth 22 0 1 0 table will have 2n rows and (n + m) columns. 1 0 1 1 1 05  Outline Truth Table Logic Gates Circuit Analysis Functions in Standard Forms Standard Design Procedure 6  Logic Gates A logic gate is an electronic device that acts as a building block for any digital circuit. We have 7 basic logic gates: – NOT, AND, OR, XOR, NAND, NOR, XNOR. 7  Logic Gates A logic gate is an electronic device that acts as a building block for any digital circuit. OR XOR NOT AND A A A A Y Y Y Y B B B Y=A Y = AB Y=A+B Y=A+B A Y A B Y A B Y A B Y 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 1 0 1 1 1 0 0 1 0 1 1 0 1 1 1 1 1 1 1 1 1 0 The output = the sum of input bits with ignoring the carry 8  Logic Gates A logic gate is an electronic device that acts as a building block for any digital circuit. NAND NOR XNOR A A Y Y Y B B Y = AB Y=A+B Y=A+B A B Y A B Y A B Y 0 0 1 0 0 1 0 0 1 0 1 1 0 1 0 0 1 0 1 0 1 1 0 0 1 0 0 1 1 0 1 1 0 1 1 1 ) 9  Logic Gates Multiple Inputs Gates Logic gates may have more than two inputs: – Multiple-input AND gate: Responds with a logic 1 output if all inputs are logic 1. The output is logic 0 if any input is logic 0. – Multiple-input OR gate: Responds with a logic 1 if any input is logic 1. The output becomes a logic 0 only when all inputs are logic 0. 10  Logic Gates Multiple Inputs Gates Logic gates may have more than two inputs: – Multiple-input XOR gate: Works by summing all bits and ignoring the carries, or: XOR operation of one variable with the result of XOR operations of the other two variables. 11  Logic Gates Transistor Operation The transistor is the workhorse of every electronic device. Transistor 12  Logic Gates Describing a Logic Circuit Algebraically Describe the output as a function of the inputs: – Traverse the circuit diagram from left to right. – Compute the outputs at each stage. a 𝐴 A 𝐴 ⨁ 𝐵𝐶. () b B 𝐵𝐶 fF c C. d D 𝐶+𝐷 F=. 13  Logic Gates Exercises Describe the following digital circuit algebraically: F= + 14  Logic Gates Exercises Describe the following digital circuit algebraically: F= + 15  Logic Gates Exercises Describe the following digital circuit algebraically: 𝐅 =( 𝐀 + 𝐂 ). ( 𝐁𝐂 ). ( 𝐀 ⨁ 𝐂 ) 16  Logic Gates Function Evaluation Compute the value of a function for specific values for the inputs. – By substitution and applying Boolean Operator Precedence. – The order of evaluation in a Boolean expression is: Parenthes First (highest priority) es NOT XOR AND OR Last (lowest priority) 17  Logic Gates Exercise Evaluate the following function for A = 1, B = 1, C = 0, D = 0: F(A, B, C, D) = 0 0 0 1 0 0 + 0 + 1 = 1 18  Logic Gates Drawing the Circuit Diagram Draw the circuit diagram for the function using 2- input gates: F(A, B, C, D) = A B C D 𝑨𝑩 + 𝑩+ 𝑪 𝑩+𝑪. 𝐂𝐃 F=+ 𝐂𝐃 𝑫 𝑨𝑫 19  Exercise Draw the circuit diagram corresponding to the following function and then evaluate it for A = 1, B = 0, C = 1, D = 1: A B C DF(A, B, C, 𝑨𝑩D) = 𝑨+ 𝑪 C⊕D ) ( 𝑨+𝑪). C ⊕ D F=+ 𝑫 𝑨𝑫 20  Exercise Draw the circuit diagram corresponding to the following function and then evaluate it for A = 1, B = 0, C = 1, D = 1: F(A, B, C, D) = 1 1 0 0 0 1 F=1 21  Outline Truth Table Logic Gates Circuit Analysis Functions in Standard Forms Standard Design Procedure 22  Circuit Analysis To analyze 1- Derive the equation of a the output signal(s) from combinatio the provided circuit nal circuit: diagram. 2- Construct the truth table according to the number of inputs and number of outputs. 3- Complete the truth table by calculating the output logic for each input combination (input vector). 23  Example A B C D F 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0 1 0 1 0 1 0 0 1 1 0 1 0 1 1 1 1 1 0 0 0 1 0 1 1 1 1 0 0 1 1 1 0 1 0 1 1 1 1 1 1 0 1 1 1 F=. 1 1 0 0 1 1 1 0 1 1 1 1 1 0 0 1 1 1 1 0 24  Exercise Draw the circuit diagram for the following equation and derive the associated truth table.. A B C 𝑩𝑪 𝑪. 𝑩𝑪 𝑩 ) 𝐀⨁𝐁. 𝑨 25  Exercise Draw the circuit diagram for the following equation and derive the associated truth table.. A B C F 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1 26  Circuit Analysis DeMorgan’s Law A Y B 𝒀 = 𝑨𝑩 = 𝑨 + 𝑩 A Y B A Y B 𝒀 = 𝑨 + 𝑩= 𝑨. 𝑩 A Y B 27  Example What is the Boolean expression for this circuit? A B Y Y = ((AB). (CD)) C D A B C Y Y = AB + CD D 28  Exercises What are the equivalent Boolean expressions for the following functions? Y = ((AB). C) = AB + C Y = (AB + C) = AB. C Y = (AB + (CD+A)) = AB. (CD+A) = AB. CD. A 29  Outline Truth Table Logic Gates Circuit Analysis Functions in Standard Forms Standard Design Procedure 30  Functions in Standard Forms A Boolean function expressed algebraically can be written in a variety of ways. non-standard F=. form There are specific ways of writing algebraic equations that are considered to be standard forms: + + (SOP). 1) Sum Of Products A (.(POS). 2) Product Of Sums (A + 31  Functions in Standard Forms Sum Of Products A product term in which all the variables appear exactly once, either complemented or uncomplemented, the variables ANDed together, is called a minterm. A minterm represents exactly one combination of binary variables in the truth table. X Y Z XYZ Product Minterm Term 0 0 0 000 m0 0 0 1 0 1 0 001 m1 0 1 1 010 m2 1 0 0 011 Z m3 1 0 1 100 m4 1 1 0 101 m5 1 1 1 32 110 m6  Functions in Standard Forms Sum Of Products A product term in which all the variables appear exactly once, either complemented or uncomplemented, the variables ANDed together, is called a minterm. A minterm represents exactly one combination of binary variables in the truth table. A circuit with n inputs has 2n minterms. We can write any function in terms of its minterms because each minterm simply represent an input combination.Sum the To obtain Set up the selected the SOP (Sum Of Products) truth table minterms. representation of a circuit: From the truth table, select all 33 minterms that  Functions in Standard Forms Sum Of Products Example (1): Obtain the SOP equation for the function shown in the following table: + A B C F 0 0 0 1 0 0 1 0 + +A 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 0 1 1 1 0 34  Functions in Standard Forms Sum Of Products Example (2): represent the following function in minterms format. 𝑭 ( 𝑨 , 𝑩 , 𝑪 )= 𝑨 𝑩 𝑪+ 𝑨 𝐵 𝑪 + 𝑨 𝑩 𝑪 + 𝑨𝑩𝑪 F (A, B, C) = m0 + m2 + m5 + m7 F (A, B, C)A = ∑m(0, B C 2, F 5, 7) 0 0 0 m0 1 0 0 1 m1 0 0 1 0 m2 1 0 1 1 m3 0 1 0 0 m4 0 1 0 1 m5 1 1 1 0 m6 0 1 1 1 m7 351  Functions in Standard Forms Sum Of Products Example (3): Obtain the SOP equation for a 2- input XOR and XNOR gates. XNOR XOR A Y = m1 + m2 A Y Y B B = Y=A+B Y=A+B A B Y 0 0 1 A B Y 0 1 0 Y = m0 + m3 0 0 0 1 0 0 0 1 1 1 1 1 1 0 1 = 1 1 0 36  Functions in Standard Forms Product Of Sums A sum term in which all the variables appear exactly once, either complemented or uncomplemented, the variables are ORed together, is called a maxterm. Maxterm is the complement of the minterm. Any function can be expressed as POS. Proof: A B C Z 0 0 0 1 0 𝑍 =𝑚0 +𝑚 2 +𝑚3 +𝑚5 + 𝑚6 0 0 1 0 1 𝑍 =𝑚1 +𝑚 4 +𝑚7 0 1 0 1 0 0 1 1 1 0 ´ =𝑚 + 𝑚 +𝑚 𝑍 =𝑍 1 0 0 0 1 1 4 7 1 0 1 1 0 𝑍 =𝑚1 ∙𝑚 4 ∙𝑚7 1 1 0 1 0 1 1 1 0 1 𝑍 =( 𝐴 𝐵 𝐶 ) ∙ ( 𝐴 𝐵 𝐶 ) ∙ ( 𝐴𝐵𝐶 ) 𝑍 =( 𝐴+ 𝐵+ 𝐶 ) ∙ ( 𝐴+ 𝐵+𝐶 ) ∙ ( 𝐴+ 𝐵+ 𝐶 ) 37 𝑍 =𝑀 1 ∙ 𝑀 4 ∙ 𝑀 7  Functions in Standard Forms Product Of Sums To express a Function in POS (Product Of Sums), just look at where the function equals 0 (output = 0). Make the POS term (maxterm) with inverted variables (A = 1 means A and A = 0 means A, and so on). XYZ Minterm Maxterm 000 001 010 011 Z 100 101 110 111 38  Functions in Standard Forms SOP & POS 𝑍 =𝑚0 +𝑚 2 +𝑚3 +𝑚5 + 𝑚6 A B C Z 0 0 0 1 0 0 0 1 0 1 0 1 0 1 0 0 1 1 1 0 𝑍 =𝑀 1 ∙ 𝑀 4 ∙ 𝑀 7 1 0 0 0 1 1 0 1 1 0 𝑍 =( 𝐴+ 𝐵+ 𝐶 ) ∙ ( 𝐴+ 𝐵+𝐶 ) ∙ ( 𝐴+ 𝐵+ 𝐶 ) 1 1 0 1 0 1 1 1 0 1 A B C SO PO P A B C S Z Z 39  Exercise Write both the SOP and the A B C D Z POS equation for the 0 0 0 0 0 function represented by 0 0 0 1 1 the following truth table: 0 0 1 0 1 0 0 1 1 0 SOP: 0 1 0 0 0 Z = m1+m2+m5+m7+m8+m11+m13+m14+m15 0 1 0 1 1 0 1 1 0 0 = A’B’C’D + A’B’CD’ + A’BC’D + A’BCD +0 1 1 1 1 AB’C’D’ + AB’CD + ABC’D + ABCD’ + 1 0 0 0 1 ABCD 1 0 0 1 0 1 0 1 0 0 1 0 1 1 1 1 1 0 0 0 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 40  Exercise Write both the SOP and the ABC D Z POS equation for the 0 0 0 0 0 function represented by 0 0 0 1 1 the following truth table: 0 0 1 0 1 0 0 1 1 0 POS: 0 1 0 0 0 Z = M0M3M4M6M9M10M12 0 1 0 1 1 0 1 1 0 0 = (A+B+C+D).(A+B+C’+D’). 0 1 1 1 1 (A+B’+C+D).(A+B’+C’+D). 1 0 0 0 1 (A’+B+C+D’).(A’+B+C’+D).(A’+B’+C+D) 1 0 0 1 0 1 0 1 0 0 1 0 1 1 1 1 1 0 0 0 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 41  Outline Truth Table Logic Gates Circuit Analysis Functions in Standard Forms Standard Design Procedure 42  Standard Design Procedure Set up the truth table Identify the minterms for each case where the output is 1 Write the SOP expression for the output Simplify the output expression Done by applying Implement Boolean Algebra or K- the circuit for the simplified maps expression 43  Example Design a logic circuit that has three inputs, and whose output will be HIGH only when a majority of the inputs are HIGH. F = m3+ m5+ m6 + m7 A B C F 0 0 0 0 = A’BC + AB’C + ABC’ + ABC 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 44  Standard Design Procedure Universality of NAND and NOR gates NAND and NOR are universal gates: – They are easy to manufacture (4 transistors each, while AND/OR made of 6). – It is possible to implement any logic expression using only NAND or only NOR NOT: AND: gates and no other type of gate. A AB B AB A A AB = A + B OR: B 45 B  Assignment #2 Solve problem 2.10 from the book on BlackBoard. 46 47