help about fft code.

I'm not familiar with this specific piece of code, but it looks like a common technique for fixed-point arithmetic.

Rather than using floating point, which is very expensive in gate count, values between zero and one (like the sine and cosine) are expressed as fractions. For convenience, all fractions have powers of two in the denominator. Also, since the denominator is the same for all fractions, adding and subtracting can just ignore it and use only the numerator.

In floating point, that code would be:

tmp = cos * data + sinreal * data;

Using fractions instead of floating point:

tmp = (cosNumer/denom) * data + (sinnumer/denom) * data;

or

tmp = (cosNumer * data + sinnumer * data ) / denom;

Since denom is a power of two of the form (1 << SCALE),

tmp = (cosNumer * data + sinnumer * data ) >> SCALE;

Imagine a Radix2 butterfly. For each real and imaginary part you have

z0 = x0 + x1

z1 = x0 - x1

and then you do a complex multiplication of z * (twiddle factor).

If you have a input signal that you want to maintain full precision then x0 and x1 are hopefully bounded between -/+1 fully. Thus, the worst case result is when x0 and x1 both equal one, and the twiddle factor is 1+1j. In this case as you go through the equation z0 will be 2 (z1 will be 0) and then z0 * twiddle factor could result in 2*sqrt(2). The 'growth' of this value would obviously overflow and cause an error. The scaling in FFTs essentially accounts for this effect, and is why the SNR for an FFT is generally we'll below the 6*2^(bitlength) rule of thumb. Some of the megacores have a variety of schemes to account for this including block floating point.

But thats a whole different beast.

blk

thank you first

and there is another question: as you said "denom is a power of two of the form" ,but I can not understand for example the real is 0.56 ,then my faction form is 56/100, but 100 is just be 10 power , how to transfer this , 0.56==56/100, I can not image there is a data can do this 0.56==56/ 2's power , that is mean the real data that I caculate will be changed??

sorry for my English and sorry for my poor FFT knowledge ;)

--- Quote Start ---

I'm not familiar with this specific piece of code, but it looks like a common technique for fixed-point arithmetic.

Rather than using floating point, which is very expensive in gate count, values between zero and one (like the sine and cosine) are expressed as fractions. For convenience, all fractions have powers of two in the denominator. Also, since the denominator is the same for all fractions, adding and subtracting can just ignore it and use only the numerator.

In floating point, that code would be:

tmp = cos * data + sinreal * data;

Using fractions instead of floating point:

tmp = (cosNumer/denom) * data + (sinnumer/denom) * data;

or

tmp = (cosNumer * data + sinnumer * data ) / denom;

Since denom is a power of two of the form (1 << SCALE),

tmp = (cosNumer * data + sinnumer * data ) >> SCALE;

--- Quote End ---

--- Quote Start ---

thank you first

and there is another question: as you said "denom is a power of two of the form" ,but I can not understand for example the real is 0.56 ,then my faction form is 56/100, but 100 is just be 10 power , how to transfer this , 0.56==56/100, I can not image there is a data can do this 0.56==56/ 2's power , that is mean the real data that I caculate will be changed??

sorry for my English and sorry for my poor FFT knowledge ;)

--- Quote End ---

First: real numbers are always wrong, except in such a small number of cases that I'll ignore them for now. Standard floating point can't even represent 1/3 exactly, or 1/100, or 56*(1/100). There's always some amount of approximation going on. Once you get to (or have to) define all your own arithmetic, including numbers of bits, you get a lot of control over the kinds of approximations being made. I don't know where you got 0.56 from, but it's [a] almost certainly a rounded-off version of the mathematically exact value you had in mind, and [b] can't be represented in binary anyway.

Second: I can't imagine why you'd want to do base-ten arithmetic on an FPGA, especially in the middle of an FFT. Writing 0.56 in base ten is easy for human purposes, but there are lots of equivalent forms: 56/100, or 14/25, or 574/1025, for example.

Interesting choice, that last one. The denominator is almost exactly 2**10. In fact, if you just say 0.56 = 574/1024, you're off by less than 0.1%. The original number had limited precision, so 0.56 is implicitly good to only two decimal digits, i.e. 0.56 +/- 0.005, or about 0.56 +/- 1%. My approximation of 574/1024 lies well within the error bounds that were already in your problem statement, so the denominator is good enough for two-decimal-digit sin or cos values -1<= x <= 1, as long as you pick the numerator correctly. In fact, a denominator of 128 should give good enough precision but require fewer hardware bits in the numerator.

In answer to your concern: No, nothing really changed when going from a denominator of 100 to a denominator of 1024. The /100 fraction already contained errors, and the /1024 fraction is no worse.

Whatever your precision, you can do the same kind of analysis to determine how many bits you need for the binary equivalent of some number of decimal digits.

-- Tom

Here is an example of an integer FFT that uses a 15 pre-scale factor that has been accelerated using the Nios II C2H compiler (perhaps this is the example you are referring to):

http://www.altera.com/literature/tt/tt_nios2_c2h_accelerating_tutorial.pdf

http://www.altera.com/literature/tt/c2h_fft_cyclone_ii.zip

http://www.altera.com/literature/tt/c2h_fft_stratix_ii.zip

So in a nutshell this example shows fixed point math. The idea of a pre-scale operation is to increase the data resolution so that operations that degrade precision (like division, >>, or multiplication of small numbers) will have as little affect on the accuracy as possible on the final result.

As Tom pointed out there is no difference between using a denominator of 100 or 1024. With that said the division (or multiplication) by 1024 is much better since that just involves a shift operation (hence why you have a >> in your FFT code) Whenever you divide binary numbers, you have no uncertainty when the denominator is a factor of 2 and the numerator contains a power of 2 (greater or equal power of 2 in the denominator). So by pre-scaling the numbers by a factor of 2, performing the calculation, then post-scaling by the same factor of 2, you minimize the amount of error in your calculation (often to 0% if you reserve enough bits). Remember when I said "greater or equal power than the denominator", well the whole idea behind a pre-scaling factor is that you remove that pre-scale from the result after the calculation is done (i.e. the numerator is a power of two, and the same power of two as the denominator).

To learn more I recommend searching the web for information on "fixed point math". You should be able to find many examples that can also explain this concept.