PRELIM CSA.pdf

Chapter 1 Computer System Architectures Chapter 1  Chapter 1 :: Topics Background The Game Plan The Art of Managing Complexity The Digital Abstraction Number Systems Logic Gates Logic Levels CMOS Transistors Power Consumption...

Chapter 1 Computer System Architectures Chapter 1  Chapter 1 :: Topics Background The Game Plan The Art of Managing Complexity The Digital Abstraction Number Systems Logic Gates Logic Levels CMOS Transistors Power Consumption Chapter 1 Background Microprocessors have revolutionized our world Cell phones, Internet, rapid advances in medicine, etc. The semiconductor industry has grown from $21 billion in 1985 to $300 billion in 2011 Chapter 1  The Game Plan Purpose of course: Understand what’s under the hood of a computer Learn the principles of digital design Learn to systematically debug increasingly complex designs Design and build a microprocessor Chapter 1  The Art of Managing Complexity Abstraction Discipline The Three –Y’s Hierarchy Modularity Regularity Chapter 1  Abstraction Hiding details when they aren’t important Chapter 1  Discipline Intentionally restrict design choices Example: Digital discipline – Discrete voltages instead of continuous – Simpler to design than analog circuits – can build more sophisticated systems – Digital systems replacing analog predecessors: i.e., digital cameras, digital television, cell phones, CDs Chapter 1  The Three -Y’s Hierarchy – A system divided into modules and submodules Modularity – Having well-defined functions and interfaces Regularity – Encouraging uniformity, so modules can be easily reused Chapter 1  Example: The Flintlock Rifle Hierarchy – Three main modules: lock, stock, and barrel – Submodules of lock: hammer, flint, frizzen, etc. Chapter 1  Example: The Flintlock Rifle Modularity – Function of stock: mount barrel and lock – Interface of stock: length and location of mounting pins Regularity – Interchangeable parts Chapter 1 The Digital Abstraction Most physical variables are continuous Voltage on a wire Frequency of an oscillation Position of a mass Digital abstraction considers discrete subset of values Chapter 1  The Analytical Engine Designed by Charles Babbage from 1834 – 1871 Considered to be the first digital computer Built from mechanical gears, where each gear represented a discrete value (0-9) Babbage died before it was finished Chapter 1  Digital Discipline: Binary Values Two discrete values: 1’s and 0’s 1, TRUE, HIGH 0, FALSE, LOW 1 and 0: voltage levels, rotating gears, fluid levels, etc. Digital circuits use voltage levels to represent 1 and 0 Bit: Binary digit Chapter 1  George Boole, 1815-1864 Born to working class parents Taught himself mathematics and joined the faculty of Queen’s College in Ireland. Wrote An Investigation of the Laws of Thought (1854) Introduced binary variables Introduced the three fundamental logic operations: AND, OR, and NOT. Chapter 1  Chapter 1 Number Systems Decimal numbers Binary numbers 537410 = 11012 = 1's column 1's column 10's column 2's column 100's column 4's column 1000's column 8's column  Number Systems Decimal numbers 1000's column 10's column 1's column 100's column 537410 = 5 × 103 + 3 × 102 + 7 × 101 + 4 × 100 five three seven four thousands hundreds tens ones Binary numbers 8's column 2's column 1's column 4's column 11012 = 1 × 23 + 1 × 22 + 0 × 21 + 1 × 20 = 1310 one one no one eight four two one Chapter 1  Powers of Two 20 = 28 = 21 = 29 = 22 = 210 = 23 = 211 = 24 = 212 = 25 = 213 = 26 = 214 = 27 = 215 = Chapter 1  Powers of Two 20 = 1 28 = 256 21 = 2 29 = 512 22 = 4 210 = 1024 23 = 8 211 = 2048 24 = 16 212 = 4096 25 = 32 213 = 8192 26 = 64 214 = 16384 27 = 128 215 = 32768 Handy to memorize up to 29 Chapter 1  Number Conversion Decimal to binary conversion: – Convert 100112 to decimal Decimal to binary conversion: – Convert 4710 to binary Chapter 1  Number Conversion Decimal to binary conversion: – Convert 100112 to decimal – 16×1 + 8×0 + 4×0 + 2×1 + 1×1 = 1910 Decimal to binary conversion: – Convert 4710 to binary – 32×1 + 16×0 + 8×1 + 4×1 + 2×1 + 1×1 = 1011112 Chapter 1  Binary Values and Range N-digit decimal number How many values? Range? Example: 3-digit decimal number: N-bit binary number How many values? Range: Example: 3-digit binary number: Chapter 1  Binary Values and Range N-digit decimal number How many values? 10N Range? [0, 10N - 1] Example: 3-digit decimal number: 103 = 1000 possible values Range: [0, 999] N-bit binary number How many values? 2N Range: [0, 2N - 1] Example: 3-digit binary number: 23 = 8 possible values Range: [0, 7] = [0002 to 1112] Chapter 1  Hexadecimal Numbers Hex Digit Decimal Equivalent Binary Equivalent 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 A 10 B 11 C 12 D 13 E 14 F 15 Chapter 1  Hexadecimal Numbers Hex Digit Decimal Equivalent Binary Equivalent 0 0 0000 1 1 0001 2 2 0010 3 3 0011 4 4 0100 5 5 0101 6 6 0110 7 7 0111 8 8 1000 9 9 1001 A 10 1010 B 11 1011 C 12 1100 D 13 1101 E 14 1110 F 15 1111 Chapter 1  Hexadecimal Numbers Base 16 Shorthand for binary Chapter 1  Hexadecimal to Binary Conversion Hexadecimal to binary conversion: – Convert 4AF16 (also written 0x4AF) to binary Hexadecimal to decimal conversion: – Convert 0x4AF to decimal Chapter 1  Hexadecimal to Binary Conversion Hexadecimal to binary conversion: – Convert 4AF16 (also written 0x4AF) to binary – 0100 1010 11112 Hexadecimal to decimal conversion: – Convert 4AF16 to decimal – 162×4 + 161×10 + 160×15 = 119910 Chapter 1 Bits, Bytes, Nibbles… Bits 10010110 most least significant significant bit bit Bytes & Nibbles byte 10010110 nibble Bytes CEBF9AD7 most least significant significant byte byte Chapter 1 Large Powers of Two 210 = 1 kilo ≈ 1000 (1024) 220 = 1 mega ≈ 1 million (1,048,576) 230 = 1 giga ≈ 1 billion (1,073,741,824) Chapter 1 Estimating Powers of Two What is the value of 224? How many values can a 32-bit variable represent? Chapter 1 Estimating Powers of Two What is the value of 224? - 24 × 220 ≈ 16 million How many values can a 32-bit variable represent? -22 × 230 ≈ 4 billion Chapter 1  Addition Decimal carries 11 3734 + 5168 8902 Binary 11 carries 1011 + 0011 1110 Chapter 1  Binary Addition Examples Add the following 1001 4-bit binary + 0101 numbers Add the following 1011 4-bit binary + 0110 numbers Chapter 1  Binary Addition Examples Add the following 1 1001 4-bit binary + 0101 numbers 1110 111 Add the following 1011 4-bit binary + 0110 numbers 10001 Overflow! Chapter 1  Overflow Digital systems operate on a fixed number of bits Overflow: when result is too big to fit in the available number of bits See previous example of 11 + 6 Chapter 1  Signed Binary Numbers Sign/Magnitude Numbers Two’s Complement Numbers Chapter 1  Sign/Magnitude Numbers 1 sign bit, N-1 magnitude bits Sign bit is the most significant (left-most) bit – Positive number: sign bit = 0 A :  a N  1 , a N  2 , a2 , a1 , a0  – Negative number: sign bit = 1 n 2 a A (  1) n 1 i a 2 i 0 i Example, 4-bit sign/mag representations of ± 6: +6 = -6= Range of an N-bit sign/magnitude number: Chapter 1  Sign/Magnitude Numbers 1 sign bit, N-1 magnitude bits Sign bit is the most significant (left-most) bit – Positive number: sign bit = 0 A :  a N  1 , a N  2 , a2 , a1 , a0  – Negative number: sign bit = 1 n 2 a A (  1) n 1 i a 2 i 0 i Example, 4-bit sign/mag representations of ± 6: +6 = 0110 - 6 = 1110 Range of an N-bit sign/magnitude number: [-(2N-1-1), 2N-1-1] Chapter 1  Sign/Magnitude Numbers Problems: – Addition doesn’t work, for example -6 + 6: 1110 + 0110 10100 (wrong!) – Two representations of 0 (± 0): 1000 0000 Chapter 1  Two’s Complement Numbers Don’t have same problems as sign/magnitude numbers: – Addition works – Single representation for 0 Chapter 1  Two’s Complement Numbers Msb has value of -2 N-1 n 2 A an  1  2n  1    ai 2i i 0 Most positive 4-bit number: Most negative 4-bit number: The most significant bit still indicates the sign (1 = negative, 0 = positive) Range of an N-bit two’s comp number: Chapter 1  Two’s Complement Numbers Msb has value of -2 N-1 n 2 A an  1  2n  1    ai 2i i 0 Most positive 4-bit number: 0111 Most negative 4-bit number: 1000 The most significant bit still indicates the sign (1 = negative, 0 = positive) Range of an N-bit two’s comp number: [-(2N-1), 2N-1-1] Chapter 1  “Taking the Two’s Complement” Flip the sign of a two’s complement number Method: 1. Invert the bits 2. Add 1 Example: Flip the sign of 310 = 00112 Chapter 1  “Taking the Two’s Complement” Flip the sign of a two’s complement number Method: 1. Invert the bits 2. Add 1 Example: Flip the sign of 310 = 00112 1. 1100 2. + 1 1101 = -310 Chapter 1  Two’s Complement Examples Take the two’s complement of 610 = 01102 What is the decimal value of 10012? Chapter 1  Two’s Complement Examples Take the two’s complement of 610 = 01102 1. 1001 2. + 1 10102 = -610 What is the decimal value of the two’s complement number 10012? 1. 110 2. + 1 1112 = 710, so 10012 = -710 Chapter 1  Two’s Complement Addition Add 6 + (-6) using two’s complement numbers 0110 + 1010 Add -2 + 3 using two’s complement numbers 1110 + 0011 Chapter 1  Two’s Complement Addition Add 6 + (-6) using two’s complement 111 numbers 0110 + 1010 10000 Add -2 + 3 using two’s complement 111 numbers 1110 + 0011 10001 Chapter 1  Increasing Bit Width Extend number from N to M bits (M > N) : – Sign-extension – Zero-extension Copyright © 2012 Elsevier Chapter 1  Sign-Extension Sign bit copied to msb’s Number value is same Example 1: – 4-bit representation of 3 = 0011 – 8-bit sign-extended value: 00000011 Example 2: – 4-bit representation of -5 = 1011 – 8-bit sign-extended value: 11111011 Chapter 1  Zero-Extension Zeros copied to msb’s Value changes for negative numbers Example 1: – 4-bit value = 00112 = 310 – 8-bit zero-extended value: 00000011 = 310 Example 2: – 4-bit value = 1011 = -510 – 8-bit zero-extended value: 00001011 = 1110 Chapter 1  Number System Comparison Number System Range Unsigned [0, 2N-1] Sign/Magnitude [-(2N-1-1), 2N-1-1] Two’s Complement [-2N-1, 2N-1-1] For example, 4-bit representation: -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Unsigned 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 1000 1001 1010 1011 1100 1101 1110 1111 0000 0001 0010 0011 0100 0101 0110 0111 Two's Complement 0000 1111 1110 1101 1100 1011 1010 1001 1000 0001 0010 0011 0100 0101 0110 0111 Sign/Magnitude Chapter 1  Logic Gates Perform logic functions: inversion (NOT), AND, OR, NAND, NOR, etc. Single-input: NOT gate, buffer Two-input: AND, OR, XOR, NAND, NOR, XNOR Multiple-input Chapter 1  Single-Input Logic Gates NOT BUF A Y A Y Y=A Y=A A Y A Y 0 0 1 1 Chapter 1  Single-Input Logic Gates NOT BUF A Y A Y Y=A Y=A A Y A Y 0 1 0 0 1 0 1 1 Chapter 1  Two-Input Logic Gates AND OR A A Y Y B B Y = AB Y=A+B A B Y A B Y 0 0 0 0 0 1 0 1 1 0 1 0 1 1 1 1 Chapter 1  Two-Input Logic Gates AND OR A A Y Y B B Y = AB Y=A+B A B Y A B Y 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 1 0 1 1 1 1 1 1 1 Chapter 1 More Two-Input Logic Gates XOR NAND NOR XNOR A A A A Y Y Y Y B B B B Y=A+B Y = AB Y=A+B Y=A+B A B Y A B Y A B Y A B Y 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 Chapter 1 More Two-Input Logic Gates XOR NAND NOR XNOR A A A A Y Y Y Y B B B B Y=A+B Y = AB Y=A+B Y=A+B A B Y A B Y A B Y A B Y 0 0 0 0 0 1 0 0 1 0 0 1 0 1 1 0 1 1 0 1 0 0 1 0 1 0 1 1 0 1 1 0 0 1 0 0 1 1 0 1 1 0 1 1 0 1 1 1 Chapter 1  Multiple-Input Logic Gates NOR3 AND4 A A B B Y C Y C D Y = A+B+C Y = ABCD A B C Y A B C Y 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 0 1 1 1 0 0 1 0 0 1 0 1 1 0 1 1 1 0 1 1 0 1 1 1 1 1 1 Chapter 1  Multiple-Input Logic Gates NOR3 AND4 A A B B Y C Y C D Y = A+B+C Y = ABCD A B C Y A B C Y 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 1 0 0 1 1 0 1 0 0 0 1 0 0 0 1 0 1 0 1 0 1 0 1 1 0 0 1 1 0 0 1 1 1 0 1 1 1 1 Multi-input XOR: Odd parity Chapter 1  Logic Levels Discrete voltages represent 1 and 0 For example: 0 = ground (GND) or 0 volts 1 = VDD or 5 volts What about 4.99 volts? Is that a 0 or a 1? What about 3.2 volts? Chapter 1 Logic Levels Range of voltages for 1 and 0 Different ranges for inputs and outputs to allow for noise Noise Driver Receiver 5V 4.5 V Output Characteristics Input Characteristics VDD Logic High Output Range Logic High VO H Input Range NMH Forbidden VIH Zone VIL VO L NML Logic Low Logic Low Input Range Output Range GND Chapter 1  What is Noise? Anything that degrades the signal E.g., resistance, power supply noise, coupling to neighboring wires, etc. Example: a gate (driver) outputs 5 V but, because of resistance in a long wire, receiver gets 4.5 V Noise Driver Receiver 5V 4.5 V Chapter 1  Noise Margins Driver Receiver Output Characteristics Input Characteristics VDD Logic High Output Range Logic High VO H Input Range NMH Forbidden VIH Zone VIL VO L NML Logic Low Logic Low Input Range Output Range GND NMH = VOH – VIH NML = VIL – VOL Chapter 1 The Static Discipline With logically valid inputs, every circuit element must produce logically valid outputs Use limited ranges of voltages to represent discrete values Chapter 1  VDD Scaling In 1970’s and 1980’s, VDD = 5 V VDD has dropped Avoid frying tiny transistors Save power 3.3 V, 2.5 V, 1.8 V, 1.5 V, 1.2 V, 1.0 V, … Be careful connecting chips with different supply voltages Chips operate because they contain magic smoke Proof: if the magic smoke is let out, the chip stops working Chapter 1  Logic Family Examples Logic Family VDD VIL VIH VOL VOH TTL 5 (4.75 - 5.25) 0.8 2.0 0.4 2.4 CMOS 5 (4.5 - 6) 1.35 3.15 0.33 3.84 LVTTL 3.3 (3 - 3.6) 0.8 2.0 0.4 2.4 LVCMOS 3.3 (3 - 3.6) 0.9 1.8 0.36 2.7 Chapter 1  Transistors Logic gates built from transistors 3-ported voltage-controlled switch – 2 ports connected depending on voltage of 3rd – d and s are connected (ON) when g is 1 g=0 g=1 d d d g OFF ON s s s Chapter 1  MOS Transistors Metal oxide silicon (MOS) transistors: – Polysilicon (used to be metal) gate – Oxide (silicon dioxide) insulator – Doped silicon source gate drain Polysilicon SiO2 n n p substrate gate source drain nMOS Chapter 1  Transistors: nMOS Gate = 0 Gate = 1 OFF (no connection ON (channel between between source and source and drain) drain) source drain source gate drain gate VDD GND +++++++ ------- n n n n channel p substrate p substrate GND GND Chapter 1  Transistors: pMOS pMOS transistor is opposite ON when Gate = 0 OFF when Gate = 1 source gate drain Polysilicon SiO2 p p n substrate gate source drain Chapter 1 Transistor Function g=0 g=1 d d d nMOS g OFF ON s s s s s s pMOS g OFF ON d d d Chapter 1  Transistor Function nMOS: pass good 0’s, so connect source to GND pMOS: pass good 1’s, so connect source to VDD pMOS pull-up network inputs output nMOS pull-down network Chapter 1  CMOS Gates: NOT Gate NOT VDD A Y P1 Y=A A Y N1 A Y 0 1 1 0 GND A P1 N1 Y 0 1 Chapter 1  CMOS Gates: NOT Gate NOT VDD A Y P1 Y=A A Y N1 A Y 0 1 1 0 GND A P1 N1 Y 0 ON OFF 1 1 OFF ON 0 Chapter 1  CMOS Gates: NAND Gate NAND A Y B P2 P1 Y Y = AB A N1 A B Y 0 0 1 B N2 0 1 1 1 0 1 1 1 0 A B P1 P2 N1 N2 Y 0 0 0 1 1 0 1 1 Chapter 1  CMOS Gates: NAND Gate NAND A Y B P2 P1 Y Y = AB A N1 A B Y 0 0 1 B N2 0 1 1 1 0 1 1 1 0 A B P1 P2 N1 N2 Y 0 0 ON ON OFF OFF 1 0 1 ON OFF OFF ON 1 1 0 OFF ON ON OFF 1 1 1 OFF OFF ON ON 0 Chapter 1 CMOS Gate Structure pMOS pull-up network inputs output nMOS pull-down network Chapter 1  NOR Gate How do you build a three-input NOR gate? Chapter 1  NOR3 Gate A B C Y Chapter 1  Other CMOS Gates How do you build a two-input AND gate? Chapter 1  AND2 Gate A Y B Chapter 1 Transmission Gates nMOS pass 1’s poorly pMOS pass 0’s poorly EN Transmission gate is a better switch passes both 0 and 1 well A B When EN = 1, the switch is ON: EN = 0 and A is connected to B When EN = 0, the switch is OFF: EN A is not connected to B Chapter 1  Pseudo-nMOS Gates Replace pull-up network with weak pMOS transistor that is always on pMOS transistor: pulls output HIGH only when nMOS network not pulling it LOW weak Y inputs nMOS pull-down network Chapter 1 Pseudo-nMOS Example Pseudo-nMOS NOR4 weak Y A B C D Chapter 1  Gordon Moore, 1929- Cofounded Intel in 1968 with Robert Noyce. Moore’s Law: number of transistors on a computer chip doubles every year (observed in 1965) Since 1975, transistor counts have doubled every two years. Chapter 1  Moore’s Law “If the automobile had followed the same development cycle as the computer, a Rolls-Royce would today cost $100, get one million miles to the gallon, and explode once a year...” – Robert Cringley Chapter 1  Power Consumption Power = Energy consumed per unit time Dynamic power consumption Static power consumption Chapter 1 Dynamic Power Consumption Power to charge transistor gate capacitances Energy required to charge a capacitance, C, to VDD is CVDD2 Circuit running at frequency f: transistors switch (from 1 to 0 or vice versa) at that frequency Capacitor is charged f/2 times per second (discharging from 1 to 0 is free) Dynamic power consumption: Pdynamic = ½CVDD2f Chapter 1 Static Power Consumption Power consumed when no gates are switching Caused by the quiescent supply current, IDD (also called the leakage current) Static power consumption: Pstatic = IDDVDD Chapter 1 Power Consumption Example Estimate the power consumption of a wireless handheld computer VDD = 1.2 V C = 20 nF f = 1 GHz IDD = 20 mA Chapter 1 Power Consumption Example Estimate the power consumption of a wireless handheld computer VDD = 1.2 V C = 20 nF f = 1 GHz IDD = 20 mA P = ½CVDD2f + IDDVDD = ½(20 nF)(1.2 V)2(1 GHz) + (20 mA)(1.2 V) = 14.4 W Chapter 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  Introduction A logic circuit is composed of: Inputs Outputs Functional specification Timing specification functional spec inputs outputs timing spec Chapter 2 Circuits Nodes – Inputs: A, B, C – Outputs: Y, Z A E1 n1 – Internal: n1 B E3 Y Circuit elements C E2 Z – E1, E2, E3 – Each a circuit Chapter 2  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 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 Rules of Combinational Composition a) is combinational d) is not combinational b) is not combinational e) is combinational c) is combinational f) is not combinational Chapter 2  Boolean Equations Functional specification of outputs in terms of inputs Example: S = F(A, B, Cin) Cout = F(A, B, Cin) A CL S B Cout Cin S = A  B  Cin Cout = AB + ACin + BCin Chapter 2  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  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 A B Y minterm name 0 0 0 A B m0 0 1 1 A B m1 1 0 0 A B m2 1 1 1 A B m3 Y = F(A, B) = Chapter 2  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 A B Y minterm name 0 0 0 A B m0 0 1 1 A B m1 1 0 0 A B m2 1 1 1 A B m3 Y = F(A, B) = Chapter 2  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 A B Y minterm name 0 0 0 A B m0 0 1 1 A B m1 1 0 0 A B m2 1 1 1 A B m3 Y = F(A, B) = AB + AB = Σ(1, 3) Chapter 2  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 A B Y maxterm name 0 0 0 A + B M0 0 1 1 A + B M1 1 0 0 A + B M2 1 1 1 A + B M3 Y = F(A, B) = (A + B)(A + B) = Π(0, 2) Chapter 2  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 C E 0 0 0 1 1 0 1 1 Chapter 2  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 C E 0 0 0 0 1 0 1 0 1 1 1 0 Chapter 2  SOP & POS Form SOP – sum-of-products O C E minterm 0 0 O C 0 1 O C 1 0 O C 1 1 O C POS – product-of-sums O C Y maxterm 0 0 O + C 0 1 O + C 1 0 O + C 1 1 O + C Chapter 2  SOP & POS Form SOP – sum-of-products O C E minterm 0 0 0 O C 0 1 0 O C Y = OC 1 0 1 O C = Σ(2) 1 1 0 O C POS – product-of-sums O C E maxterm 0 0 0 O + C Y = (O + C)(O + C)(O + C) 0 1 0 O + C 1 0 1 O + C = Π(0, 1, 3) 1 1 0 O + C Chapter 2  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 Chapter 2 Boolean Axioms Chapter 2 T1: Identity Theorem B 1=B B+0=B Chapter 2 T1: Identity Theorem B 1=B B+0=B B 1 = B B 0 = B Chapter 2 T2: Null Element Theorem B 0=0 B+1=1 Chapter 2 T2: Null Element Theorem B 0=0 B+1=1 B 0 = 0 B 1 = 1 Chapter 2 T3: Idempotency Theorem B B=B B+B=B Chapter 2 T3: Idempotency Theorem B B=B B+B=B B B = B B B = B Chapter 2 T4: Identity Theorem B=B Chapter 2 T4: Identity Theorem B=B B = B Chapter 2 T5: Complement Theorem B B=0 B+B=1 Chapter 2 T5: Complement Theorem B B=0 B+B=1 B B = 0 B B = 1 Chapter 2 Boolean Theorems Summary Chapter 2 Boolean Theorems of Several Vars Chapter 2  Simplifying Boolean Equations Example 1: Y = AB + AB Chapter 2  Simplifying Boolean Equations Example 1: Y = AB + AB = B(A + A) T8 = B(1) T5’ =B T1 Chapter 2  Simplifying Boolean Equations Example 2: Y = A(AB + ABC) Chapter 2  Simplifying Boolean Equations Example 2: Y = A(AB + ABC) = A(AB(1 + C)) T8 = A(AB(1)) T2’ = A(AB) T1 = (AA)B T7 = AB T3 Chapter 2  DeMorgan’s Theorem Y = AB = A + B A B Y A Y B Y=A+B=A B A B Y A Y B Chapter 2  Bubble Pushing Backward: – Body changes – Adds bubbles to inputs A A Y Y B B Forward: – Body changes – Adds bubble to output A A Y Y B B Chapter 2  Bubble Pushing What is the Boolean expression for this circuit? A B Y C D Chapter 2  Bubble Pushing What is the Boolean expression for this circuit? A B Y C D Y = AB + CD Chapter 2  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 Bubble Pushing Example A B C Y D Chapter 2 Bubble Pushing Example no output A bubble B C Y D Chapter 2 Bubble Pushing Example no output A bubble B C Y D bubble on A input and output B C Y D Chapter 2 Bubble Pushing Example no output A bubble B C Y D bubble on A input and output B C Y D no bubble on input and output A B C Y D Y = ABC + D Chapter 2  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  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  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 wires connect wires connect without a dot do at a T junction at a dot not connect Chapter 2  Multiple-Output Circuits Example: Priority Circuit A3 A2 A1 A0 Y3 Y2 Y1 Y0 Output asserted 0 0 0 0 0 0 0 1 corresponding to 0 0 1 0 most significant 0 0 0 1 1 0 1 0 TRUE input 0 1 0 1 0 1 1 0 0 1 1 1 A3 Y3 1 0 0 0 1 0 0 1 A2 Y2 1 0 1 0 1 0 1 1 A1 Y1 1 1 0 0 1 1 0 1 A0 Y0 1 1 1 0 PRIORITY 1 1 1 1 CiIRCUIT Chapter 2  Multiple-Output Circuits Example: Priority Circuit A3 A2 A1 A0 Y3 Y2 Y1 Y0 Output asserted 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 corresponding to 0 0 1 0 0 0 1 0 most significant 0 0 0 1 1 0 1 0 0 0 0 1 1 0 0 0 TRUE input 0 1 0 1 0 1 0 0 0 1 1 0 0 1 0 0 0 1 1 1 0 1 0 0 A3 Y3 1 0 0 0 1 0 0 0 1 0 0 1 1 0 0 0 A2 Y2 1 0 1 0 1 0 0 0 1 0 1 1 1 0 0 0 A1 Y1 1 1 0 0 1 0 0 0 1 1 0 1 1 0 0 0 A0 Y0 1 1 1 0 1 0 0 0 PRIORITY 1 1 1 1 1 0 0 0 CiIRCUIT Chapter 2 Priority Circuit Hardware A3 A2 A1 A0 Y3 Y2 Y1 Y0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 A3 A2 A1 A0 0 0 1 0 0 0 1 0 Y3 0 0 1 1 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 0 1 0 0 Y2 0 1 1 0 0 1 0 0 0 1 1 1 0 1 0 0 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 Y1 1 0 1 0 1 0 0 0 1 0 1 1 1 0 0 0 1 1 0 0 1 0 0 0 Y0 1 1 0 1 1 0 0 0 1 1 1 0 1 0 0 0 1 1 1 1 1 0 0 0 Chapter 2 Don’t Cares A3 A2 A1 A0 Y3 Y2 Y1 Y0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 1 0 0 1 0 0 1 0 0 0 1 0 0 A3 A2 A1 A0 Y3 Y2 Y1 Y0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 1 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 1 X 0 0 1 0 1 0 0 1 1 0 0 0 0 1 X X 0 1 0 0 1 0 1 0 1 0 0 0 1 X X X 1 0 0 0 1 0 1 1 1 0 0 0 1 1 0 0 1 0 0 0 1 1 0 1 1 0 0 0 1 1 1 0 1 0 0 0 1 1 1 1 1 0 0 0 Chapter 2 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  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 A Y E A Y 0 0 Z 0 1 Z 1 0 0 1 1 1 Chapter 2  Tristate Busses Floating nodes are used in tristate busses – Many different drivers processor en1 – Exactly one is active at to bus frombus once video en2 to bus frombus sharedbus Ethernet en3 to bus frombus memory en4 to bus frombus Chapter 2  Karnaugh Maps (K-Maps) Boolean expressions can be minimized by combining terms K-maps minimize equations graphically PA + PA = P A B C Y Y Y AB AB 0 0 0 1 00 01 11 10 C 00 01 11 10 0 0 1 1 C 0 1 0 0 0 1 1 0 0 1 0 0 0 0 ABC ABC ABC ABC 1 0 0 0 1 0 1 0 1 1 0 0 1 1 0 0 0 1 ABC ABC ABC ABC 1 1 1 0 Chapter 2  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 A B C Y AB 0 0 0 1 00 01 11 10 0 0 1 1 C 0 1 0 0 0 1 1 0 0 1 0 0 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 0 0 0 1 1 1 0 Y = AB Chapter 2 3-Input K-Map Y AB C 00 01 11 10 0 ABC ABC ABC ABC 1 ABC ABC ABC ABC Truth Table K-Map Y A B C Y AB 0 0 0 0 C 00 01 11 10 0 0 1 0 0 1 0 1 0 0 1 1 1 1 0 0 0 1 0 1 0 1 1 1 0 0 1 1 1 1 Chapter 2 3-Input K-Map Y AB C 00 01 11 10 0 ABC ABC ABC ABC 1 ABC ABC ABC ABC Truth Table K-Map Y A B C Y AB 0 0 0 0 C 00 01 11 10 0 0 1 0 0 0 1 1 0 1 1 1 0 0 1 1 0 1 0 0 0 1 1 0 1 1 0 0 0 1 0 1 0 0 1 1 1 1 Y = AB + BC Chapter 2  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  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 Chapter 2 4-Input K-Map A B C D Y Y 0 0 0 0 1 AB 0 0 0 1 0 CD 00 01 11 10 0 0 1 0 1 0 0 1 1 1 00 0 1 0 0 0 0 1 0 1 1 0 1 1 0 1 01 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 11 1 0 1 0 1 1 0 1 1 0 1 1 0 0 0 10 1 1 0 1 0 1 1 1 0 0 1 1 1 1 0 Chapter 2 4-Input K-Map A B C D Y Y 0 0 0 0 1 AB 0 0 0 1 0 CD 00 01 11 10 0 0 1 0 1 0 0 1 1 1 00 1 0 0 1 0 1 0 0 0 0 1 0 1 1 0 1 1 0 1 01 0 1 0 1 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 11 1 1 0 0 1 0 1 0 1 1 0 1 1 0 1 1 0 0 0 10 1 1 0 1 1 1 0 1 0 1 1 1 0 0 1 1 1 1 0 Chapter 2 4-Input K-Map A B C D Y Y 0 0 0 0 1 AB 0 0 0 1 0 CD 00 01 11 10 0 0 1 0 1 0 0 1 1 1 00 1 0 0 1 0 1 0 0 0 0 1 0 1 1 0 1 1 0 1 01 0 1 0 1 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 11 1 1 0 0 1 0 1 0 1 1 0 1 1 0 1 1 0 0 0 10 1 1 0 1 1 1 0 1 0 1 1 1 0 0 1 1 1 1 0 Y = AC + ABD + ABC + BD Chapter 2 K-Maps with Don’t Cares A B C D Y Y 0 0 0 0 1 AB 0 0 0 1 0 CD 00 01 11 10 0 0 1 0 1 0 0 1 1 1 00 0 1 0 0 0 0 1 0 1 X 0 1 1 0 1 01 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 11 1 0 1 0 X 1 0 1 1 X 1 1 0 0 X 10 1 1 0 1 X 1 1 1 0 X 1 1 1 1 X Chapter 2 K-Maps with Don’t Cares A B C D Y Y 0 0 0 0 1 AB 0 0 0 1 0 CD 00 01 11 10 0 0 1 0 1 0 0 1 1 1 00 1 0 X 1 0 1 0 0 0 0 1 0 1 X 0 1 1 0 1 01 0 X X 1 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 11 1 1 X X 1 0 1 0 X 1 0 1 1 X 1 1 0 0 X 10 1 1 X X 1 1 0 1 X 1 1 1 0 X 1 1 1 1 X Chapter 2 K-Maps with Don’t Cares A B C D Y Y 0 0 0 0 1 AB 0 0 0 1 0 CD 00 01 11 10 0 0 1 0 1 0 0 1 1 1 00 1 0 X 1 0 1 0 0 0 0 1 0 1 X 0 1 1 0 1 01 0 X X 1 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 11 1 1 X X 1 0 1 0 X 1 0 1 1 X 1 1 0 0 X 10 1 1 X X 1 1 0 1 X 1 1 1 0 X 1 1 1 1 X Y = A + BD + C Chapter 2  Combinational Building Blocks Multiplexers Decoders Chapter 2  Multiplexer (Mux) Selects between one of N inputs to connect to output log2N-bit select input – control input Example: 2:1 Mux S D0 0 Y D1 1 S D1 D0 Y S Y 0 0 0 0 0 D0 0 0 1 1 1 D1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 0 1 1 0 1 1 1 1 1 Chapter 2 Multiplexer Implementations Logic gates Tristates – Sum-of-products form – For an N-input mux, use N tristates Y – Turn on exactly one to D0 D1 S 00 01 11 10 select the appropriate input 0 0 0 1 1 S 1 0 1 1 0 D0 Y = D0S + D1S Y D0 D1 S D1 Y 2- Chapter 2  Logic using Multiplexers Using the mux as a lookup table A B Y 0 0 0 0 1 0 1 0 0 1 1 1 Y = AB AB 00 01 10 Y 11 Chapter 2  Logic using Multiplexers Reducing the size of the mux A A B Y A Y 0 0 0 0 0 0 0 1 0 Y Y = AB 1 0 0 1 B B 1 1 1 1 Chapter 2  Decoders N inputs, 2N outputs One-hot outputs: only one output HIGH at once 2:4 Decoder 11 Y3 A1 10 Y2 A0 01 Y1 00 Y0 A1 A0 Y3 Y2 Y1 Y0 0 0 0 0 0 1 0 1 0 0 1 0 1 0 0 1 0 0 1 1 1 0 0 0 Chapter 2 Decoder Implementation A1 A0 Y3 Y2 Y1 Y0 Chapter 2  Logic Using Decoders OR minterms 2:4 Decoder Minterm 11 AB A 10 AB B 01 AB 00 AB Y = AB + AB = A  B Y Chapter 2  Timing Delay between input change and output changing How to build fast circuits? A Y delay A Y Time Chapter 2  Propagation & Contamination Delay Propagation delay: tpd = max delay from input to output Contamination delay: tcd = min delay from input to output A Y tpd A Y tcd Time Chapter 2  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 Critical (Long) & Short Paths Critical Path A n1 B n2 C D Y Short Path Critical (Long) Path: tpd = 2tpd_AND + tpd_OR Short Path: tcd = tcd_AND Chapter 2  Glitches When a single input change causes multiple output changes Chapter 2  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 Glitch Example (cont.) Critical Path A=0 0 1 B=1 0 n1 Y=1 0 1 n2 C=1 1 0 Short Path B n2 n1 Y glitch Time Chapter 2 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