Digital Design and Computer Architecture Chapter 2 Summary

Chapter 2 Digital Design and Computer Architecture, 2nd Edition David Money Harris and Sarah L. Harris Edited by J Dean Brock For CSCI 320 Chapter 2 <1>

Chapter 2 :: Topics Introduction Boolean Equations Boolean Algebra From Logic to Gates Multilevel Combinational Logic X s and Z s, Oh My Karnaugh Maps Combinational Building Blocks Timing Chapter 2 <2>

Introduction A logic circuit is composed of: Inputs Outputs Functional specification Timing specification functional spec inputs outputs timing spec Chapter 2 <3>

Circuits Nodes Inputs: A, B, C Outputs: Y, Z Internal: n1 Circuit elements E1, E2, E3 Each a circuit n1 A E1 B E3 Y C E2 Z Chapter 2 <4>

Types of Logic Circuits Combinational Logic Memoryless Outputs determined by current values of inputs Sequential Logic Has memory Outputs determined by previous and current values of inputs functional spec inputs outputs timing spec Chapter 2 <5>

Rules of Combinational Composition Every element is combinational Every node is either an input or connects to exactly one output The circuit contains no cyclic paths Example: Chapter 2 <6>

Boolean Equations Functional specification of outputs in terms of inputs Example: S = F(A, B, Cin) Cout = F(A, B, Cin) A B Cin S Cout CL S = A B Cin Cout = AB + ACin + BCin Chapter 2 <7>

Some Definitions Complement: variable with a bar over it A, B, C Literal: variable or its complement A, A, B, B, C, C Implicant: product of literals ABC, AC, BC Minterm: product that includes all input variables ABC, ABC, ABC Maxterm: sum that includes all input variables (A+B+C), (A+B+C), (A+B+C) Chapter 2 <8>

Sum-of-Products (SOP) Form All equations can be written in SOP form Each row has a minterm A minterm is a product (AND) of literals Each minterm is TRUE for that row (and only that row) Form function by ORing minterms where the output is TRUE Thus, a sum (OR) of products (AND terms) minterm name m0 m1 m2 m3 Often called canonical sum-of-products minterm AB A 0 0 1 1 B 0 1 0 1 Y 0 1 0 1 AB AB AB Y = F(A, B) = AB + AB = (1, 3) Chapter 2 <9>

Product-of-Sums (POS) Form All Boolean equations can be written in POS form Each row has a maxterm A maxterm is a sum (OR) of literals Each maxterm is FALSE for that row (and only that row) Form function by ANDing the maxterms for which the output is FALSE Thus, a product (AND) of sums (OR terms) maxterm name M0 M1 M2 M3 maxterm A 0 0 1 1 B 0 1 0 1 Y 0 1 0 1 A + B A + B A + B A + B Y = F(A, B) = (A + B)(A + B)= (0, 2) Chapter 2 <10>

Boolean Equations Example You are going to the cafeteria for lunch You won t eat lunch (E) If it s not open (O) or If they only serve corndogs (C) Write a truth table for determining if you will eat lunch (E). O 0 0 1 1 C 0 1 0 1 E 0 0 1 0 This is the sort of thing done in symbolic logic course Chapter 2 <11>

SOP & POS Form SOP sum-of-products O 0 0 1 1 C 0 1 0 1 E 0 0 1 0 minterm O C Y = OC = (2) OC OC OC POS product-of-sums maxterm O 0 0 1 1 C 0 1 0 1 E 0 0 1 0 O + C O + C O + C O + C Y = (O + C)(O + C)(O + C) = (0, 1, 3) Chapter 2 <12>

Boolean Algebra Axioms and theorems to simplify Boolean equations Like regular algebra, but simpler: variables have only two values (1 or 0) Duality in axioms and theorems: ANDs and ORs, 0 s and 1 s interchanged This is a really big deal Chapter 2 <13>

Boolean Axioms Chapter 2 <14>

