O'Reilly logo

Synthesis of Arithmetic Circuits: FPGA, ASIC and Embedded Systems by Gustavo D. Sutter, Gery J.A. Bioul, Jean-Pierre Deschamps

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

4.1 ADDITION OF NATURAL NUMBERS

4.1.1 Basic Algorithm

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

image

The following (pencil and paper) algorithm computes the (n + 1)-digit representation of z = x + y + cin where cin 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:

image

The next carry qi+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); ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required