Adder/subtracter revisited
From adder to subtracter, how many inverters do you need, and where to put them?
Note: this page assumes that you have a basic understanding of half and full-adders
A full-adder cell is shown on the right.
- The sum-out is created by 'summing' (XORing) together the three bit
inputs A, B and C-in.
sum-out = XOR(A, B, C-in) = A xor B xor C-in - The C-out is the majority function (i.e. gives '1' if at least 2 inputs
are '1') of A, B and C-in.
C-out = MAJ(A, B, C-in) = (A and B) or (A and C-in) or (B and C-in).
The figure shows next 2 full-subtracter cells. They both produce the same result, the trick is the placement of the inverter (and the polarity of the carry, we'll come into that).
If A and B are multi-bits values, we can construct a multi-bits adder by chaining several full-adder cells together.
- For the first cell (that adds the LSBs of A and B), we'll most likely set the C-in to '0' to indicate that no previous carry affects the LSB of the sum.
- Additional cells are used for subsequent bits. And we'll propagate generated carries from cell to cell.
For the adder that I just described, the initial C-in is set to '0' to indicate that it is inactive, i.e. the 'default polarity' (DP) of the carry is '0' and the 'active polarity' (AP) is '1'.
This is the universal choice for an adder - DP='0'.
But note that an adder with DP='1' (i.e. '1' is an inactive carry and '0' is active) works as well, the carry polarity has just to be inverted from what we are used to. So we would use C-out = !MAJ(A, B, !C-in), and feed the first cell C-in with '1'.
For a subtracter, the carry bit becomes a borrow bit (even though I still call it carry for consistency of the cell).
Question: Should the DP be '0' or '1' for a subtracter?
Answer: both are quite valid choices.
An exhaustive search of all possible majority functions (for ADD/SUB and DP='0'/'1') brings us the following table.
| ADD | SUB | |||||
| C-in | A | B | DP='0' | DP='1' | DP='0' | DP='1' |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 | 1 | 1 | 0 |
| 1 | 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 0 | 1 | 1 |
| case E8 | case 71 | case B2 | case D4 | |||
These are the only 4 functions that create valid adder and subtracter cells (there are 2 adders and 2 subtracters, each one depending of the DP).
I call them cases E8, 71, B2 and D4 (in reference to their carry-out binary patterns).
- Case 71 (adder with DP set to '1') is never used in practice, even though it's a perfectly valid adder.
- Case B2 is a good but non-intuitive way of creating a subtracter - a single inverter on the A input of the majority function changes the ADD to a SUB.
- Case D4 is the much more intuitive and common way of doing a SUB - to invert B.
In summary, here are the possible implementations for add/sub cells:
| Sum-out | Carry-out | ||
| E8 | ADD with DP='0' | A xor B xor C | MAJ(A,B,C) |
| B2 | SUB with DP='0' | A xor B xor C | MAJ(!A,B,C) |
| 71 | ADD with DP='1' | A xor B xor !C | MAJ(!A,!B,C) or !MAJ(A,B,!C) |
| D4 | SUB with DP='1' | A xor !B xor C or A xor B xor !C |
MAJ(A,!B,C) or !MAJ(!A,B,!C) |
MAJ(A,B,C) = (A and B) or (A and C) or (B and C)
Remember that the first cell carry-in is set to the same value as DP (unless of course you want to offset the result by 1). For example, if you construct an adder 71 or subtracter D4, assign the first carry-in with '1' by default.