modulo 2**32-1 arith

On 12/21/15 1:57 PM, rickman wrote:
> On 12/21/2015 11:26 AM, Gabor Szakacs wrote:
>> I have always heard this method referred to as "end around carry,"
>> however if you are using this as an accumulator, i.e. A is the next
>> data input and B is the result of the previous sum, then it is in
>> effect the same as taking the sum of inputs modulo 2**32 - 1, with
>> the only difference being that the final result can be equal to
>> 2**32 - 1 where it would normally be zero.  Intermediate results
>> equal to 2**32-1 do not change the final outcome vs. doing a true
>> modulo operator.
>
> I guess I see what you are saying, even if this only applies to an
> accumulator rather than taking a sum of two arbitrary numbers.  When a
> sum is equal to 2**N-1 the carry is essentially delayed until the next
> cycle.  But... if the next value to be added is 2**n-1 (don't know if
> this is possible) a carry will happen, but there should be a second
> carry which will be missed.  So as long as the input domain is
> restricted to number from 0 to 2**N-2 this will work if the final result
> is adjusted to zero when equal to 2**N-1.
>

All ones (the alternate to 0 = 2^32-1) plus All ones will give us the 
result of All ones due to the end around carry (in effect the second 
carry was remembered by leaving the result as all ones).

This has all been pretty interesting to me because I may need to do this exact thing.  I had been planning to do the "end around carry", as you call it, but if that is too slow, I can use Ilya's Shannon Expansion.  Ilya's method (i.e., calculating both A+B and A+B+1 and choosing one based on the carry out) would be much faster at the expense of extra logic.  It's just standard Shannon Expansion but I hadn't thought of it.

I might need to do this for Galois field arithmetic (which is probably the case for Ilya as well).  One way to multiply GF numbers is to take the logs, add them together mod 2^m-1, and then take the inverse log, where 2^m is the size of the Galois field.  In my case, m is only 10 or 11, so I can use lookup tables for the logs and antilogs.

f*g = alog (mod ( log(f)+log(g), 2^m-1))  
         
          where f,g are elements of GF(2^m)

It's the same process as a slide rule.  It doesn't matter if the result of the mod ends up being 2^m-1 instead of 0, because the alog() function is a lookup table and will still map alog(2^m-1) = alog(0) = 1.

This method would be especially helpful if you are finding the product of several GF numbers.  So far I've just been using actual GF multipliers.  Sometimes they are big, but you can get the product in a single cycle, and the lookup tables entail latency.  Also, if you have to add in a number before the next multiplication, you have to go back into the alog domain.

On 12/25/2015 9:04 PM, Kevin Neilson wrote:
> This has all been pretty interesting to me because I may need to do
> this exact thing.  I had been planning to do the "end around carry",
> as you call it, but if that is too slow, I can use Ilya's Shannon
> Expansion.  Ilya's method (i.e., calculating both A+B and A+B+1 and
> choosing one based on the carry out) would be much faster at the
> expense of extra logic.  It's just standard Shannon Expansion but I
> hadn't thought of it.

Uh, if you read Ilya's posts the 64 bit carry chain was faster than the 
muxed selection.  Or did I misunderstand this?


> I might need to do this for Galois field arithmetic (which is
> probably the case for Ilya as well).  One way to multiply GF numbers
> is to take the logs, add them together mod 2^m-1, and then take the
> inverse log, where 2^m is the size of the Galois field.  In my case,
> m is only 10 or 11, so I can use lookup tables for the logs and
> antilogs.
>
> f*g = alog (mod ( log(f)+log(g), 2^m-1))
>
> where f,g are elements of GF(2^m)
>
> It's the same process as a slide rule.  It doesn't matter if the
> result of the mod ends up being 2^m-1 instead of 0, because the
> alog() function is a lookup table and will still map alog(2^m-1) =
> alog(0) = 1.
>
> This method would be especially helpful if you are finding the
> product of several GF numbers.  So far I've just been using actual GF
> multipliers.  Sometimes they are big, but you can get the product in
> a single cycle, and the lookup tables entail latency.  Also, if you
> have to add in a number before the next multiplication, you have to
> go back into the alog domain.
>


-- 

Rick

> Uh, if you read Ilya's posts the 64 bit carry chain was faster than the 
> muxed selection.  Or did I misunderstand this?

