synthesizable MOD operator

[Basel Naamna]

I need to implement a synthesizable mod operator , and i'm going to
impelement it through a function , also i need it to give the result
in one single clock (this means i will need to use loops) , and not
after a number of clocks, is there specific efficient way to make a
synthesizable MOD ?

 

[Ray Andraka]

There are many ways, but none that I am aware of that the tools will
infer the structure for you. Mod is basically the remainder from
division. Look up division algorithms, then figure out which one fits
your application and then write code to describe that structure. The
structure is not trivial.

Basel Naamna wrote:

I need to implement a synthesizable mod operator , and i'm going to
impelement it through a function , also i need it to give the result
in one single clock (this means i will need to use loops) , and not
after a number of clocks, is there specific efficient way to make a
synthesizable MOD ?

--
--Ray Andraka, P.E.
President, the Andraka Consulting Group, Inc.
401/884-7930 Fax 401/884-7950
email ray@andraka.com
http://www.andraka.com

"They that give up essential liberty to obtain a little
temporary safety deserve neither liberty nor safety."
-Benjamin Franklin, 1759

 

[Ralfe Cookson]

baseln@yahoo.com (Basel Naamna) wrote in message news:<f3af42e6.0405131249.4896cf62@posting.google.com>...

I need to implement a synthesizable mod operator , and i'm going to
impelement it through a function , also i need it to give the result
in one single clock (this means i will need to use loops) , and not
after a number of clocks, is there specific efficient way to make a
synthesizable MOD ?

I know of no method that can operate in one clock for general moduli,
but for specific moduli you can use various tricks derived from number
theory. One trick is to look at the least significant digit(s) or
bits of the number. For example in base 10 representation any number
ending in 0 or 5 is divisible by 5. So N mod 5 is simply the least
significant digit of N mod 5.

For binary numbers N it is very easy when the modulus is a power of 2.
N mod 2^X = the X lsb of N. Ex. 111000111 mod 8 = 111000111 mod 2^3 =
111, since the 3 lsb of N are 111.

Another trick is to take the digits of the number (in some base
representation) and sum them togther (sometimes multiplied by various
factors) with the resulting sum being smaller but still having the
same remainder upon division by the specified modulus. This same
process can be carried out repeatedly with the resulting sum until the
final sum is small enough.

You probably already learned a number of such rules in school. For
mod 3 or mod 9, the remainder is just sum of all the digits added
together.

Ex. 123456 mod 3 => 1 + 2 + 3 + 4 + 5 + 6 = 21.
Repeating the process on 21 => 2 + 1 = 3. We know that 3 mod 3 = 0, so
the remainder is 0.

Ex. 123456 mod 9 => 1 + 2 + 3 + 4 + 5 + 6 + 7 = 21
Repeating the process on 21 => 2 + 1 = 3. Therefore the remainder is
3.

Ex. 123456 mod 11 => 6 - 5 + 4 - 3 + 2 - 1 = 3.

For binary, octal, hexadecimal, etc. representations of the number
there are similar rules, but one must be careful not to assume the
same rules for base 10 apply to other bases.

The rules for various bases B can be easily derived by writing down
the number N as a sum of powers of the base B times a coefficient A
whose value ranges from 0 to B-1: N = Sigma (i = 0 to infinity)
A(i)*B^i, where A(i) = 0, ..., B-1.
Then determine how the remainder of each of the terms in the sum
affects the overall remainder. Note that the mod of a sum or product =
the mod of the sum or product of the mods of the individual terms, ie.
(x + y) mod M = [(x mod M) + (y mod M) ] mod M and similarly for *.