__ Page 1 of 3 __
**Adders With Removed Dependencies **

The following study proposes new recursive formulas, the
implementation of which shortens the longest paths in the design of a
binary adder and thus improves the execution time with respect to the
traditional formulas for the addition. Let N indicate the natural
numbers and V the exclusive OR. Let a quantity to be undefined, if
such a quantity, or any logical operation involved with such a
quantity, have no meaning, i.e., have no value attribute. Assume
that the symbol used for undefined is . Let an expression or term
that is represented as F(.) mean that F is determined by variables
not explicitly stated. Suppose that bit positions are labeled 0 for
the most significant bit and r for the least significant bit such
that r B 0, i.e., the subscripts run from high order to low. Let i,
m, n, belong to N and let n+1 be the width of the addition. We
define the following quantities: Definition 1: The pseudo-generate
signal from bit i to bit m, such that i <= m, G*(i,m), is defined
to be: G*(i,m) = 0 if i J n G*(i,m) = Gi + Gi+1 +
Ti+1Gi+2 + Ti+1Ti+2Gi+3
+.......+ Ti+1Ti+2Ti+3.......Tm-1Gm else Definition 2: The

pseudo-transmit signal from bit i to bit m, T(i,m) such that i <= m
is defined to be: T(i,m) = 1 if i J n T(i,m) =

TiTi+1Ti+2....Tm-1Tm else Definition 3: The pseudo-carry from
bit i to bit m, S(i,m), such that i <= m is defined to be:
S(i,m) = CIN if i J n S(i,m) = G*(i,m) +
T(i+1,m+1)S(m+1,z) else z being some natural number such that m O

z. Definition 4: The pseudo-half-sum for bit i, Hi, is defined to be:
Hi = if i J n Hi = Ai V Bi else Definition 5: The
pseudo-transmit-half-sum for bit i, is defined to be: Mi =
if Hi = Mi = Hi V Ti+1 else With the previous definitions and
with reductions it can be proven that the following lemmas hold true:
Lemma 1: G(i,m) = TiG*(i,m) if i,m <= n Lemma 2: G*(i,z) =

G*(i,m) + T(i+1,m+1)G*(m+1,z) such that m O z Lemma 3: S(m,z) =
S(m,n) = G*(m,n) + T(m+1,n)CIN Theorem 1: the set of equations: (2.1)
SUMi-1 = Mi-1S(i,m) + Hi-1S(i,m)' (2.2) S(i,m) = G*(i,m) +
T(i+1,m+1)S(m+1,z) is equivalent to the addition. Proof: (2.1) z
SUMi-1 = (Hi-1'Ti + Hi-1Ti')S(i,m) + Hi-1S(i,m)'
= Hi-1'TiS(i,m) + Hi-1Ti'S(i,m) + Hi-1S(i,m)'

= Hi-1'TiS(i,m) + Hi-1(Ti'S(i,m) + S(i,m)')

= Hi-1'TiS(i,m) + Hi-1(Ti' + S(i,m)')

= Hi-1'TiS(i,m) + Hi-1(TiS(i,m))'

= Hi-1 V TiS(i,m) Case 1: i J n + 1 if i > n+1
by definition 4 SUMi-1 = Case 2: i = n + 1 by definition 2
and 3 Ti = 1 and S(i,m) = CIN thus TiS(i,m) = CIN and SUMn
= Hn V CIN Thus, the set of equations 2.1 and 2.2 is equivalent to
the addition for the least significant bits Case 3: i O n + 1 It
must be proved that the carry to the bit position i-1, Ci is equal to
TiS(i,m) with S(i,m) as defined by (2.2) this is because in this case
Hi-1 is always defined to be equal to the half-sum. This means the
following: Given that Ci = G(i,n) + T(i,n)CIN prove that: (1) G(i,n)
+ T(i,n)CIN = TiS(i,m) By Lemma 3 S(i,m) = G*(i,n) + T(i+1,n)CIN thus

1

__ Pag...__