Special purpose adders

Special purpose adders

Some arithmetic algorithms can be realized with only one modified adder. For example : if a/s then S = A – B else S = A + B ; // adder/subtractor/comparator if A > B then S = A else S = B ; // maximum value S = A + B ; S' = A + B + 1 ; // two-output adder S = A + B ; S' = A + B + 1 ; S" = A + B + 2 ; // three-output adder if A – B ³ 0 then S = A – B else S = B – A ; // absolute value of the difference if A + B < 2n then S = A + B else S = A + B – 2n ; // modulo 2n sum if A + B < 2n – 1 then S = A + B else S = A + B – 2n + 1 ; // modulo 2n – 1 if A + B < 2n + 1 then S = A + B else S = A + B – 2n – 1 ; // modulo 2n + 1 The cost and the delay are similar to a fast adder's ones.

Fast adder

The special purpose adders of this page are built around the Sklansky's adder, which is recalled here for convenience of comparison.

The "BK" cells outputs are either 'P', 'G' or 'K', nevertheless a carry ci is never 'P' because in this applet the "HA" cell at the right is modified in order to exclude 'P'.

Adder/ subtractor

Adders spontaneously calculate the addition modulo 2n. To get the opposite -B of a number B, all the bits are logically complemented and a 1 is added. The addition of B with -B obtained in this way gives 2n that is 0. The input carry c0 of an adder is used to add the bit a/s and disjunction gate to complement B. This "operations box" executes addition if a/s = '0' and subtraction if a/s = '1'.

Overflow

Just like the adder, the adder/subtractor may overflow, but it may as well underflow. If the last carry cn and of the carry cn-1 differ, then the output S is incorrect : 0 1: 2n should be added to S to get the correct result (overflow) 1 0: 2n should be subtracted to S to get the correct result (underflow)

Comparison of signed integers

After a subtraction S = A – B, the sign of S indicates A ³ B or otherwise A < B. A slight modification of the adder/subtractor wiring allows the output carry cn to indicate A < B, A = B or A > B; necessary for comparisons. This indication is only valid with subtraction.

The larger from A and B

In order to compare A and B, it not necessary to compute the difference A – B. Only the sign of A – B is needed, that is the carry out. This comparator is simpler (less "BK") therefore faster (less fan-out) than a complete subtractor. A multiplexors row selects the max.

Carry-late adder

If the carry in c0 of an adder S = A + B + c0 is ready later than the inputs A and B, a carry-late adder is appropriate. The delay between input c0 and outputs S is small and independent of the number of bits.

On the contrary, if the carry in c0 is ready as soon as the inputs A and B, then the approach used in the above described adder/subtractor would be more efficient because requesting less "BK" cells.

Two-output adder

To design this adder S = A + B + c0 first the output are duplicated. Then for the output S the value 0 is substituted to c0 and the value 1 is substituted to c0 for the output S'. The obtained adder calculates simultaneously S = A + B and S' = A + B + 1 .

The output of the "BK" is either 'P', 'G' or 'K', and the carry ci must be '0' or '1'. To calculate S = A + B, 'K' or 'P' give '0', 'G' gives '1'. To calculate S' = A + B + 1, 'K' gives '0', 'P' or 'G' give '1'.

Three-output adder

We want to calculate S = A + B, S' = A + B + 1 and S" = A + B + 2. To get S and S" we calculate beforehand without carry propagation two numbers X and Y such that X + Y = A + B. In that way we get the least significant bits s0 and s"0. Then the n-1 most significant bits of X and Y are added with the preceding two-output adder .

Where is the third output S' = A + B + 1 ? The calculation of S' from S and S", either S' = S + 1 or S' = S" – 1, only claims one inverter and some 2-input multiplexers. The least significant bit s'0 is the complement of s0. For the other bits : if s0 = 0 then s'i = si else s'i = s"i .

In much the same way as above, a two-output adder can calculate S = A + B – 1, S' = A + B and S" = A + B + 1 by calculating two numbers X and Y such that X + Y = A + B + 2n – 1 with a row of HA' cells, dual of the HA cell. An extra inverter deals with the 2n .

Absolute value of the difference

With four slight modifications, Sklansky's adder with a late carry-in returns S = ½ A – B ½. insert a row of inverters to complement B (or A) modify the "BK" cell giving cn to change the value 'P' into 'G' for the signal "feed-back" ('K' gives '0', 'P' or 'G' give '1' ) insert a row of "BK" cells connected to "feed-back" modify the later cells to either complement the result S or increment it according to "feed-back".

modulo 2n– 1 adder

An adder delivers spontaneously a modulo 2n sum. With a slight modification, the Sklansky's adder with a late carry-in delivers a modulo 2n – 1 sum S. if A + B < 2n – 1 then S = A + B ; if A + B ³ 2n – 1 then S = ½ A + B + 1 ½ modulo 2 n In both cases we get S = ½ A + B ½ modulo (2n– 1). The condition is given by the carry out cn: if cn = 'K' then A + B < 2n – 1, if cn = 'P' then A + B = 2n – 1, if cn = 'G' then A + B > 2n – 1. Therefore the "feed-back" signal that controls the "+1" is '0' if cn = 'K' and is '1' otherwise (just as before for absolute value).

Modulo 2n+ 1 adder

if A + B < 2n + 1 then S = A + B ; if A + B ³ 2n + 1 then S = ½ A + B – 1 ½ modulo 2n The previous adder is used with two inputs X and Y such that X + Y = A + B + 2n – 1. A row of HA' cells carries on this addition propagation-free. if X + Y < 2n+1 then S =½ X + Y + 1 ½ modulo 2n ; if X + Y ³ 2n+1 then S = ½ X + Y ½ modulo 2n ; The horizontal "feed-back" signal that controls the "+1" is the "nand" of xn and (cn = 'G' ). The result bit sn is the "and" of xn and (cn = 'P').

The inserstion of multiplexors within the adder deals with some specific cases overlooked in the adder above. if A = 2n et B = 2n then A + B modulo 2n – 1 = 1. if A = 2n et B < 2n then A + B modulo 2n – 1 = B complemented + 2. if A < 2n et B = 2n then A + B modulo 2n – 1 = A complemented + 2.