CS231: Computer Architecture ILaxmikant KaleFall 2007Introduction to CS2311Review• There are 10 kinds of people in theworld– Those who understand binaryand those who don’t1615141312111098765432100010000032274512068257Introduction to CS2312Binary 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 CS2313Basic Gates• There are three basic kinds of logic gatesANDof two inputsOR of twoinputsNOT(complement)on one inputOperation:Logic gate:•Two Questions:•How can we implement such switches?•What can we build with Gates? And How?Introduction to CS2314Doing 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 CS2315Half AdderHalf adder: resultResultThis circuit is so common,that it has a name ansymbol as a gate byitself: Exclusive ORExclusive OROutput is 1 iffexactly one of the 2inputs is 1Introduction to CS2316XOR!"! # "!"! # "! # " = !"’ + !’"! # " = (! $ ¬") % (¬! $ ")Introduction 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 + 1 = 010 + 1 + 0 = 010 + 1 + 1 = 101 + 0 + 0 = 011 + 0 + 1 = 101 + 1 + 0 = 101 + 1 + 1 = 11X YCinCoutS0 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 latercalculation, 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 outputsare generated in response to inputs.• The basic idea is feedback: we make a “loop” in the circuit, so thecircuit outputs are inputs as wellWhen S and R are 0, Qis “stable”: whatever itwas, it stays in thatstate. 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 specifiedlocation 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 thememory!– 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– There are many kinds of controllable switches• These switches can be used to put together “Logic Gates”• Logic Gates can be put together to make half adder, full adders andmulti-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 storedata• 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 conceptsunderlying digital computer design:Deep down inside, computers work with just 1s and 0s.• Computers use voltages to represent information. In modern CPUs thevoltage 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 lecture• Having seen an overview last week,– We will now start a more thorough study• Number systems– Review of binary number representation– How to convert between binary and decimal representations– Octal and Hex representations• Basic boolean operations– AND, OR and NOT– The idea of “Truth Table”– Boolean functions and expressions– Truth table for Boolean expressionsIntroduction to CS23118Decimal review• Numbers consist of a bunch of digits, each with a weight:• The
View Full Document
Unlocking...