yeolyi.comSeongyeol's CS

Ripple-Carry Adder

A full adder is a circuit that adds three bits: two bits plus the carry coming up from the place below. But a single full adder can only do 1-bit addition. So how do we add numbers with many places, like 4 or 8 bits?

Multi-bit addition

Adding works the same way no matter how many places there are, so we can simply connect several full adders in a row. Give each place its own full adder, and wire the Carry-out of one place to the Carry-in of the next.

With 10 full adders, you can add numbers over 1,000 (2 multiplied by itself 10 times is 1,024), and with 30, numbers over a billion. The example below calculates 1112 + 12 = 10002.

  1. Change B0 to 0. It becomes 0111 + 0000, so the carry disappears, and the result C3~C0 changes one place at a time from the bottom up to 0111.
  2. Change B0 back to 1, and A3 to 1 as well. It becomes 1111 + 0001, and the carry that overflows from the top place comes out at C4.

This design is called a ripple-carry adder, because the carry spreads to each next place in turn, like a ripple.

Wrapping up

Multiplication can be built by repeating addition. What about subtraction, then? Subtracting can produce a negative number, but bits have no place to write a minus sign. In the next post, let’s start with how to represent negative numbers in bits.

Challenge

A 4-bit ripple-carry adder calculates A + B (A and B are 0~15). How many (A, B) pairs make the Cout of all four places 1? Count A=3, B=5 and A=5, B=3 as different pairs. Answer with a number.