Adders and subtractors

Why it exists

Arithmetic in a computer is built from a handful of gates. The adder is the heart of the ALU: subtraction, comparison, address calculation, incrementing the program counter and even multiplication all use it. GATE asks for the equations of the half and full adder, the number of gates, the delay of a ripple-carry adder compared with carry lookahead, how an adder becomes a subtractor and where the overflow bit comes from, and how a BCD adder corrects a binary sum.

Prerequisites

You need the design procedure from combinational design and the meaning of carry and overflow from fixed-point arithmetic.

Precise definitions

Half adder. Adds two bits $A$ and $B$. Sum $S = A \oplus B$, carry $C = AB$. Cost: 1 XOR and 1 AND. It cannot take a carry from a lower position.

Full adder. Adds three bits $A$, $B$ and the carry in $C_{in}$:

$S = A \oplus B \oplus C_{in},\qquad C_{out} = AB + BC_{in} + AC_{in} = AB + C_{in}(A \oplus B).$

$C_{out}$ is the majority of the three inputs. A full adder is two half adders (the first adds $A$ and $B$, the second adds the carry in to that sum) and an OR gate for the two carries: 2 XOR + 2 AND + 1 OR = 5 gates.

Generate and propagate. Define $G = AB$ (this position generates a carry whatever comes in) and $P = A \oplus B$ (it propagates an incoming carry). Then $C_{out} = G + P\,C_{in}$ and $S = P \oplus C_{in}$. (Some books use $P = A + B$; the carry is the same.)

Ripple-carry adder. $n$ full adders in a row, the carry out of bit $i$ feeding the carry in of bit $i + 1$. It is cheap ($n$ full adders, $5n$ gates) but the carry has to travel through all the stages: the delay grows linearly with $n$. In the model where every gate takes one unit and $P, G$ are ready after one unit, each stage adds two units (AND, then OR) to the carry, so carry $c_k$ is ready after $2k + 1$ units and the last sum bit about $2n$ units.

Carry lookahead. Instead of waiting, compute every carry directly from the $P$'s, the $G$'s and $c_0$. For four bits:

$c_1 = G_0 + P_0 c_0$ $c_2 = G_1 + P_1 G_0 + P_1 P_0 c_0$ $c_3 = G_2 + P_2 G_1 + P_2 P_1 G_0 + P_2 P_1 P_0 c_0$ $c_4 = G_3 + P_3 G_2 + P_3 P_2 G_1 + P_3 P_2 P_1 G_0 + P_3 P_2 P_1 P_0 c_0$

Each is a two-level AND-OR circuit, so in the same model all carries are ready after 3 units ($P, G$ at 1, AND at 2, OR at 3) and the sums after 4, independent of the number of bits in the group. The price is more gates with larger fan-in. For wide words, lookahead is applied in groups (a second level of lookahead on group $P$ and $G$).

Half subtractor. $A - B$: difference $D = A \oplus B$, borrow out $B_{out} = A'B$. Full subtractor $A - B - B_{in}$:

$D = A \oplus B \oplus B_{in},\qquad B_{out} = A'B + A'B_{in} + B\,B_{in}.$

