CS231: Computer Architecture IReviewBinary addition example worked outBasic GatesDoing addition with gatesSlide 5Adding two bitsAdding three bitsFull adder circuitA 4-bit adderAn example of 4-bit additionNow that we can add, how about some memory?So, we have built a calculatorComponents of a basic computerSummaryNumber systemsRest of Today’s lectureDecimal reviewConverting binary to decimalConverting decimal to binaryWhy does this work?Base 16 is useful tooBinary and hexadecimal conversionsNumber Systems SummaryBoolean OperationsBoolean valuesFunctionsBasic Boolean operationsBoolean expressionsTruth tablesPrimitive logic gatesExpressions and circuitsBoolean operations summaryCS231: Computer Architecture ILaxmikant KaleFall 2002Introduction to CS2312Review•There are 10 kinds of people in the world–Those who understand binary and those who don’t0000 00001 1234567891011121314151625768120452732Introduction to CS2313Binary addition example worked out•Some terms are given here•Exercise: what are these numbers equivalent to in decimal?1 1 1 0 (Carries)1 0 1 1 (Augend)+ 1 1 1 0 (Addend)1 1 0 0 1 (Sum)The initial carryin is implicitly 0most significantbit (MSB)least significantbit (LSB)Introduction to CS2314Basic Gates •There are three basic kinds of logic gatesANDof two inputsOR of two inputsNOT(complement)on one inputOperation:Logic gate:•Two Questions:•How can we implement such switches?•What can we build with Gates? And How?Introduction to CS2315Doing addition with gates•Lets do simple stuff first:–Can we add two numbers each with just 1 bit?•Bit: binary digit–0+0 = 0, 0+1 = 1 , 1+0 = 1, and 1+1 = ???•2. But 2 is not a symbol.•10 (just as 5 + 5 is 10 in decimal)•Result is 0 with 1 carried over to the next bit..–Whats 1 and 0? High and low voltage respectively.ResultCarryHalf adderIntroduction to CS2316Half adder: resultResultThis circuit is so common, that it has a name an symbol as a gate by itself: Exclusive ORExclusive OROutput is 1 iff exactly one of the 2 inputs is 1Introduction to CS2317Adding two bits•A half adder is used to add two bits.•The result consists of two bits: a sum (the right bit) and a carry out (the left bit)•Here is the circuit and its block symbol0 + 0 = 00 + 1 = 11 + 0 = 11 + 1 = 10Introduction to CS2318Adding three bits•But what we really need to do is add three bits: the augend and addend, and the carry in from the right.1 1 1 01 0 1 1+ 1 1 1 01 1 0 0 10 + 0 + 0 = 000 + 0 + 0 = 010 + 1 + 0 = 010 + 1 + 1 = 101 + 0 + 0 = 011 + 0 + 1 = 101 + 1 + 0 = 101 + 1 + 1 = 11X Y CinCoutS0 0 0 0 00 0 1 0 10 1 0 0 10 1 1 1 01 0 0 0 11 0 1 1 01 1 0 1 01 1 1 1 1Introduction to CS2319Full adder circuit•Why are these things called half adders and full adders?•You can build a full adder by putting together two half adders.Introduction to CS23110A 4-bit adder•Four full adders together can make a 4-bit adder•There are nine total inputs to the 4-bit adder:–two 4-bit numbers, A3 A2 A1 A0 and B3 B2 B1 B0–an initial carry in, CI•The five outputs are:–a 4-bit sum, S3 S2 S1 S0–a carry out, COIntroduction to CS23111An example of 4-bit addition•Let’s put our initial example into this circuit: A=1011, B=1110•Step 1: Fill in all the inputs, including CI=0•Step 2: The circuit produces C1 and S0 (1 + 0 + 0 = 01)•Step 3: Use C1 to find C2 and S1 (1 + 1 + 0 = 10)•Step 4: Use C2 to compute C3 and S2 (0 + 1 + 1 = 10)•Step 5: Use C3 to compute CO and S3 (1 + 1 + 1 = 11)•The final answer is 110011 1 1 0 1 1 0 101 1 0 0 1011Introduction to CS23112Now that we can add, how about some memory?•We want to save results computed before, and recall them in a later calculation, for example•Gates help us build memory•How can a circuit “remember” anything on its own?–After all, the values on the wires are always changing, as outputs are generated in response to inputs.•The basic idea is feedback: we make a “loop” in the circuit, so the circuit outputs are inputs as wellWhen S and R are 0, Q is “stable”: whatever it was, it stays in that state. Ergo : memory.When S is 1 and R is 0, Q becomes 1When R is 1 and S is 0, Q becomes 0Set and Reset inputs…Introduction to CS23113So, we have built a calculator•It is not a computer yet…–We have to type each step into a calculator–We’d like to “program” standard steps•E.g. Add 57 numbers sitting in memory in specific places–Also, support other operations (subtract..)•Two new ideas and components are needed for this:–Addressable memory–Stored Program•Addressable memory –Memory organized in a bunch of locations, such that contents of specified location can be brought back to the adder when needed.–Each memory location has an “address” (binary, of course)•Stored Program:–The instructions for which numbers to operate on, what operation to do (add/subtract, ..) and where to store the result–The instructions themselves can be represented in binary and stored in the memory!–The processor must have circuits to decode and “interpret” these instructionsIntroduction to CS23114Components of a basic computerMemoryALU(Arithmetic/Logic Unit:Basic operationsDataProgramControl and DecodingIntroduction to CS23115Summary•Controllable Switches are easy to make•These switches can be used to put together “Logic Gates”•Logic Gates can be put together to make half adder, full adders and multi-bit adders–So we can see they can be used for other such circtuits as well•Logic Gates can be used to make circtuits that “remember” or store data•A Computer includes, at its heart :–An ALU (Arithmetic Logic Unit)–Instruction Decoding and associated circuits–Memory–Stored Program©2000-2002 Howard Huang16Number systems•To get started, we’ll discuss one of the fundamental concepts underlying digital computer design: Deep down inside, computers work with just 1s and 0s.•Computers use voltages to represent information. In modern CPUs the voltage is usually limited to 1.6-1.8V to minimize power consumption.•It’s convenient for us to translate these analogvoltages into the discrete, or digital, values 1 and 0.•But how can two lousy digits be useful for anything?–First, we’ll see how to represent numbers withjust 1s and 0s.–Then we’ll introduce special operationsfor computing with 1s and 0s, by treating them asthe logical values “true” and “false.”Volts1.8010Introduction to CS23117Rest of Today’s
View Full Document
Unlocking...