T1: Identity Theorem B 1 = B B + 0 = B Chapter 2 <15>

T2: Null Element Theorem B 0 = 0 B + 1 = 1 annihilation Chapter 2 <16>

T3: Idempotency Theorem B B = B B + B = B Chapter 2 <17>

T4: Identity Theorem B = B they meant Involution Chapter 2 <18>

T5: Complement Theorem B B = 0 B + B = 1 In ordinary mathematics, Minus is an inverse for addition Reciprocal is an inverse for multiplication In Boolean algebra the complement is the inverse for both AND and OR Chapter 2 <19>

Boolean Theorems of Several Vars In set theory, make the following replacements + with union * with intersection complementation with set complementation That gives you many Boolean algebras Chapter 2 <20>

Simplifying Boolean Equations Example 2: Y = A(AB + ABC) = A(AB(1 + C)) = A(AB(1)) = A(AB) = (AA)B = AB T8 T2 T1 T7 T3 Chapter 2 <21>

Bubble Pushing Rules Begin at output, then work toward inputs Push bubbles on final output back Draw gates in a form so bubbles cancel A B C Y D Chapter 2 <22>

From Logic to Gates Two-level logic: ANDs followed by ORs Example: Y = ABC + ABC + ABC A B C A B C minterm: ABC minterm: ABC minterm: ABC Y Chapter 2 <23>

Circuit Schematics Rules Inputs on the left (or top) Outputs on right (or bottom) Gates flow from left to right Straight wires are best Chapter 2 <24>

Circuit Schematic Rules (cont.) Wires always connect at a T junction A dot where wires cross indicates a connection between the wires Wires crossing without a dot make no connection wires crossing without a dot do not connect wires connect at a T junction wires connect at a dot Chapter 2 <25>

Contention: X Contention: circuit tries to drive output to 1 and 0 Actual value somewhere in between Could be 0, 1, or in forbidden zone Might change with voltage, temperature, time, noise Often causes excessive power dissipation A = 1 Y = X B = 0 Warnings: Contention usually indicates a bug. X is used for don t care and contention - look at the context to tell them apart Chapter 2 <26>

Floating: Z Floating, high impedance, open, high Z Floating output might be 0, 1, or somewhere in between A voltmeter won t indicate whether a node is floating Tristate Buffer E Y A E 0 0 1 1 A 0 1 0 1 Y Z Z 0 1 Chapter 2 <27>

Tristate Busses Floating nodes are used in tristate busses Many different drivers Exactly one is active at once processor en1 to bus from bus video en2 to bus from bus shared bus Ethernet en3 to bus from bus memory en4 to bus from bus Chapter 2 <28>

Karnaugh Maps (K-Maps) Boolean expressions can be minimized by combining terms K-maps minimize equations graphically PA + PA = P A 0 0 0 0 1 1 1 1 B 0 0 1 1 0 0 1 1 C 0 1 0 1 0 1 0 1 Y Y Y AB AB 1 1 0 0 0 0 0 0 00 01 11 10 00 01 11 10 C C 0 0 0 0 0 1 ABC ABC ABC ABC 1 0 0 0 1 ABC ABC ABC ABC 1 Chapter 2 <29>

K-Map Circle 1 s in adjacent squares In Boolean expression, include only literals whose true and complement form are not in the circle Y AB A 0 0 0 0 1 1 1 1 B 0 0 1 1 0 0 1 1 C 0 1 0 1 0 1 0 1 Y 00 01 11 10 1 1 0 0 0 0 0 0 C 0 1 0 0 0 1 1 0 0 0 Y = AB Chapter 2 <30>

3-Input K-Map Y AB 00 01 11 10 C 0 ABC ABC ABC ABC 1 ABC ABC ABC ABC Truth Table K-Map Y A 0 0 0 0 1 1 1 1 B 0 0 1 1 0 0 1 1 C 0 1 0 1 0 1 0 1 Y 0 0 AB 00 01 11 10 C 0 1 1 0 0 0 1 1 Chapter 2 <31>

