COMP 411 Computer Organization Arithmetic and Logic Circuits Don Porter Lecture 12 1 COMP 411 Computer Organization Topics Arithmetic Circuits adder subtractor Logic Circuits Arithmetic Logic Unit ALU putting it all together COMP 411 Computer Organization Review 2 s Complement N bits Range 2N 1 to 2N 1 1 22 23 21 20 2N 1 2N 2 sign bit binary point 8 bit 2 s complement example 11010110 128 64 16 4 2 42 Beauty of 2 s complement representation same binary addition procedure will work for adding both signed and unsigned numbers as long as the leftmost carry out is properly handled ignored Insert a binary point to represent fractions too 1101 0110 8 4 1 0 25 0 125 2 625 COMP 411 Computer Organization Binary Addition Example of binary addition by hand Adding two N bit numbers produces an N 1 bit result 1011 A 1101 B 0101 10010 Carries from previous column Let s design a circuit to do it Start by building a block that adds one column called a full adder FA Then cascade them to add two numbers of any size A B FA CO CI S 4 bit adder A3 B3 A2 B2 A1 B1 A0 B0 A B FA CO CI S A B FA CO CI S A B FA CO CI S A B FA CO CI S S4 S3 S2 S1 S0 COMP 411 Computer Organization Binary Addition Extend to arbitrary of bits n bits cascade n full adders An 1 Bn 1 A2 B2 A1 B1 A0 B0 A B SFA CO CI A B SFA CO CI A B SFA CO CI A B SFA CO CI Sn Sn 1 S2 S1 S0 Called Ripple Carry Adder carries ripple through from right to left longest chain of carries has length n how long does it take to add the numbers 0 and 1 how long does it take to add the numbers 1 and 1 COMP 411 Computer Organization Designing a Full Adder 1 bit adder Follow the step by step method 1 Start with a truth table 2 Write down eqns for the 1 outputs Co CiAB Ci AB CiAB CiAB S Ci AB CiAB Ci AB CiAB 3 Simplifying a bit seems hard but experienced designers are good at this art Co Ci A B S Ci A B AB Ci A B Ci A B Co S 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 1 1 0 1 0 0 0 1 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 AB COMP 411 Computer Organization Simplifying the Boolean for Adder Start with definitions of xor 2 and 3 term Intuitively Either only one is true or all three are true i e an odd number of 1 s Co CiAB Ci AB CiAB CiAB S Ci AB CiAB Ci AB CiAB S is just the identify of a 3 term xor 7 COMP 411 Computer Organization Simplifying the Boolean for Adder Definition of 2 term xor Commutative Distributive Identity 7 Distributive Def of xor 8 COMP 411 Computer Organization For Those Who Prefer Logic Diagrams A little tricky but only 5 gates bit A B Co Ci A B S Ci A B Carry Logic A B Co Ci S Sum Logic COMP 411 Computer Organization Subtraction A B A B Subtract B from A add 2 s complement of B to A In 2 s complement B B 1 bit wise complement B 0 B B 1 B Let s build an arithmetic unit that does both add and sub operation selected by control input B3 B2 B1 B0 Subtract But what about the 1 A3 A2 A1 A0 A B FA CO CI S A B FA CO CI S S4 S3 S0 S1 S0 A B FA CO CI S A B FA CO CI S COMP 411 Computer Organization Condition Codes One often wants 4 other bits of information from an arith unit C carry the most significant position produced a carry e g 1 1 Z zero result is 0 big NOR gate N negative result is 0 Sn 1 Carry from leftmost column V overflow indicates answer doesn t fit when both operands are ve but sum is ve both operands are ve but sum is ve another way to detect V An 1Bn 1N An 1Bn 1N carry into leftmost column is different from carry out of leftmost column V Con 1 Cin 1 COMP 411 Computer Organization Condition Codes Subtraction is useful also for comparing numbers To compare A and B First compute A B Then check the flags Z N C V Examples LTU less than for unsigned numbers A B is given by C LT less than for signed numbers A B is given by N V Others in table To compare A and B To compare A and B perform A B and use perform A B and use condition codes condition codes Signed comparison Signed comparison EQ Z EQ Z NE Z NE Z LT N V LT N V LE Z N V LE Z N V GE N V GE N V GT Z N V GT Z N V Unsigned comparison Unsigned comparison EQ Z EQ Z NE Z NE Z LTU C LTU C LEU C Z LEU C Z GEU C GEU C GTU C Z GTU C Z COMP 411 Computer Organization How long does addition take Latency TPD max propagation delay or latency of the entire adder C An 1 Bn 1 An 2 Bn 2 A2 B2 A1 B1 A0 B0 A B A B FA FA CO CO CI CI S S Sn 1 Sn 2 S2 S1 S0 A B FA CO CI S A B FA CO CI S A B FA CO CI S Worst case path carry propagation from LSB to MSB e g when adding 11 111 to 00 001 Total latency max delay in producing outputs is proportional to N TPD O N O N is read order N and tells us that the latency of our adder grows in proportion to the number of bits in the operands COMP 411 Computer Organization Can we add faster Yes there are many sophisticated designs that are faster Carry Lookahead Adders CLA Carry Skip Adders Carry Select Adders See textbook for details COMP 411 Computer Organization Adder Summary Adding is not only common but it is also tends to be one of the most time critical of operations As a result a wide range of adder architectures have been developed that allow a designer to tradeoff complexity in terms of the number of gates for performance Bigger Faster Smaller Slower Ripple Carry Carry Skip At this point we ll define a high level functional unit for an adder and specify the details of the implementation as necessary Carry Select A Carry Lookahead B A B Add S sub Add Sub S COMP 411 Computer Organization Shifting and Logical Operations COMP 411 Computer Organization Shifting Logic Shifting is useful for logic operations …
View Full Document