Module 0255: Binary addition and subtraction as boolean operations

Tak Auyeung, Ph.D.

January 26, 2017

1 About this module

Prerequisites: 0144
Objectives: This module explores how arithmetic operations can be converted to boolean operations. This is signiﬁcant because with transistors we can implement logic gates, and it is good to be able to add and subtract using logic gates!

2 Arithmetic operations

Recall in module 0144 that we explore the addition and subtraction operations of binary numbers. While we can certainly appreciate the simplistic nature of binary number addition and subtraction, how do we do that with a computer?

The key is to look at the result of addition/subtraction and the result of carry/borrow as two diﬀerent functions. Let us review the addition rules:

$0_{2} + 0_{2}$ is $0_{2}$ with a carry of 0.
$0_{2} + 1_{2}$ is $1_{2}$ with a carry of 0.
$1_{2} + 0_{2}$ is $1_{2}$ with a carry of 0.
$1_{2} + 1_{2}$ is $0_{2}$ with a carry of 1.

Likewise, we can look at subtraction similarly:

$0_{2} - 0_{2}$ is $0_{2}$ with a borrow of 0.
$0_{2} - 1_{2}$ is $1_{2}$ with a borrow of 1.
$1_{2} - 0_{2}$ is $1_{2}$ with a borrow of 0.
$1_{2} - 1_{2}$ is $0_{2}$ with a borrow of 0.

To make the notation more concenient, let us deﬁne $R (x, y)$ be the result of adding or subtracting two single digit binary numbers $x$ and $y$ . This means that

$R (0, 0) = 0$
$R (0, 1) = 1$
$R (1, 0) = 1$
$R (1, 1) = 0$

We can also deﬁne $C (x, y)$ to represent the carry of adding two single bit numbers $x$ and $y$ . The deﬁnition is as follows:

$C (0, 0) = 0$
$C (0, 1) = 0$
$C (1, 0) = 0$
$C (1, 1) = 1$

Last, we deﬁne $B (x, y)$ to represent the borrow of subtracting a single bit number $y$ from another single bit number $x$ :

$B (0, 0) = 0$
$B (0, 1) = 1$
$B (1, 0) = 0$
$B (1, 1) = 0$

Of course, so far, we have not made much progress to implement addition or subtraction using transistors.

3 Recognizing boolean operations

Because the functions $R$ , $C$ and $B$ all take zero and one as parameters, and they only return zero and one as results, we suspect that they can be implemented using boolean operations. This is done by looking at 0 as false, 1 as true.

Let us pick the easiest one, $C$ . $C (1, 1) = 1$ whereas all other inputs has a result of 0. Doesn’t this remind you of conjunction? Indeed, $C (x, y) = x \land y$ . In electrical engineering, the conjunction operator is often omitted so that we can say $C (x, y) = x y$ .

The next one to implement is $B$ . Only one input combination yields a result of 1, namely $B (0, 1) = 1$ . There is no single boolean operation to do this, but we can deﬁne $B (x, y) = (\neg x) \land y$ . It is a little more complex than $C$ , but still doable using boolean operations! Anything that can be done using boolean operations can also be done using logic gates.

In electrical engineering, the notation is often as $B (x, y) = \bar{x} y$ where the bar on top means negation.

The last one is $R (x, y)$ . We notice that this function returns a value of 1 in two instances. We can capture each instance with a conjunction, then use a disjunction to connect the two instances. This means $R (x, y) = ((\neg x) \land y) \lor (x \land (\neg y))$ . In short hand, the disjunction is represented by a plus symbol, and so $R (x, y) = \bar{x} y + x \bar{y}$ .

4 But that’s only half the operation!

Let us consider the following addition. Letters are used to represent individual bits:

    m n
+   o p
-------
    q r
+ c s 0
-------
    a b

In this example, “m n” is a two-bit number, and “o p” is another two-bit number. “a b” is the sum. “c” is a left over carry because we want the result to use the same number of bits as the numbers being added.

Immediately, we know that $r = R (n, p)$ because it is the result of adding those two bits. We also know that $b = R (n, p)$ because the least signiﬁcant column has no carry from another column.

