Non radix-2 size Fast Fourier Transform (FFT)

[linu95k]

Hi, 

I have been studying Radix-2 FFT algorithm and am confused about something.

One of the properties of FFT is that the input sequence size is equal to the size of the output sequence.

This is the result obtained by FFT.vi available in Transforms palette in Labview.

However FFT output is largely dependent on FFT size, which is recommended to be a power of 2 for Radix-2 algorithms. If I understand correctly, the algorithm zero-pads the input to in case the input sequence size is not a power of 2. But in this case the size of FFT will be larger than the input sequence size and the output sequence is also bigger.

eg. If size of input sequence = 6

After zero padding FFT size = 8

Thus, the size of output sequence = 8

I have been trying to create a FFT VI of my own and stumbled upon this observation. Can anyone tell me what changes do I need to make to a Radix-2 algorithm in order to obtain proper output sequence.

Thank you 

Regards,

Linus Koli

[altenbach · Accepted solution]

There are plenty of FFT algorithms available for all sizes. Three is no padding, which would greatly distort the input.

Quote from here:

"The best-known FFT algorithms depend upon the factorization  of N, but there are FFTs with O(N log N)  complexity  for all N, even for prime  N."

It will be hard to beat the built-in LabVIEW FFTs, they are extremely efficient and well written (which was not the case 20++ years ago), but you can use them to validate your results. See also the help.

[linu95k]

Is it possible to maintain the size of the output sequence of a non-power of 2 input sequence, using radix-2?

What I mean is if my input sequence has size 5, is it possible to obtain output sequence of size 5 using  radix-2?

I am aware using other algorithms like Z-transform, prime factor algorithm and composite radix algorithm is possible. But I am wondering can a single algorithm deal with variable sizes?

[altenbach]

radix-2 implies a size that is an integer power of two, so no!

I am still not quite sure what you are trying to do. Is this just an academic exercise or are you trying to improve the stock FFT implementations (no chance!).

A single algorithm can deal with all sizes, but it will be complicated and could automatically reduce to radix-2 if 2 is the only prime factor. I have not tried.

If speed does not matter, you can of course do an explicit "slow" fourier transform that works for all sizes. 😄

[linu95k]

It just something I was wondering... sort of for my own understanding... Thank you for your response.