Textbook Chapter 3CMPE12 – Summer 2008Digital Logic: Boolean Algebra and GatesCMPE12 – Summer 2008 – Slides by ADB 2Basic Logic GatesCMPE12 – Summer 2008 – Slides by ADB 3Truth Table The most basic representation of a logic function Lists the output for all possible input combinations How many rows of the truth table needed?2#inputsX Y …A B …OutputsInputsX Y …A B …OutputsInputsCMPE12 – Summer 2008 – Slides by ADB 5Truth Table: Inverter Inverted signals are denoted with an overbar Or with a prime symbol A’Y = A’AOutputInputCMPE12 – Summer 2008 – Slides by ADB 6Truth Table: AND Gate The result of an AND operation is 1 if and only if all inputs are 1 Depict AND by the multiplication symbol A·B Or by lumping the signals together AB We don’t really build these gates…Y = A · BA BOutputInputsCMPE12 – Summer 2008 – Slides by ADB 7Truth Table: OR Gate The result of an OR operation is 1 if and only if any inputs are 1 Depict OR by the addition symbol A+BY = A + BA BOutputInputsCMPE12 – Summer 2008 – Slides by ADB 8About the Little Circle… The little circle is what invertsCMPE12 – Summer 2008 – Slides by ADB 9Sum of Products How do you get from a truth table to a logic expression? Sum of products is standard way of synthesizing simple circuits Procedure:1. Find the rows with the ‘1’ output2. Write the product-form expression for the inputs in that row (0=inverted, 1=normal)3. Combine the products in step 2 into a sum (OR the results of step 2)CMPE12 – Summer 2008 – Slides by ADB 10Sum of Products1. Find the rows with the ‘1’output2. Write the product-form expression for the inputs in that row (0=inverted, 1=normal)3. Combine the products in step 2 into a sum (OR the results of step 2)101110000011YBACMPE12 – Summer 2008 – Slides by ADB 11De Morgan’s Laws “Break the line, change the sign” Two laws: A’ + B’ = (AB)’ A’ B’ = (A+B)’CMPE12 – Summer 2008 – Slides by ADB 12De Morgan’s Laws(A + B)’ = A’B’ conversely (AB)’ = A’ + B’“Break the line, change the sign”1 0A1 10 10 0A·BA BA+BA+B A BCMPE12 – Summer 2008 – Slides by ADB 13De Morgan’s Laws(A + B)’ = A’B’ conversely (AB)’ = A’ + B’“Break the line, change the sign”1 0A1 10 10 0A+BA BABAB A BCMPE12 – Summer 2008 – Slides by ADB 14De Morgan’s Laws In other words… Push the bubbles through!CMPE12 – Summer 2008 – Slides by ADB 15De Morgan’s Laws and SOP Generate equivalent circuits NAND/NAND NOR/NOR We prefer NAND/NAND circuits Same transistor count as NOR NANDs are fasterCMPE12 – Summer 2008 – Slides by ADB 17Masking Want to look only at certain bits of a binary word Use a mask to remove the uninteresting bits Example:CMPE12 – Summer 2008 – Slides by ADB 18Axioms of Boolean Algebra 0 · 0 = 1 + 1 = 1 · 1 = 0 + 0 = 0 · 1 = 1 · 0 = 1 + 0 = 0 + 1 = 1 + 0 = 0 + 1 = if x = 0 then x’ = if x = 1 then x’ =CMPE12 – Summer 2008 – Slides by ADB 19Single-Variable Theorems x · 0 = x + 1 = x · 1 = x + 0 = x · x = x + x = x · x’ = x + x’ = (x’)’ = CMPE12 – Summer 2008 – Slides by ADB 20Properties of Boolean Algebra Commutative x · y = x + y = Associative x · (y · z) = x + (y + z) = Distributive x · (y + z ) = x + y · z = CMPE12 – Summer 2008 – Slides by ADB 21Properties of Boolean Algebra Absorption x + x · y = x · (x + y) = Combining x · y + x · y’ = (x + y) · (x + y’) = De Morgan’s Laws (x · y)’ = (x + y)’ = Other x + x’·y = x · (x’ + y) =CMPE12 – Summer 2008 – Slides by ADB 22Logic Minimization01111011010110011110101001000000YCBA
View Full Document
Unlocking...