The Full Adder and Ripple Carry Adder

Binary Addition

The four ways to add two bits worked out by hand: 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, and 1 + 1 = 10, where the 1 carried into the next column is labeled Cout.

Adding two bits in binary works exactly like adding two digits in the base-10 number system — also called the decimal number system — that you already know. Start with the smallest cases: 0 + 0 = 0, 0 + 1 = 1, and 1 + 0 = 1.

The interesting one is 1 + 1, which equals 2. The only problem is that we need two bits to represent 2 in binary — so 1 + 1 = 10! If you look closely at our answer, the bit we started with actually turned into a 0, and we “carried” a 1 to the left by one position.

Just like in decimal, binary addition requires carrying bits. In fact, each time we add two input bits we actually get two output bits: the sum of our two input bits, and a carry into the next most significant bit.

The table at right illustrates the different results we could get from adding two bits. As expected, C_out is only 1 when both a and b are 1, because this is the only combination where adding the two bits would result in an answer that we cannot fit in just one bit.

A four-column table with headers a, b, Cout, and Sum. Its rows list every pair of input bits: 0 and 0 give Cout 0 and Sum 0; 0 and 1 give Cout 0 and Sum 1; 1 and 0 give Cout 0 and Sum 1; 1 and 1 give Cout 1 and Sum 0. — Outputs `C_out` and `Sum` for each input combination of `a` and `b`.

The Full Adder

Believe it or not, we are now just one step away from the makings of a full adder. If you think back to how addition is performed by hand, each time we exceed the decimal value of 1 we must carry a 1 to the next bit. We called this the C_out of our bit — but from the perspective of the bit it carries into, what should we call it?

With each bit having a C_out, it only makes sense that each bit should also have a C_in, because the C_out of one bit is by definition the C_in of the next bit. Each of a, b, and C_in are inputs to our full adder, and are summed together to produce both the Sum and the C_out that we then pass on to the next bit.

Since we now have three inputs to our full adder, we can update our truth table to now have 8 different input combinations. The updated truth table is below.

A full adder block: inputs a and b enter from the left and a carry-in Cin enters from the top; the box outputs a Sum on the right and a carry-out Cout on the bottom. — Full adder · 1-bit **The smallest circuit that can really add.**

Verilog HDL

module full_adder (
    input  wire a,
    input  wire b,
    input  wire cin,
    output wire sum,
    output wire cout
);

  assign sum  = a ^ b ^ cin;   // 3-input XOR
  assign cout = (a & b) | (a & cin) | (b & cin);

endmodule

module full_adder (
    input  wire a,
    input  wire b,
    input  wire cin,
    output wire sum,
    output wire cout
);

  assign sum  = a ^ b ^ cin;   // 3-input XOR
  assign cout = (a & b) | (a & cin) | (b & cin);

endmodule

sum = 0

cout = 0

The full-adder truth table with three input columns a, b, and Cin, two output columns Cout and Sum, and a comments column showing the arithmetic. All eight input combinations are listed; Cout is 1 whenever at least two inputs are 1, and Sum is 1 whenever an odd number of inputs are 1.

We can use the truth table to create what are called logic expressions for both of our outputs, Sum and C_out. A logic expression will always describe an output purely in terms of its inputs, combining them with the logic gates — AND, OR, NOT, and XOR — that we met last lesson. For example, if you look closely at the truth table, the output Sum is only ever 1 when an odd number of the input bits are 1. This is precisely the XOR functionality we learned last lesson! Therefore, we can write the logic expression for Sum as Sum = a ⊕ b ⊕ C_in and draw the circuit as follows.

An XOR gate with three inputs — a, b, and Cin — producing the output Sum. — The circuit for `Sum`: a three-input XOR of `a`, `b`, and `C_in`.

The Ripple Carry Adder

Naturally, the next step is adding numbers with multiple bits. The good news is that this isn't hard at all, so long as we remember to include the carry-out from the previous bit when we add the next one. With some careful thinking, you might reason that to add multiple bits, the carry-out of the previous bit has to become the carry-in of the next bit. And you'd be right!

To add multiple bits, we must chain multiple full adders together, connecting each bit's C_out to the next bit's C_in. This chain is often referred to as a ripple carry adder, and it is the backbone of our ALU design.

Remarkably, this same circuit can subtract with only a tiny tweak. Recall that in two's complement, negating a number means flipping all its bits and adding 1 — so a − b is just a + b + 1. To pull this off, we feed each bit of b through an XOR gate controlled by a single subtract signal: when it's 0 the bits pass through untouched (plain addition), and when it's 1 every bit of b is inverted. Wiring that same subtract signal into the very first C_in supplies the “+ 1”, and just like that our adder becomes an adder–subtractor.

See the code on GitHub Browse the Verilog behind the ripple carry adder

A vertical chain of full adders. The topmost adder takes a, b, and a carry-in Cin and produces Sum-0; its carry-out feeds down into the next adder producing Sum-1, and so on down to the last adder producing Sum-31 and the final carry-out Cout. — Swap between the ripple carry adder and the adder–subtractor.

The same chain reworked into an adder–subtractor: each bit of b now passes through an XOR gate driven by a shared Sub control line before entering its full adder, and Sub also feeds the first carry-in. — Swap between the ripple carry adder and the adder–subtractor.

A Word on Overflow

Because our adder is built from a fixed number of bits, some sums simply have no room to land. Adding two large numbers can produce a result too big for the available bits, and the extra information spills off the top. This is called overflow, and if we don't catch it, the answer we read back will be flat-out wrong.

The good news is that overflow is cheap to detect. For unsigned numbers it's simple: if the final C_out — the carry off the most significant bit — is 1, the sum didn't fit, and overflow has occurred. For signed (two's complement) numbers the tell-tale sign is different: overflow happens exactly when we add two numbers of the same sign and get a result of the opposite sign (two positives yielding a negative, or two negatives yielding a positive).

Hardware has an even slicker trick. It compares the carry into the most significant bit with the carry out of it: if those two carries differ, signed overflow has occurred. In other words, a single XOR gate on those two carry bits, ovf = C_in ⊕ C_out at the top bit, gives us an overflow flag essentially for free — one of several status flags a real ALU hands back alongside the result.

Check Yourself

Given the truth table below, what would be the logic expression for C_out?

Continue to the 32-bit ALU Slice