Another easy one is $q = R (m, o)$ , that is still easy to understand. “s” is the carry of the addition of the least signiﬁcant column, which means $s = C (n, p)$ . The result bit “a” is then $a = R (q, s) = R (R (m, o), C (n, p))$ .

Now we have the last carry “c” to resolve. This time it gets a little more tricky because a carry can result from “m+o” or “q+s”. As a result, $c = C (m, o) + C (q, s) = C (m, o) + C (R (m, o), C (n, p))$ .

5 Carry ripple

Let $x_{i}$ denotes bit $i$ (least signiﬁcant bit is bit 0) of a multi-bit value $x$ , and $y_{i}$ denote bit $i$ of $y$ . Let $w_{i}$ be bit $i$ of the intermediate sum (“q” and “r” in the previous example), let $c_{i}$ be the carry of bit $i$ (“c”, “s” and 0 in the previous example). Let $s_{i}$ be bit $i$ of the sum.

In general, we can express $w_{i} = R (x_{i}, y_{i})$ , $c_{i + 1} = C (x_{i}, y_{i}) + C (w_{i}, c_{i})$ , and $s_{i} = R (w_{i}, c_{i})$ . We can assume $c_{0} = 0$ .

This is a rather simple way to add numbers of multiple bits. However, there is one major drawback to this approach.

Note how the ﬁnal answer (the sum) is $s_{i} = R (w_{i}, c_{i})$ . $w_{i}$ is not a problem because it can be computed using just the supplied numbers. $c_{i} = C (x_{i - 1}, y_{i - 1}) + C (w_{i - 1}, c_{i - 1})$ . This means that the carry of a previous digit is needed.

Logic gates do not change their output simultaneously. There is a propagational delay involved. This is the amount of time that it takes for the input to stabilize and the output becoming valid. Let us examine the propagational delay of an adder like this.

$C (x, y) = x y$ , this involves just one gate. However, $c_{i + 1} = C (x_{i}, y_{i}) + C (w_{i}, c_{i})$ . We don’t have to count the delay of $C (x_{i}, y_{i})$ or even $w_{i} = R (x_{i}, y_{i})$ because these are computed from the given numbers. There is a or-gate involved in the computation of $c_{i + 1}$ in addition to the and-gate used to compute $C (w_{i}, c_{i})$ .

This means that each bit of a multi-bit adder has a delay of two gates. For a 64-bit integer, the total propagational delay is 128 times the propagational delay of one gate.

Generally, this method of rippling carry linearly is not considered acceptable in commercial processors.

6 Carry lookahead

Carry lookahead is a method to “cut the ripple”. Let us reexamine the equations. $c_{i + 1} = C (x_{i}, y_{i}) + C (w_{i}, c_{i})$ . Expanding the functions (to boolean operations) results in $c_{i + 1} = x_{i} y_{i} + w_{i} c_{i}$ . Then we expand $w_{i}$ , resulting in $c_{i + 1} = x_{i} y_{i} + (\bar{x_{i}} y_{i} + x_{i} \bar{y_{i}}) c_{i}$ .

At this point, we can simplify the equation a little bit.

\begin{array}{l} c_{i + 1} & = x_{i} y_{i} + (\bar{x_{i}} y_{i} + x_{i} \bar{y_{i}}) c_{i} \\ = x_{i} y_{i} + \bar{x_{i}} y_{i} c_{i} + x_{i} \bar{y_{i}} c_{i} \\ = x_{i} y_{i} + x_{i} y_{i} c_{i} + \bar{x_{i}} y_{i} c_{i} + x_{i} y_{i} c_{i} + x_{i} \bar{y_{i}} c_{i} & (introduce more speciﬁc terms) \\ = x_{i} y_{i} + (x_{i} + \bar{x_{i}}) y_{i} c_{i} + x_{i} (y_{i} + \bar{y_{i}}) c_{i} & (factoring) \\ = x_{i} y_{i} + y_{i} c_{i} + x_{i} c_{i} & (simplication) \\ = x_{i} y_{i} + (x_{i} + y_{i}) c_{i} & (factoring) \end{array}

Now we example some individual $c_{i}$ terms. $c_{0}$ is given either as 0 or as some input value, but either case it has no equation.