I hadn't seen the part about the 64-bit add.  That's a nice idea, too.  I wouldn't have expected it to be faster than the basic Shannon Expander, but with the quirks of getting data on and off the carry chain, it doesn't surprise me that it is.

This is somewhat unrelated, but I just remembered that recently I had to make a circuit to find modulo-24.  I tried several things, but what ended up being fastest and smallest, by far, was mathematically rephrasing the expression, something like this:

reg [11:0] x;
reg [4:0] x_mod_24;
...
x_mod_24 =  ((x>>3)%3)<<3  &  x[2:0];

On 12/26/2015 9:01 PM, Kevin Neilson wrote:
>> Uh, if you read Ilya's posts the 64 bit carry chain was faster than the
>> muxed selection.  Or did I misunderstand this?
>
> I hadn't seen the part about the 64-bit add.  That's a nice idea, too.  I wouldn't have expected it to be faster than the basic Shannon Expander, but with the quirks of getting data on and off the carry chain, it doesn't surprise me that it is.

I don't think it has anything to do with getting "data on and off the 
carry chain".  The slow part of FPGAs is often just routing.  The 64 bit 
add eliminates a lot of routing that is needed to implement the mux as 
well as eliminating the mux itself.


> This is somewhat unrelated, but I just remembered that recently I had to make a circuit to find modulo-24.  I tried several things, but what ended up being fastest and smallest, by far, was mathematically rephrasing the expression, something like this:
>
> reg [11:0] x;
> reg [4:0] x_mod_24;
> ...
> x_mod_24 =  ((x>>3)%3)<<3  &  x[2:0];

Interesting.  I guess a divide by 24 is a lot more complex than a divide 
by 3 even though it doesn't have to be.

-- 

Rick

> > This is somewhat unrelated, but I just remembered that recently I had to make a circuit to find modulo-24.  I tried several things, but what ended up being fastest and smallest, by far, was mathematically rephrasing the expression, something like this:
> >
> > reg [11:0] x;
> > reg [4:0] x_mod_24;
> > ...
> > x_mod_24 =  ((x>>3)%3)<<3  &  x[2:0];
> 
> Interesting.  I guess a divide by 24 is a lot more complex than a divide 
> by 3 even though it doesn't have to be.

Doing a division is one way to do it, but if you look at what the synthesizer does to do mod-24, it's something like this:

x_mod_24_stage1 = x[11]*( (1<<11)%24) + x[10]*( (1<<10)%24) ... + x[3:0];

adding up the mod-24 values due to each bit (and then adding the last 3 bits, which are already mod-24).  These are all 5-bit values.  After you add these, the result may be bigger than 24 and there's a second and third stage of this process.  When you do it the "rephrased" way, the mod-3 logic is a lot smaller (the sums are all 2 bits) and has fewer stages.

On 12/29/2015 12:17 PM, Kevin Neilson wrote:
>>> This is somewhat unrelated, but I just remembered that recently I had to make a circuit to find modulo-24.  I tried several things, but what ended up being fastest and smallest, by far, was mathematically rephrasing the expression, something like this:
>>>
>>> reg [11:0] x;
>>> reg [4:0] x_mod_24;
>>> ...
>>> x_mod_24 =  ((x>>3)%3)<<3  &  x[2:0];
>>
>> Interesting.  I guess a divide by 24 is a lot more complex than a divide
>> by 3 even though it doesn't have to be.
>
> Doing a division is one way to do it, but if you look at what the synthesizer does to do mod-24, it's something like this:
>
> x_mod_24_stage1 = x[11]*( (1<<11)%24) + x[10]*( (1<<10)%24) ... + x[3:0];
>
> adding up the mod-24 values due to each bit (and then adding the last 3 bits, which are already mod-24).  These are all 5-bit values.  After you add these, the result may be bigger than 24 and there's a second and third stage of this process.  When you do it the "rephrased" way, the mod-3 logic is a lot smaller (the sums are all 2 bits) and has fewer stages.

But clearly there is no need for it to be more complex.  What you 
describe above is essentially a product.  I think there last term should 
be x[2:0] which is the three lsbs.  These bits on the output are only 
affected by the three lsbs of the input.  The upper bits of the input 
can only affect the upper bits of the output.  So clearly there is no 
reason for the tool to calculate the entire 5 bits of the output based 
on the entire N bits of the input.

-- 

Rick