Part 2 - Binary Adders | rezarezvan.com

In this part we’ll cover different kinds of (binary) adders that digital circuits use. They’re an essential part for all the arithmetic operations which are needed.

Full Adder

The (1-bit) full adder is the simplest adder unit we can create.

It takes two input bits $a$ and $b$ , with $c_{in}$ (carry in) - it outputs two bit signals, $c_{out}$ and $r$ .

If we use a truth table and find a boolean function for it, we find that,

r = a \bar{b} \bar{c}_{in} + \bar{a} b \bar{c}_{in} + a b c_{in} + \bar{a} \bar{b} c_{in},

which we can simplify to,

r = c_{in} \oplus (a \oplus b).

For $c_{out}$ ,

c_{out} = a \bar{b} c_{in} + \bar{a} b c_{in} + a b,

which simplifies to,

c_{out} = c_{in} (a \oplus b) + a b.

Ripple Carry Adder

So the full adder is the building block for adding two bit inputs. But that isn’t of much use, we usually use bigger numbers. So chaining full adders to each other becomes, for example, a 4-bit adder. For adding 4 bit numbers.

This is called a Ripple Carry Adder.

For each Full Adder (FA) cell we have,

\begin{align*} r_i & = a_i \oplus b_i \oplus c_{in}, \newline c_{out} & = c_{in} (a_i \oplus b_i) + a_i b_i. \end{align*}

Subtraction

Subtraction, mathematically is just,

a - b = a + (-b).

But how do we transform an integer represented in binary as negative?

Complement/Negate B
Add 1

Or we can write it as,

a - b = a + (\bar{b} + 1).

One problem that occurs with the ripple adder is that, it’s an inherently slow design. $r_7$ needs to wait for $c_7$ .

Which makes the time $\mathcal{O}(n)$ .

Carry Select Adder

While the Ripple Carry Adder is simple, it’s quite slow. A faster type of adder is the carry select adder. It consists of ripple adders and a multiplexer (MUX). You can prove with some examples and some math that:

The time it takes for a carry select adder is $\mathcal{O}(\sqrt{n})$ .

Carry Look-ahead Adders

In general, for addition, the best we can achieve is $\mathcal{O}(\log(n))$ , but we need to think in terms of trees.

We introduce two new signals. Carry ‘propagate’ and carry ‘generate’.

\begin{align*} p_i & = a_i \oplus b_i, \newline g_i & = a_i b_i. \end{align*}

We propagate if, one of the 2 inputs is ‘1’. Then propagate the carry you received from the previous stage. If both inputs are 1, then no matter what carry-in you received, generate a carry (out).

With this we can define,

\begin{align*} c_{i + 1} & = g_i + p_i c_i, \newline r_i & = p_i \oplus c_i. \end{align*}

Summary

This was quite a short part, but adders are quite a simple, yet powerful concept.