Figure 1: A simple two-bit adder.
Unfortunately, we are not quite done, yet. Let us consider the addition of two binary numbers, x and y. In this case, we can assume that each number has exactly n bits. Further, we can use xi to mean bit i of x.
Let us denote the sum s = x + y, and it also has n bits. How do we compute si for all i from 0 to n - 1?
The discussion of module 0144 gives us some idea. s0 is easy, as there is no carry from a less significant digit. As a result, s0 = R(x0,y0).
s1 is a little more tricky, as it is the result of R(x1,y1) added to C(x0,y0). Using our notation, however, this simply means that s1 = R(R(x1,y1),C(x0,y0)).
How about s2? It is no more complicated than s1, as s1 depends on R(x2,y2) and “the carry from the previous digit”. However, the “the carry from the previous digit makes things a little sticky. This is because there are two sources of a carry from the less significant digit. First, there is C(x1,y1), then there is C(R(x1,y1),C(x0,y0)).
How should we combine the two sources of carry from the less significant digit? Since only up to one can be a one, it is safe to use a disjunction. This means that s2 = R(R(x2,y2),C(x1,y1) + C(R(x1,y1),C(x0,y0))).
You can probably see how s3 is a bit more complicated than s2 because of the computation of the carry from bit 2.
This method of being free to directly referring to all less significant digits (x0 to xi, y0 to yi) in the computation of si is combinatorial. This method has the distinct advantage of being very fast. At the same time, this method also complicates the equation to compute si. This complexity in equations translates to complexity of gate logic, and hence size of an ALU core. A long time ago, this was too much complexity for 8-bit processors (consider the computation of s7).
As a result, the concept of a “half-adder” was used. In addition to a sum s, there is also a carry term k. ki is defined as the carry from the digit less significant than bit i. Using this definition, k0 is defined as 0, as there are no digits less significant than bit 0.
The introduction of k simplifies the computation of s. This is because s1 is now defined as R(R(x1,y1),k1), and k1 = C(x0,y0) + C(R(x0,y0),k0).
In fact, one can now generalize and define that for all i greater than 0 and less than or equal to n- 1 (∀i ∈{1,…n- 1}). si = R(R(xi,yi),ki), and ki = C(xi-1,yi-1) + C(R(xi-1,yi-1),ki-1).
A pictorial representation of this is in figure 1. In this case, each box is a “half-adder”. The symbol labeled k1 and k2 are or-gates. “A” and “B” of each box represent the inputs to a half adder. “R” is the result R(A,B), and “C” is the carry C(A,B). You can imagine how this can be extended to the left with more columns of stacked half adders.
The problem of the introduction of k is that the adder of bit i must wait for the adder of bit i- 1 to finish first (in order for ki to have a meaningful value). This is called “carry propagation”. An adder designed this way takes considerably more time to compute a sum compared to a combinatorial implementation.