FFT for an arbitrary number of points (not power of 2)

On 30 oct, 12:03, dbd <d...@ieee.org> wrote:

> Since you have used zero-filling, you don't seem to need a transform
> the exact size of the data.

Correct. Although I want to minimize data growth as much as possible
(which is the drawback of zero-filling).

> There is another technique complementary
> to zero-filling, sometimes called data folding. Since the DFT is a
> circular convolution, when your data set is larger than the transform
> size you can continue to 'wrap' the data in a circular manner and sum
> the overlapped samples. You then perform the smaller sized FFT. You
> might consider data folding up to sqrt 2 times the smaller power of
> two FFT size and zero-filling up to the larger transform size above
> that.
>
> Chapter 8 (by fred harris) of 'Handbook of Digital Signal Processing
> Engineering Applications' edited by Douglas Eliot discusses this
> approach.

Interesting. Thanks for the reference, I'll try to find a copy of the
book.

Patrick

> I'd like to ask experts here about ideas to perform a FFT on an
> arbitrary number of points (for real data).

Hi Patrick,
A popular misconception seems to be that in order to use cooley-turkey
FFT the number of points must be a power of 2. Digital Signal
Processing with Field Programmable Gate Arrays by Uwe Meyer-Baese, for
example, has an example we he shows the Cooley-Tukey FFT for N = 12.
He claims 674 real additions and 432 real multiplications for a 12
point DFT, and for the 12 point FFT 108 real additions and 28 real
multiplications. The signal flow graph he shows, shows in the 1st
stage, 3x four point DFTs, followed by twiddle factors, and then a
final stage of 4x three point DFT's.

He also goes on to present the Good-Thomas FFT algorithm and Winograd
FFT. Again he demonstrates for N=12.

Regards
Andrew

Patrick Dubois wrote:

> Hi,
> 
> I'd like to ask experts here about ideas to perform a FFT on an
> arbitrary number of points (for real data).
> 
> The cores usually found for an FPGA implementation only permit FFTs on
> a number of points that is a power of 2. In our particular case
> however, we need to be able to do an FFT on a vector of say, 1025
> points. Our current algorithm is to zero-pad this vector to 2048
> points.
> 
> The problem with this approach is that we nearly double the number of
> points for downstream processing. This is very problematic at high
> datarates.
> 
> We have a few ideas but since this seems like a common problem, I'd
> like to ask people here for tips.
> 
> Thanks!
> 
> Patrick
> 


As others have mentioned, you need non-power of two FFT kernels to get 
non-power of two transform sizes unless you use zero padding.  A 
possibility would be to have a set of non-power of two kernels you could 
combine using the mixed radix algorithm to get larger FFTs.  If your FFT 
kernel sizes are relatively prime, you get a significant simplification 
because it doesn't need phase rotations between the FFT kernels.  For 
example, a 1540 point FFT can be had by combining 4, 5, 7 and 11 point 
kernels with no intervening rotations.  If you use rotations between the 
FFT kernels, you can mix the kernels without regard to whether or not 
they are relatively prime. There are Winograd kernels for all these 
sizes, and others (Rader or Singleton as I recall) for 3 and 5 point. 
These are actually quite a bit easier to do in hardware than they are 
with a microprocessor, as the reordering is a bit convoluted.  You might 
look at the Smith & Smith book on FFT's 
(http://www.amazon.com/exec/obidos/ASIN/0780310918/andraka), as they 
have a very good coverage of non-Cooley-Tukey FFTs.  Unfortunately, 
arbitrary sizes are a little harder to do if it is to be flexible 
because the addressing and phase rotations are not as well ordered as 
they are for power of 2 sizes.

Thank you for the last three responses from John, Andrew and Ray (and
everyone else who responded). You pretty much convinced me of the need
to have different size kernels to be able to handle a larger range of
points possibility. Unfortunately that means that I won't be able to
use Xilinx Coregen FFT. I guess we'll stick with zero-padding for the
time being but at least now I know my options if I really wanna go
that route.

I'm still intriged by the chirp z-transform (Bluestein's FFT
algorithm) however, because it seems to use power of 2 FFTs (at least
the Matlab implementation of czt does). I don't quite yet grasp the
algorithm though. I see that it is discussed in chapter 9.5 of the
book Ray Andraka suggested. I'll try to get a copy.

Thanks,
Patrick