Digital Circuits CS 217 1 Course Outline First four weeks C programming Second four weeks Machine architecture Third four weeks Unix operating system 2 1 Levels of Abstraction We have been looking at programming at high level Abstractions provided by C Let s now look under the hood How does C program actually execute Start from bottom device hardware and work our way up C language Compiler Assembly language Assembler Machine language Microcontroller Digital logic Gates Device hardware 3 Analog circuits Components resistors inductors capacitors transistors Voltage current are continuous functions of time and of d dt of current voltage Build amplifiers radios output voltage Typical device characteristic input voltage 4 2 Digital circuits Components transistors transistors transistors and the occasional capacitor Pick two voltages of interest VCC and Ground Build clocks adders computers computers computers computers includes cell phone Nintendo cash register output voltage Typical device characteristic VCC Ground device saturated we care only about these two points on the graph input voltage 5 Digital Circuits Wires voltage resistors ground etc Vcc Vin Vout 0 Vcc Vcc 0 This is an NOT gate an inverter Vout Vin Transistor electrical switch Ground Electricity flows through iff Vin exceeds critical value VC 6 3 Digital Circuits Vcc Vout V1 V1 V2 Vout 0 0 Vcc 0 Vcc Vcc Vcc 0 Vcc Vcc Vcc 0 This is a NAND gate V2 7 Digital Circuits Vcc Vout V1 V2 V1 V2 Vout 0 0 Vcc 0 Vcc 0 Vcc 0 0 Vcc Vcc 0 This is a NOR gate 8 4 Gates x y NAND gate x y x y 0 0 1 1 0 1 0 1 y x y 0 1 1 0 0 0 1 0 x y NOR gate x 0 0 1 1 x NOT gate x x 0 1 1 0 also written xy 1 1 1 0 also written x y also written x x 9 Gates x y AND gate x 0 0 1 1 y x y 0 0 1 0 0 0 1 1 also written xy OR gate x 0 0 1 1 y x y 0 0 1 1 0 1 1 1 also written x y x y x y x y 10 5 Circuits Build higher level boolean logic out of gates x 0 0 1 1 x z y x y y 0 1 0 1 z 0 1 1 0 XOR gate x XOR y x y x y wires crossing not connected wire junction connection 11 Adder for 1 bit binary numbers x 0 0 1 1 y add x y 0 00 1 01 0 01 1 10 carry x sum y carry sum sum x XOR y carry x y 12 6 N bit binary adder x3 x2 x1 x0 sumi xi XOR yi XOR carryi 1 y3 y2 y1 y0 carryi xi yi xi XOR yi carryi 1 z4 z3 z2 z1 z0 x3 y3 x2 y2 x1 y1 x0 y0 z4 0 z3 z2 z1 z0 13 N bit binary adder x3 x2 x1 x0 0110 6 y3 y2 y1 y0 0011 3 z4 z3 z2 z1 z0 01001 9 0 0 0 1 0 0 0 1 1 1 1 0 0 1 0 1 0 0 0 0 1 1 1 1 0 0 1 0 0 0 0 0 1 1 14 7 Seat of the pants design You just saw it Can be inefficient x2 x2 y2 y2 longest path goes through 6 gates that s slow z2 z2 15 Systematic design 1 State purpose of circuit in words 2 Make truth tables 3 Identify true rows 4 Construct sum of products expression 5 Construct circuit 16 8 Systematic design of adder 1 State purpose of circuit in words Inputs carry in x y Outputs z if odd number of inputs are 1 carry out if at least two inputs are 1 2 Make truth tables Inputs cin x 0 0 0 0 0 1 0 1 1 0 1 0 1 1 1 1 y 0 1 0 1 0 1 0 1 Outputs z cout 0 0 1 0 1 0 0 1 1 0 0 1 0 1 1 1 17 Systematic design of adder 3 Identify true rows cin 0 0 0 0 1 1 1 1 x 0 0 1 1 0 0 1 1 y 0 1 0 1 0 1 0 1 z 0 1 1 0 1 0 0 1 cin 0 0 0 0 1 1 1 1 x 0 0 1 1 0 0 1 1 y 0 1 0 1 0 1 0 1 cout 0 0 0 1 0 1 1 1 4 Construct sum of products expression for each output z cin x y cin x y cin x y cin x y cout cin x y cin x y cin x y cin x y 18 9 Systematic design of adder 5 Construct circuit cin 0 0 0 0 1 1 1 1 x 0 0 1 1 0 0 1 1 y 0 1 0 1 0 1 0 1 z 0 1 1 0 1 0 0 1 z cin x y cin x y cin x y cin x y cin x y cin x y cin x y cin x y 19 Sum of products circuit cin 0 0 0 0 1 1 1 1 x 0 0 1 1 0 0 1 1 y 0 1 0 1 0 1 0 1 z 0 1 1 0 1 0 0 1 z cin x y cin x y cin x y cin x y cin x y One AND gate for each 1 output in table cin x y Each AND gate has as many inputs as truth table cin x y One OR gate cin x y Constant depth 2 or 3 counting NOTs 20 10 Finishing the adder cin 0 0 0 0 1 1 1 1 cin 0 0 0 0 1 1 1 1 x 0 0 1 1 0 0 1 1 x 0 0 1 1 0 0 1 1 y 0 1 0 1 0 1 0 1 y 0 1 0 1 0 1 0 1 z z 0 1 cout 1 0 cin 1 x 0 y 0 cin 1 x cout y 0 cin 0 x 0 y 1 cin 0 x 1 y 1 1 cin x y cin x y cin x y cin x y cin x y cin x y cin x y cin x y cin x y z cin x y cout cin x y cin x y 21 Duplicate terms duplicate gates cin 0 0 0 0 1 1 1 1 cin 0 0 0 0 1 1 1 1 x 0 0 1 1 0 0 1 1 x 0 0 1 1 0 0 1 1 y 0 1 0 1 0 1 0 1 y 0 1 0 1 0 1 0 1 z z 0 1 cout 1 0 cin 1 x 0 y 0 cin 1 x cout y 0 cin 0 x 0 y 1 cin …
View Full Document
Unlocking...