Part 2 - Binary Adders

In this part we’ll cover different kind 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 simply this to: $$ c_{in}\ \oplus (a\ \oplus\ b) $$

For $c_{out}$ : $$ a\ \bar{b}\ c_{in} + \bar{a}\ b\ c_{in} + a\ b $$

Which simplifies to: $$ 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: $$ r_i = a_i\ \oplus\ b_i\ \oplus\ c_{in} \newline c_{out} = c_{in}\ (a_i \oplus\ b_i) + a_i\ b_i $$

Subtraction

Subtraction, mathematically is just: $$ a + b = a + (-b) $$

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

1. Complement/Negate B
2. 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 consits 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, 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’. $$ p_i = a_i\ \oplus\ b_i \newline g_i = a_i\ b_i $$

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: $$ c_{i + 1} = g_i + p_i\ c_i \newline r_i = p_i\ \oplus\ c_i $$

Summary

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