K-Map Definitions Complement: variable with a bar over it A, B, C Literal: variable or its complement A, A, B, B, C, C Implicant: product of literals ABC, AC, BC Prime implicant: implicant corresponding to the largest circle in a K-map Chapter 2 <32>

K-Map Rules Every 1 must be circled at least once Each circle must span a power of 2 (i.e. 1, 2, 4) squares in each direction Each circle must be as large as possible A circle may wrap around the edges A don't care (X) is circled only if it helps minimize the equation A similar process is called Quine-McCluskey minimization Circuit minimization is an NP complete program Win $1,000,000 for a polynomial algorithm. Chapter 2 <33>

4-Input K-Map A 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 D 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 B 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 C 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 Y Y 1 AB 00 01 11 10 CD 0 1 1 0 1 1 1 1 00 1 0 0 1 01 0 1 0 1 11 1 1 0 0 1 1 0 0 0 0 0 10 1 1 0 1 Chapter 2 <34>

K-Maps with Dont Cares Y A 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 D 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 B 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 C 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 Y AB 1 00 01 11 10 CD 0 1 1 0 X 1 1 1 00 1 0 X 1 01 0 X X 1 11 1 1 X X 1 X X X X X X 10 1 1 X X Chapter 2 <35>

Logic using Multiplexers Using the mux as a lookup table A 0 0 1 1 B 0 1 0 1 Y 0 0 0 1 Lookup tables are used in FPGA chips programmed using Verilog; however, they use PROMs. Y = AB A B 00 01 10 11 Y Chapter 2 <36>

Logic using Multiplexers Reducing the size of the mux A A Y A 0 0 1 1 B 0 1 0 1 Y 0 0 0 1 0 0 0 Y Y = AB 1 1 B B This is still taught in EE digital logic courses. Chapter 2 <37>

Logic Using Decoders OR minterms 2:4 Decoder Minterm 11 AB AB AB AB A B 10 01 00 Y = AB + AB = A B Y Chapter 2 <38>

Timing Delay between input change and output changing How to build fast circuits? A Y delay A Y Time Chapter 2 <39>

Propagation & Contamination Delay Propagation delay:tpd = max delay from input to output Contamination delay:tcd = min delay from input to output A Y The output is contaminated because it may not be the ultimate output. It could be a glitch . tpd A Y tcd Time Chapter 2 <40>

Propagation & Contamination Delay Delay is caused by Capacitance and resistance in a circuit Speed of light limitation Reasons why tpd and tcd may be different: Different rising and falling delays Multiple inputs and outputs, some of which are faster than others Circuits slow down when hot and speed up when cold Chapter 2 <41>

Critical (Long) & Short Paths Critical Path A B C n1 n2 Y D Short Path Critical (Long) Path: tpd = 2tpd_AND + tpd_OR Short Path: tcd = tcd_AND Chapter 2 <42>

Glitches When a single input change causes multiple output changes Well, I guess that s one definition. Chapter 2 <43>

Glitch Example What happens when A = 0, C = 1, B falls? A B Y C Y AB 00 01 11 10 C 0 1 0 0 0 1 1 1 1 0 Y = AB + BC Chapter 2 <44>

Glitch Example (cont.) Critical Path 0 1 n1 A = 0 B = 1 0 Y = 1 0 1 n2 C = 1 1 0 Short Path B n2 n1 Y glitch Time Chapter 2 <45>

Fixing the Glitch Y AB 00 01 11 10 C 0 1 0 0 0 1 1 1 1 0 AC Y = AB + BC + AC A = 0 B = 1 0 Y = 1 C = 1 Chapter 2 <46>

Why Understand Glitches? Glitches don t cause problems because of synchronous design conventions (see Chapter 3) It s important to recognize a glitch: in simulations or on oscilloscope Can t get rid of all glitches simultaneous transitions on multiple inputs can also cause glitches Chapter 2 <47>