Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 275-1Binary Circuits and Computing•Remember:–Boolean logic and truth table evaluations–Transistors and the design of simple logic circuits •In this lecture:–The connection between boolean logic and circuits and computing–The design of simple logic circuits–Representing simple logical sentences in hardware–Building more complicated sentences in hardware5-2Logic and Logic Circuits•What is a circuit?–the complete path of an electric current, or a collection of electronic elements–we will consider transistors to be the basic building blocks of logic computer hardware.–Logic circuits are built from a series of transistors•What is a transistor?5-3Transistors–A transistor is an electronic device that has three ends: a source, a sink, and a gate–In this type of transistor, when the gate is:•ON, power flows from the source to the sink. •OFF, power does not flow to the sinkgatesourcesink5-4Transistors–The current technology used to build computer hardware (chips) is called CMOS. •In CMOS we also use another kind of transistor, distinguished by the little bubble•The bubble means that this transistor works in the opposite way (it's ON when the gate is OFF and OFF when the gate is ON). gatesourcesink5-5Building Circuits with Transistors0110?ABatteryA ZWhat logical operator does this circuit perform?5-6Building Circuits with TransistorsBatteryABZWhat does this circuit do?-- build a truth table!10110001A ? BBA5-7Building Circuits with TransistorsBatteryABZ110011100101X NAND YBALooks like a negated AND (NAND)… Attach a “NOT” circuit to the output of Z and we’d get AND5-8Building Circuits with TransistorsBatteryABZ010011100001A NOR BBA5-9Logic Gates•We can construct the main logic functions AND, OR, and NOT using transistors.–We will be using these gates in future designs, so we will give them shorthand symbols to avoid drawing all the transistors and connections each time we want to use (say) an AND gate...5-10Logic Gates: ANDABA  B010111000001A  BBA•A AND B•A  B5-11Logic Gates: OR•A OR B•A  B110111000101A  BBAABA  B5-12Logical Not•Used to invert a meaning•Inverts the “bit” of input.10011001AAA A5-13XOR- Exclusive Or•True when either A or B are true, but not both•Exclusive Or•This gate can be built from simpler gates – a circuit•(A  B)  (A  B)110011000101A XOR BBAAB1 11110000015-14XOR- Exclusive Or•Also drawn as:110011000101A XOR BBAABA XOR B5-15Truth table analysis0010(A  B)1010B1100A1101A  B110111100001(A  B)BA5-16Representing a Sentence as Gates•Alice and Bob are both here or Carol is not here(0  1)   1 = 0  0 = 0110(0  1)   0 = 0  1 = 1010(0  0)   1 = 0  0 = 0100(1  0)   0 = 0  1 = 10010011B(1  0)   1 = 0  0 = 011(1  1)   1 = 1  0 = 111(0  0)   0 = 0  1 = 100(1  1)   0 = 1  1 = 101(A  B)   CCABCA•A = Alice•B = Bob•C = Carol•(A AND B) OR NOT C5-17Building Sentences from Circuits (and back)•Look for the last operation- this is the “inner-most” operation in the sentence.ABC5-18Building Sentences from Circuits (and vise versa)•Look for the last operation- this is the “inner-most” operation in the sentence.ABC1. ( ) OR ( )2. (A AND ( ) ) OR ( )3. (A AND (NOT B)) OR ( )4. (A AND (NOT B)) OR (( ) AND C)5. (A AND (NOT B)) OR ((NOT B) AND C)5-19Adding it all up... 0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = 1 0•Single-bit addition•How would we represent this functionality as an expression in binary logic?•How would we physically build this functionality with logic gates?5-20Binary Addition via Logic Gates 0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = 1 0•Single-bit addition•How would we represent this functionality as an expression in binary logic?–Hint: Construct a truth table:0111100101Sum00Carry-Out0010BA5-21Binary Addition via Logic Gates•The sum seems to be an XOR of A, B•Carry is A  B–We often need to add more than just two bits – what about bit strings?ABC-outA  BA XOR BSum5-22Binary Addition via Logic Gates 0 0 0 1 1 0  carried bits 1 0 1 0 0 1  A+ 0 0 0 0 1 1  B ----------- 1 0 1 1 0 0  A + B•In this example of adding two bit-strings we see everything that needs to be done:–In each position we add •a bit from A•a bit from B•a bit we carried from the previous addition of bits5-23Binary Addition via Logic Gates01010101Carry-In11110111010110010110Sum0001Carry-Out00100010BA•Let’s look at a truth table:–Three inputs: A, B, and what we’ve carried from a previous addition–We need to calculate:•the sum part (what we write in the current position) •what we need to carry to the next position•With gates, we will wire the output of the previous bit carried out, to the next bit carried in•When do we carry-out?•When is there a sum?5-24Binary Addition via Logic Gates•Carry out when there’s at least two bits (two or three)•Sum when there’s one or three bits–Carry out = (A  B)  (A  C)  (B  C)–Sum = (A XOR B) XOR C01010101C(0 XOR 1) XOR 1 = 1 XOR 1 = 0(0)  (1)  (0) = 110(0 XOR 1) XOR 0 = 1 XOR 0 = 1(0)  (0)  (0) = 010(0 XOR 0) XOR 1 = 0 XOR 1 = 1(0)  (0)  (0) = 000(1 XOR 0) XOR 0 = 1 XOR 0 = 1(0)  (0)  (0) = 0010011B(1 XOR 0) XOR 1 = 1 XOR 1 = 0(0)  (0)  (1) = 11(1 XOR 1) XOR 1 = 0 XOR 1 = 1(1)  (1)  (1) = 11(0 XOR 0) XOR 0 = 0 XOR 0 = 0(0)  (0)  (0) = 00(1 XOR 1) XOR 0 = 0 XOR 0 = 0(1)  (0)  (0) = 11(A XOR B) XOR C(A  B)  (B  C)  (A  C)A5-25Building the circuit–Carry out = (A  B)  (A  C)  (B  C)–Sum = (A XOR B) XOR CABC-inSumC-outA  CA  BB  C(A  B)  (A  C)((A  B)  (A  C))  (B  C)A XOR B(A XOR B) XOR C5-26Building Memory from Circuits•Flip-flop style memorysetresetqq’100011•Using NOR gates, the circuit preserves the signal entered:–Send 1 on set and q = 1–Send 0 on reset and q = 0•The Flip-Flop gives you a (simplified) idea of how RAM is actually built5-27Building “computers”•Transistors allow us to build physical components that can compute. –Devices whose output vary based on their