### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Computer Architecture CPSC 5155U

GPA 3.91

### View Full Document

## 55

## 0

## Popular in Course

## Popular in ComputerScienence

This 21 page Class Notes was uploaded by Earlene Cremin III on Sunday October 11, 2015. The Class Notes belongs to CPSC 5155U at Columbus State University taught by Edward Bosworth in Fall. Since its upload, it has received 55 views. For similar materials see /class/221204/cpsc-5155u-columbus-state-university in ComputerScienence at Columbus State University.

## Similar to CPSC 5155U at

## Reviews for Computer Architecture

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/11/15

Boolean Algebra amp Digital Logic Boolean algebra was developed by the Englishman George Boole who published the basic principles in the 1854 treatise An Investigation of the Laws of Thought on Which to Found the Mathematical Theories of Logic and Probabilities The applicability to computing machines was discovered by three Americans Claude Shannon Symbolic Analysis of Relay and Switching Circuits 1938 George Stibitz An employee of Bell Labs he developed a binary adder using mechanical relays in 1937 the model K 1 adder because he built it at home on his kitchen table John Atanasoff He was probably the rst to use purely electronic relays vacuum tubes to build a binary adder Boolean algebra is a two valued algebra based on the constant values denoted as either FALSE TRUE 0 1 The use of this algebra for computation is based on the fact that binary arithmetic is based on two values always called 0 and 1 Basic Boolean Operators Boolean algebra is de ned in terms oftwo constants de ned above which we call 0 and Other courses will call these values and T Boolean algebra is de ned in terms ofthree basic operators to which we shall add auseful fourth operator The three operators are NOT AND OR called a logic gate We present the gates along with the de nition NOT an r at below The circle at the right end ofthe triangle is important A Algebrajcally this function is denoted x x or x X The evaluation ofthe function is simple 6 1 andi 0 Basic Boolean Operators Part 2 Logic OR This is a function of two Boolean variables We denote the logical OR of two Boolean variables X and Y by X Y Some logic books will use X v Y The evaluation of the logical OR function is shown by a truth table X Y XY O O O O l l l O l l l l Basic Boolean Operators Part 3 Logic AND This is a function of two Boolean variables We denote the logical AND of two Boolean variables X and Y by X 0 Y Some logic books will use X Y The evaluation of the logical AND function is shown by a truth table X Y XoY O O O O l O l O O l l l Another Boolean Operator While not a basic Boolean operator the exclusive OR is very handy Logic XOR This is a function of two Boolean variables We denote the logical XOR of two Boolean variables X and Y by X 6 Y Most logic books seem to ignore this function The evaluation of the logical XOR function is shown by a truth table X Y XGDY O O O O l l l O l l l O From this last table we see immediately ithat X OXandX l X Truth Tables The fact that any Boolean variable can assume only one of two possibly values can be shown by induction to imply the following For N gt O N Boolean variables can take only 2N different combinations of values For small values of N we can use this to specify a function using a truth table with 2N rows plus a header row to label the variables and the function N 2 4 8 16 32 6 64 Four variable truth tables have 17 rows total This is just manageable Five variable truth tables have 33 rows total This is excessive N variable truth tables for N gt 5 are almost useless Sample Truth Table cu F1A B C l al Il Al IOQQQgt Ht OOl l OO gt Ogt Ogt Ol O HOOHOHl O This truth table for 3 variables has 23 8 rows plus a label row This truth table forms a complete de nition of the function We shall later give it another name but can base all our discussions on this table Another Sample Truth Table A B C F2A B C o o o o o o 1 o o 1 o o o 1 1 1 1 o o o 1 o 1 1 1 1 o 1 1 1 1 1 Two Truth Tables in One A B C F1A B C F2A B C 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 1 0 1 1 1 0 0 1 1 1 1 1 1 Truth tables are often used to show pairs of functions such as these two which will later be shown to be related This is easier than two complete tables Truth tables rarely show more than two functions just because large truth tables are messy and hard to read Labeling Rows in a Truth Table The row numbers are just labels They are not really a part of the truth table but aid in our discussions and conversions to Boolean expressions The row numbers are the decimal equivalents of the variable values viewed as binary Row X Y z FX Y Z Number 0 O O O 1 1 O O 1 1 2 O 1 O O 3 O 1 1 1 4 1 O O 1 5 1 O 1 O 6 1 1 O 1 7 1 1 1 1 numbers The rst row is always row 0 0004O02O01 1O04O02101 2O04102O01 3 O04102101 4 104O02001 5 104002 101 6 104 102O01 7 104 102 101 The 2 and H Notations These can be viewed as shorthand notation for expressing truth tables 2 notation Give the row numbers in which the function has value 1 H notation Give the row numbers in which the function has value 0 Example The Exclusive OR XOR function Row Number X Y X 6 Y O O O O 1 O 1 1 2 1 O 1 3 1 1 O X YZ12 X YHO3 Exercise Convert FX Y Z Z O 2 4 6 to the H notation Answer The function has three variables so the truth table has 23 8 rows numbered 0 through 7 If rows 0 2 4 and 6 have ones then the rows containing zeroes must be 1 3 5 and 7 FX Y Z H l 3 5 7 Examples F1 and F2 Consider the two functions F1 and F2 which we shall explain later Row A B C F1A B C F2A B C 0 0 0 0 0 0 1 0 0 1 1 0 2 0 1 0 1 0 3 0 1 1 0 1 4 1 0 0 1 0 5 1 0 1 0 1 6 1 1 0 0 1 7 1 1 1 1 1 F1XYZZ1247H0356 F2XYZZ3567ll0124 Evaluation of Boolean Expressions The relative precedence of the operators is 1 NOT do this rst 2 AND 3 OR do this last As in the usual algebra parentheses take precedence AoB C0D often written as AB CD is read as AOB COD 2 O B C O E is read as B C 0 The latter is really messy AoBCoD1o01o1011 ABCD1o111111 ZoBCoEloOlolooo1o0000 AB10o1 ZoEl060o10 Question Where to Put the 0 s and 1 s We now ask how to ll a truth table by evaluating a Boolean expression Example FX Y Z XoYYozXovoz Step 1 There are three Boolean variables so the truth table will have 8 rows Let s evaluate this function for all eight possible values of X Y Z RowO XO Y0 ZO FXYZ000000001000000 Rowl XO YO Zl FXYZOOOOolOolol0000 Row2 XO Yl ZO FXYZOol100000000000 Row3 XO Yl Zl FXYZOollol00001Ol0l Row4 Xl YO ZO FXYZ100000101000000 Row5 Xl YO Zl FXYZ100Oollolol00ll Row6 Xl Yl ZO FXYZlol10010000l00l Row7 Xl Yl Zl FXYZlollol10001ll0l This function can be written as FX Y Z 23 5 6 7 where the 1 s are HO l 2 4 where the 0 s are Question Where to Put the 0 s and 1 s Part 2 By evaluating the function FX Y Z X 0 Y Y 0 Z X I Y 0 Z we have determined that it can be represented as FX Y Z 23 5 6 7 This is just a notation to remind us where to put the 1 s in the truth table The truth table itself is now generated easily pa 0 2 gtlt lt N F Y 56 OOOO OO l Oo HOl Ol Ol O O looo O l 2 3 4 5 6 7 The Basic Unusual Boolean Theorem Here are two sets of theorems in Boolean algebra For all X For all X For all X For all X 00X 10X OX lX Consider the following truth tables From this we derive the truth table proving the last two theorems 0 OK X OK X OK 1 What W X W X 0 O O O 1 1 1 O 1 1 1 1 X 0 X 1 X 0 O 1 l l l Chapter 7 Some Advanced Topics A Better Shift Unit The shift unit in the ASC is quite primitive it shifts only one place at a time Multiple shifts must take one clock pulse per shift so that it would take eight clock pulses to shift by 8 We now examine a shift unit that is more typical of modern computers The rst thing to note is that there are three different types of shifts arithmetic logical and circular Operations on the ASC shift a 16bit input into a 16bit output For simplicity we shall consider shift operations on a signed 8bit integer bit 7 is the sign bit with input 543210 l7 6 X7X6X5X4X3X2X1IXOI Input to Shift Operations Logical Shift Left Shift 5 4 3 2 1 0 0 l7 6 X6X5X4X3X2X1X0 I Arithmetic Shift LeftShift 76543210 X7X5X4X3X2X1IX0 0 Circular Shift LeftShift 76543210 X6X5X4X3X2X1X0X7l RightShift 76543210 X7X7X6X5X4X3X2X1I RightShift 76543210 X0X7X6X5X4X3X2X1I The observant student should note that there is little intrinsic difference between a left circular shift and a right circular shift For a 16bit input as in the ASC a left circular shift by K places is equivalent to a right circular shift by 16 7 K places The shift register used by many modern computers is called a barrel shifter We shall investigate two varieties of barrel shifters l a crossbar barrel shifter requiring N2 tristate buiTers for an N bit input and 2 a logarithmic barrel shifter requiring fewer gates but being a bit slower CPSC 5155 Version of 792010 Chapter 7 page 1 Same Advanced Tupics labeled wuh bu 1nd1ces o 1 z and 3 wuh bu 3 bemg the my bu for anLhmeuc shx s Lhe Lable below Smce the rotator s set up as a crossbar much u has 16 Lnrstate buffers Note that for each le shx mu 3 number ofbus are shx ed out othe MSB back mm the LSB This le rotationjust The ngm cxmular shx cxmulams them to the nght Tn m qur ab r that us used to select a set of four LnrsLaLe buffers used no affed the shut Tn Mu sthch woulu wdvk A full crossbar swuch for a 3M u rotator would requue 4096 Lnrstate buffers CPSC 5155 Versxon of792010 chapte page Z Same Advanced Tnpics shtfter The output oftth ts speetfted m the following table As opposedto the rotator thts shtfter lls the low order btts wtth zeroes for eaeh shttt Here ts the crossbar swtteh togte for atogteat left shttt Note that many ofthe mrstate quot its on eertath shtfts Note also that the shtft eouht ts the deetrhat shtft eouht as the decoderhas removed from the dAagram to save spaee on the drawthg shirt Chum 0 3 z 1 Agamv m m t a In thts th swttehes one each for le and nght shtfts tt hm umt CPSC 5155 Verstoh of 792010 chapter 7 page 3 Same Advanced Topics count Conslder a shl by 13 places As13 8 4 l thls shl could be accompllshed by three shle a shl by 1 then a shl by 4 and nally a shl by 8 The baslc unlt ofa logarlthmlc barrel XK shl er ls the shl bypass unlt Thls u 1t acer t lt a 5 6 l X1 Here the output 11 gets elther xl the same blt or xle a blt shllteol oyer Shirt 1 Bypass In orderto save some space wlth thls drawmg as used ln our dlagrarns othe shllter we represent lt as shown at nght Note that the unltwlll shl only when the control slgnal ls l otherwlse ltls apassthrough Thlswlllbecomemore obylous when we show the rst shlller whlch shle nghtby oneplace Shift Bypass Arithmetic Rig Shin with 2 Lu We have been conslolerlng foureblt lglu lt u l l that ls stlll manageable In the elghtrblt ecarnple the blts are numbered 7 through 0 wlth garithmic Barrel Shimr busses for the crossbar swltch aiamples but move w three levels one each for shl by l shl by z and shl by 4 Here ls the shl rnghtrbyrone stage Note thatblt7 the slglblt ls copled X X X X X X X Xquot s I l Is l l I Vl t39 l l Y5 Y4 Y3 312 Y Yn S E ls set to 0 output SB ls set l copylng the slgl blt lnto the slgl blt othe output CPSC 5155 Verslon of792010 chaple page 4 Same Advanced Tnpics eouht Then the control bus for the vanous stages are as follows ch Stage 0 Shut hght by 1 preserving the stgh bu c Stage 1 Shut hght by 2 preserving the stgh bu ca Stage 2 Shut hght by 4 preserving the stgh bu The eomp1ete dAagram is as follows X X X X X X Xquot 1 15 I I 12I T39 as Q W i 1 Y7 Y6 Y5 Y1 Y3 312 Y Ya In geheha1 the number ofstages for a1oganthmte barrel shtfteh ls og N1 sthee we 1sebubus 4 stages 12 gate delays 32ebubut 5 stages 15 gate delays CPSC 5155 Verstoh of792010 Chapter 7 page 5

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.