State Machine for Addition

Let's go back to our first example. We'll start by adding the leftmost two bits of the inputs.

Then we add the next two bits to produce a new partial result.

The last row represents the most recent result, and the part that changed from the previous step is marked in orange. Now the next two bits:

Continuing to the end, we get the following sequence of partial results. The column that the input bits come from at each step is marked with a short line.

In this example at least, the range of influenced bits at each step does not extend more than three places to the left and one to the right of the input bits being added. In other words, all the changes are confined to the green band above.

Might this be a general rule? In ordinary binary arithmetic, there is no limit to how far carries can propagate to the left, but here our inputs are constrained by the rules of BF normalisation, which limit how densely ones can be packed together. It's plausible that this could limit how far upward and downward carries can propagate.

Unfortunately, this is not always the case, as the next example shows.

But wait, let's back up a little.

At this point, there's something else we could do. Let's perform a partial normalisation and replace the yellow 011 by 100.

Now we carry on. Whenever we produce a 11 within the green band, we will normalise it to 100. Below, the places where this has been done are marked in yellow.

There is quite a dramatic improvement. All the changes now fit neatly into a 5-bit wide band that moves along with the column being processed.

This is very encouraging, but can we prove that it always works?

We can regard the process as a finite-state machine with 4 bits of state, initially zero. At each step we add a pair of bits X and Y to the state, aligned like this, to give a 5-bit result:

Then we normalise the last 4 bits of the result, with carry into the 5th bit. The leftmost bit of this result becomes the next bit Z of the output, and the remaining bits become the state for the next step.

Here are the first three state transitions from Example 4 showing how these rules work.

Note that there is a subtlety in these rules: We do not normalise the whole 5 bit result; rather, we normalise the last 4 bits, and if there is a carry from that, add it to the leftmost bit. The difference can be seen in the transition at step 11 above:

Here 10110 becomes 11000, not 100000, because 0110 normalises to 1000 without any carry. On the other hand, 01100 becomes to 10000, because 1100 normalises to 10000 with a carry into the 5th bit.

You may be wondering what happens if this carry causes another carry from the 5th bit. For now we'll just assume that this does not happen, and that the result always fits in 5 bits. We will validate this assumption later.

Now let's build a state transition table.

There are a couple of things to note about this table. One is that, out of the 8 possible normalised 4-bit BF bit patterns, states 0101 and 1010 are missing. This is because they cannot be reached starting from the initial state 0000.

The other is that there is no entry for state 1001 with inputs 11. If this combination were to occur it would be a problem, because the unnormalised result is 11011, which would normalise to 100011 and overflow 5 bits.

Fortunately, this combination cannot occur. The only way to reach state 1001 is to either be in state 0000 and see input bits 11, or be in state 0010 and see input bits 01 or 10. But as long as the input numbers are normalised, an input bit pair of 11 can only follow 00, so the missing entry will never be needed.

So we have established that our state machine produces exactly one bit of output at each step, which cannot be changed by a carry from any later step.

Here's Example 4 again, presented in a way that shows the action of the state machine. The state bits are marked in orange and tbe output bits in green. At the end, we just need to read off the output from all the green bits and normalise it.

When we reach the end, we need to run the state machine for two more steps with inputs 00 to flush out the last two output bits.

After these last two steps, the last two bits of the state will be zero, but the rest of the state might not be, as in this example:

At step 6, the pale orange bits are either always zero or have weight zero, so can be ignored. The underlined orange bit has weight 1, so it needs to be added to the result at the position of the underlined green bit. This is easy, however: the two underlined bits cannot both be 1, because that would require the state in the previous step to contain two consecutive 1s, and since we are only using normalised states, this cannot happen. So we can simply "or" the underlined bits together at the final step to give the yellow bit.

We now have an addition algorithm that produces an unnormalised result with a constant amount of work per bit. If we can also perform normalisation with constant work per bit, we will have accomplished our goal of finding an efficient addition algorithm.