Introduction to Computer EngineeringChapter 3 Digital Logic StructuresTransistor: Building Block of ComputersSimple Switch CircuitN-type MOS TransistorP-type MOS TransistorLogic GatesCMOS CircuitInverter (NOT Gate)NOR GateOR GateNAND Gate (AND-NOT)AND GateBasic Logic GatesMore than 2 Inputs?PracticeLogical CompletenessSlide 18DeMorgan's LawSummaryBuilding Functions from Logic GatesDecoderMultiplexer (MUX)Full AdderFour-bit AdderCombinational vs. SequentialR-S Latch: Simple Storage ElementClearing the R-S latchSetting the R-S LatchR-S Latch SummaryGated D-LatchRegisterRepresenting Multi-bit ValuesMemory22 x 3 MemoryMore Memory DetailsState MachineSlide 38StateState of Sequential LockState DiagramFinite State MachineThe ClockImplementing a Finite State MachineStorage: Master-Slave FlipflopStorageComplete ExampleTraffic Sign State DiagramTraffic Sign Truth TablesTraffic Sign LogicFrom Logic to Data PathLC-2/LC-3 Data PathIntroduction to Computer EngineeringCS/ECE 252, Fall 2007Prof. David A. WoodComputer Sciences DepartmentUniversity of Wisconsin – MadisonChapter 3Digital LogicStructuresSlides based on set prepared by Gregory T. Byrd, North Carolina State University3-3Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Transistor: Building Block of ComputersShow LED flashlightBattery, Switch, LEDNormal state: Switch open, no current, no lightPush botton: Switch closed, current flows, light3-4Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Simple Switch CircuitSwitch open:•No current through circuit•Light is off•Vout is +2.9VSwitch closed:•Short circuit across switch•Current flows•Light is on•Vout is 0VSwitch-based circuits can easily represent two states:on/off, open/closed, voltage/no voltage.3-5Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.N-type MOS TransistorMOS = Metal Oxide Semiconductor•two types: N-type and P-typeN-type•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 must beconnected to GND (0V).3-6Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.P-type MOS TransistorP-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 must beconnected to +2.9V.3-7Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Logic GatesUse switch behavior of MOS transistorsto implement logical functions: AND, OR, NOT.Digital symbols:•recall that we assign a range of analog voltages to eachdigital (logic) symbol•assignment of voltage ranges depends on electrical properties of transistors being usedtypical values for "1": +5V, +3.3V, +2.9V, +1.1Vfor purposes of illustration, we'll use +2.9V3-8Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.CMOS CircuitComplementary MOSUses both N-type and P-type MOS transistors•P-typeAttached to + voltagePulls output voltage UP when input is zero•N-typeAttached to GNDPulls output voltage DOWN when input is oneFor all inputs, make sure that output is either connected to GND or to +,but not both!Draw generic CMOS gate w/ P and N blocks.3-9Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Inverter (NOT Gate)In Out0 V 2.9 V2.9 V 0 VIn Out0 11 0Truth table3-10Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.NOR GateA B C0 0 10 1 01 0 01 1 0Note: Serial structure on top, parallel on bottom.3-11Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.OR GateAdd inverter to NOR.A B C0 0 00 1 11 0 11 1 13-12Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.NAND Gate (AND-NOT)A B C0 0 10 1 11 0 11 1 0Note: Parallel structure on top, serial on bottom.3-13Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.AND GateAdd inverter to NAND.A B C0 0 00 1 01 0 01 1 13-14Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Basic Logic Gates3-15Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.More 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.Can implement with multiple two-input gates,or with single CMOS circuit.3-16Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.PracticeImplement a 3-input NOR gate with CMOS.3-17Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Logical CompletenessCan implement ANY truth table with AND, OR, NOT.A B C D0 0 0 00 0 1 00 1 0 10 1 1 01 0 0 01 0 1 11 1 0 01 1 1 01. AND combinations that yield a "1" in the truth table.2. OR the resultsof the AND gates.3-18Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.PracticeImplement the following truth table.A B C0 0 00 1 11 0 11 1 03-19Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.DeMorgan's LawConverting AND to OR (with some help from NOT)Consider the following gate:A B0 0 1 1 1 00 1 1 0 0 11 0 0 1 0 11 1 0 0 0 1BA BABA Same as A+B!To convert AND to OR (or vice versa),invert inputs and output.3-20Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.SummaryMOS transistors are used as switches to implementlogic functions.•N-type: connect to GND, turn on (with 1) to pull down to 0•P-type: connect to +2.9V, turn on (with 0) to pull up to 1Basic gates: NOT, NOR, NAND•Logic functions are usually expressed with AND, OR, and NOTProperties of logic gates•Completenesscan implement any truth table with AND, OR, NOT•DeMorgan's Lawconvert AND to OR by inverting inputs and output3-21Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Building Functions from Logic GatesWe've already seen how to implement truth tablesusing AND, OR, and NOT -- an example of combinational