Based on slides © McGraw-HillAdditional material © 2004/2005/2006 Lewis/MartinChapter 3Digital LogicStructures3-2CSE 240Transistor: Building Block of Computers Microprocessors contain millions of transistors• Intel Pentium 4 (2000): 48 million• IBM PowerPC 750FX (2002): 38 million• IBM PowerPC G5 (2003): 58 million• Intel Core Duo 2 (2006): 291 million (192+ million in cache alone) Logically, each transistor acts as a switch Combined to implement logic functions• AND, OR, NOT Combined to build higher-level structures• Adder, multiplexer, decoder, register, … Combined to build processor• LC-33-3CSE 2403-4CSE 240How do we represent data in a computer? At the lowest level, a computer has electronic “plumbing”• Operates by controlling the flow of electrons Easy to recognize two conditions:1. Presence of a voltage – we’ll call this state “1”2. Absence of a voltage – we’ll call this state “0”Computer use transistors as switches to manipulate bits• Before transistors: tubes, electro-mechanical relays (pre 1950s)• Mechanical adders (punch cards, gears) as far back as mid-1600s Before describing transistors, we present an analogy…3-5CSE 240A Transistor Analogy: Computing with Air Use air pressure to encode values• High pressure represents a “1” (blow)• Low pressure represents a “0” (suck) Valve can allow or disallow the flow of air• Two types of valves High (On) High (Off) N-Valve P-Valve Low (On) Low (Off) hole3-6CSE 240Pressure Inverter High Low Out N-Valve P-Valve In3-7CSE 240Pressure Inverter (Low to High) High Low Low N-Valve P-Valve High3-8CSE 240Pressure Inverter High Low N-Valve P-Valve3-9CSE 240 LowPressure Inverter (High to Low) High Low High N-Valve P-Valve3-10CSE 240Analogy Explained Pressure differential ! electrical potential (voltage)• Air molecules ! electrons• High pressure ! high voltage• Low pressure ! low voltage Air flow ! electrical current• Pipes ! wires• Air only flows from high to low pressure• Electrons only flow from high to low voltage• Flow only occurs when changing from 1 to 0 or 0 to 1 Valve ! transistor• The transistor: one of the century’s most important inventions3-11CSE 240Transistors as Switches Two types• N-type• P-type Properties• Solid state (no moving parts)• Reliable (low failure rate)• Small (90nm channel length)• Fast (<0.1ns switch latency) N-Valve P-Valve N-MOSFET P-MOSFET3-12CSE 240MOS + FET MOS: three materials needed to make a transistor• Metal (Al, W, Cu): conductor• Oxide (SiO2): insulator• Semiconductor (doped Si): conducts under certain conditions FET: field effect (the mechanism) transistor• Voltage on gate: current flows source to drain (transistor on)• No voltage on gate: no current (transistor off) Recall, two types of MOSFET: n and pchannelsource draininsulatorgate (cross-section view of a MOSFET)3-13CSE 240N-type MOS Transistor• When Gate has positive voltage,short circuit between #1 and #2(switch closed)• When Gate has zero voltage,open circuit between #1 and #2(switch open)Gate = 1Gate = 0Terminal #2 connectedto GROUND (0V).3-14CSE 240P-type MOS Transistor P-type is complementary to n-type• When Gate has positive voltage,open circuit between #1 and #2(switch open)• When Gate has zero voltage,short circuit between #1 and #2(switch closed)Gate = 1Gate = 0Terminal #1 connected to POWER (in this example, +2.9V)3-15CSE 240Inverter (NOT Gate)0110OutInTruth table Power Ground3-16CSE 240CMOS Circuit Inverter is an example of Complementary MOS (CMOS) Uses both n-type and p-type MOS transistors• p-type!Attached to POWER (high voltage)!Pulls output voltage UP when input is zero• n-type!Attached to GROUND (low voltage)!Pulls output voltage DOWN when input is one For all inputs, make sure that output is either connected to GROUNDor to POWER, but not both! (why?)3-17CSE 240NAND Gate (NOT-AND)11010110A0110CBNote: Parallel structure on top, serial on bottom. Power Ground3-18CSE 240AND Gate01000110A1100CBAdd inverter to NAND. Power Ground3-19CSE 240NOR Gate (NOT-OR)01000110A0110CBNote: Serial structure on top, parallel on bottom. Power Ground3-20CSE 240OR Gate11010110A1100CBAdd inverter to NOR. Power Ground3-21CSE 240AND ORNOT/INVBasic Gates From Now On… Gates• Covered transistors mostly so that you know they exist• Note: “Logic Gate” not related to “Gate” of transistors Will study implementation in terms of gates• Circuits that implement Boolean functions More complicated gates from transistors possible• XOR, Multiple-input AND-OR-Invert (AOI) gatesNANDNOR3-22CSE 240More than 2 Inputs? AND/OR can take any number of inputs• AND = 1 if all inputs are 1• OR = 1 if any input is 1• Similar for NAND/NOR Implementation• Multiple two-input gates or single CMOS circuit3-23CSE 240Visual Shorthand for Multi-bit Gates Use a cross-hatch mark to group wires• Example: calculate the AND of a pair of 4-bit numbers• A3 is “high-order” or “most-significant” bit• If “A” is 1000, then A3 = 1, A2 = 0, A1 = 0, A0 = 0 A0 B0 A1 B1 A2 B2 A3 B3 Out0 Out1 Out2 Out3 A B Out 4 4 43-24CSE 240Shorthand for Inverting Signals Invert a signal by adding either• A before/after a gate• A “bar” over letter A AND B A AND B A B A B A OR B A B3-25CSE 240Logical Completeness AND, OR, NOT can implement ANY truth table10101001010100111000A11001110B1100SCin A B Cin S1. AND combinations that yield a "1" in the truth table2. OR the resultsof the AND gates3-26CSE 240Logical Completeness via PLAs Any truth table as a Programmable Logic Array (PLA)• Traditionally a grid of AND and OR gates• Configurable by removing wires Single-output custom PLA (as on previous slide):• One AND gate per row with “1” in output in truth table• Maximum number of AND gates: 2n for n inputs• One OR gate Multiple-output custom PLA:• Build multiple single-output PLAs• Share AND gates “in common”• One OR gate per output column in truth table3-27CSE 240DeMorgan's Law Converting AND to OR (with some help from NOT) Consider the following gate:00011110To convert AND to OR (or vice versa),invert inputs and output.A AND B A AND B0110110A0B00110101A BA AND BWhy might this be useful?= A OR BA AND B = A OR BA AND B = A OR B3-28CSE 240Summary MOS transistors: switches to implement logic functions• n-type: connect to GROUND, turn on (with 1) to pull down to 0• p-type: connect to POWER, turn on (with 0) to pull up to