$c_{1} = x_{0} y_{0} + (x_{0} + y_{0}) c_{0}$ , that is a easy one!

\begin{array}{l} c_{2} & = x_{1} y_{1} + (x_{1} + y_{1}) c_{1} \\ = x_{1} y_{1} + (x_{1} + y_{1}) (x_{0} y_{0} + (x_{0} + y_{0}) c_{0}) & (expand) \\ = x_{1} y_{1} + (x_{1} + y_{1}) (x_{0} y_{0}) + (x_{1} + y_{1}) (x_{0} + y_{0}) c_{0} & (distribute) \end{array}

At this point, it is handy to introduce the following deﬁnitions. Let $g_{i} = x_{i} y_{i}$ be the “generate term” and $p_{i} = (x_{i} + y_{i})$ be the “propagate term”.

We can then rewrite $c_{1} = g_{0} + p_{0} c_{0}$ and $c_{2} = g_{1} + p_{1} g_{0} + p_{1} p_{0} c_{0}$ .

In general, $c_{i + 1} = g_{i} + p_{i} c_{i}$ . This is a recursive deﬁnition, we can theorize that $c_{i + 1} = \lor_{j = 0}^{i} g_{j} (\land_{k = j + 1}^{i} p_{k}) + c_{0} \land_{j = 0}^{i} p_{j}$ . This can be proven by induction, but that is a topic in CISP440. Nonetheless, here is the proof:

It is easier to prove looking at $c_{i} = \lor_{j = 0}^{i - 1} g_{i} (\land_{k = j + 1}^{i - 1} p_{k}) + c_{0} \land_{j = 0}^{i - 1} p_{j}$ . As such, $c_{0} = c_{0}$ .

Now on the the induction step. The induction step states that assume $c_{i} = \lor_{j = 0}^{i - 1} g_{j} (\land_{k = j + 1}^{i - 1} p_{k}) + c_{0} \land_{j = 0}^{i - 1} p_{j}$ . is true when $i = n$ . Now we need to prove the case when $i = n + 1$ .

\begin{array}{l} c_{n + 1} & = x_{n} y_{n} + (x_{n} + y_{n}) c_{n} & (by deﬁnition) \\ = g_{n} + p_{n} c_{n} & (by deﬁnition of g and p terms) \\ = g_{n} + p_{n} (\lor_{j = 0}^{n - 1} g_{j} (\land_{k = j + 1}^{n - 1} p_{k}) + c_{0} \land_{j = 0}^{n - 1} p_{j}) & (based on induction step assumption) \\ = g_{n} + p_{n} (\lor_{j = 0}^{n - 1} g_{j} (\land_{k = j + 1}^{n - 1} p_{k})) + p_{n} (c_{0} \land_{j = 0}^{n - 1} p_{j}) & (distribution) \\ = g_{n} + (\lor_{j = 0}^{n - 1} g_{j} (\land_{k = j + 1}^{n} p_{k})) + c_{0} \land_{j = 0}^{n} p_{j} & (absorb standalone term) \\ = \lor_{j = 0}^{n} g_{j} (\land_{k = j + 1}^{n} p_{k}) + c_{0} \land_{j = 0}^{n} p_{j} & (absorb standalone term) \end{array}

The bottomline is that we now have a fast way to come up with all the $c_{i}$ . Recall that $w_{i}$ is easy to compute. This means the sum iself is now much faster to compute.

How much faster?

It depends on the actual gates available. If we can have gates that can take as many inputs as we need, then the $c_{i}$ terms can all be computed using one layer of and gates followed by a layer of or gates, a total of two gate propagation. The $s_{i}$ terms still require the $w_{i}$ and $R (w_{i}, c_{i})$ . Note that $R (x, y)$ is just exclusive-or, which can be done by a gate. This means the sum can be computed in 6 gate propagations.

In reality, there is a limit to the number of inputs to gates. By structuring gates in a hierarchy, we can still manage to make the propagation delay be proportional to the log of the number of bits. This is still far better than the linear carry rippling method!

7 What about subtraction?

Subtraction works the same way in the “ripple” method, except the borrow is rippled instead of the carry. Let us concentrate on the “lookahead” method here.

