Synthesis of Arithmetic Circuits: FPGA, ASIC and Embedded Systems

4.1 ADDITION OF NATURAL NUMBERS

4.1.1 Basic Algorithm

Consider the base-B representations of two n-digit numbers:

The following (pencil and paper) algorithm computes the (n + 1)-digit representation of z = x + y + c_in where c_in is an initial carry equal to 0 or 1.

Algorithm 4.1 Classic Addition

q(0): =c_in;
for i in 0..n-1 loop
   if x(i)+y(i)+q(i)>B-1 then q(i+1):=1; else q(i+1):=0;
   end if;
   z(i):=(x(i)+y(i)+q(i)) mod B;
end loop;
z(n):=q(n);

As q(i + 1) is a function of q(i) the execution time of Algorithm 4.1 is proportional to n. In order to reduce the execution time of each iteration step, Algorithm 4.1 can be modified. First, define two binary functions of two B-valued variables, namely, the propagate (p) and generate (g) functions:

The next carry q_i+1 can be calculated as follows:

if p(x(i), y(i))=1 then q(i+1):=q(i); else q(i+1):=g(x(i),
y(i)); end if;

The corresponding modified algorithm is the following one.

Algorithm 4.2 Carry-Chain Addition

--computation of the generation and propagation conditions:
for i in 0..n-1 loop g(i):=g(x(i),y(i)); p(i):=p(x(i),y(i));
end loop;
--carry computation:
q(0):=c_in;
for i in 0..n-1 loop
  if p(i)=1 then q(i+1):=q(i); else q(i+1):=g(i); end if;
end loop;
-sum computation
for i in 0..n-1 loop z(i):=(x(i)+y(i)+q(i)) mod B; end loop; z(n):=q(n); ...