COS126: General Computer Sci ence • http://ww w.cs.Princeton.EDU/~cos126Lecture 10: Combinational CircuitsGeorge Boole (1815 – 1864)Claude Shannon (1916 – 2001)2Computer ArchitecturePrevious two lectures.! TOY machine.Next two lectures.! Digital circuits.Culminating lecture.! Putting it all together and building a TOY machine.3Digital CircuitsWhat is a digital system?! Digital: signals are 0 or 1.! Analog: signals vary continuously.Why digital systems?! Accuracy and reliability.! Staggeringly fast and cheap.Basic abstractions.! On, off.! Switch that can turn something on or off.Digital circuits and you.! Computer microprocessors.! Antilock brakes.! Cell phones.4WiresWires.! Propagate logical values from place to place.! Signals "flow" from left to right.– A drawing convention, sometimes violated– Actually: flow from producer to consumer(s) of signal0 01 111Input Output5Logic GatesLogical gates.! Fundamental building blocks.0110NOT010AND100111000000011101111ORxx'xyxyxyx + y6Multiway AND GatesAND(x0, x1, x2, x3, x4, x5, x6, x7).! 1 if all inputs are 1.! 0 otherwise.7Multiway OR GatesOR(x0, x1, x2, x3, x4, x5, x6, x7).! 1 if at least one input is 1.! 0 otherwise.8Boolean AlgebraHistory.! Developed by Boole to solve mathematical logic problems (1847).! Shannon first applied to digital circuits (1937).Basics.! Boolean variable: value is 0 or 1.! Boolean function: function whose inputs and outputs are 0, 1.Relationship to circuits.! Boolean variables: signals.! Boolean functions: circuits.9Truth TableTruth table.! Systematic method to describe Boolean function.! One row for each possible input combination.! N inputs ! 2N rows.ANDAND(x, y)AND Truth Tableyx00001000111101010011100010Truth Table for Functions of 2 VariablesTruth table.! 16 Boolean functions of 2 variables.– every 4-bit value represents oneZEROTruth Table for All Boolean Functions of 2 Variablesy0 00 1 01 0 01 1 000100100x0011AND0001y0101XOR0110OR0111x0NORTruth Table for All Boolean Functions of 2 Variablesy0 10 1 01 0 01 1 0y'1010x'11001011EQ10011101NAND1110ONE1111x011Truth Table for Functions of 3 VariablesTruth table.! 16 Boolean functions of 2 variables.– every 4-bit value represents one! 256 Boolean functions of 3 variables.– every 8-bit value represents one! 2^(2^N) Boolean functions of N variables!ANDSome Functions of 3 Variablesz0 00 1 01 0 01 10y0x000000 11 01 1011110001OR01111111MAJ00010111ODD0110100112Universality of AND, OR, NOTAny Boolean function can be expressed using AND, OR, NOT.! "Universal."! XOR(x,y) = xy' + x'yExercise: {AND, NOT}, {OR, NOT}, {NAND}, {AND, XOR} are universal.x'Expressing XOR Using AND, OR, NOTy0 11 10 01 0x'y0100x'y + xy'0110xy'0010y'1010XOR0110x0011MeaningNOT xx AND yx OR yNotationx'x yx + y13Sum-of-ProductsAny Boolean function can be expressed using AND, OR, NOT.! Sum-of-products is systematic procedure.– form AND term for each 1 in truth table of Boolean function– OR terms togetherx'yzExpressing MAJ Using Sum-of-Productszxyz' xyzxy'zMAJyx0001011101010101001100110000111100010000000001000000001000000001x'yz + xy'z + xyz' + xyz0001011114Translate Boolean Formula to Boolean CircuitUse sum-of-products form.! XOR(x, y) = xy' + x'y.15Translate Boolean Formula to Boolean CircuitUse sum-of-products form.! MAJ(x, y, z) = x'yz + xy'z + xyz' + xyz.16Simplification Using Boolean AlgebraMany possible circuits for each Boolean function.! Sum-of-products not necessarily optimal in:– number of gates (space)– depth of circuit (time)! MAJ(x, y, z) = x'yz + xy'z + xyz' + xyz = xy + yz + xz.size = 4, depth = 2size = 8, depth = 317Expressing a Boolean Function Using AND, OR, NOTIngredients.! AND gates.! OR gates.! NOT gates.! Wire.Instructions.! Step 1: represent input and output signals with Boolean variables.! Step 2: construct truth table to carry out computation.! Step 3: derive (simplified) Boolean expression using sum-of products.! Step 4: transform Boolean expression into circuit.18ODD Parity CircuitODD(x, y, z).! 1 if odd number of inputs are 1.! 0 otherwise.x'y'zExpressing ODD Using Sum-of-Productszxy'z' xyzx'yz'ODDyx0110100101010101001100110000111101000000001000000000100000000001x'y'z + x'yz' + xy'z' + xyz0110100119ODD Parity CircuitODD(x, y, z).! 1 if odd number of inputs are 1.! 0 otherwise.20Let's Make an Adder CircuitGoal: x + y = z for 4-bit integers.! We build 4-bit adder: 9 inputs, 4 outputs.! Same idea scales to 128-bit adder.! Key computer component.Step 1.! Represent input and output in binary.x1x2x3x0y1y2y3y0+z1z2z3z0100 0110 1+001 1011842 7753 9+606 6111x3x2x1x0y3y2y1y0z3z2z1z0+c00021Let's Make an Adder CircuitGoal: x + y = z for 4-bit integers.Step 2. (first attempt)! Build truth table.! Why is this a bad idea?– 128-bit adder: 2256+1 rows > # electrons in universe!4-Bit Adder Truth Tabley2y3000011.1000000.1x1x2x3x0y1y2y3y0+z1z2z3z0x0x1000000.1000000.1x2x3000000.1000000.1y0y1010101.1001100.1z2z3000011.1000000.1z0z1010101.1001100.128+1 = 512 rows!c0000000.1c022Let's Make an Adder CircuitGoal: x + y = z for 4-bit integers.Step 2. (do one bit at a time)! Build truth table for carry bit.! Build truth table for summand bit.Carry Bitcici+1yixi00010111010101010011001100001111Summand Bitciziyixi01101001010101010011001100001111x1x2x3x0y1y2y3y0+z1z2z3z0c1c2c3c0 = 023Let's Make an Adder CircuitGoal: x + y = z for 4-bit integers.Step 3.! Derive (simplified) Boolean expression.Carry Bitcici+1yixi00010111010101010011001100001111MAJ00010111Summand Bitciziyixi01101001010101010011001100001111ODD01101001x1x2x3x0y1y2y3y0+z1z2z3z0c1c2c3c0 = 024Let's Make an Adder CircuitGoal: x + y = z for 4-bit integers.Step 4.! Transform Boolean expression into circuit.! Chain together 1-bit adders.25Let's Make an Adder CircuitGoal: x + y = z for 4-bit integers.Step 4.! Transform Boolean expression into circuit.! Chain together 1-bit adders.26SubtractorSubtractor circuit: z = x - y.! One approach: design like adder circuit.! Better idea: reuse adder circuit.– 2's complement: to negate an integer, flip bits, then add 1x2x1x0y3y2y1y0x3z3z2z1z0yxx - y4-Bit Subtractor Interface 4-Bit Subtractor Implementationcarry1+-27Arithmetic Logic Unit: InterfaceALU Interface.! Add, subtract, bitwise and, bitwise xor, shift left, shift right, copy.! Associate 3-bit integer with 5 primary ALU operations.– ALU performs operations in parallel– control wires select which result ALU outputsALUselect161616Input 1Input 2op 1+, - 0& 0^ 1<<, >> 100101ALUinput 2 0