Fixed-Point FFT

Hi all,

I am working on a fixed-point FFT based application.
The Input to FFT is a real signal while the FFT Core is Complex (a.k.a it
can take real and imaginary inputs). Normally, one would tie the real
signal to real input of the core and the imaginary input to zero. In order
to optimize the resources, I want to use the complex input of the FFT Core
efficiently.

According to articles I found on the website, you can use split the input
data into two streams and combine the outputs of the FFT. 
http://processors.wiki.ti.com/index.php/Efficient_FFT_Computation_of_Real_Input

This all seems great for floating point. I am curious as what would be the
rounding issues if the FFT Core is fixed-point core. The core I am using
outputs unscaled fixed-point output.

Any insights or suggestions into the problem are welcome.

Thanks,
rakumarudu

rakumarudu <kalyanramu@n_o_s_p_a_m.gmail.com> wrote:

> I am working on a fixed-point FFT based application.
> The Input to FFT is a real signal while the FFT Core is Complex (a.k.a it
> can take real and imaginary inputs). Normally, one would tie the real
> signal to real input of the core and the imaginary input to zero. In order
> to optimize the resources, I want to use the complex input of the FFT Core
> efficiently.

> According to articles I found on the website, you can use split 
> the input data into two streams and combine the outputs of the FFT. 

Well described in "Numerical Recipes in C" (and probably others).

> This all seems great for floating point. I am curious as what 
> would be the rounding issues if the FFT Core is fixed-point core. 

I believe the results should be pretty much the same. 

It transforms the data from N real points to N/2 complex points,
applies the complex FFT, then fixes up the result. You should be
able to go through the math for small N, such as 4, and see what
it really does. Because of the way the FFT scales, it will work the
same for larger N.

-- glen

Hi Glen,

From what I understand, there are some rounding issues in the final
spectrum. I am no expert at this though.

rakumarudu <kalyanramu@n_o_s_p_a_m.gmail.com> wrote:

>> According to articles I found on the website, you can use split the input
>> data into two streams and combine the outputs of the FFT.

Yes - the "2N point real FFT using an N point complex FFT" technique
(sometimes called the "N point real FFT using an N/2 point complex FFT
technique").  You split up the real input data into 2 half-sized
arrays (r(0), r(2), r(4), ... etc., and r(1), r(3), r(5), ... etc.;
then use the even (half-sized) array as your real FFT inputs, and the
odd (half-sized) array as your imaginary inputs, followed by some add/
subtract/twiddle manipulations to recombine the parts properly.  Note
that to perform the above, you also need to know how to do a related
technique: "Two N point real points using an N point complex FFT."

One reference for both of the above is:

http://www.fftguru.com/fftguru.com.tutorial2.pdf

And a TI reference:

http://www.ti.com/lit/an/spra291/spra291.pdf

(beware - I've seen another, earlier version of the TI paper that had
a math error - the TI version also presumes a + exponent FFT -
something you have to be careful about).

Although the technique has been around since 1967 (Bingham, Godfrey,
Tukey paper), there are different ways of implementing it, and they
can affect your accuracy.

For instance, in the TI version above, the author (Robert Matusiak)
uses on the order of 8N multiplies and 6N adds, plus four N sized look-
up tables.

I have an improved version (not shown in the first link above), which
uses on the order of 2N multiplies, 5N adds, and an N/2 sized look-up
table (and it took many, many months to figure out how to do it).

But I'm not sure you should be overly concerned about efficiency right
now - I think you should work towards understanding and getting your
algorithm performing correctly.  A 'standard' way of doing it, even if
it's not the best, is preferable to struggling with the technique -
fixed point is difficult enough as it is.

As for fixed point rounding errors - in general, the fewer operations,
the better.  There's a large literature about fixed point error
analysis for FFT - I suggest you read as much of it as you can.

You'll still have to scale, of course - to prevent overflow/
underflow.  But I don't know what kind of guard bits or overflow
circuitry your core is using - a lot will depend on the details of
your processing.

Kevin McGee

Hi Kevin,

Thanks for such a detailed explanation. The TI Reference was very helpful.

I am using FFT Cores for Xilinx FPGA. I am not sure what kind of gaurd bits
they have but I will dig through the literature of Xilinx and FFT Fixed
Point Error Analysis.

Thanks,
rakumarudu