Synthesis of Arithmetic Circuits: FPGA, ASIC and Embedded Systems

8.1 OPERATIONS IN Z_m

Given a natural number m > 1, the set Z_m = {0, 1, … , m − 1} is a ring whose operations are defined modulo m (Chapter 2):

8.1.1 Addition

Given two natural numbers x and y belonging to the interval 0 ≤ x, y < m, compute z = (x + y) mod m. Taking into account that

z must be equal to either x + y or x + y − m. The corresponding algorithm is the following.

Algorithm 8.1 Modulo m Addition

z1:=x+y; z2:=z1 − m;
if z2>=0 then z:=z2; else z:=z1; end if;

Assume now that Bⁿ⁻¹ < m ≤ Bⁿ and that x and y are n-digit base-B numbers. Consider three cases:

So Algorithm 8.1 can be substituted by the following one where all operands have n digits.

Algorithm 8.2 Base B Modulo m Addition

z1:=(x+y) mod B**n; c1:=(x+y)/B**n;
z2:=(z1+B**n - m) mod B**n; c2:=(z1+B**n - m)/B**n;
if c1=0 and c2=0 then z:=z1; else z:=z2; end if;

Example 8.1 Assume that B = 10, n = 3, m = 750, so that Bⁿ − m = 250:

8.1.2 Subtraction

Given two natural numbers x and y belonging to the interval 0 ≤ x, y < m, compute z = (x − y) mod m. Taking into account that

z must be equal to either x − y or x − y + m ...