First, we have to relate the various parts of a subtraction. Assuming $x_{i}$ and $y_{i}$ are bit $i$ of two numbers, $x$ and $y$ , we use $w_{i}$ to represent the intermediate diﬀerent of bit $i$ . $b_{i}$ is the borrow from bit $i$ . Last, let $d_{i}$ be bit $i$ of the diﬀerence.

$w_{i} = R (x_{i}, y_{i})$ is the same as an adder. $d_{i} = R (w_{i}, b_{i})$ is also similar to addition. The main diﬀerence is $b_{i + 1} = B (x_{i}, y_{i}) + B (w_{i}, b_{i})$ . This equation expands diﬀerently:

\begin{array}{l} b_{i + 1} & = B (x_{i}, y_{i}) + B (w_{i}, b_{i}) \\ = \bar{x_{i}} y_{i} + \bar{w_{i}} b_{i} \\ = \bar{x_{i}} y_{i} + \bar{(\bar{x_{i}} y_{i} + x_{i} \bar{y_{i}})} b_{i} \\ = \bar{x_{i}} y_{i} + (\bar{\bar{x_{i}} y_{i}}) (\bar{x_{i} \bar{y_{i}}}) b_{i} \\ = \bar{x_{i}} y_{i} + (x_{i} + \bar{y_{i}}) (\bar{x_{i}} + y_{i}) b_{i} \\ = \bar{x_{i}} y_{i} + (x_{i} \bar{x_{i}} + x_{i} y_{i} + \bar{x_{i}} \bar{y_{i}} + y_{i} \bar{y_{i}}) b_{i} \\ = \bar{x_{i}} y_{i} + (x_{i} y_{i} + \bar{x_{i}} \bar{y_{i}}) b_{i} \\ = \bar{x_{i}} y_{i} + x_{i} y_{i} b_{i} + \bar{x_{i}} \cdot \bar{y_{i}} b_{i} \\ = \bar{x_{i}} y_{i} + \bar{x_{i}} y_{i} b_{i} + x_{i} y_{i} b_{i} + \bar{x_{i}} y_{i} b_{i} + \bar{x_{i}} \cdot \bar{y_{i}} b_{i} \\ = \bar{x_{i}} y_{i} + (\bar{x_{i}} + x_{i}) y_{i} b_{i} + \bar{x_{i}} (y_{i} + \bar{y_{i}}) b_{i} \\ = \bar{x_{i}} y_{i} + y_{i} b_{i} + \bar{x_{i}} b_{i} \\ = \bar{x_{i}} y_{i} + (y_{i} + \bar{x_{i}}) b_{i} \\ = \bar{x_{i}} y_{i} + (\bar{x_{i}} + y_{i}) b_{i} \end{array}

This means that we can redeﬁned $g_{i} = \bar{x_{i}} y_{i}$ and $p_{i} = \bar{x_{i}} + y_{i}$ , then rewrite $b_{i} = \lor_{j = 0}^{i - 1} g_{j} (\land_{k = j + 1}^{i - 1} p_{k}) + b_{0} \land_{j = 0}^{i - 1} p_{j}$ .. There is no need to prove this again because the proof did not rely on the deﬁnitions of $g_{i}$ and $p_{i}$ !

Once we have $b_{i}$ ﬁgured out, $d_{i} = R (w_{i}, b_{i})$ and we are done!

8 Deﬁning some “ﬂags”

After a n-bit computation involving $x$ , $y$ with a result of $r$ , we deﬁne some “ﬂags” as follows:

$Z = \bar{\lor_{i = 0}^{n - 1} r_{i}}$ is called the zero ﬂag, it is 1 iﬀ the result is zero.
$C = b_{n}$ for a subtraction and $C = c_{n}$ for an addition. This is the “carry” ﬂag, but it also serves as the borrow ﬂag.
$S = r_{n - 1}$ . The sign ﬂag is the most signiﬁcant digit of the result.
The overﬂow ﬂag is not deﬁned until signed numbers are discussed!

These ﬂags indicate important aspects of a computation, especially after a subtraction. We will revisit the ﬂags when we need to implement instructions that make decisions, as these ﬂags are the only basic mechanisms (at the lowest level) for any code to make decisions!