Numbers & Arithmetic !Hakim&Weatherspoon &&CS&3410,&Spring&2011&Computer&Science&&Cornell&University&&See:&P&H&Chapter&2.4&C&2.6,&3.2,&C.5&–&C.6&2&Announcements!Make&sure&you&are&• Registered&for&class&• Can&access&CMS&• Have&a&SecKon&you&can&go&to&• Have&a&project&partner&&SecKons&are&on&this&week&&HW&1&out&later&today&• Due&in&one&week,&start&early&• Work&alone&• Use&your&resources&• Class¬es,&book,&SecKons,&office&hours,&newsgroup,&CSUGLab&3&Announcements!Check&online&syllabus/schedule&&• Slides&and&Reading&for&lectures&• Office&Hours&• Homework&and&Programming&Assignments&• Prelims:&Thursday,&March&11&and&April&28th&• Schedule&is&subject&to&change&4&Goals for today!Review&• Circuit&design&(e.g.&voKng&machine)&• Number&representaKons&• Building&blocks&(en cod ers,&d ecod ers,&mu l Kp l exors)&Binary&OperaKons&• OneCbit&and&fourCbit&adders&• NegaKve&numbers&and&two’s&compliment&• AddiKon&(two’s&compliment)&• SubtracKon&(two’s&compliment)&&• Performance&5&Logic Minimization!• How&to&implement&a&desired&funcKon?&&&&&&&a& b& c& out&0" 0" 0" 0"0" 0" 1" 1"0" 1" 0" 0"0" 1" 1" 1"1" 0" 0" 0"1" 0" 1" 1"1" 1" 0" 0"1" 1" 1" 0"6&Logic Minimization!• How&to&implement&a&desired&funcKon?&&&&&&&a& b& c& out&0" 0" 0" 0"0" 0" 1" 1"0" 1" 0" 0"0" 1" 1" 1"1" 0" 0" 0"1" 0" 1" 1"1" 1" 0" 0"1" 1" 1" 0"sum&of&products:&• OR&of&all&minterms&where&out=1&corollary:&any&combinaKonal&circuit&can%be&implemented&in&two&levels&of&logic&(ignoring&inverters)&minterm&a&b&c&a&b&c&a&b&c&a&b&c&a&b&c&a&b&c&a&b&c&a&b&c&7&Karnaugh Maps!How&does&one&find&the&most&efficient&equaKon?&– Manipulate&algebraically&un Kl… ?&– Use&Karnaugh&maps&(opKmize&visually)&– Use&a&sofware&opKmizer&&For&large&circuits&– DecomposiKon&&&reuse&of&building&blocks&&8&Voting machine!• VoKng&Machine!&– opKcal&scan&(thanks&FL)&&&&• Assume:&&– vote&is&recorded&on&paper&&by&filling&a&circle&– fixed&number&of&choices&– don’t&worry&about&“invalids”&&Al Franken Bill Clinton Condi Rice Dick Cheney Eliot Spitzer Fred Upton Write-in9&Voting Machine Components!Ballots&The&3410&opKcal&scan&&vote&counter&reader&machine&– Input:&paper&with&at&exactly&one&mark&– Datapath:&process¤t&ballot&– Output:&a&number&the&supervisor&can&record&– Memory&&&control:&none&for&now&5&EssenKal&Components?&10&Input!• PhotoCsensiKve&transistor&• photons&replenish&gate&depleKon®ion&&• can&disKnguish&dark&and&light&spots&on&paper&• Use&array&of&N&sensors&for&voKng&machine&input&i0&i1&i2&i3&i5&i4&i6&Vdd&11&Output!• 7CSegment&LED&• photons&emioed&when&electrons&fall&into&holes&d7&d6&d5&d4&d3&d2&d1&d0&12&Block Diagram!detect&8&N&13&Encoders!• N&might&be&large&• RouKng&wires&is&expensive&• More&efficient&encoding?&1&2&3&4&5&6&7&0&encoder&N."."."."."."14&Number Representations!• Base&10&C&Decimal&• Just&as&easily&use&other&bases&– Base&2&C&Binary&– Base&8&C&Octal&– Base&16&C&Hexadecimal&&&&6&3&7&102&101&100&15&Counting!• CounKng&16&Base Conversion!• Base&conversion&via&repeKKve&division&– Divide&by&base,&write&remainder,&move&lef&with&quoKent&17&Base Conversion!• Base&conversion&via&repeKKve&division&– Divide&by&base,&write&remainder,&move&lef&with&quoKent&18&Base Conversion!• Base&conversion&via&repeKKve&division&– Divide&by&base,&write&remainder,&move&lef&with&quoKent&19&Hexadecimal, Binary, Octal Conversions!20&Encoder Implementation!• ImplementaKon&.&.&.&– assume&8&choices,&exactly&one&mark&detected&i0&i1&b0&1&i2&i3&2&3&4&b1&3Cbit&encoder&(8CtoC3)&b2&i4&5&i5&i6&i7&6&7&0&encoder&21&Ballot Reading!detect&enc&8 38&22&7-Segment LED Decoder!• 3&inputs&&• encode&0&–&7&in&binary&• 7&outputs&• one&for&each&LED&&7LED&decode&23&7 Segment LED Decoder Implementation!d0"d1"d2"d3"d4"d5"d6"b2"b1"b0"d6"d5"d4"d3"d2"d1"d0"0" 0" 0"0" 0" 1"0" 1" 0"0" 1" 1"1" 0" 0"1" 0" 1"1" 1" 0"1" 1" 1"24&7 Segment LED Decoder Implementation!d0"d1"d2"d3"d4"d5"d6"b2"b1"b0"d6"d5"d4"d3"d2"d1"d0"0" 0" 0"0" 0" 1"0" 1" 0"0" 1" 1"1" 0" 0"1" 0" 1"1" 1" 0"1" 1" 1"1" 1" 1" 0" 1" 1" 1"1" 0" 0" 0" 0" 0" 1"0" 1" 1" 1" 0" 1" 1"1" 1" 0" 1" 0" 1" 1"1" 0" 0" 1" 1" 0" 1"1" 1" 0" 1" 1" 1" 0"1" 1" 1" 1" 1" 1" 0"1" 0" 0" 0" 0" 1" 1"25&Ballot Reading and Display!Ballots&The&3410&opKcal&scan&&vote&counter&reader&machine&detect&enc&8 37&7LED&&decode&26&Building Blocks!binary&encoder&2N&N&binary&decoder&N&2N&&MulKplexor&N&M&N&N&N&N&."."."0&1&2&2MC1&27&Goals for today!Review&• Circuit&design&(e.g.&voKng&machine)&• Number&representaKons&• Building&blocks&(en cod ers,&d ecod ers,&mu l Kp l exors)&Binary&OperaKons&• OneCbit&and&fourCbit&adders&• NegaKve&numbers&and&two’s&compliment&• AddiKon&(two’s&compliment)&• SubtracKon&(two’s&compliment)&&• Performance&28&Binary Addition!• AddiKon&works&the&same&way®ardless&of&base&• Add&the&digits&in&each&posiKon&• Propagate&the&carry&&&&183&+&254&&&&&&001110&+&011100&&&&29&1-bit Adder!Half&Adder&• Adds&two&1Cbit&numbers&• Computes&1Cbit&result&and&1Cbit&carry&&ABRC&30&1-bit Adder with Carry!Full&Adder&• Adds&three&1Cbit&numbers&• Computes&1Cbit&result&and&1Cbit&carry&• Can&be&cascaded&ABRCout& Cin&31&4-bit Adder!4CBit&Full&Adder&• Adds&two&4Cbit&numbers&and&carry&in&• Computes&4Cbit&result&and&carry&out&• Can&be&cascaded&A[4]&B[4]&R[4]&Cout& Cin&32&4-bit Adder!A0&&&B0&R0&A1&&&B1&R1&A2&&&B2&R2&A3&&&B3&R3&Cout&Cin&33&4-bit Adder!• Adds&two&4Cbit&numbers,&along&with&carryCin&• Computes&4Cbit&result&and&carry&out&A0&&&B0&R0&A1&&&B1&R1&A2&&&B2&R2&A3&&&B3&R3&Cout&Cin&34&Arithmetic with Negative Numbers!• AddiKon&with&negaKves:&• pos&+&p os& &add &magnitu des,&result&posi Kve&• neg&+&neg&&add&magnitudes,&result&negaKve&• pos&+&neg&&subtract&small er&magnitude,&&& &&keep&sign&of&bigger&magnitude&35&First Attempt: Sign/Magnitude #Representation!• First&Aoempt:&Sign/Magnitude&RepresentaKon&• 1&bit&for&sign&(0=posiKve,&1=negaKve)&• NC1&bits&for&magnitude&36&Twoʼs Complement Representation!• Beoer:&Two’s&Complement&RepresentaKon&• Leading&1’s&for&negaKve&numbers&• To&negate&any&number:&– complement&all&the&bits&– then&add&1&37&Twoʼs Complement!• NonCnegaKves&•
View Full Document
Unlocking...