University of Illinois at Urbana Champaign Dept of Electrical and Computer Engineering ECE 120 Introduction to Computing The Ripple Carry Adder Build an Addition Device Based on Human Addition Weeks ago we talked about a hardware device to perform addition Now you re ready to design it Let s start by reviewing the human approach Basing a design on the human approach is usually the easiest way and often leads to a good design too Humans are pretty smart ECE 120 Introduction to Computing 2016 Steven S Lumetta All rights reserved slide 1 ECE 120 Introduction to Computing 2016 Steven S Lumetta All rights reserved slide 2 Example Addition of Unsigned Bit Patterns Name Signals Bits for Our Hardware Design Let s do an example with 5 bit unsigned 1 1 01110 14 00100 4 0 18 01 1 0 Good we got the right answer Let s do an example with 5 bit unsigned 000 1 1 01110 00100 0 01 carry C A B sum S There is no blank bit 0 1 Good we got the right answer For least significant bit C 0 Each 1 bit sum needs a C input For other bits C comes from next bit to right ECE 120 Introduction to Computing 2016 Steven S Lumetta All rights reserved slide 3 ECE 120 Introduction to Computing 2016 Steven S Lumetta All rights reserved slide 4 3 4 2018 1 Inputs and Outputs for a Full One Bit Adder Connecting the Full Adder to the N Bit Problem Think about adding a single bit a column A full adder has three inputs A one bit of the number A B one bit of the number B Cin a carry input from the next least significant bit or 0 for bit 0 And a full adder produces two outputs Cout a carry output for the next most significant bit S one bit of the sum S A one bit adder is called a full adder for historical reasons A half adder adds two bits instead of three Consider bit M of the addition bit 0 is on the right bit 1 to the left of bit 0 and so forth We need to add AM BM and CM to produce bit SM of the sum and bit CM 1 the carry into bit M 1 of the addition ECE 120 Introduction to Computing 2016 Steven S Lumetta All rights reserved slide 5 ECE 120 Introduction to Computing 2016 Steven S Lumetta All rights reserved slide 6 Write a Truth Table for Full Adder Outputs Fill a K map for Cout from the Truth Table Let s calculate the outputs for a full adder You may remember solving this truth table a few weeks ago But let s do it again A B Cin Cout S 0 0 0 1 0 0 1 0 1 0 0 1 1 1 0 0 1 0 0 1 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 1 0 1 0 1 Now fill in the truth table for Cout Cout A 0 1 00 0 0 BCin 11 01 0 1 1 1 10 0 1 A B Cin Cout S 0 0 0 1 0 0 1 0 1 0 0 1 1 1 0 0 1 0 0 1 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 1 0 1 0 1 ECE 120 Introduction to Computing 2016 Steven S Lumetta All rights reserved slide 7 ECE 120 Introduction to Computing 2016 Steven S Lumetta All rights reserved slide 8 3 4 2018 2 Solve the K map to Find Cout And find the loops So we can write Cout AB ACin BCin called a majority function by the way Cout 00 A 0 0 1 0 BCin 11 01 0 1 1 1 10 0 1 The Sum is Best Written as an XOR What about S We can of course use another K map But a K map doesn t give us the best answer in this case a rare case S is 1 when an odd number of inputs are 1 So S A B C A B Cin Cout S 0 0 0 1 0 0 1 0 1 0 0 1 1 1 0 0 1 0 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 1 1 ECE 120 Introduction to Computing 2016 Steven S Lumetta All rights reserved slide 9 ECE 120 Introduction to Computing 2016 Steven S Lumetta All rights reserved slide 10 XOR Shows up as a Checkerboard Pattern Circuit for a Full Adder Using AND OR and XOR We can draw our full adder using AND OR and XOR Here s the K map for S Notice the checkerboard pattern of the XOR S A 00 0 0 1 1 BCin 11 01 1 0 0 1 10 1 0 A B Cin Cout S 0 0 0 1 0 0 1 0 1 0 0 1 1 1 0 0 1 0 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 1 1 ECE 120 Introduction to Computing 2016 Steven S Lumetta All rights reserved slide 11 ECE 120 Introduction to Computing 2016 Steven S Lumetta All rights reserved slide 12 3 4 2018 3 CMOS Implementation Using NAND and XOR How Do We Add N Bits In CMOS we replace AND OR with NAND NAND The XOR remains as an XOR gate Use a full adder for each of the N columns Feed a 0 into Cin for the least significant bit Cout of the most significant bit is the adder s carry out For the other carry signals connect Cout of each bit to Cin of the next most significant bit Divide the bits of A and B amongst the full adders Collect the bits of S from the full adders ECE 120 Introduction to Computing 2016 Steven S Lumetta All rights reserved slide 13 ECE 120 Introduction to Computing 2016 Steven S Lumetta All rights reserved slide 14 Use N One Bit Adders to Build an N Bit Adder Symbol for an N Bit Adder The figure below illustrates construction of an N bit adder from N full adders This approach is called a ripple carry adder because the carry ripples slowly from low to high We also call it a bit sliced adder We draw an N bit adder as shown here Note the shape Note also the crosshatch and bit width N for multi bit signals ECE 120 Introduction to Computing 2016 Steven S Lumetta All rights reserved slide 15 ECE 120 Introduction to Computing 2016 Steven S Lumetta All rights reserved slide 16 3 4 2018 4 To Build a Bigger Adder Just Connect Cout to Cin We can build bigger adders by connecting adders together physically as shown below or virtually by saving the carry out bit and using it as the carry in to the next adder ECE 120 Introduction …