1 1 ECE 545—Digital System Design with VHDL Lecture 1 Digital Logic Review 2 Lecture Roadmap – Combinational Logic • Basic Logic Review • Basic Gates • DeMorgan’s Law • Combinational Logic Blocks • Multiplexers • Decoders, Demultiplexers • Encoders, Priority Encoders • Half Adders, Full Adders • Multi-Bit Combinational Logic Blocks • Multi-bit multiplexers • Multi-bit adders • Comparators 3 • Sequential Logic Building Blocks • Latches, Flip-Flops • Sequential Logic Circuits • Registers, Shift Registers, Counters • Memory (RAM, ROM) Lecture Roadmap – Sequential Logic 4 Textbook References • Combinational Logic Review • Stephen Brown and Zvonko Vranesic, Fundamentals of Digital Logic with VHDL Design, 2nd or 3rd Edition • Chapter 2 Introduction to Logic Circuits (2.1-2.8 only) • Chapter 6 Combinational-Circuit Building Blocks (6.1-6.5 only) • OR your undergraduate digital logic textbook (chapters on combinational logic) • Sequential Logic Review • Stephen Brown and Zvonko Vranesic, Fundamentals of Digital Logic with VHDL Design, 2nd or 3rd Edition • Chapter 7 Flip-flops, Registers, Counters, and a Simple Processors (7.3-7.4, 7.8-7.11 only) • OR your undergraduate digital logic textbook (chapters on sequential logic) 5 Basic Logic Review some slides modified from: S. Dandamudi, “Fundamentals of Computer Organization and Design” 6 Basic Concepts • Simple logic gates • AND  0 if one or more inputs is 0 • OR  1 if one or more inputs is 1 • NOT • NAND = AND + NOT • 1 if one or more inputs is 0 • NOR = OR + NOT • 0 if one or more input is 1 • XOR implements exclusive-OR function • NAND and NOR gates require fewer transistors than AND and OR in standard CMOS • Functionality can be expressed by a truth table • A truth table lists output for each possible input combination2 7 Basic Logic Gates 8 Number of Functions • Number of functions • With N logical variables, we can define 22N functions • Some of them are useful • AND, NAND, NOR, XOR, … • Some are not useful: • Output is always 1 • Output is always 0 • “Number of functions” definition is useful in proving completeness property 9 Complete Set of Gates • Complete sets • A set of gates is complete • if we can implement any logical function using only the type of gates in the set • Some example complete sets • {AND, OR, NOT} Not a minimal complete set • {AND, NOT} • {OR, NOT} • {NAND} • {NOR} • Minimal complete set • A complete set with no redundant elements. 10 NAND as a Complete Set • Proving NAND gate is universal 11 Logic Functions • Logical functions can be expressed in several ways: • Truth table • Logical expressions • Graphical form • HDL code • Example: • Majority function • Output is one whenever majority of inputs is 1 • We use 3-input majority function 12 Logic Functions (cont’d) Truth table A B C F 0 0 0 0 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 Logical expression form F = A B + B C + A C Graphical schematic form3 13 Boolean Algebra Boolean identities Name AND version OR version Identity x.1 = x x + 0 = x Complement x. x’ = 0 x + x’ = 1 Commutative x.y = y.x x + y = y + x Distribution x. (y+z) = xy+xz x + (y. z) = (x+y) (x+z) Idempotent x.x = x x + x = x Null x.0 = 0 x + 1 = 1 14 Boolean Algebra (cont’d) • Boolean identities (cont’d) Name AND version OR version Involution x = (x’)’ --- Absorption x. (x+y) = x x + (x.y) = x Associative x.(y. z) = (x. y).z x + (y + z) = (x + y) + z de Morgan (x. y)’ = x’ + y’ (x + y)’ = x’ . y’ (de Morgan’s law in particular is very useful) 15 Majority Function Using Other Gates • Using NAND gates • Get an equivalent expression A B + C D = (A B + C D)’’ • Using de Morgan’s law A B + C D = ( (A B)’ . (C D)’)’ • Can be generalized • Example: Majority function A B + B C + AC = ((A B)’ . (B C)’ . (AC)’)’ 16 Majority Function Using Other Gates (cont'd) • Majority function 17 Combinational Logic Building Blocks Some slides modified from: S. Dandamudi, “Fundamentals of Computer Organization and Design” S. Brown and Z. Vranesic, "Fundamentals of Digital Logic" 18 Multiplexers • multiplexer • n binary inputs (binary input = 1-bit input) • log2n binary selection inputs • 1 binary output • Function: one of n inputs is placed onto output • Called n-to-1 multiplexer n inputs 1 output log2n selection inputs4 19 2-to-1 Multiplexer (a) Graphical symbol f s w 0 w 1 0 1 (b) Truth table 0 1 f f s w 0 w 1 (c) Sum-of-products circuit s w 0 w 1 (d) Circuit with transmission gates w 0 w 1 f s Source: Brown and Vranesic 20 4-to-1 Multiplexer f s 1 w 0 w 1 00 01 (b) Truth table w 0 w 1 s 0 w 2 w 3 10 11 0 0 1 1 1 0 1 f s 1 0 s 0 w 2 w 3 f (c) Circuit s 1 w 0 w 1 s 0 w 2 w 3 (a) Graphic symbol Source: Brown and Vranesic 21 Decoders • Decoder • n binary inputs • 2n binary outputs • Function: decode encoded information • If enable=1, one output is asserted high, the other outputs are asserted low • If enable=0, all outputs asserted low • Often, enable pin is not needed (i.e. the decoder is always enabled) • Called n-to-2n decoder • Can consider n binary inputs as a single n-bit input • Can consider 2n binary outputs as a single 2n-bit output • Decoders are often used for RAM/ROM addressing n-1 w 0 n inputs En Enable 2 n outputs y 0 w y 2 n 1 – 22 2-to-4 Decoder 0 0 1 1 1 0 1 y 3 w 1 0 w 0 (c) Logic circuit w 1 w 0 - - 1 1 0 1 1 En 0 0 1 0 0 y 2 0 1 0 0 0 y 1 1 0 0 0 0 y 0 0 0 0 1 0 y 0 y 1 y 2 y 3 En w 1 En y 3 w 0 y 2 y 1 y 0 (a) Truth table (b) Graphical symbol Source: Brown and Vranesic 23 Demultiplexers • Demultiplexer • 1 binary input • n binary outputs • log2n binary selection inputs • Function: places input onto one of n outputs, with the