Martin Kochanski’s web site / Encryption / The FAP4 chip

 

Can adders subtract?

You may be puzzled that I haven't mentioned subtractors even when I'm talking about subtraction.  The reason is that adders can be made to subtract quite easily.

Let's try a simple subtraction sum: 314159 - 271828.

    3 1 4 1 5 9
-   2 7 1 8 2 8
=     4 2 3 3 1

Now take the number we're subtracting and transform it as follows: replace 0 by 9 and 9 by 0, replace 1 by 8 and 8 by 1, replace 2 by 7 and 7 by 2, and so on (this is called "finding the nines complement" of the number).  Thus 271828 becomes 728171.

Let's add this transformed number to 314159, and add 1 to the total:

    3 1 4 1 5 9
+   7 2 8 1 7 1
+             1
= 1 0 4 2 3 3 1

Ignoring that extra 1 at the front, we've got exactly the answer we need, with no subtraction.

How the trick works

Suppose that we are trying to calculate X - Y, where both X and Y are six-digit numbers.

Forming the nines complement of Y is quick and simple for a chip to do, because it can be done on every digit at the same time: the digits don't influence one another.  For each digit, replacing 0, 1, 2, 3,... by 9, 8, 7, 6,... is the same as subtracting the digit from 9.  So forming the nines complement of Y effectively calculates 999999 - Y.

So adding the nines complement to X, and then adding 1, simply means calculating

X + 999999 - Y + 1

which with a bit of rearrangement becomes

1000000 + X - Y

... which also accounts for that intrusive 1 that we got at the beginning of our result.  In fact, the 1 acts as a useful signal: if it's not there, then it means that X - Y is negative.

Why it's as fast as addition

We've already seen that forming the nines complement is a fast operation: in fact (as I'll explain below) in our chip design it could be done in no time at all.

The only real worry is that it looks as if we're having to do two additions: we add the complement and then we add 1.  This is an illusion.

The thing about the adder circuits that handle each digit is that each one of them has to be able to receive a carry from its right-hand neighbour; and the carry means "please increase your result by 1".  The rightmost adder hasn't got a neighbour, so it hasn't been receiving carries during normal additions.  Now we decide to give the rightmost adder a carry whenever we subtract.  That carry will increase the result by 1, which is just what we need... and the best thing is that it will take no extra time and no extra circuits, because everything is designed to handle carries anyway.

How it all works in binary

All this works even better when you get down to chip design and start having to think in binary rather than decimal.

Instead of forming a nines complement you form a ones complement, which means turning every 0 into a 1 and every 1 into a 0.  This is very quick and simple, and it is made even quicker and simpler by the fact that flip-flops (the circuits that store a result at the end of one clock cycle and make it available during the next one) naturally, by their very design, output both the digit they are storing and its complement.  All we have to do in the rest of the circuit is decide which of these outputs to use: we use the digit itself if we are adding, or the complement if we are subtracting.