Half Adders, Full Adders, Ripple Carry Adders

Introduction

At the very least, most people expect computers to do some kind of arithmetic computation, and thus, most people expect computers to add.

We're going to construct combinational logic circuits that perform binary addition. The first question you should ask when adding binary numbers, given all the time we've spent talking about representation is "what representation are we talking about"?

Clearly the choice of representation is going to affect how we perform the addition. Certain representations allow us to add in the way we add base ten numbers. So, initially, we assume UB representation.

First, let's consider adding two 3-bit UB numbers.

     1  1  0
  +  0  1  1 
  -----------

Most of add numbers right to left. We start at the rightmost column (the least signifcant bit) and work our way to the left.

     1  1  0
  +  0  1  1 
  -----------
           1

As we add, we may need to carry. We add 0 to 1. What should we carry? You might answer "Nothing". Technically, you don't have to carry anything. However, hardware isn't so simple. In general, once you decide there is an output (such as carry), you need to generate that output all the time. Thus, we need to find a reasonable carry, even when there's "no need" to carry.

In this case, a reasonable carry is to carry a 0, into the next column, and then add that column.

        0
     1  1  0
  +  0  1  1 
  -----------
        0  1

This time, when we add the middle column, we get 0 + 1 + 1 which sums to 0, with a carry of 1.

     1  0
     1  1  0
  +  0  1  1 
  -----------
 (1) 0  0  1

The final (leftmost) column adds 1 + 1 + 0, which sums to 0, and also generates a carry. We put the carry in parentheses on the left.

Typically, when we perform an addition of two k-bit numbers, we expect the answer to be k-bits. If the numbers are represented in UB, the result can be k+1 bits. To handle that case, we have a carry bit (the one written in parentheses above).

Building Blocks: Half Adders

As you look at how numbers are added, it seems to be added column by column. While we might create an addition circuit which adds two 3-bit values at once, it might not allow us to generalize to adding two k-bit values.

It makes some sense to design a circuit that adds in "columns". To begin, let's consider adding the rightmost column. We're adding two bits. So, the adder we want to create should have two inputs bits. It generates a sum bit for that column, plus a carry. So there should be two bits of output.

This device is called a half-adder. I have no idea why, except that it can't really be used to (easily) build k-bit adders.

Data inputs: 2 (call them x and y)
Outputs: 2 (call them s, for sum, and c, for carry)

Here's a truth table for half adders.

Row	x	y	c	s
0	0	0	0	0
1	0	1	0	1
2	1	0	0	1
3	1	1	1	0

Let's see what's happening. Look at row 3. We add x + y = 1 + 1. This has a sum of 0, and a carry of 1.

Writing a Boolean Expression

The first step to converting a truth table to a circuit is to write a Boolean expression.

We use the same technique as before. Identify rows with 1, and create a minterm. This doesn't always produce a minimal expression, but at least it produces an expression without too much work.

   c = xy
   s = \xy + x\y
     = x XOR y

Again, we use multiplication to denote AND₂ and addition to denote OR₂.

Drawing the Circuit

The next step is to draw the circuit. First, we draw it as a black box.

Then, we add the detail of the circuits.

In this circuit above, you see an AND₂ gate and an XOR₂ gate.

Building Blocks: Full Adders

The problem with a half-adder is that there it doesn't handle carries. When you look at the left column of the addition

     1  0
     1  1  0
  +  0  1  1 
  -----------
 (1) 0  0  1

you see that you add three bits. Half adders only add two bits.

We need a circuit that can add three bits. That circuit is called a full adder.

Here are the characteristics of a full adder.

Data inputs: 3 (call them x, y, and c_in, for carry in)
Outputs: 2 (call them s, for sum, and c_out, for carry out)

Notice we now need to make a distinction whether the carry is an input (c_in) or an output (c_out). Carry in's in column i are due to carry outs from column i - 1 (assuming we number columns right to left, starting at column 0 at the least significant bit).

Here's a truth table for full adders.

Row	x	y	c_in	c_out	s
0	0	0	0	0	0
1	0	0	1	0	1
2	0	1	0	0	1
3	0	1	1	1	0
4	1	0	0	0	1
5	1	0	1	1	0
6	1	1	0	1	0
7	1	1	1	1	1

Exercise

As an exercise, write out the Boolean expressions for c_out and s. Draw the circuit, too.

Ripple Carry Adders

Once you have half adders and full adders, you can now construct ripple carry adders.

A ripple carry adder allows you to add two k-bit numbers. We use the half adders and full adders and add them a column at a time.

Let's put the adder together one step at a time.

Before Adding

Adding Column 0

We add x₀ to y₀, to produce z₀.

Adding Column 1

In column 1, We add x₁ to y₁ and c₁ and, to produce z₁, and c₂, where c_i is the carry-in for column i and c_{i + 1} is the carry-out of column i.

Adding Column 2

In column 2, We add x₂ to y₂ and c₂ and, to produce z₂, and c₃.

Using Only Full Adders

We don't really need to use the half adder. We could replace the half adder with a full adder, with a hardwired 0 for the carry in.

Delay

We know that combinational logic circuits can't compute the outputs instantaneously. There is some delay between the time the inputs are sent to the circuit, and the time the output is computed.

Let's say the delay is T units of time.

Suppose you want to implement an n-bit ripple carry adder. How much total delay is there?

Since an n-bit ripple carry adder consists of n adders, there will be a delay of nT. This is O(n) delay.

Why is there this much delay? After all, aren't the adders working in parallel?

While the adders are working in parallel, the carrys must "ripple" their way from the least significant bit and work their way to the most significant bit. It takes T units for the carry out of the rightmost column to make it as input to the adder in the next to rightmost column.

Thus, the carries slow down the circuit, making the addition linear with the number of bits in the adder.

This is not a big problem, usually, because hardware adders are fixed in size. They add, say, 32 bits at a time. There's no way to make an adder add an arbitrary number of bits. It can be done in software, not in hardware. In effect, this is what makes hardware "hard". It's not flexible to change.

Even though there are a fixed number of bits to add in an adder, there are ways to make the adder add more quickly (at least, by a constant).

Carry lookahead adders add much faster than ripple carry adders. They do so by making some observations about carries. We will look at this at a later set of notes.

Which Representation?

When we designed the adder, we were making some assumption about the representation of x_3-0 and y_3-0. We assumed they were UB.

Or we could also assume the representation is 2C. This is the advantage of using 2C for signed representation. The same hardware that adds UB can be used to add 2C (although the conditions for overflow are not the same for UB as 2C).

Summary

Here are some summarizing facts about adders.

Half adders add two bits.
Full adders add three bits.
Ripple carry adders use half adders and full adders to add two n-bit numbers represented in either UB or 2C.
Ripple carry adders have O(n) delay. Even though the adders can add x_i and y_i in parallel (for all i between 0 and n-1, inclusive), the delay is due to the carry "rippling" from the rightmost adder to the leftmost.
There are adders that can add faster than O(n), by using more hardware (see Carry Lookahead Adders).

Web Accessibility