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).

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.

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

In this circuit above, you see an AND_{2} gate and an
XOR_{2} gate.

**
**

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**, for carry in)_{in} - Outputs: 2 (call them
**s**, for sum, and**c**, for carry out)_{out}

Notice we now need to make a distinction whether the carry is an
input (**c _{in}**) or an output (

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 |

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.

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.

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).

- 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**and_{i}**y**in parallel (for all_{i}**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).