Synthesis of Arithmetic Circuits: FPGA, ASIC and Embedded Systems

4.3 INTEGERS

In the case of integer numbers, the addition and subtraction algorithms depend on the particular representation. Three nonredundant representation methods are considered in what follows: B's complement, sign-magnitude, and excess-E (Chapter 3).

4.3.1 B's Complement Addition

Given two n-digit B's complement integers x and y, and an initial carry c_in equal to 0 or 1, then z = x + y + c_in is an (n + 1)-digit B's complement integer. Assume that x and y are represented with n+1 digits. Then the natural numbers associated with x, y, and z are R(x) = x mod Bⁿ⁺¹, R(y) = y mod Bⁿ⁺¹, and R(z) = z mod Bⁿ⁺¹ (Definition 3.4), so that

Thus a straightforward addition algorithm consists in representing x and y with n+1 digits and adding the corresponding natural numbers, as well as the initial carry, modulo Bⁿ⁺¹ (that means without taking into account the output carry). In order to represent x and y with one additional digit, Comment 3.2 is taken into account. As before, the procedure natural_addition computes the sum of two natural numbers.

Algorithm 4.18 B's Complement Addition

if x(n-1)<B/2 then x(n):=0; else x(n):=B-1; end if;
if y(n-1)<B/2 then y(n):=0; else y(n):=B-1; end if;
natural_addition(n+1, c_in, x, y, not_used, z);

Example 4.1 Assume that B = 10, n = 4, c_in = 0, x = −2345, and y = −3674.. Both x and y are negative so that they are represented by R(x) = − 2345 + 10