Special purpose adders


Special purpose adders

Some arithmetic algorithms can be realized with only one modified adder. For example :

  • if A + B < 2n then S = A + B else S = A + B 2n ; // modulo 2n sum
  • if A + B < 2n then S = A + B else S = 2n 1 ; // adder with saturation
  • 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 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 the value 'P' for c1.

Addition with saturation

If the output carry cn is neglected then S = A + B 2n whenever A + B is too large. In order to retain the continuity of the addition, the adder with saturation is sometimes preferred to the adder modulo. It computes S = min( A + B , 2n 1) .

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 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)

Addition/ subtraction with saturation

Just as with the addition with saturation, the two carries cn and cn-1 may be used to select the largest representable positive interger or the smallest representable negative integer. S = min ( max ( A ± B , -2n-1) , 2n-11) .

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 multiplexers 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" (yellow cells)
  • modify the later cells to either complement the result S or increment it according to "feed-back".

Addition in "Sign Magnitude"
representation

Let sa and sb be the sign of A and B respectively and Ma and Mb their magnitude (absolute value). The addition of A and B is performed by the addition of Ma and Mb if A and B have the same sign, and the subtraction otherwise. In any cases, the result S sign is the sign of the addend with the larger magnitude.

if (saÅ sb) then { Ms = Ma + Mb , ss= sa }
else if Ma ³ Mb then { Ms = Ma Mb , ss= sa }
else { Ms = Mb Ma , ss= sb }
The adder in "Sign Magnitude" representation inherits from both the "adder/subtractor" and the "absolute value of the difference" operator.
  The horizontal line "feed-back" controls the last row of modified "BK" cells (yellow) :
if feed-back = '2' then Ms = Ma + Mb; //identity: 'P' gives '0', 'G' gives '1' and 'K' gives '0'
if feed-back = '1' then Ms = Ma Mb; //incr: 'P' gives '1', 'G' gives '1' and 'K' gives '0'
if
feed-back = '0' then Ms = Mb Ma; //invert: 'P' gives '1', 'G' gives '0' and 'K' gives '1'

modulo 2n 1 adder

An adder delivers spontaneously a modulo 2n sum. With a slight modification, the Sklansky's adder with a late carry 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 2n

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). The yellow cells are the same as in the carry-late adder.

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 + c0. A row of "HA' " cells carries on this addition propagation-free. The input carry c0 = '0'.

  • 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 value range for A and B is from 0 to 2n. The inputs bits an and bn are missing in the above adder. These two bits indicate whether A = 2n and B = 2n respectively.
if A = 2n and B = 2n then ( A + B ) modulo 2n + 1 = 2n 1.
if A = 2n and B < 2n then A is rewritten ( 2n 1 ) + 1, all the ai input bits are set to '1' as well as the input carry c0.
if A < 2n and B = 2n then B is rewritten ( 2n 1 ) + 1 thanks to the input carry c0.