Adder-subtractor. To subtract, use $A - B = A + \bar{B} + 1$ (2's complement). One $n$-bit adder with an XOR gate on each bit of $B$ and a control input $M$:

• each $B_i$ goes through $B_i \oplus M$,
• $M$ is also the carry into bit 0.

$M = 0$ adds ($A + B$) and $M = 1$ subtracts ($A + \bar{B} + 1$). The carry out is 1 for a subtraction exactly when $A \ge B$ as unsigned numbers (no borrow). Overflow of the signed operation is $V = c_{n-1} \oplus c_n$ (the carries into and out of the sign bit).

Incrementer. A chain of half adders adds 1: $S_i = A_i \oplus c_i$, $c_{i+1} = A_i c_i$ with $c_0 = 1$.

BCD adder. Adds two BCD digits (and a carry in) and gives a BCD digit and a carry. Procedure: add the digits and the carry in with a 4-bit binary adder, giving the 4-bit binary sum $Z_8 Z_4 Z_2 Z_1$ and a carry out $K$. If the true sum is more than 9, add 6 (0110) to correct the digit and produce a decimal carry. The correction is needed exactly when

$\text{carry} = K + Z_8 Z_4 + Z_8 Z_2 .$

The correction adds 6 because a 4-bit binary digit holds 16 values while a decimal digit uses 10: adding 6 skips the six unused codes and produces the carry into the next digit.

How it works

Step through a 4-bit ripple-carry addition. Each step is one full adder: the three input bits, the sum bit and the new carry. Unknown positions are shown as dots; they are filled in from the right, which is exactly what the circuit does and why the carry limits the speed.

A = 1011
B = 0110
M = 0 (carry into bit 0)

The adder becomes a subtractor by feeding the inverted $B$ and setting the carry in to 1. Here is $7 - 5$: the third row is $B$ XOR $M$ with $M = 1$.

A = 0111
B = 0101
M = 1 (carry into bit 0)

The full adder's equations are visible in its truth table: the carry out is the majority of the inputs, and it equals $G + P\,C_{in}$.

Worked examples

#include <stdio.h>
 
typedef struct { int sum, cout; } Fa;
 
static Fa full_adder(int a, int b, int cin) {
    int p = a ^ b, g = a & b;
    Fa r = { p ^ cin, g | (p & cin) };
    return r;
}
 
/* 4-bit ripple-carry adder-subtractor: mode 0 adds, mode 1 subtracts (b is XORed with mode, mode is the carry in) */
static unsigned add_sub4(unsigned a, unsigned b, int mode, int *cout, int *carry_into_sign) {
    unsigned s = 0;
    int c = mode;
    for (int i = 0; i < 4; i++) {
        if (i == 3) *carry_into_sign = c;
        Fa r = full_adder((a >> i) & 1, ((b >> i) & 1) ^ mode, c);
        s |= (unsigned)r.sum << i;
        c = r.cout;
    }
    *cout = c;
    return s;
}
 
/* 4-bit carry-lookahead carries from p, g and c0 */
static int cla_carry(unsigned a, unsigned b, int c0, int k) {
    int c = c0;
    for (int i = 0; i < k; i++) {
        int p = ((a ^ b) >> i) & 1, g = ((a & b) >> i) & 1;
        c = g | (p & c);
    }
    return c;
}
 
int main(void) {
    int bad_add = 0, bad_sub = 0, bad_cla = 0, bad_bcd = 0;
    for (unsigned a = 0; a < 16; a++)
        for (unsigned b = 0; b < 16; b++) {
            int co, cs;
            for (int cin = 0; cin < 2; cin++) {
                unsigned t = a + b + (unsigned)cin;
                int c = cin;
                unsigned s = 0;
                for (int i = 0; i < 4; i++) {
                    Fa r = full_adder((a >> i) & 1, (b >> i) & 1, c);
                    s |= (unsigned)r.sum << i;
                    c = r.cout;
                }
                bad_add += s != (t & 15) || c != (int)(t >> 4);
                for (int k = 1; k <= 4; k++) {
                    unsigned lo = (1u << k) - 1;
                    bad_cla += cla_carry(a, b, cin, k) != (int)(((a & lo) + (b & lo) + (unsigned)cin) >> k);
                }
            }
            unsigned d = add_sub4(a, b, 1, &co, &cs);
            bad_sub += d != ((a - b) & 15) || co != (a >= b);
        }
    for (int x = 0; x < 10; x++)
        for (int y = 0; y < 10; y++)
            for (int cin = 0; cin < 2; cin++) {
                int z = x + y + cin;
                int carry = z > 15;
                int s4 = z & 15;
                int fix = carry || s4 > 9;
                int res = fix ? s4 + 6 : s4;
                int tens = fix ? 1 : 0, ones = res & 15;
                bad_bcd += tens * 10 + ones != x + y + cin;
            }
    printf("ripple add wrong: %d, subtract wrong: %d, lookahead wrong: %d, BCD wrong: %d\n", bad_add, bad_sub, bad_cla, bad_bcd);
    int co, cs;
    unsigned s = add_sub4(11, 6, 0, &co, &cs);
    printf("1011 + 0110 = %u%u%u%u%u (carry out %d)\n", (unsigned)co, (s >> 3) & 1, (s >> 2) & 1, (s >> 1) & 1, s & 1, co);
    s = add_sub4(7, 5, 1, &co, &cs);
    printf("7 - 5 = %u with carry out %d (no borrow)\n", s, co);
    s = add_sub4(5, 7, 1, &co, &cs);
    printf("5 - 7 = %u (%d signed) with carry out %d (borrow)\n", s, (int)s - 16, co);
    s = add_sub4(7, 1, 0, &co, &cs);
    printf("7 + 1 = %u, carry into sign %d, carry out %d, overflow %d\n", s, cs, co, cs ^ co);
    return 0;
}

ripple add wrong: 0, subtract wrong: 0, lookahead wrong: 0, BCD wrong: 0
1011 + 0110 = 10001 (carry out 1)
7 - 5 = 2 with carry out 1 (no borrow)
5 - 7 = 14 (-2 signed) with carry out 0 (borrow)
7 + 1 = 8, carry into sign 1, carry out 0, overflow 1

Cheat box

Traps and GATE patterns

Connections

The adder-subtractor, with its flags, is the arithmetic core of the ALU. The signed interpretation of the result and the meaning of $C$ and $V$ come from signed number representation and fixed-point arithmetic. The gates used are those of logic gates (the XOR especially), and the digit code that the BCD adder works on is in codes.

PYQs

We consider the addition of two 2's complement
numbers bn-1 bn-2 ... b0 and an-1 an-2 ... a0. A binary
adder for adding unsigned binary numbers is used to
add the two numbers. The sum is denoted by cn-1 cn-2
... c0 and the carry-out by cout. Which one of the
following options correctly identifies the overflow
condition?

Consider an eight-bit ripple-carry adder for
computing the sum of A and B, where A and B are
integers represented in 2's complement form. If the
decimal value of A is one, the decimal value of B that
leads to the longest latency for the sum to stabilize is
______.

Consider a carry look ahead adder for adding two n-
bit integers, built using gates of fan-in at most two.
The time to perform addition using this adder is:

A half adder is implemented with XOR and AND
gates. A full adder is implemented with two half
adders and one OR gate. The propagation delay of
an XOR gate is twice that of an AND/OR gate. The
propagation delay of an AND/OR gate is 1.2
microseconds. A 4-bit ripple-carry binary adder is
implemented by using four full adders. The total
propagation time of this 4-bit binary adder in
microseconds is ______.

Which one of the following adders reduces carry
propagation delay by generating carries in
advance?

In a look-ahead carry generator, the carry generates
function Gi and the carry propagate function Pi for
inputs Ai and Bi are given by:

Pi = Ai ⊕ Bi and Gi = AiBi

The expressions for the sum bit Si and the carry bit
Ci+1 of the look ahead carry adder are given by:

Si = Pi ⊕ Ci and Ci+1 = Gi + PiCi, where C0 is the input
carry.

Consider a two-level logic implementation of the
look-ahead carry generator. Assume that all Pi are
available for the carry generator circuit and that the
AND and OR gates can have any number of inputs.
The number of AND gates and OR gates needed to
implement the look-ahead carry generator for a 4-bit
adder with S3, S2, S1, S0 and C4 as its outputs are
respectively:

Given two three-bit numbers a2 a1 a0 and b2 b1 b0
and c the carry in, the function that represents the
carry generate function when these two numbers
are added is:

Self-check

Revision card

References