Follow along with the video below to see how to install our site as a web app on your home screen.
Note: This feature may not be available in some browsers.
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.
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.
Uh, if you read Ilya's posts the 64 bit carry chain was faster than the
muxed selection. Or did I misunderstand this?
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];
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.
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.