Switching Circuits & Logic Design - 國立臺灣大學
Switching Circuits &Logic DesignJie-Hong Roland Jiang江介宏Department of Electrical EngineeringNational Taiwan UniversityFall 20131§2 Boolean Algebra2
Outline Introduction Basic operations Boolean expressions and truth tables Basic theorems Commutative, associative, and distributivelaws Simplification theorems Multiplying out and factoring DeMorgan’s laws3Introduction Boolean algebra is the mathematicalfoundation of logic design George Boole (1847) logic algebra Boolean algebra Claude Shannon (1939) Boolean algebra logic design4
Introduction Boolean (switching) variable x {0,1} 0, 1 are abstract symbols They may correspond to {false, true} in logic, {off, on} ofa switch, {low voltage, high voltage} of a CMOS circuit, orother meanings Boolean space {0,1}n The configuration space of all possible {0,1}assignments to n Boolean variablesE.g.,the Boolean space spanned by (x1,x2) is {0,1}2 {0,1} {0,1} {00, 01, 10, 11}1x201x1011100105Introduction Boolean function f(x1, x2, , xn) is a mapping:{0,1}n {0,1}, where xi’s are Boolean 11y01How many Boolean functions of n variables are there?6
Introduction There are many different ways to represent a Booleanfunction E.g., truth tables, Boolean expressions (formulas), logiccircuits, Binary Decision Diagrams, combinatorial cubes, .x1x2x3fBinary decision diagramyTruth inatorial 01107Introduction Different Boolean-function representations havetheir own strengths and weaknesses They affect the computational efficiency of Booleanmanipulations in logic synthesis, hardware/softwareverification, and many other applications Truth tables, Boolean expressions, and logiccircuits will be our main use in representingBoolean functions Boolean expressions and logic circuits are closely related They are built up from logic operators and Booleanvariables8
Basic Operations Three most basic operations in Booleanalgebra: {AND, OR, NOT} They form a functionally complete set ofoperations, that is, any Boolean functions canbe constructed using these three operations(why?) Are {AND, NOT} functionally complete?9Basic OperationsNOT NOT (complement, or inverse) Notation: “ ”, “ ”,or “ ” Logic gate symbol:0 11 0XX 1 if and only if X 0X 0 if and only if X 1X (X, X )NOT-gate, inverterX X 0 11 010
Basic OperationsAND AND (conjunction) Notation: “ ”, “ ” Logic gate symbol:0011 0101 0001AC A BBAND-gateAB C A B00001010011111Basic OperationsOR OR (disjunction) Notation: “ ”, “ ” Logic gate symbol:0011 0101 0111AC A BBOR-gateAB C A B00001110111112
Boolean Expressions & Logic Circuits AB CAAB'(AB' C)BB'C [A(C D)] BECD(C D)A(C D)[A(C D)]'[A(C D)]' BEABEBE13Boolean Expressions & Logic Circuits Given a Boolean expression, we can construct afunctionally equivalent logic circuit (not unique) Given a logic circuit, we can derive a Booleanexpression of the corresponding Boolean function Given a Boolean expression or logic circuit, wecan derive the truth table of the correspondingBoolean function14
Boolean Expressions & Logic Circuits A Boolean expression (logic circuit) gives aunique Boolean function The converse is not true, that is, a Boolean function canbe represented by different Boolean expressions (logiccircuits) A truth table gives a unique Boolean function,and vice versa Truth tables are canonical in representing Booleanfunctions Can use truth tables to show the equivalence of twoBoolean functions15Boolean Expressions & Truth TablesTruth-table proof of AB C (A C)(B C)(equivalence under all truth assignments)ABCB AB AB CA CB C(A C)(B 01011111110111010101110116
Basic Theorems of Boolean Algebra Operations with 0 and 1: X 0 Xdual X 1 1X 1 XX 0 0 Idempotent laws X X XX X XDuality: interchange “0” and “1” and interchange “ ” and “ ”17Basic Theorems of Boolean Algebra Involution law (X ) X Laws of complementarity X X 1X X 0Applications to logic simplificationE.g.,(AB D)E 1 1(AB D)(AB D) 018
Boolean Algebra with SwitchesXSYS 0, switch openS 1, switch closedX and Y are connected if and only if S 1The connectivity between X and Y is a function over S19Boolean Algebra with SwitchesXABYX and Y are connected if and only if A B 1ABX and Y are connected if and only if A B 120
Boolean Algebra with SwitchesBasic Theorems Revisited Idempotent lawsAA A(A A A)AA A(A A A)21Boolean Algebra with SwitchesBasic Theorems Revisited Operations with 0 and 1A A(A 0 A)A (A 1 1)22
Boolean Algebra with SwitchesBasic Theorems Revisited Laws of complementarityA A’(A A 1)AA’ (A A 0)23Commutative, Associative, andDistributive laws Commutative laws X Y Y XABABX Y Y X BA BA24
Commutative, Associative, andDistributive laws Associative laws (XY)Z X(YZ) XYZ(X Y) Z X (Y Z) X Y ZABABCC ABC ABC25Commutative, Associative, andDistributive laws Distributive laws X(Y Z) XY XZX YZ (X Y)(X Z) The second equality is valid for Boolean algebra butnot for ordinary algebraProof.(X Y)(X Z) XX XZ YX YZ X XZ XY YZ X 1 XZ XY YZ X(1 Z Y) YZ X 1 YZ X YZ26
Simplification Theorems XY XY X(X Y)(X Y ) X X XY XX(X Y) XProof.X XY X 1 XY X(1 Y) X 1 XX(X Y) XX XY X XY X (X Y )Y XYXY Y X YProof.Y XY (Y X)(Y Y ) (Y X) 1 X Y27Logic Circuit Simplification F A(A B) AA AB 0 AB ABABAF ABFExercise (p.48) Simplify Z [A B C D EF] [A B C (D EF) ] Simplify Z (AB C)(B D C E ) (AB C) 28
Multiplying Out and Factoring Sum-of-products (SOP), or Disjunctive Normal Form (DNF) Sum of products of literals (a literal is a variable x or itscomplement x ) E.g.,ab c a bda b cabca(b c) a bdyesyesyesno Any Boolean function can be represented in the SOP form(Why?) Product-of-sums (POS), or Conjunctive Normal Form (CNF) Product of clauses (a clause is a sum of literals) E.g.,(a b c)(a d)(a b c)(a)(b)(c)(a bc)(a d)yesyesyesno Any Boolean function can be represented in the POS form(Why?)29Multiplying Out SOP When multiplying out an expression (to obtain an SOP),the 2nd distributive law(X Y)(X Z) X YZcan be applied first when possible to simply theexpressionE.g.,(A BC)(A D E) A BC(D E) A BCD BCEXYXZXYZIn contrast to,(A BC)(A D E) A AD AE ABC BCD BCE A(1 D E BC) BCD BCE A BCD BCE30
Factoring POS Apply distributive lawsXY XZ X(Y Z)X YZ (X Y)(X Z)to factor an expression in the POS form Any expression can be factored to the POS form An expression cannot be further factored if and only if it isin the POS formE.g.,(A B CD) (A B )(A CD) (A B )(A C)(A D)(AB CD) (AB C)(AB D) (A C)(B C)(A D)(B D)Exercise (p.51): Factor (C D C E G H)31Multiplying Out and Factoring SOP in AND-OR circuitAB CD EAC E D EAB CD E AC E AB CA B C D E32
Multiplying Out and Factoring POS in OR-AND circuitAB CD EAC E D EAB C(A B )(C D E)(A C E )AB C(D E)33DeMorgan’s Laws Complement by DeMorgan’s laws (X Y) X Y (X Y) X Y Proof by truth tableXYX Y(X Y) X Y XY000110110111100010000001(X Y) X Y 1110111034
Generalized DeMorgan’s Laws (X1 X2 Xn) X1 X2 Xn Complement of sum product of complements (X1 X2 Xn) X1 X2 Xn Complement of product sum of complementsE.g.,[(A B)C ] (A B) (C ) AB C[(AB C)D E] [(AB C)D ] E [(AB C) D]E [(AB ) C D]E [(A B)C D]E 35Duality The dual FD of an expression F is formed byreplacing AND with OR, OR with AND, 0 with 1,and 1 with 0 FD can also be obtained by complementing F and thencomplementing each individual variableE.g.,(AB C)D (A B )C Equalities are preserved under duality, i.e.,F G iff FD GD (justify prior theorems)E.g.,dualX(Y Z) XY XZX YZ (X Y)(X Z)36
Boolean Expressions & Logic Circuits A Boolean expression (logic circuit) gives a unique Boolean function The converse is not true, that is, a Boolean function can be represented by different Boolean expressions (logic circuits) A truth table gives a unique Boolean function, and vice
Engr354: Digital Logic Circuits Chapter 2: Introduction to Logic Circuits Dr. Curtis Nelson Chapter 2 Objectives Define and illustrate basic logic functions and circuits; Present Boolean algebra for dealing with logic functions; Illustrate logic gates and synthesis of simple circuits
To implement simple logical operations using combinational logic circuits 4 To design combinational logic circuits, sequential logic circuits 5 To impart to student the concepts of sequential circuits, enabling them to analyze sequential systems interms of state machines. 6
Dynamic Logic Dynamic Circuits will be introduced and their performance in terms of power, area, delay, energy and AT2 will be reviewed. We will review the following logic families: Domino logic P-E logic NORA logic 2-phase logic Multiple O/P domino logic Cascode logic
ECE380 Digital Logic Introduction to Logic Circuits: Variables, functions, truth tables, gates and networks Electrical & Computer Engineering Dr. D. J. Jackson Lecture 2-2 Logic circuits Logic circuits perform operations on digital signals – Implemented as electronic circuits wh
Logic Design Chapter 2: Introduction to Logic Circuits Introduction Logic circuits operate on digital signals Unlike continuous analog signals that have an infinite number of possible values, digital signals are restricted to a few discrete values In particular for binary logic circuits, signals can have only two values: 0 and 1.
Contemporary Electric Circuits, 2nd ed., Prentice-Hall, 2008 Class Notes Ch. 9 Page 1 Strangeway, Petersen, Gassert, and Lokken CHAPTER 9 Series–Parallel Analysis of AC Circuits Chapter Outline 9.1 AC Series Circuits 9.2 AC Parallel Circuits 9.3 AC Series–Parallel Circuits 9.4 Analysis of Multiple-Source AC Circuits Using Superposition 9.1 AC SERIES CIRCUITS
Digital Design is concerned with the design of digital electronic circuits. The subject is also known by other names such as logic design, digital logic, switching circuits, and digital systems. Digital circuits are employed in the design of systems such as digital computers, control syst
Some digital banking features may not be available depending on your computer, mobile device or operating system. You may not be able to access all the products and services we offer through digital banking. We can restrict access to digital banking for any of the reasons set out in your Product terms. We may add products and services you receive (individually or jointly with someone else .
