__ Page 1 of 4 __
**Algorithm to Implement Adders With Small Book Sizes **

One of the major concerns in logic design is the size of the
books (logic gates) available in the technology that a function has
to be implemented in. A study which describes an algorithm for an
adder develops the implementing equations dependent on the limits of
the technology used (in terms of book size), thereby developing an
efficient implementation for any particular technology. The algorithm
is based on the formulation of the SUM as follows. Given the inputs
into the adder, Ai and Bi, and its width, n + 1 (such that n
is a natural number B 1), then the SUM of the bit position i -
1 is formulated as follows, (1) Sum (i-1) = M(i-1)S(i,m) +
H(i-1)S(i,m)' (2) S(i,m) = G*(i,m) + T(i+1,m+1)S(m+1,z) such that the
bit positions are labeled O for the most significant bit and n for
the least significant bit and if (i,m) belong to N then the
quantities present in equations (1) and (2) are described by the
following definitions: 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 > n Hi = Ai V Bi else
DEFINITION 5: The pseudo-transmit-half-sum for bit i, Mi, is defined
to be: Mi = if Hi = Mi = Hi V Ti+1 else The SUM
equations and definitions have been reported in [*]. Given that the
formulation of the SUM is recursive and the parameters involved are
arbitrary (i.e., there is no law that attributes a value to them), it
can be easily derived that there exist several representations of the
SUM. In addition, the following holds true. Theorem A: For every
removal of recursion, the following holds true: 1) The resulting
expressions have two terms that are recursive, namely, one that
contains the pseudo-carry and one that contains its complement. 2)
There are two OR terms added in respect to the previous removal. 3)
The terms that contain recursion are maximum width ANDs. 4) If an "m"
way was the maximum way AND in the previous removal then "m+1" way
AND is the maximum way AND in the current. Theorem B: The equation
that computes the SUM is a (i+2) x 2(i+1) AND-OR function, i being
equal to the number of the removed recurrences. In addition, the
following can be proven: Theorem 1: If a formulation for the sum is
adopted, then its m x n AND-OR formulation can be written as an S x
L AND-OR for every S and L, such that 2 & S & m, and
2 & L & n, and such that one AND term contains S(.) and another
contai...