modulo 2**32-1 arith

This has all been pretty interesting to me because I may need to do this ex act thing. I had been planning to do the "end around carry", as you call i t, but if that is too slow, I can use Ilya's Shannon Expansion. Ilya's met hod (i.e., calculating both A+B and A+B+1 and choosing one based on the car ry out) would be much faster at the expense of extra logic. It's just stan dard 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 s everal GF numbers. So far I've just been using actual GF multipliers. Som etimes 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.

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)

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.

o 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 e xpression, something like this:

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

x_mod_24_stage1 = x[11]*( (1