Logic Design PDF

LOGIC DESIGN Dr.Eng. Mahmoud Abu Alfutuh Chapter 3 Boolean Algebra and Logic Gates Dr.Eng. Mahmoud Abu_Alfutuh 2 Chapter 3 - Boolean Algebra and Logic Gates Boolean Algebra Logic gates 3 ...

LOGIC DESIGN Dr.Eng. Mahmoud Abu Alfutuh Chapter 3 Boolean Algebra and Logic Gates Dr.Eng. Mahmoud Abu_Alfutuh 2 Chapter 3 - Boolean Algebra and Logic Gates Boolean Algebra Logic gates 3  Chapter 3 Logic gates ❖Universal Gates: NAND and NOR ❖Implementation using NAND Gates ❖Implementation using NOR Gates ❖Implementation of SOP Expressions ❖Implementation of POS Expressions Digital Logic gates – Boolean functions are expressed in terms of AND, OR, and NOT operations. – There are eight functions: —Transfer (or buffer), NOT, AND, OR, NAND, NOR, XOR, and XNOR that may be considered to be standard gates in digital design. 5 Summary of Logic Gates 6 Summary of Logic Gates 7  Universal gates NAND and NOR are known as universal gates because they are inexpensive to manufacture. Universal gates can be used for implementing AND, OR and NOT gate. Any Boolean function can be constructed using only NAND or only NOR gates.  Universal NOR Gate New graphic symbols for NOR gates.  Universal NAND Gate New graphic symbols for NAND gate  Universal NOR Gate New graphic symbols for NOR gates. Universal Property - NAND Gate NAND GATE AS A UNIVERSAL LOGIC ELEMENT NAND gate is a universal gate because it can be used to produce the NOT, AND, OR and NOR functions. Universal Property - NAND Gate NAND GATE AS A UNIVERSAL LOGIC ELEMENT (Cont.) Universal Property - NAND Gate Universal Property – NOR Gate NOR GATE AS A UNIVERSAL LOGIC ELEMENT NOR gate is also a universal gate because it can be used to produce the NOT, AND, OR and NAND functions. Universal Property – NOR Gate NOR GATE AS A UNIVERSAL LOGIC ELEMENT (Cont.) Universal Property – NOR Gate Two-Level Implementation using NAND gates First: the logic function has to be written in Sum of Product (SOP) form. Then implement using NAND gate. Any logic circuit with AND gates in first level and OR gates in second level can be converted into a NAND-NAND gate circuit. Implications and alternative symbol for NAND function (xy)'=x'+y'  Implementation of SOP Expressions (1/2) ▪ Sum-of-Products expressions can be implemented using: ❖ 2-level AND-OR logic circuits ❖ 2-level NAND logic circuits ▪ Consider the following SOP expression: F = A.B + C.D + E ▪ AND-OR logic circuit A B C F D E 20  Implementation of SOP Expressions (2/2) A B A C B F D C F D E E ▪ NAND-NAND circuit a) add double bubbles A B b) change OR-with- inverted-inputs to NAND C F D E' 21 Two-Level Implementation using NOR gates The logic function has to be written in Product of Sum (POS) form. Then implement using NOR gate. Any logic circuit with OR gates in first level and AND gates in second level can be converted into a NOR-NOR gate circuit. Implications and alternative symbol for NOR function (x+y)'=x'y' Implementation of POS Expressions (1/2) ▪ Product-of-Sums expressions can be implemented using: ❖ 2-level OR-AND logic circuits ❖ 2-level NOR logic circuits ▪ Consider the following SOP expression: G = (A+B).(C+D).E ▪ OR-AND logic circuit A B C G D E 24  Implementation of POS Expressions (2/2) A B A C B G C D G D E E ▪ NOR-NOR circuit: A a) add double bubbles B b) changed AND-with- C inverted-inputs to NOR G D E' 25  Example Implement the following logic function: F = x + yz – Using universal NAND gates. – Using universal NOR gates. 26 Implementation using NAND gates (2/2) F = x.(y + z) F = x.y + x.z x (x.y)' y F x z (x.z)' F = ((x.y)'.(x.z)')' = x.y + x.z 27 Implementation using NOR gates (2/2) F = x+yz F = (x+y).(x+z) x (x+y)' y F x z (x+z)' F = ((x+y)'+(x+z)')' = (x+y).(x+z) 28  Multilevel NAND Circuits Process for NAND Implementation 1. Starting from a logic expression, implement the design with AND,OR, and NOT gate. 2. Identify and replace every AND,OR, and NOT gate with its NAND equivalent. 3. Redraw the circuit. 4. Identify and eliminate any double inversions (i.e., back- to-back inverters). 5. Redraw the final circuit. 29  NAND Implementation Example: Design a NAND Logic Circuit that is equivalent to the circuit shown below. =BC+ A C 30  NAND Implementation Solution – Step 2 Identify and replace every AND,OR, and NOT gate with its NAND equivalent. 31  NAND Implementation Solution – Step 3 Redraw the circuit. 32  NAND Implementation Solution – Step 4 Identify and eliminate any double inversions. 33  NAND Implementation Solution – Step 5 Redraw the circuit. 34 Proof of Equivalence C BC =BCAC Z =BC+AC AC Z =BC+ AC 35  AND,OR, and NOT gate vs. NAND IC Type Gates Gate / IC # ICs IC Type Gates Gate / IC # ICs 74LS04 1 6 1 74LS00 4 4 1 74LS08 2 4 1 Total Number of ICs → 1 74LS32 1 4 1 Total Number of ICs → 3 36  Multilevel NOR Circuits Process for NOR Implementation 1. Starting from a logic expression, implement the design with AND,OR, and NOT gate. 2. Identify and replace every AND,OR, and NOT gate with its NOR equivalent. 3. Redraw the circuit. 4. Identify and eliminate any double inversions. (i.e. back- to-back inverters) 5. Redraw the final circuit. 37  NOR Implementation Example: Design a NOR Logic Circuit that is equivalent to the AND,OR, and NOT gate circuit shown below. =BC+ A C 38  NOR Implementation Solution – Step 2 Identify and replace every AND,OR, and NOTgate with its NAND equivalent. 39  NOR Implementation Solution – Step 3 Redraw Circuit. 40  NOR Implementation Solution – Step 4 Identify and eliminate any double inversions. 41  NOR Implementation Solution – Step 5 Redraw Circuit. 42 Proof of Equivalence B+C=BC=BC C B =BC+ AC C Z =BC+ AC BC+ AC A A+C=AC=AC 43  AND,OR, and NOT gate vs NOR IC Type Gates Gate / IC # ICs IC Type Gates Gate / IC # ICs 74LS04 1 6 1 74LS02 7 4 2 74LS08 2 4 1 Total Number of ICs → 2 74LS32 1 4 1 Total Number of ICs → 3 44 45 Implementation using NAND gates (1/2) ▪ Possible to implement any Boolean expression using NAND gates. Procedure: (i) Obtain sum-of-products Boolean expression: e.g. F3 = x.y' + x'.z (ii) Use DeMorgan theorem to obtain expression using 2-level NAND gates e.g. F3 = x.y' + x'.z = (x.y'+ x'.z)' ' involution = ((x.y')'. (x'.z)')' DeMorgan Implementation using NAND gates (2/2) F3 = x.y' + x'.z x (x.y')' y' F3 x' z (x'.z)' F3 = ((x.y')'.(x'.z)’)' = x.y' + x'.z 47 Implementation using NAND gates (2/2) F3 = x.(y + z) F3 = x.y + x.z x (x.y)' y F3 x z (x.z)' F3 = ((x.y)'.(x.z)')' = x.y + x.z 48 Implementation using NOR gates (1/2) ▪ Possible to implement any Boolean expression using NOR gates. Procedure: (i) Obtain product-of-sums Boolean expression: e.g. F6 = (x+y').(x'+z) (ii) Use DeMorgan theorem to obtain expression using 2-level NOR gates. e.g. F6 = (x+y').(x'+z) = ((x+y').(x'+z))' ' involution = ((x+y')'+(x'+z)')' DeMorgan 49 Implementation using NOR gates (2/2) F6 = x+yz F6 = (x+y).(x+z) x (x+y)' y F6 x z (x+z)' F6 = ((x+y)'+(x+z)')' = (x+y).(x+z) 50 EXAMPLES 51 Example: Implementations of Two-level Logic Sum-of-products AND gates to form product terms (minterms) OR gate to form sum Product-of-sums OR gates to form sum terms (maxterms) AND gates to form product Two-level Logic using NAND Gates Replace minterm AND gates with NAND gates Place compensating inversion at inputs of OR gate Two-level Logic using NAND Gates (cont’d) OR gate with inverted inputs is a NAND gate de Morgan's: A' + B' = (A B)' Two-level NAND-NAND network Two-level Logic using NOR Gates Replace maxterm OR gates with NOR gates Place compensating inversion at inputs of AND gate Two-level Logic using NOR Gates (cont’d) AND gate with inverted inputs is a NOR gate de Morgan's: A' B' = (A + B)' Two-level NOR-NOR network End of file QUIZ Simplify the function: F(A,B,C) = BC+ABC+ABC' Implement the following logic function: F = AB + BC Using universal NAND gates. Using universal NOR gates. Express the function F(x,y,z)=∑(1,3,5,7) as a product of maxterms Express the complement of the function F= ∑(1,3,5,7) as a sum of minterms CS 150 - Fall 2000 - Combinational Implementation - 58