Lecture 9 EGR 270 Fundamentals of Computer Engineering Reading Assignment Chapter 4 in Logic and Computer Design Fundamentals 4th Edition by Mano Arithmetic Functions Arithmetic functions are important parts of many digital systems This chapter will look at components such as Adders Subtractors Multipliers Incrementers Decrementers As with most of the text a constant theme is the development of iterative circuits corresponding to reusable functional blocks Complements were introduced in Chapter 1 In this chapter we will see that complements are often involved in arithmetic operations 1 Lecture 9 EGR 270 Fundamentals of Computer Engineering Binary Adders We will develop binary adders by means of a hierarchical iterative design For example the design of 1 bit adders can be extended to 4 bit adders 4 bit adder designs can be extended to 16 bit adders etc Additionally we will look at improvements to designs that will significantly increase an adder s speed Half adder adds 2 bits with no carry in and one carry out Design a half adder 2 Lecture 9 EGR 270 Fundamentals of Computer Engineering Example Full adder adds 2 bits with one carry in and one carry out Develop the basic design for the full adder Illustrate the SOP implementation Illustrate the XOR implementation Show how a full adder can be constructed using two half adders 3 Lecture 9 EGR 270 Fundamentals of Computer Engineering 4 Bit Adder Illustrate how a 4 bit adder can be constructed using 4 full adders 16 Bit Adder Illustrate how four 4 bit adders can be used to construct a 16 bit adder 4 Lecture 9 EGR 270 Fundamentals of Computer Engineering Delay problems in binary adders One problem with constructing an N bit adder from N full adders is that the delay becomes excessive Each full adder has to wait for the carry out from the previous bit before performing its addition We will see shortly that the longest delay path is 2N 2 gate delays for an N bit adder This corresponds to a delay of 34 gates for a 32 bit adder We need a better solution Adding a look ahead carry or fast carry circuit to adders will greatly improve their performance Partial Full Adder Illustrate how the full adder can be redrawn as a partial full adder and a ripple carry circuit This is also illustrated for a 4 bit adder on the following page 5 Lecture 9 EGR 270 Fundamentals of Computer Engineering Partial Full Adder with Ripple Carry Circuit Discuss the delay problems in the circuit below We will replace the Ripple Carry Circuit with a Carry Lookahead circuit to improve this delay problem 6 Lecture 9 EGR 270 Fundamentals of Computer Engineering Propagate and Generate Terms An output carry can be generated in two ways 1 Generate terms If Ai Bi 1 then Cout 1 Define Gi AiBi 2 Propagate terms If Ai 1 and Bi 0 or if Ai 0 and Bi 1 then Cout 1 if Cin 1 or Cout Cin or the carry is propagated Define Pi Ai Bi So C1 G0 C0P0 discuss Also develop expressions for C2 C3 and C4 7 Lecture 9 EGR 270 Fundamentals of Computer Engineering Carry Lookahead Circuit Ripple Carry is replaced by the Carry Lookahead circuit Note that C4 is replaced by G0 3 and P0 3 for expandability The number of gate delays is significantly reduced as seen in the following examples Adder Size gate delays Ripple Carry Gate delays Carry Lookahead 4 bit 10 6 16 bit 34 10 64 bit 130 14 8 Lecture 9 EGR 270 Fundamentals of Computer Engineering Subtraction using r s complement A complement can be used to represent a negative value It is difficult for a computer to subtract but relatively simple to add and to find complements Therefore it is common to add a complement rather than to subtract M N M r s complement of N if C 1 drop C and result 0 if C 0 drop C and result 0 and is in r s comp form result carry bit C Note add leading 0 s to original M or N so that they have the same number of digits Examples 857 392 100100 162 638 110111 1101011 1001 9 Lecture 9 EGR 270 Fundamentals of Computer Engineering Subtraction using r 1 s complement M N M r 1 s complement of N result carry bit C if C 1 add C and result 0 if C 0 add or drop C and result 0 and is in r 1 s comp form Note add leading 0 s to original M or N so that they have the same number of digits Examples 2495 2481 1011011 10011 672 6903 111000 1110111 Question What is the disadvantage of using 1 s complement addition instead of 2 s 10 complement addition to perform subtraction Lecture 9 EGR 270 Fundamentals of Computer Engineering Subtraction using 2 s complement with signed numbers Signed numbers are represented as follows The MSB is the sign bit If the MSB 0 the number is positive If the MSB 1 the number is negative and stored in 2 s complement form Example Represent each number below using 8 bits where the MSB is the sign bit A 12 B 12 C 32 D 32 Example Perform various subtractions and additions using pairs of the numbers in the example above and verify that the results are correct A 12 32 B 32 12 C 12 32 D 32 12 11 12 Lecture 9 EGR 270 Fundamentals of Computer Engineering Adder Subtractor Circuit We have seen that subtraction can be performed using 2 s complement addition The adder subtractor circuit shown below can perform either addition or subtraction using 2 s complement addition as follows Addition S 0 If S 0 then X3 B3 so the adder circuit simply adds A and B with C0 S 0 input carry 0 Subtraction S 1 If S 1 then X3 B3 so the adder circuit simply adds A and B with C0 S 1 input carry 1 Since B is the 1 s complement of B adding the 1 s complement 1 input carry is equivalent to adding the 2 s complement of B or subtracting B from A X3 X2 X1 X0 Lecture 9 EGR 270 Fundamentals of Computer Engineering Adder Subtractor Circuit 13 Trace through the circuit below to show that the adder subtractor circuit works correctly for the following example using 4 bit signed binary numbers so the range of allowable values is 7 to 8 Example 1 7 3 4 Lecture 9 EGR 270 Fundamentals of Computer Engineering Adder Subtractor Circuit 14 Trace through the circuit below to show that the adder subtractor circuit works correctly for the following example using 4 bit signed binary numbers so the range of allowable values is 7 to 8 Example 2 6 1 5 Lecture 9 EGR 270 Fundamentals of Computer Engineering Other Arithmetic Functions 15 Contraction Using the result of an existing function or circuit to create a related function or circuit The text illustrates how the following circuits can be designed using contraction based on existing designs for adders …