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

8.1 OPERATIONS IN Zm

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

image

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

image

z must be equal to either x + y or x + ym. 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 Bn−1 < mBn and that x and y are n-digit base-B numbers. Consider three cases:

image

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 Bnm = 250:

image

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 ...

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