synthesizable MOD operator

Discussion in 'VHDL' started by Basel Naamna, May 13, 2004.

  1. Basel Naamna

    Basel Naamna Guest

    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 ?
     
    Basel Naamna, May 13, 2004
    #1
    1. Advertisements

  2. Basel Naamna

    Ray Andraka Guest

    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.

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

    "They that give up essential liberty to obtain a little
    temporary safety deserve neither liberty nor safety."
    -Benjamin Franklin, 1759
     
    Ray Andraka, May 13, 2004
    #2
    1. Advertisements

  3. 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 *.
     
    Ralfe Cookson, May 14, 2004
    #3
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.